![]() |
libzmq master
The Intelligent Transport Layer
|
00001 /* 00002 Copyright (c) 2011 250bpm s.r.o. 00003 Copyright (c) 2011 Other contributors as noted in the AUTHORS file 00004 00005 This file is part of 0MQ. 00006 00007 0MQ is free software; you can redistribute it and/or modify it under 00008 the terms of the GNU Lesser General Public License as published by 00009 the Free Software Foundation; either version 3 of the License, or 00010 (at your option) any later version. 00011 00012 0MQ is distributed in the hope that it will be useful, 00013 but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 GNU Lesser General Public License for more details. 00016 00017 You should have received a copy of the GNU Lesser General Public License 00018 along with this program. If not, see <http://www.gnu.org/licenses/>. 00019 */ 00020 00021 #include <stdlib.h> 00022 00023 #include <new> 00024 #include <algorithm> 00025 00026 #include "platform.hpp" 00027 #if defined ZMQ_HAVE_WINDOWS 00028 #include "windows.hpp" 00029 #endif 00030 00031 #include "err.hpp" 00032 #include "pipe.hpp" 00033 #include "mtrie.hpp" 00034 00035 zmq::mtrie_t::mtrie_t () : 00036 min (0), 00037 count (0) 00038 { 00039 } 00040 00041 zmq::mtrie_t::~mtrie_t () 00042 { 00043 if (count == 1) 00044 delete next.node; 00045 else if (count > 1) { 00046 for (unsigned short i = 0; i != count; ++i) 00047 if (next.table [i]) 00048 delete next.table [i]; 00049 free (next.table); 00050 } 00051 } 00052 00053 bool zmq::mtrie_t::add (unsigned char *prefix_, size_t size_, pipe_t *pipe_) 00054 { 00055 return add_helper (prefix_, size_, pipe_); 00056 } 00057 00058 bool zmq::mtrie_t::add_helper (unsigned char *prefix_, size_t size_, 00059 pipe_t *pipe_) 00060 { 00061 // We are at the node corresponding to the prefix. We are done. 00062 if (!size_) { 00063 bool result = pipes.empty (); 00064 pipes.insert (pipe_); 00065 return result; 00066 } 00067 00068 unsigned char c = *prefix_; 00069 if (c < min || c >= min + count) { 00070 00071 // The character is out of range of currently handled 00072 // charcters. We have to extend the table. 00073 if (!count) { 00074 min = c; 00075 count = 1; 00076 next.node = NULL; 00077 } 00078 else if (count == 1) { 00079 unsigned char oldc = min; 00080 mtrie_t *oldp = next.node; 00081 count = (min < c ? c - min : min - c) + 1; 00082 next.table = (mtrie_t**) 00083 malloc (sizeof (mtrie_t*) * count); 00084 zmq_assert (next.table); 00085 for (unsigned short i = 0; i != count; ++i) 00086 next.table [i] = 0; 00087 min = std::min (min, c); 00088 next.table [oldc - min] = oldp; 00089 } 00090 else if (min < c) { 00091 00092 // The new character is above the current character range. 00093 unsigned short old_count = count; 00094 count = c - min + 1; 00095 next.table = (mtrie_t**) realloc ((void*) next.table, 00096 sizeof (mtrie_t*) * count); 00097 zmq_assert (next.table); 00098 for (unsigned short i = old_count; i != count; i++) 00099 next.table [i] = NULL; 00100 } 00101 else { 00102 00103 // The new character is below the current character range. 00104 unsigned short old_count = count; 00105 count = (min + old_count) - c; 00106 next.table = (mtrie_t**) realloc ((void*) next.table, 00107 sizeof (mtrie_t*) * count); 00108 zmq_assert (next.table); 00109 memmove (next.table + min - c, next.table, 00110 old_count * sizeof (mtrie_t*)); 00111 for (unsigned short i = 0; i != min - c; i++) 00112 next.table [i] = NULL; 00113 min = c; 00114 } 00115 } 00116 00117 // If next node does not exist, create one. 00118 if (count == 1) { 00119 if (!next.node) { 00120 next.node = new (std::nothrow) mtrie_t; 00121 zmq_assert (next.node); 00122 } 00123 return next.node->add_helper (prefix_ + 1, size_ - 1, pipe_); 00124 } 00125 else { 00126 if (!next.table [c - min]) { 00127 next.table [c - min] = new (std::nothrow) mtrie_t; 00128 zmq_assert (next.table [c - min]); 00129 } 00130 return next.table [c - min]->add_helper (prefix_ + 1, size_ - 1, pipe_); 00131 } 00132 } 00133 00134 00135 void zmq::mtrie_t::rm (pipe_t *pipe_, 00136 void (*func_) (unsigned char *data_, size_t size_, void *arg_), 00137 void *arg_) 00138 { 00139 unsigned char *buff = NULL; 00140 rm_helper (pipe_, &buff, 0, 0, func_, arg_); 00141 free (buff); 00142 } 00143 00144 void zmq::mtrie_t::rm_helper (pipe_t *pipe_, unsigned char **buff_, 00145 size_t buffsize_, size_t maxbuffsize_, 00146 void (*func_) (unsigned char *data_, size_t size_, void *arg_), 00147 void *arg_) 00148 { 00149 // Remove the subscription from this node. 00150 if (pipes.erase (pipe_) && pipes.empty ()) 00151 func_ (*buff_, buffsize_, arg_); 00152 00153 // Adjust the buffer. 00154 if (buffsize_ >= maxbuffsize_) { 00155 maxbuffsize_ = buffsize_ + 256; 00156 *buff_ = (unsigned char*) realloc (*buff_, maxbuffsize_); 00157 alloc_assert (*buff_); 00158 } 00159 00160 // If there are no subnodes in the trie, return. 00161 if (count == 0) 00162 return; 00163 00164 // If there's one subnode (optimisation). 00165 if (count == 1) { 00166 (*buff_) [buffsize_] = min; 00167 buffsize_++; 00168 next.node->rm_helper (pipe_, buff_, buffsize_, maxbuffsize_, 00169 func_, arg_); 00170 return; 00171 } 00172 00173 // If there are multiple subnodes. 00174 for (unsigned short c = 0; c != count; c++) { 00175 (*buff_) [buffsize_] = min + c; 00176 if (next.table [c]) 00177 next.table [c]->rm_helper (pipe_, buff_, buffsize_ + 1, 00178 maxbuffsize_, func_, arg_); 00179 } 00180 } 00181 00182 bool zmq::mtrie_t::rm (unsigned char *prefix_, size_t size_, pipe_t *pipe_) 00183 { 00184 return rm_helper (prefix_, size_, pipe_); 00185 } 00186 00187 bool zmq::mtrie_t::rm_helper (unsigned char *prefix_, size_t size_, 00188 pipe_t *pipe_) 00189 { 00190 if (!size_) { 00191 pipes_t::size_type erased = pipes.erase (pipe_); 00192 zmq_assert (erased == 1); 00193 return pipes.empty (); 00194 } 00195 00196 unsigned char c = *prefix_; 00197 if (!count || c < min || c >= min + count) 00198 return false; 00199 00200 mtrie_t *next_node = 00201 count == 1 ? next.node : next.table [c - min]; 00202 00203 if (!next_node) 00204 return false; 00205 00206 return next_node->rm_helper (prefix_ + 1, size_ - 1, pipe_); 00207 } 00208 00209 void zmq::mtrie_t::match (unsigned char *data_, size_t size_, 00210 void (*func_) (pipe_t *pipe_, void *arg_), void *arg_) 00211 { 00212 mtrie_t *current = this; 00213 while (true) { 00214 00215 // Signal the pipes attached to this node. 00216 for (pipes_t::iterator it = current->pipes.begin (); 00217 it != current->pipes.end (); ++it) 00218 func_ (*it, arg_); 00219 00220 // If we are at the end of the message, there's nothing more to match. 00221 if (!size_) 00222 break; 00223 00224 // If there are no subnodes in the trie, return. 00225 if (current->count == 0) 00226 break; 00227 00228 // If there's one subnode (optimisation). 00229 if (current->count == 1) { 00230 if (data_ [0] != current->min) 00231 break; 00232 current = current->next.node; 00233 data_++; 00234 size_--; 00235 continue; 00236 } 00237 00238 // If there are multiple subnodes. 00239 if (data_ [0] < current->min || data_ [0] >= 00240 current->min + current->count) 00241 break; 00242 if (!current->next.table [data_ [0] - current->min]) 00243 break; 00244 current = current->next.table [data_ [0] - current->min]; 00245 data_++; 00246 size_--; 00247 } 00248 } 00249