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 = 51437, const double load = 0.5) {
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;
339 if (max_load > load_factor ) {
341 // roughly double the size of the table
344 hash_mask = num_buckets-1;
346 buckets = new hash_bucket[num_buckets];
347 total_memory = num_buckets * sizeof(hash_bucket);
354 size_t size() const {
367 unsigned int get_mem_footprint() {
374 template <class key_type, class hasher_func, class equal_func>
380 data_item* next; // next data item in overflow chain
382 data_item(const key_type& k) : key(k), next(NULL) { }
387 hash_bucket* next_bucket; // index of the next bucket in the list of used buckets
391 next_bucket = 0; // 0 means no bucket follows this one
399 iterator& operator++() {
403 bucket = bucket->next_bucket;
412 bool operator!=(const iterator& it) {
413 return (data != it.data || bucket != it.bucket);
416 bool operator==(const iterator& it) {
417 return (data == it.data && bucket == it.bucket);
420 // NOTE : not certain if returning ref always works
421 key_type &operator*() {
438 hash_bucket* first_bucket; // first used bucket
439 hash_bucket* last_bucket; // last used bucket
441 hash_bucket* buckets;
444 hash_set(const size_t n_buckets = 131072, const double load = 0.75) {
448 for(nb=2;nb<n_buckets;nb*=2);
450 hash_mask = num_buckets-1;
452 buckets = new hash_bucket[num_buckets];
461 int insert(const key_type& key) {
462 data_item* d = new data_item(key);
464 // find the insertion bucket
465 size_t bucket_index = hasher(key) & hash_mask;
466 // if the bucket is empty just add new data_item
467 if (!buckets[bucket_index].data) {
468 // create new data item
470 buckets[bucket_index].data = d;
472 first_bucket = &buckets[bucket_index];
474 last_bucket->next_bucket = &buckets[bucket_index];
475 last_bucket = &buckets[bucket_index];
476 } else { // we already have data items in this bucket
477 // prepend the item to overflow chain
478 data_item* temp = buckets[bucket_index].data;
479 buckets[bucket_index].data = d;
489 iterator find(const key_type& key) {
492 // find the insertion bucket
493 size_t bucket_index = hasher(key) & hash_mask;
494 // if the bucket is empty just add new data_item
495 if (!buckets[bucket_index].data) {
498 } else { // we already have data items in this bucket
499 data_item* temp = buckets[bucket_index].data;
500 while (temp && !equal(temp->key, key))
506 iter.bucket = &buckets[bucket_index];
511 void erase(const key_type& key) {
513 size_t bucket_index = hasher(key) & hash_mask;
514 // if the bucket is empty just add new data_item
515 if (!buckets[bucket_index].data)
518 data_item* temp = buckets[bucket_index].data;
519 data_item* prev = NULL;
520 while (temp && !equal(temp->key, key)) {
527 // delete this data item from the chain
529 if (!prev) // we are deleting the first element in chain
530 buckets[bucket_index].data = temp->next;
532 prev->next = temp->next;
538 // find the first data item
539 iter.bucket = first_bucket;
540 iter.data = (first_bucket) ? first_bucket->data : NULL;
556 while (first_bucket) {
557 temp = first_bucket->data;
558 while ( (next = temp->next) ) {
562 if(temp) delete(temp);
563 first_bucket->data = NULL;
565 first_bucket = first_bucket->next_bucket;
566 tmp->next_bucket = NULL;
575 fprintf(stderr, "Error: rehashing non-empty hash table\n");
579 double max_load = (1.0 * _max_size) / num_buckets;
581 if (max_load > load_factor ) {
583 // roughly double the size of the table
586 hash_mask = num_buckets -1;
587 buckets = new hash_bucket[num_buckets];
594 size_t size() const {
610 #endif // __HASH_TABLE_H