Change default hashtable size

[iotcloud.git] / version2 / src / C / hashtable.h

diff --git a/version2/src/C/hashtable.h b/version2/src/C/hashtable.h
index 513d31198e5e379b6576c941a353e5b789080240..6107e339c3ea972e5997374708f999cb7b4d2b5c 100644 (file)
--- a/version2/src/C/hashtable.h
+++ b/version2/src/C/hashtable.h
@@ -31,6 +31,8 @@ struct Hashlistnode {
        _Key key;
        _Val val;
        uint hashcode;
+       struct Hashlistnode<_Key, _Val> *next;
+       struct Hashlistnode<_Key, _Val> *prev;
 };
 
 template<typename _Key, int _Shift, typename _KeyInt>
@@ -57,6 +59,7 @@ inline bool defaultEquals(_Key key1, _Key key2) {
  *                 manipulation and storage.
  * @tparam _Shift  Logical shift to apply to all keys. Default 0.
  */
+
 template<typename _Key, typename _Val, typename _KeyInt = uintptr_t, int _Shift = 0, unsigned int (*hash_function)(_Key) = defaultHashFunction<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = defaultEquals<_Key> >
 class Hashtable {
 public:
@@ -67,7 +70,7 @@ public:
         * @param factor Sets the percentage full before the hashtable is
         * resized. Default ratio 0.5.
         */
-       Hashtable(unsigned int initialcapacity = 1024, double factor = 0.5) {
+       Hashtable(unsigned int initialcapacity = 32, double factor = 0.5) {
                // Allocate space for the hash table
                table = (struct Hashlistnode<_Key, _Val> *)ourcalloc(initialcapacity, sizeof(struct Hashlistnode<_Key, _Val>));
                zero = NULL;
@@ -76,9 +79,21 @@ public:
                capacitymask = initialcapacity - 1;
 
                threshold = (unsigned int)(initialcapacity * loadfactor);
-               size = 0;                                                       // Initial number of elements in the hash
+               Size = 0;                                                       // Initial number of elements in the hash
+               tail = list = NULL;
+       }
+
+       Hashtable<_Key, _Val, _KeyInt, _Shift, hash_function, equals> *clone() {
+               Hashtable<_Key, _Val, _KeyInt, _Shift, hash_function, equals> *ctable = new Hashtable<_Key, _Val, _KeyInt, _Shift, hash_function, equals> (capacity, loadfactor);
+               struct Hashlistnode<_Key, _Val> *ptr = list;
+               while (ptr != NULL) {
+                       ctable->put(ptr->key, ptr->val);
+                       ptr = ptr->next;
+               }
+               return ctable;
        }
 
+
        /** @brief Hash table destructor */
        ~Hashtable() {
                ourfree(table);
@@ -107,13 +122,14 @@ public:
        }
 
        /** @brief Reset the table to its initial state. */
-       void reset() {
+       void clear() {
                memset(table, 0, capacity * sizeof(struct Hashlistnode<_Key, _Val>));
                if (zero) {
                        ourfree(zero);
                        zero = NULL;
                }
-               size = 0;
+               Size = 0;
+               tail = list = NULL;
        }
 
        /** Doesn't work with zero value */
@@ -142,7 +158,8 @@ public:
                        ourfree(zero);
                        zero = NULL;
                }
-               size = 0;
+               Size = 0;
+               tail = list = NULL;
        }
 
        void resetAndDeleteVals() {
@@ -162,7 +179,8 @@ public:
                        ourfree(zero);
                        zero = NULL;
                }
-               size = 0;
+               Size = 0;
+               tail = list = NULL;
        }
 
        void resetAndFreeVals() {
@@ -182,7 +200,8 @@ public:
                        ourfree(zero);
                        zero = NULL;
                }
-               size = 0;
+               Size = 0;
+               tail = list = NULL;
        }
 
        /**
@@ -190,19 +209,28 @@ public:
         * @param key The key for the new value; must not be 0 or NULL
         * @param val The value to store in the table
         */
-       void put(_Key key, _Val val) {
+       _Val put(_Key key, _Val val) {
                /* Hashtable cannot handle 0 as a key */
                if (!key) {
+                       _Val oldval;
                        if (!zero) {
                                zero = (struct Hashlistnode<_Key, _Val> *)ourmalloc(sizeof(struct Hashlistnode<_Key, _Val>));
-                               size++;
-                       }
+                               zero->next = list;
+                               if (list != NULL)
+                                       list->prev = zero;
+                               else
+                                       tail = zero;
+                               list = zero;
+                               Size++;
+                               oldval = (_Val) 0;
+                       } else
+                               oldval = zero->val;
                        zero->key = key;
                        zero->val = val;
-                       return;
+                       return oldval;
                }
 
-               if (size > threshold)
+               if (Size > threshold)
                        resize(capacity << 1);
 
                struct Hashlistnode<_Key, _Val> *search;
@@ -218,8 +246,9 @@ public:
                        }
                        if (search->hashcode == hashcode)
                                if (equals(search->key, key)) {
+                                       _Val oldval = search->val;
                                        search->val = val;
-                                       return;
+                                       return oldval;
                                }
                        index++;
                } while (true);
@@ -227,7 +256,14 @@ public:
                search->key = key;
                search->val = val;
                search->hashcode = hashcode;
-               size++;
+               search->next = list;
+               if (list == NULL)
+                       tail = search;
+               else
+                       list->prev = search;
+               list = search;
+               Size++;
+               return (_Val) 0;
        }
 
        /**
@@ -274,15 +310,24 @@ public:
        _Val remove(_Key key) {
                struct Hashlistnode<_Key, _Val> *search;
 
-               /* Hashtable cannot handle 0 as a key */
                if (!key) {
                        if (!zero) {
                                return (_Val)0;
                        } else {
                                _Val v = zero->val;
+                               if (zero->next != NULL)
+                                       zero->next->prev = zero->prev;
+                               else
+                                       tail = zero->prev;
+
+                               if (zero->prev != NULL)
+                                       zero->prev->next = zero->next;
+                               else
+                                       list = zero->next;
+
                                ourfree(zero);
                                zero = NULL;
-                               size--;
+                               Size--;
                                return v;
                        }
                }
@@ -303,7 +348,18 @@ public:
                                        //empty out this bin
                                        search->val = (_Val) 1;
                                        search->key = 0;
-                                       size--;
+
+                                       if (search->next != NULL)
+                                               search->next->prev = search->prev;
+                                       else
+                                               tail = search->prev;
+
+                                       if (search->prev != NULL)
+                                               search->prev->next = search->next;
+                                       else
+                                               list = search->next;
+
+                                       Size--;
                                        return v;
                                }
                        index++;
@@ -311,8 +367,8 @@ public:
                return (_Val)0;
        }
 
-       unsigned int getSize() const {
-               return size;
+       unsigned int size() const {
+               return Size;
        }
 
 
@@ -363,7 +419,7 @@ public:
                table = newtable;                                                                                       // Update the global hashtable upon resize()
                capacity = newsize;
                capacitymask = newsize - 1;
-
+               list = tail = NULL;
                threshold = (unsigned int)(newsize * loadfactor);
 
                struct Hashlistnode<_Key, _Val> *bin = &oldtable[0];
@@ -383,6 +439,12 @@ public:
                                index++;
                        } while (search->key);
 
+                       if (tail == NULL)
+                               tail = search;
+                       search->next = list;
+                       if (list != NULL)
+                               list->prev = search;
+                       list = search;
                        search->hashcode = hashcode;
                        search->key = key;
                        search->val = bin->val;
@@ -394,8 +456,10 @@ public:
        unsigned int getCapacity() {return capacity;}
        struct Hashlistnode<_Key, _Val> *table;
        struct Hashlistnode<_Key, _Val> *zero;
+       struct Hashlistnode<_Key, _Val> *list;
+       struct Hashlistnode<_Key, _Val> *tail;
        unsigned int capacity;
-       unsigned int size;
+       unsigned int Size;
 private:
        unsigned int capacitymask;
        unsigned int threshold;