diff options
| -rw-r--r-- | node/Hashtable.hpp | 74 | ||||
| -rw-r--r-- | 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 */ @@ -141,6 +179,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; } } |