1 /* ------------------------------------------------------------------
2 * Copyright (C) 1998-2009 PacketVideo
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
13 * express or implied.
14 * See the License for the specific language governing permissions
15 * and limitations under the License.
16 * -------------------------------------------------------------------
17 */
18 // -*- c++ -*-
19 // = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
20
21 // H A S H T A B L E C L A S S
22
23 // = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
24
25 #ifndef HASHTABLE_H
26 #define HASHTABLE_H
27
28
29 // - - Inclusion - - - - - - - - - - - - - - - - - - - - - - - - - - - -
30
31
32 #include "sorted_list.h"
33 #include "hash_functions.h"
34
35 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
36 template <class keyclass, class hashclass> struct HashListElement;
37
38 template <class keyclass, class hashclass> int
39 operator==(const HashListElement<keyclass, hashclass>& a,
40 const HashListElement<keyclass, hashclass>& b)
41 {
42 return ((a.fullkey == b.fullkey) && (a.data == b.data));
43 }
44
45 template <class keyclass, class hashclass> struct HashListElement
46 {
47 keyclass fullkey;
48 hashclass data;
49
50 // #if defined( PV_OS_HPUX )
51 // friend int operator==
52 // ( HashListElement<keyclass,hashclass> &a,
53 // HashListElement<keyclass,hashclass> &b );
54 // #else
55 friend int operator==<keyclass, hashclass>
56 (const HashListElement<keyclass, hashclass> & a,
57 const HashListElement<keyclass, hashclass> & b);
58 // #endif
59
60 };
61
62 /*
63 template <class keyclass, class hashclass> int
64 operator==( const HashListElement<keyclass,hashclass>& a,
65 const HashListElement<keyclass,hashclass>& b)
66 {
67 return ((a.fullkey == b.fullkey) && (a.data == b.data));
68 }
69 */
70
71 template <class keyclass, class hashclass> int
72 operator<(const HashListElement<keyclass, hashclass>& a,
73 const HashListElement<keyclass, hashclass>& b)
74 {
75 return ((a.fullkey < b.fullkey));
76 }
77
78 template <class keyclass, class hashclass> int
79 operator<=(const HashListElement<keyclass, hashclass>& a,
80 const HashListElement<keyclass, hashclass>& b)
81 {
82 return ((a.fullkey <= b.fullkey));
83 }
84
85 template <class keyclass, class hashclass> int
86 operator>(const HashListElement<keyclass, hashclass>& a,
87 const HashListElement<keyclass, hashclass>& b)
88 {
89 return ((a.fullkey > b.fullkey));
90 }
91
92 template <class keyclass, class hashclass> int
93 operator>=(const HashListElement<keyclass, hashclass>& a,
94 const HashListElement<keyclass, hashclass>& b)
95 {
96 return ((a.fullkey >= b.fullkey));
97 }
98
99
100 template <class keyclass, class hashclass> class HashTable
101 {
102 public:
103 HashTable(int in_hash_table_size);
104
105 ~HashTable();
106
107 int is_unique(const keyclass& fullkey);
108 int add_element(const keyclass& fullkey, const hashclass& data);
109 int add_element(uint32 key, const keyclass& fullkey, const hashclass& data);
110 int remove_element(uint32 key, const keyclass& fullkey);
111 int remove_element(const keyclass& fullkey);
112 int get_element(uint32 key, const keyclass& fullkey, hashclass& data);
113 int get_element(const keyclass& fullkey, hashclass& data);
114 int get_element(int index, uint32& key, keyclass& fullkey,
115 hashclass& data);
get_num_elements()116 int get_num_elements()
117 {
118 return num_elements;
119 };
120
121 private:
122 SortedList<HashListElement<keyclass, hashclass> >* hash_table;
123
124 uint32 hash_mask;
125 uint32 hash_table_size;
126 int num_elements;
127
128 };
129
130 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
131
132
is_unique(const keyclass & key)133 template <class keyclass, class hashclass> int HashTable<keyclass, hashclass>::is_unique(const keyclass& key)
134 {
135 HashListElement<keyclass, hashclass> tmp;
136 uint32 hash = compute_hash(key);
137 uint32 masked_hash = hash & hash_mask;
138
139 int list_elements = hash_table[masked_hash].get_num_elements();
140
141 for (int ii = 0; ii < list_elements; ++ii)
142 {
143 hash_table[masked_hash].get_element(ii, tmp);
144 // if (tmp.key == key)
145 if (tmp.fullkey == key)
146 return 0;
147 }
148
149 return 1;
150 }
151
152 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
153
154
155 template <class keyclass, class hashclass>
add_element(const keyclass & fullkey,const hashclass & data)156 int HashTable<keyclass, hashclass>::add_element(const keyclass& fullkey,
157 const hashclass& data)
158 {
159 uint32 key = compute_hash(fullkey);
160
161 return add_element(key, fullkey, data);
162
163 }
164
165
166 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
167
168 template <class keyclass, class hashclass>
add_element(uint32 key,const keyclass & fullkey,const hashclass & data)169 int HashTable<keyclass, hashclass>::add_element(uint32 key,
170 const keyclass& fullkey,
171 const hashclass& data)
172 {
173 HashListElement<keyclass, hashclass> tmp;
174
175 uint32 masked_key = key & hash_mask;
176 tmp.fullkey = fullkey;
177 tmp.data = data;
178
179 hashclass tmp2;
180
181 if (get_element(fullkey, tmp2))
182 {
183 // bark - hash table corruption
184
185 //#define HASH_CORRUPTION_DEBUG 1
186 return 0;
187 }
188
189 hash_table[masked_key].add_element(tmp);
190
191
192 ++num_elements;
193
194 return 1;
195 }
196
197 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
198
199 template <class keyclass, class hashclass>
remove_element(const keyclass & fullkey)200 int HashTable<keyclass, hashclass>::remove_element(const keyclass& fullkey)
201 {
202 uint32 key = compute_hash(fullkey);
203 return remove_element(key, fullkey);
204 }
205
206 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
207
208 template <class keyclass, class hashclass>
remove_element(uint32 key,const keyclass & fullkey)209 int HashTable<keyclass, hashclass>::remove_element(uint32 key,
210 const keyclass& fullkey)
211 {
212 HashListElement<keyclass, hashclass> tmp;
213 uint32 masked_key = key & hash_mask;
214
215 int list_elements = hash_table[masked_key].get_num_elements();
216
217 for (int ii = 0; ii < list_elements; ++ii)
218 {
219 hash_table[masked_key].get_element(ii, tmp);
220 if (tmp.fullkey == fullkey)
221 {
222 hash_table[masked_key].remove_element(tmp);
223 --num_elements;
224 return 1;
225 }
226 else if (tmp.fullkey > fullkey)
227 {
228 return 0;
229 }
230
231 }
232
233 return 0;
234 }
235
236 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
237 template <class keyclass, class hashclass>
get_element(const keyclass & fullkey,hashclass & data)238 int HashTable<keyclass, hashclass>::get_element(const keyclass& fullkey,
239 hashclass& data)
240 {
241 uint32 key = compute_hash(fullkey);
242
243 return get_element(key, fullkey, data);
244
245 }
246
247 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
248
249 template <class keyclass, class hashclass>
get_element(uint32 key,const keyclass & fullkey,hashclass & data)250 int HashTable<keyclass, hashclass>::get_element(uint32 key,
251 const keyclass& fullkey,
252 hashclass& data)
253 {
254 HashListElement<keyclass, hashclass> tmp;
255 uint32 masked_key = key & hash_mask;
256
257 int list_elements = hash_table[masked_key].get_num_elements();
258
259 for (int ii = 0; ii < list_elements; ++ii)
260 {
261 hash_table[masked_key].get_element(ii, tmp);
262 if (tmp.fullkey == fullkey)
263 {
264 data = tmp.data;
265 return 1;
266 }
267 else if (tmp.fullkey > fullkey)
268 {
269 return 0;
270 }
271 }
272
273 return 0;
274 }
275
276 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
277
278 template <class keyclass, class hashclass>
get_element(int index,uint32 & key,keyclass & fullkey,hashclass & data)279 int HashTable<keyclass, hashclass>::get_element(int index,
280 uint32& key, keyclass& fullkey,
281 hashclass& data)
282 {
283 HashListElement<keyclass, hashclass> tmp;
284 unsigned int hash_idx;
285
286 if (index < 0 || index >= num_elements)
287 return 0;
288
289 // find the proper hash element
290 for (hash_idx = 0; hash_idx < hash_table_size; ++hash_idx)
291 {
292 if (index < hash_table[hash_idx].get_num_elements())
293 break;
294 index -= hash_table[hash_idx].get_num_elements();
295 }
296
297 assert(index >= 0);
298
299 if (!hash_table[hash_idx].get_element(index, tmp))
300 return 0;
301
302 data = tmp.data;
303 key = compute_hash(tmp.fullkey);
304 fullkey = tmp.fullkey;
305
306 return 1;
307
308 }
309
310 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
311
HashTable(int in_hash_table_size)312 template <class keyclass, class hashclass> HashTable<keyclass, hashclass>::HashTable(int in_hash_table_size)
313 {
314 hash_mask = in_hash_table_size - 1;
315 hash_table_size = in_hash_table_size;
316
317 if (hash_mask & in_hash_table_size)
318 {
319 int tmp, cnt;
320 // find next larger power of two
321 for (tmp = in_hash_table_size, cnt = 0; tmp; tmp >>= 1, ++cnt);
322
323 hash_table_size = (1 << cnt);
324 hash_mask = hash_table_size - 1;
325
326 // bark - hash table size is not a power of two, changing
327
328 }
329
330 hash_table = new SortedList< HashListElement<keyclass, hashclass> >[hash_table_size];
331
332 num_elements = 0;
333
334 }
335
336 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
337
338
~HashTable()339 template <class keyclass, class hashclass> HashTable<keyclass, hashclass>::~HashTable()
340 {
341 delete[] hash_table;
342
343 }
344
345 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
346
347
348
349
350 template <class keyclass, class hashclass> class MTHashTable
351 {
352 public:
353 MTHashTable(int in_hash_table_size);
354
355 ~MTHashTable();
356
357 int is_unique(const keyclass& fullkey);
358 int add_element(const keyclass& fullkey, const hashclass& data);
359 int add_element(uint32 key, const keyclass& fullkey, const hashclass& data);
360 int remove_element(uint32 key, const keyclass& fullkey);
361 int remove_element(const keyclass& fullkey);
362 int get_element(uint32 key, const keyclass& fullkey, hashclass& data);
363 int get_element(const keyclass& fullkey, hashclass& data);
364 int get_element(int index, uint32& key, keyclass& fullkey,
365 hashclass& data);
get_num_elements()366 int get_num_elements()
367 {
368 if (the_hash)
369 {
370 return the_hash->get_num_elements();
371 }
372 return 0;
373 };
374
375 private:
376 HashTable<keyclass, hashclass> *the_hash;
377 PVMutex mutex;
378 };
379
380
381 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
382
383
is_unique(const keyclass & key)384 template <class keyclass, class hashclass> int MTHashTable<keyclass, hashclass>::is_unique(const keyclass& key)
385 {
386 int status;
387 mutex.Lock();
388 status = the_hash->is_unique(key);
389 mutex.Unlock();
390 return status;
391 }
392
393 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
394
395
396 template <class keyclass, class hashclass>
add_element(const keyclass & fullkey,const hashclass & data)397 int MTHashTable<keyclass, hashclass>::add_element(const keyclass& fullkey,
398 const hashclass& data)
399 {
400 int status;
401 mutex.Lock();
402 status = the_hash->add_element(fullkey, data);
403 mutex.Unlock();
404 return status;
405
406 }
407
408
409 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
410
411 template <class keyclass, class hashclass>
add_element(uint32 key,const keyclass & fullkey,const hashclass & data)412 int MTHashTable<keyclass, hashclass>::add_element(uint32 key,
413 const keyclass& fullkey,
414 const hashclass& data)
415 {
416 int status;
417 mutex.Lock();
418 status = the_hash->add_element(key, fullkey, data);
419 mutex.Unlock();
420 return status;
421
422 }
423
424 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
425
426 template <class keyclass, class hashclass>
remove_element(const keyclass & fullkey)427 int MTHashTable<keyclass, hashclass>::remove_element(const keyclass& fullkey)
428 {
429 int status;
430 mutex.Lock();
431 status = the_hash->remove_element(fullkey);
432 mutex.Unlock();
433 return status;
434
435 }
436
437 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
438
439 template <class keyclass, class hashclass>
remove_element(uint32 key,const keyclass & fullkey)440 int MTHashTable<keyclass, hashclass>::remove_element(uint32 key,
441 const keyclass& fullkey)
442 {
443 int status;
444 mutex.Lock();
445 status = the_hash->remove_element(key, fullkey);
446 mutex.Unlock();
447 return status;
448
449 }
450
451 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
452 template <class keyclass, class hashclass>
get_element(const keyclass & fullkey,hashclass & data)453 int MTHashTable<keyclass, hashclass>::get_element(const keyclass& fullkey,
454 hashclass& data)
455 {
456 int status;
457 mutex.Lock();
458 status = the_hash->get_element(fullkey, data);
459 mutex.Unlock();
460 return status;
461 }
462
463 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
464
465 template <class keyclass, class hashclass>
get_element(uint32 key,const keyclass & fullkey,hashclass & data)466 int MTHashTable<keyclass, hashclass>::get_element(uint32 key,
467 const keyclass& fullkey,
468 hashclass& data)
469 {
470 int status;
471 mutex.Lock();
472 status = the_hash->get_element(key, fullkey, data);
473 mutex.Unlock();
474 return status;
475 }
476
477 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
478
479 template <class keyclass, class hashclass>
get_element(int index,uint32 & key,keyclass & fullkey,hashclass & data)480 int MTHashTable<keyclass, hashclass>::get_element(int index,
481 uint32& key, keyclass& fullkey,
482 hashclass& data)
483 {
484 int status;
485 mutex.Lock();
486 status = the_hash->get_element(index, key, fullkey, data);
487 mutex.Unlock();
488 return status;
489 }
490
491 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
492
MTHashTable(int in_hash_table_size)493 template <class keyclass, class hashclass> MTHashTable<keyclass, hashclass>::MTHashTable(int in_hash_table_size)
494 {
495 the_hash = OSCL_NEW(HashTable<keyclass, hashclass>, (in_hash_table_size));
496 }
497
498 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
499
500
~MTHashTable()501 template <class keyclass, class hashclass> MTHashTable<keyclass, hashclass>::~MTHashTable()
502 {
503 OSCL_DELETE(the_hash);
504 }
505
506 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
507
508
509
510 #endif // HASHTABLE_H
511