X-Git-Url: http://plrg.eecs.uci.edu/git/?p=iotcloud.git;a=blobdiff_plain;f=version2%2Fsrc%2FC%2Fhashtable.h;fp=version2%2Fsrc%2FC%2Fhashtable.h;h=3ded5b5993f7b9568501f874bcf08fa6ba8cc31f;hp=b610154dc87d111cc123a1cf309f538e25657f73;hb=f0e5bd79679ee0241e757953260e481dca736068;hpb=1982d44395bc486667d8b25d6d7763c2ffbf61bc

diff --git a/version2/src/C/hashtable.h b/version2/src/C/hashtable.h
index b610154..3ded5b5 100644
--- 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;