edits

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

diff --git a/version2/src/C/hashtable.h b/version2/src/C/hashtable.h
index b610154dc87d111cc123a1cf309f538e25657f73..3ded5b5993f7b9568501f874bcf08fa6ba8cc31f 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>
@@ -77,6 +79,7 @@ public:
 
                threshold = (unsigned int)(initialcapacity * loadfactor);
                Size = 0;                                                       // Initial number of elements in the hash
+               tail = list = NULL;
        }
 
        /** @brief Hash table destructor */
@@ -114,6 +117,7 @@ public:
                        zero = NULL;
                }
                Size = 0;
+               tail = list = NULL;
        }
 
        /** Doesn't work with zero value */
@@ -143,6 +147,7 @@ public:
                        zero = NULL;
                }
                Size = 0;
+               tail = list = NULL;
        }
 
        void resetAndDeleteVals() {
@@ -163,6 +168,7 @@ public:
                        zero = NULL;
                }
                Size = 0;
+               tail = list = NULL;
        }
 
        void resetAndFreeVals() {
@@ -183,6 +189,7 @@ public:
                        zero = NULL;
                }
                Size = 0;
+               tail = list = NULL;
        }
 
        /**
@@ -196,6 +203,12 @@ public:
                        _Val oldval;
                        if (!zero) {
                                zero = (struct Hashlistnode<_Key, _Val> *)ourmalloc(sizeof(struct Hashlistnode<_Key, _Val>));
+                               zero->next = list;
+                               if (list != NULL)
+                                       list->prev = zero;
+                               else
+                                       tail = zero;
+                               list = zero;
                                Size++;
                                oldval = (_Val) 0;
                        } else
@@ -231,6 +244,11 @@ public:
                search->key = key;
                search->val = val;
                search->hashcode = hashcode;
+               search->next = list;
+               if (list == NULL)
+                       tail = search;
+               else
+                       list->prev = search;
                Size++;
                return (_Val) 0;
        }
@@ -279,12 +297,21 @@ 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--;
@@ -308,6 +335,17 @@ public:
                                        //empty out this bin
                                        search->val = (_Val) 1;
                                        search->key = 0;
+                                       
+                                       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;
                                }
@@ -368,7 +406,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];
@@ -388,6 +426,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;
@@ -399,7 +443,9 @@ public:
        unsigned int getCapacity() {return capacity;}
        struct Hashlistnode<_Key, _Val> *table;
        struct Hashlistnode<_Key, _Val> *zero;
-       unsigned int capacity;
+  struct Hashlistnode<_Key, _Val> * list;
+  struct Hashlistnode<_Key, _Val> * tail;
+  unsigned int capacity;
        unsigned int Size;
 private:
        unsigned int capacitymask;