1 /* ------------------------------------------------
2 Copyright 2014 AT&T Intellectual Property
3 Licensed under the Apache License, Version 2.0 (the "License");
4 you may not use this file except in compliance with the License.
5 You may obtain a copy of the License at
7 http://www.apache.org/licenses/LICENSE-2.0
9 Unless required by applicable law or agreed to in writing, software
10 distributed under the License is distributed on an "AS IS" BASIS,
11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 See the License for the specific language governing permissions and
13 limitations under the License.
14 ------------------------------------------- */
16 #ifndef __HASH_TABLE_H
17 #define __HASH_TABLE_H
26 static unsigned int primes[NUM_PRIMES] = {
27 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, 12853,
28 25717, 51437, 102877, 205759, 411527, 823117, 1646237,
29 3292489, 6584983, 13169977, 26339969, 52679969
34 template <class key_type, class value_type, class hasher_func, class equal_func>
41 data_item* next; // next data item in overflow chain
43 data_item(const key_type& k, const value_type& v) : first(k), second(v), next(NULL) { }
48 hash_bucket* next_bucket; // index of the next bucket in the list of used buckets
49 hash_bucket* prev_bucket; // index of the next bucket in the list of used buckets
53 next_bucket = 0; // 0 means no bucket follows this one
54 prev_bucket = 0; // 0 means no bucket precedes this one
62 iterator& operator++() {
66 bucket = bucket->next_bucket;
75 // Like ++, but don't go beyond the end of the bucket chain.
86 bool operator!=(const iterator& it) {
87 return (data != it.data || bucket != it.bucket);
90 bool operator==(const iterator& it) {
91 return (data == it.data && bucket == it.bucket);
94 data_item &operator*() {
111 hash_bucket* first_bucket; // first used bucket
112 hash_bucket* last_bucket; // last used bucket
114 hash_bucket* buckets;
116 // memory footpritn in bytes
117 unsigned int total_memory;
122 hash_table(const size_t n_buckets = 65536, const double load = 1.0) {
125 for(nb=2;nb<n_buckets;nb*=2);
128 buckets = new hash_bucket[num_buckets];
136 total_memory = num_buckets * sizeof(hash_bucket);
139 int insert(const key_type& key, const value_type& val) {
140 data_item* d = new data_item(key, val);
141 total_memory += sizeof(data_item);
143 // find the insertion bucket
144 size_t bucket_index = hasher(key) & hash_mask;
145 // if the bucket is empty just add new data_item
146 if (!buckets[bucket_index].data) {
147 // create new data item
149 buckets[bucket_index].data = d;
151 first_bucket = &buckets[bucket_index];
153 last_bucket->next_bucket = &buckets[bucket_index];
157 buckets[bucket_index].prev_bucket = last_bucket;
159 last_bucket = &buckets[bucket_index];
160 } else { // we already have data items in this bucket
161 // prepend the item to overflow chain
162 data_item* temp = buckets[bucket_index].data;
163 buckets[bucket_index].data = d;
173 data_item *iterate_find(data_item* t, const key_type& key) {
175 while (temp && !equal(temp->first, key)){
182 iterator find(const key_type& key) {
185 // find the insertion bucket
186 size_t bucket_index = hasher(key) & hash_mask;
187 // if the bucket is empty just add new data_item
188 if (!buckets[bucket_index].data) {
191 } else { // we already have data items in this bucket
192 data_item* temp = buckets[bucket_index].data;
193 // temp = iterate_find(temp,key);
195 while (temp && !equal(temp->first, key))
202 iter.bucket = &buckets[bucket_index];
207 void erase(const key_type& key) {
209 size_t bucket_index = hasher(key) & hash_mask;
210 // if the bucket is empty just add new data_item
211 if (!buckets[bucket_index].data)
214 data_item* temp = buckets[bucket_index].data;
215 data_item* prev = NULL;
216 while (temp && !equal(temp->first, key)) {
223 // delete this data item from the chain
225 if (!prev){ // we are deleting the first element in chain
226 buckets[bucket_index].data = temp->next;
228 if(temp->next == NULL){
229 if(buckets[bucket_index].next_bucket){
230 buckets[bucket_index].next_bucket->prev_bucket = buckets[bucket_index].prev_bucket;
232 last_bucket = buckets[bucket_index].prev_bucket;
234 if(buckets[bucket_index].prev_bucket){
235 buckets[bucket_index].prev_bucket->next_bucket = buckets[bucket_index].next_bucket;
237 first_bucket = buckets[bucket_index].next_bucket;
239 buckets[bucket_index].next_bucket = NULL;
240 buckets[bucket_index].prev_bucket = NULL;
243 prev->next = temp->next;
246 total_memory -= sizeof(data_item);
249 void erase_full(const key_type& key) {
251 size_t bucket_index = hasher(key) & hash_mask;
252 // if the bucket is empty just add new data_item
253 if (!buckets[bucket_index].data)
256 data_item* temp = buckets[bucket_index].data;
257 data_item* prev = NULL;
258 while (temp && !equal(temp->first, key)) {
265 // delete this data item from the chain
267 if (!prev){ // we are deleting the first element in chain
268 buckets[bucket_index].data = temp->next;
270 if(temp->next == NULL){
271 if(buckets[bucket_index].next_bucket){
272 buckets[bucket_index].next_bucket->prev_bucket = buckets[bucket_index].prev_bucket;
274 last_bucket = buckets[bucket_index].prev_bucket;
276 if(buckets[bucket_index].prev_bucket){
277 buckets[bucket_index].prev_bucket->next_bucket = buckets[bucket_index].next_bucket;
279 first_bucket = buckets[bucket_index].next_bucket;
281 buckets[bucket_index].next_bucket = NULL;
282 buckets[bucket_index].prev_bucket = NULL;
285 prev->next = temp->next;
287 delete (*temp).first;
288 delete (*temp).second;
290 total_memory -= sizeof(data_item);
295 // find the first data item
296 iter.bucket = first_bucket;
297 iter.data = (first_bucket) ? first_bucket->data : NULL;
313 while (first_bucket) {
314 temp = first_bucket->data;
315 while ( (next = temp->next) ) {
319 if(temp) delete(temp);
320 first_bucket->data = NULL;
322 first_bucket = first_bucket->next_bucket;
323 tmp->next_bucket = NULL;
324 tmp->prev_bucket = NULL;
328 total_memory = num_buckets * sizeof(hash_bucket);
334 fprintf(stderr, "Error: rehashing non-empty hash table\n");
338 double max_load = (1.0 * _max_size) / num_buckets;
340 // reize table if its maximum load exceed the load factor
341 // OR it was less then half of the load factor
342 size_t min_buckets = 0;
343 if ((max_load > load_factor) || ((2 * max_load) < load_factor)) {
344 min_buckets = _max_size / load_factor;
348 // find power-of-2 size large than min_buckets;
350 for(nb=2;nb<min_buckets;nb*=2);
354 hash_mask = num_buckets-1;
356 buckets = new hash_bucket[num_buckets];
364 size_t size() const {
377 unsigned int get_mem_footprint() {
384 template <class key_type, class hasher_func, class equal_func>
390 data_item* next; // next data item in overflow chain
392 data_item(const key_type& k) : key(k), next(NULL) { }
397 hash_bucket* next_bucket; // index of the next bucket in the list of used buckets
401 next_bucket = 0; // 0 means no bucket follows this one
409 iterator& operator++() {
413 bucket = bucket->next_bucket;
422 bool operator!=(const iterator& it) {
423 return (data != it.data || bucket != it.bucket);
426 bool operator==(const iterator& it) {
427 return (data == it.data && bucket == it.bucket);
430 // NOTE : not certain if returning ref always works
431 key_type &operator*() {
448 hash_bucket* first_bucket; // first used bucket
449 hash_bucket* last_bucket; // last used bucket
451 hash_bucket* buckets;
454 hash_set(const size_t n_buckets = 65536, const double load = 1.0) {
458 for(nb=2;nb<n_buckets;nb*=2);
460 hash_mask = num_buckets-1;
462 buckets = new hash_bucket[num_buckets];
471 int insert(const key_type& key) {
472 data_item* d = new data_item(key);
474 // find the insertion bucket
475 size_t bucket_index = hasher(key) & hash_mask;
476 // if the bucket is empty just add new data_item
477 if (!buckets[bucket_index].data) {
478 // create new data item
480 buckets[bucket_index].data = d;
482 first_bucket = &buckets[bucket_index];
484 last_bucket->next_bucket = &buckets[bucket_index];
485 last_bucket = &buckets[bucket_index];
486 } else { // we already have data items in this bucket
487 // prepend the item to overflow chain
488 data_item* temp = buckets[bucket_index].data;
489 buckets[bucket_index].data = d;
499 iterator find(const key_type& key) {
502 // find the insertion bucket
503 size_t bucket_index = hasher(key) & hash_mask;
504 // if the bucket is empty just add new data_item
505 if (!buckets[bucket_index].data) {
508 } else { // we already have data items in this bucket
509 data_item* temp = buckets[bucket_index].data;
510 while (temp && !equal(temp->key, key))
516 iter.bucket = &buckets[bucket_index];
521 void erase(const key_type& key) {
523 size_t bucket_index = hasher(key) & hash_mask;
524 // if the bucket is empty just add new data_item
525 if (!buckets[bucket_index].data)
528 data_item* temp = buckets[bucket_index].data;
529 data_item* prev = NULL;
530 while (temp && !equal(temp->key, key)) {
537 // delete this data item from the chain
539 if (!prev) // we are deleting the first element in chain
540 buckets[bucket_index].data = temp->next;
542 prev->next = temp->next;
548 // find the first data item
549 iter.bucket = first_bucket;
550 iter.data = (first_bucket) ? first_bucket->data : NULL;
566 while (first_bucket) {
567 temp = first_bucket->data;
568 while ( (next = temp->next) ) {
572 if(temp) delete(temp);
573 first_bucket->data = NULL;
575 first_bucket = first_bucket->next_bucket;
576 tmp->next_bucket = NULL;
585 fprintf(stderr, "Error: rehashing non-empty hash table\n");
589 double max_load = (1.0 * _max_size) / num_buckets;
591 // reize table if its maximum load exceed the load factor
592 // OR it was less then half of the load factor
593 size_t min_buckets = 0;
594 if ((max_load > load_factor) || ((2 * max_load) < load_factor)) {
595 min_buckets = _max_size / load_factor;
599 // find power-of-2 size large than min_buckets;
601 for(nb=2;nb<min_buckets;nb*=2);
605 hash_mask = num_buckets-1;
607 buckets = new hash_bucket[num_buckets];
614 size_t size() const {
630 #endif // __HASH_TABLE_H