projects
/
iotcloud.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
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;
_Key key;
_Val val;
uint hashcode;
+ struct Hashlistnode<_Key, _Val> * next;
+ struct Hashlistnode<_Key, _Val> * prev;
};
template<typename _Key, int _Shift, typename _KeyInt>
};
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
threshold = (unsigned int)(initialcapacity * loadfactor);
Size = 0; // Initial number of elements in the hash
+ tail = list = NULL;
}
/** @brief Hash table destructor */
}
/** @brief Hash table destructor */
@@
-114,6
+117,7
@@
public:
zero = NULL;
}
Size = 0;
zero = NULL;
}
Size = 0;
+ tail = list = NULL;
}
/** Doesn't work with zero value */
}
/** Doesn't work with zero value */
@@
-143,6
+147,7
@@
public:
zero = NULL;
}
Size = 0;
zero = NULL;
}
Size = 0;
+ tail = list = NULL;
}
void resetAndDeleteVals() {
}
void resetAndDeleteVals() {
@@
-163,6
+168,7
@@
public:
zero = NULL;
}
Size = 0;
zero = NULL;
}
Size = 0;
+ tail = list = NULL;
}
void resetAndFreeVals() {
}
void resetAndFreeVals() {
@@
-183,6
+189,7
@@
public:
zero = NULL;
}
Size = 0;
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>));
_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
Size++;
oldval = (_Val) 0;
} else
@@
-231,6
+244,11
@@
public:
search->key = key;
search->val = val;
search->hashcode = hashcode;
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;
}
Size++;
return (_Val) 0;
}
@@
-279,12
+297,21
@@
public:
_Val remove(_Key key) {
struct Hashlistnode<_Key, _Val> *search;
_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 (!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--;
ourfree(zero);
zero = NULL;
Size--;
@@
-308,6
+335,17
@@
public:
//empty out this bin
search->val = (_Val) 1;
search->key = 0;
//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;
}
Size--;
return v;
}
@@
-368,7
+406,7
@@
public:
table = newtable; // Update the global hashtable upon resize()
capacity = newsize;
capacitymask = newsize - 1;
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];
threshold = (unsigned int)(newsize * loadfactor);
struct Hashlistnode<_Key, _Val> *bin = &oldtable[0];
@@
-388,6
+426,12
@@
public:
index++;
} while (search->key);
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;
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 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;
unsigned int Size;
private:
unsigned int capacitymask;