From da9a720c3fc2d69e35f393fbb96a716599ac0a6f Mon Sep 17 00:00:00 2001
From: Adam Ierymenko <adam.ierymenko@gmail.com>
Date: Thu, 3 Sep 2015 17:33:06 -0700
Subject: Hash table bug fix, and add copy constructor and assignment operator
for principle of least surprise.
---
node/Hashtable.hpp | 74 +++++++++++++++++++++++++++++++++++++++++++++++++-----
selftest.cpp | 39 ++++++++++++++++++++++++----
2 files changed, 102 insertions(+), 11 deletions(-)
diff --git a/node/Hashtable.hpp b/node/Hashtable.hpp
index c997d54f..5076751d 100644
--- a/node/Hashtable.hpp
+++ b/node/Hashtable.hpp
@@ -29,6 +29,7 @@
#include <stdlib.h>
#include <stdexcept>
+#include <vector>
namespace ZeroTier {
@@ -47,9 +48,11 @@ private:
{
_Bucket(const K &k,const V &v) : k(k),v(v) {}
_Bucket(const K &k) : k(k),v() {}
+ _Bucket(const _Bucket &b) : k(b.k),v(b.v) {}
+ inline _Bucket &operator=(const _Bucket &b) { k = b.k; v = b.v; return *this; }
K k;
V v;
- _Bucket *next;
+ _Bucket *next; // must be set manually for each _Bucket
};
public:
@@ -115,12 +118,47 @@ public:
_t[i] = (_Bucket *)0;
}
+ Hashtable(const Hashtable<K,V> &ht) :
+ _t(reinterpret_cast<_Bucket **>(::malloc(sizeof(_Bucket *) * ht._bc))),
+ _bc(ht._bc),
+ _s(ht._s)
+ {
+ if (!_t)
+ throw std::bad_alloc();
+ for(unsigned long i=0;i<_bc;++i)
+ _t[i] = (_Bucket *)0;
+ for(unsigned long i=0;i<_bc;++i) {
+ const _Bucket *b = ht._t[i];
+ while (b) {
+ _Bucket *nb = new _Bucket(*b);
+ nb->next = _t[i];
+ _t[i] = nb;
+ b = b->next;
+ }
+ }
+ }
+
~Hashtable()
{
- clear();
+ this->clear();
::free(_t);
}
+ inline Hashtable &operator=(const Hashtable<K,V> &ht)
+ {
+ this->clear();
+ if (ht._s) {
+ for(unsigned long i=0;i<ht._bc;++i) {
+ const _Bucket *b = ht._t[i];
+ while (b) {
+ this->set(b->k,b->v);
+ b = b->next;
+ }
+ }
+ }
+ return *this;
+ }
+
/**
* Erase all entries
*/
@@ -140,6 +178,24 @@ public:
}
}
+ /**
+ * @return Vector of all keys
+ */
+ inline typename std::vector<K> keys()
+ {
+ typename std::vector<K> k;
+ if (_s) {
+ for(unsigned long i=0;i<_bc;++i) {
+ _Bucket *b = _t[i];
+ while (b) {
+ k.push_back(b->k);
+ b = b->next;
+ }
+ }
+ }
+ return k;
+ }
+
/**
* @param k Key
* @return Pointer to value or NULL if not found
@@ -187,7 +243,8 @@ public:
*/
inline V &set(const K &k,const V &v)
{
- const unsigned long bidx = _hc(k) % _bc;
+ const unsigned long h = _hc(k);
+ unsigned long bidx = h % _bc;
_Bucket *b = _t[bidx];
while (b) {
@@ -198,8 +255,10 @@ public:
b = b->next;
}
- if (_s >= _bc)
+ if (_s >= _bc) {
_grow();
+ bidx = h % _bc;
+ }
b = new _Bucket(k,v);
b->next = _t[bidx];
@@ -215,7 +274,8 @@ public:
*/
inline V &operator[](const K &k)
{
- const unsigned long bidx = _hc(k) % _bc;
+ const unsigned long h = _hc(k);
+ unsigned long bidx = h % _bc;
_Bucket *b = _t[bidx];
while (b) {
@@ -224,8 +284,10 @@ public:
b = b->next;
}
- if (_s >= _bc)
+ if (_s >= _bc) {
_grow();
+ bidx = h % _bc;
+ }
b = new _Bucket(k);
b->next = _t[bidx];
diff --git a/selftest.cpp b/selftest.cpp
index 15afe52e..5e3b620b 100644
--- a/selftest.cpp
+++ b/selftest.cpp
@@ -581,31 +581,60 @@ static int testOther()
{
std::cout << "[other] Testing Hashtable... "; std::cout.flush();
{
- Hashtable<uint64_t,std::string> ht(128);
+ Hashtable<uint64_t,std::string> ht;
+ Hashtable<uint64_t,std::string> ht2;
std::map<uint64_t,std::string> ref; // assume std::map works correctly :)
for(int x=0;x<2;++x) {
for(int i=0;i<25000;++i) {
uint64_t k = rand();
while ((k == 0)||(ref.count(k) > 0))
++k;
- std::string v;
+ std::string v("!");
for(int j=0;j<(int)(k % 64);++j)
v.push_back("0123456789"[rand() % 10]);
ht.set(k,v);
ref[k] = v;
}
if (ht.size() != ref.size()) {
- std::cout << "FAILED! (size mismatch)" << std::endl;
+ std::cout << "FAILED! (size mismatch, original)" << std::endl;
+ return -1;
+ }
+ ht2 = ht;
+ Hashtable<uint64_t,std::string> ht3(ht2);
+ if (ht2.size() != ref.size()) {
+ std::cout << "FAILED! (size mismatch, assigned)" << std::endl;
+ return -1;
+ }
+ if (ht3.size() != ref.size()) {
+ std::cout << "FAILED! (size mismatch, copied)" << std::endl;
return -1;
}
for(std::map<uint64_t,std::string>::iterator i(ref.begin());i!=ref.end();++i) {
std::string *v = ht.get(i->first);
if (!v) {
- std::cout << "FAILED! (key not found)" << std::endl;
+ std::cout << "FAILED! (key " << i->first << " not found, original)" << std::endl;
+ return -1;
+ }
+ if (*v != i->second) {
+ std::cout << "FAILED! (key " << i->first << " not equal, original)" << std::endl;
+ return -1;
+ }
+ v = ht2.get(i->first);
+ if (!v) {
+ std::cout << "FAILED! (key " << i->first << " not found, assigned)" << std::endl;
+ return -1;
+ }
+ if (*v != i->second) {
+ std::cout << "FAILED! (key " << i->first << " not equal, assigned)" << std::endl;
+ return -1;
+ }
+ v = ht3.get(i->first);
+ if (!v) {
+ std::cout << "FAILED! (key " << i->first << " not found, copied)" << std::endl;
return -1;
}
if (*v != i->second) {
- std::cout << "FAILED! (key not equal)" << std::endl;
+ std::cout << "FAILED! (key " << i->first << " not equal, copied)" << std::endl;
return -1;
}
}
--
cgit v1.2.3