-/* ------------------------------------------------
-Copyright 2014 AT&T Intellectual Property
- Licensed under the Apache License, Version 2.0 (the "License");
- you may not use this file except in compliance with the License.
- You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- See the License for the specific language governing permissions and
- limitations under the License.
- ------------------------------------------- */
-
-#ifndef __HASH_TABLE_H
-#define __HASH_TABLE_H
-
-#include <stdlib.h>
-#include <stdio.h>
-
-
-
-#define NUM_PRIMES 23
-
-static unsigned int primes[NUM_PRIMES] = {
- 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, 12853,
- 25717, 51437, 102877, 205759, 411527, 823117, 1646237,
- 3292489, 6584983, 13169977, 26339969, 52679969
-};
-
-
-
-template <class key_type, class value_type, class hasher_func, class equal_func>
-class hash_table {
-
-public :
- struct data_item {
- key_type first;
- value_type second;
- data_item* next; // next data item in overflow chain
-
- data_item(const key_type& k, const value_type& v) : first(k), second(v), next(NULL) { }
- };
-
- struct hash_bucket {
- data_item* data; //
- hash_bucket* next_bucket; // index of the next bucket in the list of used buckets
- hash_bucket* prev_bucket; // index of the next bucket in the list of used buckets
-
- hash_bucket() {
- data = NULL;
- next_bucket = 0; // 0 means no bucket follows this one
- prev_bucket = 0; // 0 means no bucket precedes this one
- }
- };
-
- struct iterator {
- hash_bucket* bucket;
- data_item* data;
-
- iterator& operator++() {
- if (data->next)
- data = data->next;
- else {
- bucket = bucket->next_bucket;
- if (bucket)
- data = bucket->data;
- else
- data = NULL;
- }
- return *this;
- }
-
-// Like ++, but don't go beyond the end of the bucket chain.
- iterator& next() {
- if (data->next)
- data = data->next;
- else {
- bucket = NULL;
- data = NULL;
- }
- return *this;
- }
-
- bool operator!=(const iterator& it) {
- return (data != it.data || bucket != it.bucket);
- }
-
- bool operator==(const iterator& it) {
- return (data == it.data && bucket == it.bucket);
- }
-
- data_item &operator*() {
- return *data;
- }
- };
-
-private:
- hasher_func hasher;
- equal_func equal;
-
- double load_factor;
-// double max_load;
-
- size_t _size;
- size_t _max_size;
- size_t num_buckets;
- size_t hash_mask;
-
- hash_bucket* first_bucket; // first used bucket
- hash_bucket* last_bucket; // last used bucket
-
- hash_bucket* buckets;
-
- // memory footpritn in bytes
- unsigned int total_memory;
-
-public:
-
-
- hash_table(const size_t n_buckets = 131072, const double load = 0.5) {
- load_factor = load;
- int nb;
- for(nb=2;nb<n_buckets;nb*=2);
- num_buckets = nb;
- hash_mask = nb-1;
- buckets = new hash_bucket[num_buckets];
-
- _size = 0;
- _max_size = 0;
-// max_load = 0.0;
- first_bucket = 0;
- last_bucket = 0;
-
- total_memory = num_buckets * sizeof(hash_bucket);
- }
-
- int insert(const key_type& key, const value_type& val) {
- data_item* d = new data_item(key, val);
- total_memory += sizeof(data_item);
-
- // find the insertion bucket
- size_t bucket_index = hasher(key) & hash_mask;
- // if the bucket is empty just add new data_item
- if (!buckets[bucket_index].data) {
- // create new data item
-
- buckets[bucket_index].data = d;
- if (!first_bucket){
- first_bucket = &buckets[bucket_index];
- }else{
- last_bucket->next_bucket = &buckets[bucket_index];
- }
-
- if (last_bucket)
- buckets[bucket_index].prev_bucket = last_bucket;
-
- last_bucket = &buckets[bucket_index];
- } else { // we already have data items in this bucket
- // prepend the item to overflow chain
- data_item* temp = buckets[bucket_index].data;
- buckets[bucket_index].data = d;
- d->next = temp;
- }
- _size++;
- if(_size>_max_size)
- _max_size = _size;
-
- return 0;
- }
-
- data_item *iterate_find(data_item* t, const key_type& key) {
- data_item *temp = t;
- while (temp && !equal(temp->first, key)){
- temp = temp->next;
- }
- return temp;
- }
-
-
- iterator find(const key_type& key) {
- iterator iter;
-
- // find the insertion bucket
- size_t bucket_index = hasher(key) & hash_mask;
- // if the bucket is empty just add new data_item
- if (!buckets[bucket_index].data) {
- iter.bucket = NULL;
- iter.data = NULL;
- } else { // we already have data items in this bucket
- data_item* temp = buckets[bucket_index].data;
-// temp = iterate_find(temp,key);
-
- while (temp && !equal(temp->first, key))
- temp = temp->next;
-
- iter.data = temp;
- if (!temp)
- iter.bucket = NULL;
- else
- iter.bucket = &buckets[bucket_index];
- }
- return iter;
- }
-
- void erase(const key_type& key) {
- // find the bucket
- size_t bucket_index = hasher(key) & hash_mask;
- // if the bucket is empty just add new data_item
- if (!buckets[bucket_index].data)
- return;
-
- data_item* temp = buckets[bucket_index].data;
- data_item* prev = NULL;
- while (temp && !equal(temp->first, key)) {
- prev = temp;
- temp = temp->next;
- }
- if (!temp)
- return;
-
- // delete this data item from the chain
- _size--;
- if (!prev){ // we are deleting the first element in chain
- buckets[bucket_index].data = temp->next;
-
- if(temp->next == NULL){
- if(buckets[bucket_index].next_bucket){
- buckets[bucket_index].next_bucket->prev_bucket = buckets[bucket_index].prev_bucket;
- }else{
- last_bucket = buckets[bucket_index].prev_bucket;
- }
- if(buckets[bucket_index].prev_bucket){
- buckets[bucket_index].prev_bucket->next_bucket = buckets[bucket_index].next_bucket;
- }else{
- first_bucket = buckets[bucket_index].next_bucket;
- }
- buckets[bucket_index].next_bucket = NULL;
- buckets[bucket_index].prev_bucket = NULL;
- }
- }else{
- prev->next = temp->next;
- }
- delete temp;
- total_memory -= sizeof(data_item);
- }
-
- void erase_full(const key_type& key) {
- // find the bucket
- size_t bucket_index = hasher(key) & hash_mask;
- // if the bucket is empty just add new data_item
- if (!buckets[bucket_index].data)
- return;
-
- data_item* temp = buckets[bucket_index].data;
- data_item* prev = NULL;
- while (temp && !equal(temp->first, key)) {
- prev = temp;
- temp = temp->next;
- }
- if (!temp)
- return;
-
- // delete this data item from the chain
- _size--;
- if (!prev){ // we are deleting the first element in chain
- buckets[bucket_index].data = temp->next;
-
- if(temp->next == NULL){
- if(buckets[bucket_index].next_bucket){
- buckets[bucket_index].next_bucket->prev_bucket = buckets[bucket_index].prev_bucket;
- }else{
- last_bucket = buckets[bucket_index].prev_bucket;
- }
- if(buckets[bucket_index].prev_bucket){
- buckets[bucket_index].prev_bucket->next_bucket = buckets[bucket_index].next_bucket;
- }else{
- first_bucket = buckets[bucket_index].next_bucket;
- }
- buckets[bucket_index].next_bucket = NULL;
- buckets[bucket_index].prev_bucket = NULL;
- }
- }else{
- prev->next = temp->next;
- }
- delete (*temp).first;
- delete (*temp).second;
- delete temp;
- total_memory -= sizeof(data_item);
- }
-
- iterator begin() {
- iterator iter;
- // find the first data item
- iter.bucket = first_bucket;
- iter.data = (first_bucket) ? first_bucket->data : NULL;
- return iter;
- }
-
- iterator end() {
- iterator iter;
- iter.bucket = NULL;
- iter.data = NULL;
- return iter;
- }
-
- void clear() {
- data_item* temp;
- data_item* next;
-
- hash_bucket* tmp;
- while (first_bucket) {
- temp = first_bucket->data;
- while ( (next = temp->next) ) {
- delete temp;
- temp = next;
- }
- if(temp) delete(temp);
- first_bucket->data = NULL;
- tmp = first_bucket;
- first_bucket = first_bucket->next_bucket;
- tmp->next_bucket = NULL;
- tmp->prev_bucket = NULL;
- }
- last_bucket = NULL;
- _size = 0;
- total_memory = num_buckets * sizeof(hash_bucket);
-
- }
-
- int rehash() {
- if (_size) {
- fprintf(stderr, "Error: rehashing non-empty hash table\n");
- exit(1);
- }
-
- double max_load = (1.0 * _max_size) / num_buckets;
- if (max_load > load_factor ) {
- delete[] buckets;
- // roughly double the size of the table
-
- num_buckets *= 2;
- hash_mask = num_buckets-1;
-
- buckets = new hash_bucket[num_buckets];
- total_memory = num_buckets * sizeof(hash_bucket);
- }
- _max_size = _size;
- return 0;
- }
-
-
- size_t size() const {
- return _size;
- }
-
- bool empty() const {
- return (_size == 0);
- }
-
- ~hash_table() {
- clear();
- delete[] buckets;
- }
-
- unsigned int get_mem_footprint() {
- return total_memory;
- }
-
-};
-
-
-template <class key_type, class hasher_func, class equal_func>
-class hash_set {
-
-public :
- struct data_item {
- key_type key;
- data_item* next; // next data item in overflow chain
-
- data_item(const key_type& k) : key(k), next(NULL) { }
- };
-
- struct hash_bucket {
- data_item* data; //
- hash_bucket* next_bucket; // index of the next bucket in the list of used buckets
-
- hash_bucket() {
- data = NULL;
- next_bucket = 0; // 0 means no bucket follows this one
- }
- };
-
- struct iterator {
- hash_bucket* bucket;
- data_item* data;
-
- iterator& operator++() {
- if (data->next)
- data = data->next;
- else {
- bucket = bucket->next_bucket;
- if (bucket)
- data = bucket->data;
- else
- data = NULL;
- }
- return *this;
- }
-
- bool operator!=(const iterator& it) {
- return (data != it.data || bucket != it.bucket);
- }
-
- bool operator==(const iterator& it) {
- return (data == it.data && bucket == it.bucket);
- }
-
-// NOTE : not certain if returning ref always works
- key_type &operator*() {
- return data->key;
- }
- };
-
-private:
- hasher_func hasher;
- equal_func equal;
-
- double load_factor;
-// double max_load;
-
- size_t _size;
- size_t _max_size;
- size_t num_buckets;
- size_t hash_mask;
-
- hash_bucket* first_bucket; // first used bucket
- hash_bucket* last_bucket; // last used bucket
-
- hash_bucket* buckets;
-
-public:
- hash_set(const size_t n_buckets = 131072, const double load = 0.75) {
- load_factor = load;
-
- int nb;
- for(nb=2;nb<n_buckets;nb*=2);
- num_buckets = nb;
- hash_mask = num_buckets-1;
-
- buckets = new hash_bucket[num_buckets];
-
- _size = 0;
- _max_size = 0;
-// max_load = 0.0;
- first_bucket = 0;
- last_bucket = 0;
- }
-
- int insert(const key_type& key) {
- data_item* d = new data_item(key);
-
- // find the insertion bucket
- size_t bucket_index = hasher(key) & hash_mask;
- // if the bucket is empty just add new data_item
- if (!buckets[bucket_index].data) {
- // create new data item
-
- buckets[bucket_index].data = d;
- if (!first_bucket)
- first_bucket = &buckets[bucket_index];
- else
- last_bucket->next_bucket = &buckets[bucket_index];
- last_bucket = &buckets[bucket_index];
- } else { // we already have data items in this bucket
- // prepend the item to overflow chain
- data_item* temp = buckets[bucket_index].data;
- buckets[bucket_index].data = d;
- d->next = temp;
- }
- _size++;
- if(_size>_max_size)
- _max_size = _size;
-
- return 0;
- }
-
- iterator find(const key_type& key) {
- iterator iter;
-
- // find the insertion bucket
- size_t bucket_index = hasher(key) & hash_mask;
- // if the bucket is empty just add new data_item
- if (!buckets[bucket_index].data) {
- iter.bucket = NULL;
- iter.data = NULL;
- } else { // we already have data items in this bucket
- data_item* temp = buckets[bucket_index].data;
- while (temp && !equal(temp->key, key))
- temp = temp->next;
- iter.data = temp;
- if (!temp)
- iter.bucket = NULL;
- else
- iter.bucket = &buckets[bucket_index];
- }
- return iter;
- }
-
- void erase(const key_type& key) {
- // find the bucket
- size_t bucket_index = hasher(key) & hash_mask;
- // if the bucket is empty just add new data_item
- if (!buckets[bucket_index].data)
- return;
-
- data_item* temp = buckets[bucket_index].data;
- data_item* prev = NULL;
- while (temp && !equal(temp->key, key)) {
- prev = temp;
- temp = temp->next;
- }
- if (!temp)
- return;
-
- // delete this data item from the chain
- _size--;
- if (!prev) // we are deleting the first element in chain
- buckets[bucket_index].data = temp->next;
- else
- prev->next = temp->next;
- delete temp;
- }
-
- iterator begin() {
- iterator iter;
- // find the first data item
- iter.bucket = first_bucket;
- iter.data = (first_bucket) ? first_bucket->data : NULL;
- return iter;
- }
-
- iterator end() {
- iterator iter;
- iter.bucket = NULL;
- iter.data = NULL;
- return iter;
- }
-
- void clear() {
- data_item* temp;
- data_item* next;
-
- hash_bucket* tmp;
- while (first_bucket) {
- temp = first_bucket->data;
- while ( (next = temp->next) ) {
- delete temp;
- temp = next;
- }
- if(temp) delete(temp);
- first_bucket->data = NULL;
- tmp = first_bucket;
- first_bucket = first_bucket->next_bucket;
- tmp->next_bucket = NULL;
- }
- last_bucket = NULL;
- _size = 0;
-
- }
-
- int rehash() {
- if (_size) {
- fprintf(stderr, "Error: rehashing non-empty hash table\n");
- exit(1);
- }
-
- double max_load = (1.0 * _max_size) / num_buckets;
-
- if (max_load > load_factor ) {
- delete[] buckets;
- // roughly double the size of the table
-
- num_buckets *= 2;
- hash_mask = num_buckets -1;
- buckets = new hash_bucket[num_buckets];
- }
- _max_size = _size;
- return 0;
- }
-
-
- size_t size() const {
- return _size;
- }
-
- bool empty() const {
- return (_size == 0);
- }
-
- ~hash_set() {
- clear();
- delete[] buckets;
- }
-
-};
-
-
-#endif // __HASH_TABLE_H
+/* ------------------------------------------------\r
+Copyright 2014 AT&T Intellectual Property\r
+ Licensed under the Apache License, Version 2.0 (the "License");\r
+ you may not use this file except in compliance with the License.\r
+ You may obtain a copy of the License at\r
+\r
+ http://www.apache.org/licenses/LICENSE-2.0\r
+\r
+ Unless required by applicable law or agreed to in writing, software\r
+ distributed under the License is distributed on an "AS IS" BASIS,\r
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
+ See the License for the specific language governing permissions and\r
+ limitations under the License.\r
+ ------------------------------------------- */\r
+\r
+#ifndef __HASH_TABLE_H\r
+#define __HASH_TABLE_H\r
+\r
+#include <stdlib.h>\r
+#include <stdio.h>\r
+\r
+\r
+\r
+#define NUM_PRIMES 23\r
+\r
+static unsigned int primes[NUM_PRIMES] = {\r
+ 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, 12853,\r
+ 25717, 51437, 102877, 205759, 411527, 823117, 1646237,\r
+ 3292489, 6584983, 13169977, 26339969, 52679969\r
+};\r
+\r
+\r
+\r
+template <class key_type, class value_type, class hasher_func, class equal_func>\r
+class hash_table {\r
+\r
+public :\r
+ struct data_item {\r
+ key_type first;\r
+ value_type second;\r
+ data_item* next; // next data item in overflow chain\r
+\r
+ data_item(const key_type& k, const value_type& v) : first(k), second(v), next(NULL) { }\r
+ };\r
+\r
+ struct hash_bucket {\r
+ data_item* data; //\r
+ hash_bucket* next_bucket; // index of the next bucket in the list of used buckets\r
+ hash_bucket* prev_bucket; // index of the next bucket in the list of used buckets\r
+\r
+ hash_bucket() {\r
+ data = NULL;\r
+ next_bucket = 0; // 0 means no bucket follows this one\r
+ prev_bucket = 0; // 0 means no bucket precedes this one\r
+ }\r
+ };\r
+\r
+ struct iterator {\r
+ hash_bucket* bucket;\r
+ data_item* data;\r
+\r
+ iterator& operator++() {\r
+ if (data->next)\r
+ data = data->next;\r
+ else {\r
+ bucket = bucket->next_bucket;\r
+ if (bucket)\r
+ data = bucket->data;\r
+ else\r
+ data = NULL;\r
+ }\r
+ return *this;\r
+ }\r
+\r
+// Like ++, but don't go beyond the end of the bucket chain.\r
+ iterator& next() {\r
+ if (data->next)\r
+ data = data->next;\r
+ else {\r
+ bucket = NULL;\r
+ data = NULL;\r
+ }\r
+ return *this;\r
+ }\r
+\r
+ bool operator!=(const iterator& it) {\r
+ return (data != it.data || bucket != it.bucket);\r
+ }\r
+\r
+ bool operator==(const iterator& it) {\r
+ return (data == it.data && bucket == it.bucket);\r
+ }\r
+\r
+ data_item &operator*() {\r
+ return *data;\r
+ }\r
+ };\r
+\r
+private:\r
+ hasher_func hasher;\r
+ equal_func equal;\r
+\r
+ double load_factor;\r
+// double max_load;\r
+\r
+ size_t _size;\r
+ size_t _max_size;\r
+ size_t num_buckets;\r
+ size_t hash_mask;\r
+\r
+ hash_bucket* first_bucket; // first used bucket\r
+ hash_bucket* last_bucket; // last used bucket\r
+\r
+ hash_bucket* buckets;\r
+\r
+ // memory footpritn in bytes\r
+ unsigned int total_memory;\r
+\r
+public:\r
+\r
+\r
+ hash_table(const size_t n_buckets = 131072, const double load = 0.5) {\r
+ load_factor = load;\r
+ int nb;\r
+ for(nb=2;nb<n_buckets;nb*=2);\r
+ num_buckets = nb;\r
+ hash_mask = nb-1;\r
+ buckets = new hash_bucket[num_buckets];\r
+\r
+ _size = 0;\r
+ _max_size = 0;\r
+// max_load = 0.0;\r
+ first_bucket = 0;\r
+ last_bucket = 0;\r
+\r
+ total_memory = num_buckets * sizeof(hash_bucket);\r
+ }\r
+\r
+ int insert(const key_type& key, const value_type& val) {\r
+ data_item* d = new data_item(key, val);\r
+ total_memory += sizeof(data_item);\r
+\r
+ // find the insertion bucket\r
+ size_t bucket_index = hasher(key) & hash_mask;\r
+ // if the bucket is empty just add new data_item\r
+ if (!buckets[bucket_index].data) {\r
+ // create new data item\r
+\r
+ buckets[bucket_index].data = d;\r
+ if (!first_bucket){\r
+ first_bucket = &buckets[bucket_index];\r
+ }else{\r
+ last_bucket->next_bucket = &buckets[bucket_index];\r
+ }\r
+\r
+ if (last_bucket)\r
+ buckets[bucket_index].prev_bucket = last_bucket;\r
+\r
+ last_bucket = &buckets[bucket_index];\r
+ } else { // we already have data items in this bucket\r
+ // prepend the item to overflow chain\r
+ data_item* temp = buckets[bucket_index].data;\r
+ buckets[bucket_index].data = d;\r
+ d->next = temp;\r
+ }\r
+ _size++;\r
+ if(_size>_max_size)\r
+ _max_size = _size;\r
+\r
+ return 0;\r
+ }\r
+\r
+ data_item *iterate_find(data_item* t, const key_type& key) {\r
+ data_item *temp = t;\r
+ while (temp && !equal(temp->first, key)){\r
+ temp = temp->next;\r
+ }\r
+ return temp;\r
+ }\r
+\r
+\r
+ iterator find(const key_type& key) {\r
+ iterator iter;\r
+\r
+ // find the insertion bucket\r
+ size_t bucket_index = hasher(key) & hash_mask;\r
+ // if the bucket is empty just add new data_item\r
+ if (!buckets[bucket_index].data) {\r
+ iter.bucket = NULL;\r
+ iter.data = NULL;\r
+ } else { // we already have data items in this bucket\r
+ data_item* temp = buckets[bucket_index].data;\r
+// temp = iterate_find(temp,key);\r
+\r
+ while (temp && !equal(temp->first, key))\r
+ temp = temp->next;\r
+\r
+ iter.data = temp;\r
+ if (!temp)\r
+ iter.bucket = NULL;\r
+ else\r
+ iter.bucket = &buckets[bucket_index];\r
+ }\r
+ return iter;\r
+ }\r
+\r
+ void erase(const key_type& key) {\r
+ // find the bucket\r
+ size_t bucket_index = hasher(key) & hash_mask;\r
+ // if the bucket is empty just add new data_item\r
+ if (!buckets[bucket_index].data)\r
+ return;\r
+\r
+ data_item* temp = buckets[bucket_index].data;\r
+ data_item* prev = NULL;\r
+ while (temp && !equal(temp->first, key)) {\r
+ prev = temp;\r
+ temp = temp->next;\r
+ }\r
+ if (!temp)\r
+ return;\r
+\r
+ // delete this data item from the chain\r
+ _size--;\r
+ if (!prev){ // we are deleting the first element in chain\r
+ buckets[bucket_index].data = temp->next;\r
+\r
+ if(temp->next == NULL){\r
+ if(buckets[bucket_index].next_bucket){\r
+ buckets[bucket_index].next_bucket->prev_bucket = buckets[bucket_index].prev_bucket;\r
+ }else{\r
+ last_bucket = buckets[bucket_index].prev_bucket;\r
+ }\r
+ if(buckets[bucket_index].prev_bucket){\r
+ buckets[bucket_index].prev_bucket->next_bucket = buckets[bucket_index].next_bucket;\r
+ }else{\r
+ first_bucket = buckets[bucket_index].next_bucket;\r
+ }\r
+ buckets[bucket_index].next_bucket = NULL;\r
+ buckets[bucket_index].prev_bucket = NULL;\r
+ }\r
+ }else{\r
+ prev->next = temp->next;\r
+ }\r
+ delete temp;\r
+ total_memory -= sizeof(data_item);\r
+ }\r
+\r
+ void erase_full(const key_type& key) {\r
+ // find the bucket\r
+ size_t bucket_index = hasher(key) & hash_mask;\r
+ // if the bucket is empty just add new data_item\r
+ if (!buckets[bucket_index].data)\r
+ return;\r
+\r
+ data_item* temp = buckets[bucket_index].data;\r
+ data_item* prev = NULL;\r
+ while (temp && !equal(temp->first, key)) {\r
+ prev = temp;\r
+ temp = temp->next;\r
+ }\r
+ if (!temp)\r
+ return;\r
+\r
+ // delete this data item from the chain\r
+ _size--;\r
+ if (!prev){ // we are deleting the first element in chain\r
+ buckets[bucket_index].data = temp->next;\r
+\r
+ if(temp->next == NULL){\r
+ if(buckets[bucket_index].next_bucket){\r
+ buckets[bucket_index].next_bucket->prev_bucket = buckets[bucket_index].prev_bucket;\r
+ }else{\r
+ last_bucket = buckets[bucket_index].prev_bucket;\r
+ }\r
+ if(buckets[bucket_index].prev_bucket){\r
+ buckets[bucket_index].prev_bucket->next_bucket = buckets[bucket_index].next_bucket;\r
+ }else{\r
+ first_bucket = buckets[bucket_index].next_bucket;\r
+ }\r
+ buckets[bucket_index].next_bucket = NULL;\r
+ buckets[bucket_index].prev_bucket = NULL;\r
+ }\r
+ }else{\r
+ prev->next = temp->next;\r
+ }\r
+ delete (*temp).first;\r
+ delete (*temp).second;\r
+ delete temp;\r
+ total_memory -= sizeof(data_item);\r
+ }\r
+\r
+ iterator begin() {\r
+ iterator iter;\r
+ // find the first data item\r
+ iter.bucket = first_bucket;\r
+ iter.data = (first_bucket) ? first_bucket->data : NULL;\r
+ return iter;\r
+ }\r
+\r
+ iterator end() {\r
+ iterator iter;\r
+ iter.bucket = NULL;\r
+ iter.data = NULL;\r
+ return iter;\r
+ }\r
+\r
+ void clear() {\r
+ data_item* temp;\r
+ data_item* next;\r
+\r
+ hash_bucket* tmp;\r
+ while (first_bucket) {\r
+ temp = first_bucket->data;\r
+ while ( (next = temp->next) ) {\r
+ delete temp;\r
+ temp = next;\r
+ }\r
+ if(temp) delete(temp);\r
+ first_bucket->data = NULL;\r
+ tmp = first_bucket;\r
+ first_bucket = first_bucket->next_bucket;\r
+ tmp->next_bucket = NULL;\r
+ tmp->prev_bucket = NULL;\r
+ }\r
+ last_bucket = NULL;\r
+ _size = 0;\r
+ total_memory = num_buckets * sizeof(hash_bucket);\r
+\r
+ }\r
+\r
+ int rehash() {\r
+ if (_size) {\r
+ fprintf(stderr, "Error: rehashing non-empty hash table\n");\r
+ exit(1);\r
+ }\r
+\r
+ double max_load = (1.0 * _max_size) / num_buckets;\r
+ if (max_load > load_factor ) {\r
+ delete[] buckets;\r
+ // roughly double the size of the table\r
+\r
+ num_buckets *= 2;\r
+ hash_mask = num_buckets-1;\r
+\r
+ buckets = new hash_bucket[num_buckets];\r
+ total_memory = num_buckets * sizeof(hash_bucket);\r
+ }\r
+ _max_size = _size;\r
+ return 0;\r
+ }\r
+\r
+\r
+ size_t size() const {\r
+ return _size;\r
+ }\r
+\r
+ bool empty() const {\r
+ return (_size == 0);\r
+ }\r
+\r
+ ~hash_table() {\r
+ clear();\r
+ delete[] buckets;\r
+ }\r
+\r
+ unsigned int get_mem_footprint() {\r
+ return total_memory;\r
+ }\r
+\r
+};\r
+\r
+\r
+template <class key_type, class hasher_func, class equal_func>\r
+class hash_set {\r
+\r
+public :\r
+ struct data_item {\r
+ key_type key;\r
+ data_item* next; // next data item in overflow chain\r
+\r
+ data_item(const key_type& k) : key(k), next(NULL) { }\r
+ };\r
+\r
+ struct hash_bucket {\r
+ data_item* data; //\r
+ hash_bucket* next_bucket; // index of the next bucket in the list of used buckets\r
+\r
+ hash_bucket() {\r
+ data = NULL;\r
+ next_bucket = 0; // 0 means no bucket follows this one\r
+ }\r
+ };\r
+\r
+ struct iterator {\r
+ hash_bucket* bucket;\r
+ data_item* data;\r
+\r
+ iterator& operator++() {\r
+ if (data->next)\r
+ data = data->next;\r
+ else {\r
+ bucket = bucket->next_bucket;\r
+ if (bucket)\r
+ data = bucket->data;\r
+ else\r
+ data = NULL;\r
+ }\r
+ return *this;\r
+ }\r
+\r
+ bool operator!=(const iterator& it) {\r
+ return (data != it.data || bucket != it.bucket);\r
+ }\r
+\r
+ bool operator==(const iterator& it) {\r
+ return (data == it.data && bucket == it.bucket);\r
+ }\r
+\r
+// NOTE : not certain if returning ref always works\r
+ key_type &operator*() {\r
+ return data->key;\r
+ }\r
+ };\r
+\r
+private:\r
+ hasher_func hasher;\r
+ equal_func equal;\r
+\r
+ double load_factor;\r
+// double max_load;\r
+\r
+ size_t _size;\r
+ size_t _max_size;\r
+ size_t num_buckets;\r
+ size_t hash_mask;\r
+\r
+ hash_bucket* first_bucket; // first used bucket\r
+ hash_bucket* last_bucket; // last used bucket\r
+\r
+ hash_bucket* buckets;\r
+\r
+public:\r
+ hash_set(const size_t n_buckets = 131072, const double load = 0.75) {\r
+ load_factor = load;\r
+\r
+ int nb;\r
+ for(nb=2;nb<n_buckets;nb*=2);\r
+ num_buckets = nb;\r
+ hash_mask = num_buckets-1;\r
+\r
+ buckets = new hash_bucket[num_buckets];\r
+\r
+ _size = 0;\r
+ _max_size = 0;\r
+// max_load = 0.0;\r
+ first_bucket = 0;\r
+ last_bucket = 0;\r
+ }\r
+\r
+ int insert(const key_type& key) {\r
+ data_item* d = new data_item(key);\r
+\r
+ // find the insertion bucket\r
+ size_t bucket_index = hasher(key) & hash_mask;\r
+ // if the bucket is empty just add new data_item\r
+ if (!buckets[bucket_index].data) {\r
+ // create new data item\r
+\r
+ buckets[bucket_index].data = d;\r
+ if (!first_bucket)\r
+ first_bucket = &buckets[bucket_index];\r
+ else\r
+ last_bucket->next_bucket = &buckets[bucket_index];\r
+ last_bucket = &buckets[bucket_index];\r
+ } else { // we already have data items in this bucket\r
+ // prepend the item to overflow chain\r
+ data_item* temp = buckets[bucket_index].data;\r
+ buckets[bucket_index].data = d;\r
+ d->next = temp;\r
+ }\r
+ _size++;\r
+ if(_size>_max_size)\r
+ _max_size = _size;\r
+\r
+ return 0;\r
+ }\r
+\r
+ iterator find(const key_type& key) {\r
+ iterator iter;\r
+\r
+ // find the insertion bucket\r
+ size_t bucket_index = hasher(key) & hash_mask;\r
+ // if the bucket is empty just add new data_item\r
+ if (!buckets[bucket_index].data) {\r
+ iter.bucket = NULL;\r
+ iter.data = NULL;\r
+ } else { // we already have data items in this bucket\r
+ data_item* temp = buckets[bucket_index].data;\r
+ while (temp && !equal(temp->key, key))\r
+ temp = temp->next;\r
+ iter.data = temp;\r
+ if (!temp)\r
+ iter.bucket = NULL;\r
+ else\r
+ iter.bucket = &buckets[bucket_index];\r
+ }\r
+ return iter;\r
+ }\r
+\r
+ void erase(const key_type& key) {\r
+ // find the bucket\r
+ size_t bucket_index = hasher(key) & hash_mask;\r
+ // if the bucket is empty just add new data_item\r
+ if (!buckets[bucket_index].data)\r
+ return;\r
+\r
+ data_item* temp = buckets[bucket_index].data;\r
+ data_item* prev = NULL;\r
+ while (temp && !equal(temp->key, key)) {\r
+ prev = temp;\r
+ temp = temp->next;\r
+ }\r
+ if (!temp)\r
+ return;\r
+\r
+ // delete this data item from the chain\r
+ _size--;\r
+ if (!prev) // we are deleting the first element in chain\r
+ buckets[bucket_index].data = temp->next;\r
+ else\r
+ prev->next = temp->next;\r
+ delete temp;\r
+ }\r
+\r
+ iterator begin() {\r
+ iterator iter;\r
+ // find the first data item\r
+ iter.bucket = first_bucket;\r
+ iter.data = (first_bucket) ? first_bucket->data : NULL;\r
+ return iter;\r
+ }\r
+\r
+ iterator end() {\r
+ iterator iter;\r
+ iter.bucket = NULL;\r
+ iter.data = NULL;\r
+ return iter;\r
+ }\r
+\r
+ void clear() {\r
+ data_item* temp;\r
+ data_item* next;\r
+\r
+ hash_bucket* tmp;\r
+ while (first_bucket) {\r
+ temp = first_bucket->data;\r
+ while ( (next = temp->next) ) {\r
+ delete temp;\r
+ temp = next;\r
+ }\r
+ if(temp) delete(temp);\r
+ first_bucket->data = NULL;\r
+ tmp = first_bucket;\r
+ first_bucket = first_bucket->next_bucket;\r
+ tmp->next_bucket = NULL;\r
+ }\r
+ last_bucket = NULL;\r
+ _size = 0;\r
+\r
+ }\r
+\r
+ int rehash() {\r
+ if (_size) {\r
+ fprintf(stderr, "Error: rehashing non-empty hash table\n");\r
+ exit(1);\r
+ }\r
+\r
+ double max_load = (1.0 * _max_size) / num_buckets;\r
+\r
+ if (max_load > load_factor ) {\r
+ delete[] buckets;\r
+ // roughly double the size of the table\r
+\r
+ num_buckets *= 2;\r
+ hash_mask = num_buckets -1;\r
+ buckets = new hash_bucket[num_buckets];\r
+ }\r
+ _max_size = _size;\r
+ return 0;\r
+ }\r
+\r
+\r
+ size_t size() const {\r
+ return _size;\r
+ }\r
+\r
+ bool empty() const {\r
+ return (_size == 0);\r
+ }\r
+\r
+ ~hash_set() {\r
+ clear();\r
+ delete[] buckets;\r
+ }\r
+\r
+};\r
+\r
+\r
+#endif // __HASH_TABLE_H\r
Code Review / com / gs-lite.git / blobdiff