diff options
Diffstat (limited to 'node/Hashtable.hpp')
| -rw-r--r-- | node/Hashtable.hpp | 52 |
1 files changed, 35 insertions, 17 deletions
diff --git a/node/Hashtable.hpp b/node/Hashtable.hpp index 66f2990a..777e88dc 100644 --- a/node/Hashtable.hpp +++ b/node/Hashtable.hpp @@ -1,6 +1,6 @@ /* * ZeroTier One - Network Virtualization Everywhere - * Copyright (C) 2011-2016 ZeroTier, Inc. https://www.zerotier.com/ + * Copyright (C) 2011-2018 ZeroTier, Inc. https://www.zerotier.com/ * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -14,11 +14,21 @@ * * You should have received a copy of the GNU General Public License * along with this program. If not, see <http://www.gnu.org/licenses/>. + * + * -- + * + * You can be released from the requirements of the license by purchasing + * a commercial license. Buying such a license is mandatory as soon as you + * develop commercial closed-source software that incorporates or links + * directly against ZeroTier software without disclosing the source code + * of your own application. */ #ifndef ZT_HASHTABLE_HPP #define ZT_HASHTABLE_HPP +#include "Constants.hpp" + #include <stdint.h> #include <stdio.h> #include <stdlib.h> @@ -32,11 +42,6 @@ namespace ZeroTier { /** * A minimal hash table implementation for the ZeroTier core - * - * This is not a drop-in replacement for STL containers, and has several - * limitations. Keys can be uint64_t or an object, and if the latter they - * must implement a method called hashCode() that returns an unsigned long - * value that is evenly distributed. */ template<typename K,typename V> class Hashtable @@ -100,7 +105,7 @@ public: Hashtable *_ht; _Bucket *_b; }; - friend class Hashtable::Iterator; + //friend class Hashtable<K,V>::Iterator; /** * @param bc Initial capacity in buckets (default: 64, must be nonzero) @@ -111,7 +116,7 @@ public: _s(0) { if (!_t) - throw std::bad_alloc(); + throw ZT_EXCEPTION_OUT_OF_MEMORY; for(unsigned long i=0;i<bc;++i) _t[i] = (_Bucket *)0; } @@ -122,7 +127,7 @@ public: _s(ht._s) { if (!_t) - throw std::bad_alloc(); + throw ZT_EXCEPTION_OUT_OF_MEMORY; for(unsigned long i=0;i<_bc;++i) _t[i] = (_Bucket *)0; for(unsigned long i=0;i<_bc;++i) { @@ -251,6 +256,24 @@ public: inline const V *get(const K &k) const { return const_cast<Hashtable *>(this)->get(k); } /** + * @param k Key + * @param v Value to fill with result + * @return True if value was found and set (if false, v is not modified) + */ + inline bool get(const K &k,V &v) const + { + _Bucket *b = _t[_hc(k) % _bc]; + while (b) { + if (b->k == k) { + v = b->v; + return true; + } + b = b->next; + } + return false; + } + + /** * @param k Key to check * @return True if key is present */ @@ -351,12 +374,12 @@ public: /** * @return Number of entries */ - inline unsigned long size() const throw() { return _s; } + inline unsigned long size() const { return _s; } /** * @return True if table is empty */ - inline bool empty() const throw() { return (_s == 0); } + inline bool empty() const { return (_s == 0); } private: template<typename O> @@ -366,12 +389,7 @@ private: } static inline unsigned long _hc(const uint64_t i) { - /* NOTE: this assumes that 'i' is evenly distributed, which is the case for - * packet IDs and network IDs -- the two use cases in ZT for uint64_t keys. - * These values are also greater than 0xffffffff so they'll map onto a full - * bucket count just fine no matter what happens. Normally you'd want to - * hash an integer key index in a hash table. */ - return (unsigned long)i; + return (unsigned long)(i ^ (i >> 32)); // good for network IDs and addresses } static inline unsigned long _hc(const uint32_t i) { |