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