_Key key;
_Val val;
uint hashcode;
+ struct Hashlistnode<_Key, _Val> * next;
+ struct Hashlistnode<_Key, _Val> * prev;
};
template<typename _Key, int _Shift, typename _KeyInt>
threshold = (unsigned int)(initialcapacity * loadfactor);
Size = 0; // Initial number of elements in the hash
+ tail = list = NULL;
}
/** @brief Hash table destructor */
zero = NULL;
}
Size = 0;
+ tail = list = NULL;
}
/** Doesn't work with zero value */
zero = NULL;
}
Size = 0;
+ tail = list = NULL;
}
void resetAndDeleteVals() {
zero = NULL;
}
Size = 0;
+ tail = list = NULL;
}
void resetAndFreeVals() {
zero = NULL;
}
Size = 0;
+ tail = list = NULL;
}
/**
_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
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;
}
_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--;
//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;
}
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];
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;
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;