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