1 /* 2 * $Id: hash_table.h 1486 2009-08-29 14:40:38Z rco $ 3 * 4 * Copyright (C) 2007 Raphael Coeffic 5 * 6 * This file is part of SEMS, a free SIP media server. 7 * 8 * SEMS is free software; you can redistribute it and/or modify 9 * it under the terms of the GNU General Public License as published by 10 * the Free Software Foundation; either version 2 of the License, or 11 * (at your option) any later version. This program is released under 12 * the GPL with the additional exemption that compiling, linking, 13 * and/or using OpenSSL is allowed. 14 * 15 * For a license to use the SEMS software under conditions 16 * other than those described here, or to purchase support for this 17 * software, please contact iptel.org by e-mail at the following addresses: 18 * info@iptel.org 19 * 20 * SEMS is distributed in the hope that it will be useful, 21 * but WITHOUT ANY WARRANTY; without even the implied warranty of 22 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 23 * GNU General Public License for more details. 24 * 25 * You should have received a copy of the GNU General Public License 26 * along with this program; if not, write to the Free Software 27 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 28 */ 29 30 31 #ifndef _hash_table_h 32 #define _hash_table_h 33 34 #include "AmThread.h" 35 #include "log.h" 36 37 #include <list> 38 #include <map> 39 using std::list; 40 using std::map; 41 using std::less; 42 43 44 template<class Value> 45 class ht_bucket: public AmMutex 46 { 47 public: 48 typedef list<Value*> value_list; 49 ht_bucket(unsigned long id)50 ht_bucket(unsigned long id) : id(id) {} ~ht_bucket()51 virtual ~ht_bucket() {} 52 53 /** 54 * Caution: The bucket MUST be locked before you can 55 * do anything with it. 56 */ 57 58 /** 59 * Searches for the value ptr in this bucket. 60 * This is used to check if the value 61 * still exists. 62 * 63 * @return true if the value still exists. 64 */ exist(Value * t)65 bool exist(Value* t) { 66 return find(t) != elmts.end(); 67 } 68 69 /** 70 * Remove the value from this bucket, 71 * if it was still present. 72 */ remove(Value * t)73 void remove(Value* t) { 74 typename value_list::iterator it = find(t); 75 76 if(it != elmts.end()){ 77 elmts.erase(it); 78 delete t; 79 } 80 } 81 82 /** 83 * Returns the bucket id, which should be an index 84 * into the corresponding hash table. 85 */ get_id()86 unsigned long get_id() const { 87 return id; 88 } 89 90 // debug method dump()91 void dump() const { 92 93 if(elmts.empty()) 94 return; 95 96 DBG("*** Bucket ID: %i ***\n",(int)get_id()); 97 98 for(typename value_list::const_iterator it = elmts.begin(); it != elmts.end(); ++it) { 99 100 (*it)->dump(); 101 } 102 } 103 104 protected: 105 /** 106 * Finds a transaction ptr in this bucket. 107 * This is used to check if the transaction 108 * still exists. 109 * 110 * @return iterator pointing at the value. 111 */ find(Value * t)112 typename value_list::iterator find(Value* t) 113 { 114 typename value_list::iterator it = elmts.begin(); 115 for(;it!=elmts.end();++it) 116 if(*it == t) 117 break; 118 119 return it; 120 } 121 122 unsigned long id; 123 value_list elmts; 124 }; 125 126 template<class Value> 127 class ht_delete 128 { 129 public: new_elmt(Value * v)130 Value* new_elmt(Value* v) { 131 return v; 132 } dispose(Value * v)133 void dispose(Value* v) { 134 delete v; 135 } 136 }; 137 138 template<class Value> 139 class ht_ref_cnt 140 { 141 public: new_elmt(Value * v)142 Value* new_elmt(Value* v) { 143 inc_ref(v); 144 return v; 145 } dispose(Value * v)146 void dispose(Value* v) { 147 dec_ref(v); 148 } 149 }; 150 151 template<class Key, class Value, 152 class ElmtAlloc = ht_delete<Value>, 153 class ElmtCompare = less<Key> > 154 class ht_map_bucket: public AmMutex 155 { 156 public: 157 typedef map<Key,Value*,ElmtCompare> value_map; 158 typedef ElmtAlloc allocator; 159 ht_map_bucket(unsigned long id)160 ht_map_bucket(unsigned long id) : id(id) {} ~ht_map_bucket()161 virtual ~ht_map_bucket() {} 162 163 /** 164 * Caution: The bucket MUST be locked before you can 165 * do anything with it. 166 */ 167 168 /** 169 * Searches for the value ptr in this bucket. 170 * This is used to check if the value 171 * still exists. 172 * 173 * @return true if the value still exists. 174 */ exist(const Key & k)175 bool exist(const Key& k) { 176 return find(k) != elmts.end(); 177 } 178 179 /** 180 * Insert the value into this bucket. 181 */ insert(const Key & k,Value * v)182 virtual bool insert(const Key& k, Value* v) { 183 v = ElmtAlloc().new_elmt(v); 184 bool res = elmts.insert(typename value_map::value_type(k,v)).second; 185 if(!res) ElmtAlloc().dispose(v); 186 return res; 187 } 188 189 /** 190 * Remove the value from this bucket, 191 * if it was still present. 192 */ remove(const Key & k)193 virtual bool remove(const Key& k) { 194 typename value_map::iterator it = find(k); 195 196 if(it != elmts.end()){ 197 Value* v = it->second; 198 elmts.erase(it); 199 ElmtAlloc().dispose(v); 200 return true; 201 } 202 return false; 203 } 204 get(const Key & k)205 Value* get(const Key& k) { 206 typename value_map::iterator it = find(k); 207 if(it != elmts.end()) 208 return it->second; 209 return NULL; 210 } 211 212 /** 213 * Returns the bucket id, which should be an index 214 * into the corresponding hash table. 215 */ get_id()216 unsigned long get_id() const { 217 return id; 218 } 219 220 // debug method dump()221 void dump() const { 222 223 if(elmts.empty()) 224 return; 225 226 DBG("*** Bucket ID: %i ***\n",(int)get_id()); 227 228 for(typename value_map::const_iterator it = elmts.begin(); 229 it != elmts.end(); ++it) { 230 dump_elmt(it->first,it->second); 231 } 232 } 233 dump_elmt(const Key & k,const Value * v)234 virtual void dump_elmt(const Key& k, const Value* v) const {} 235 236 protected: find(const Key & k)237 typename value_map::iterator find(const Key& k) 238 { 239 return elmts.find(k); 240 } 241 242 unsigned long id; 243 value_map elmts; 244 }; 245 246 template<class Bucket> 247 class hash_table 248 { 249 unsigned long size; 250 Bucket** _table; 251 252 public: hash_table(unsigned long size)253 hash_table(unsigned long size) 254 : size(size) 255 { 256 _table = new Bucket* [size]; 257 for(unsigned long i=0; i<size; i++) 258 _table[i] = new Bucket(i); 259 } 260 ~hash_table()261 ~hash_table() { 262 for(unsigned long i=0; i<size; i++) 263 delete _table[i]; 264 delete [] _table; 265 } 266 267 Bucket* operator [](unsigned long hash) const { 268 return get_bucket(hash); 269 } 270 get_bucket(unsigned long hash)271 Bucket* get_bucket(unsigned long hash) const { 272 return _table[hash % size]; 273 } 274 dump()275 void dump() const { 276 for(unsigned long l=0; l<size; l++){ 277 _table[l]->lock(); 278 _table[l]->dump(); 279 _table[l]->unlock(); 280 } 281 } 282 get_size()283 unsigned long get_size() { return size; } 284 }; 285 286 287 288 #endif 289 290 291 /** EMACS ** 292 * Local variables: 293 * mode: c++ 294 * c-basic-offset: 4 295 * End: 296 */ 297