X-Git-Url: http://plrg.eecs.uci.edu/git/?p=iotcloud.git;a=blobdiff_plain;f=version2%2Fsrc%2FC%2Fhashtable.h;h=91d1e5a465c9358364e547a7da55c1ee2b01645a;hp=c642804f99433c1ab221ae6c220c2345459d2346;hb=d28d6cb0b30fcb629eb66feb8506c7e76a3652f8;hpb=f3fdb1f3b472981933d32c8f707f0cdc0db2f050

diff --git a/version2/src/C/hashtable.h b/version2/src/C/hashtable.h
index c642804..91d1e5a 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>
@@ -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:
@@ -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;
 	}
 
 	/**
@@ -196,7 +215,13 @@ public:
 			_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;
@@ -205,7 +230,7 @@ public:
 			return oldval;
 		}
 
-		if (size > threshold)
+		if (Size > threshold)
 			resize(capacity << 1);
 
 		struct Hashlistnode<_Key, _Val> *search;
@@ -231,7 +256,12 @@ public:
 		search->key = key;
 		search->val = val;
 		search->hashcode = hashcode;
-		size++;
+		search->next = list;
+		if (list == NULL)
+			tail = search;
+		else
+			list->prev = search;
+		Size++;
 		return (_Val) 0;
 	}
 
@@ -279,15 +309,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;
 			}
 		}
@@ -308,7 +347,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++;
@@ -316,8 +366,8 @@ public:
 		return (_Val)0;
 	}
 
-	unsigned int getSize() const {
-		return size;
+	unsigned int size() const {
+		return Size;
 	}
 
 
@@ -368,7 +418,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 +438,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,8 +455,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;