HashSet with 2^n slots. More...
#include <HashSet.hpp>
Classes | |
| struct | Data |
Public Member Functions | |
| HashSet (unsigned bits) | |
| Constructs a hashset with 2^bits slots. | |
| HashSet (const HashSet &other) | |
| Copy constructor. | |
| ~HashSet () | |
| Destructor. | |
| unsigned | bits () const |
| Returns the lg2 of the number of slots. | |
| unsigned | size () const |
| Returns the number of slots. | |
| unsigned | count () const |
| Returns number of objects stored. | |
| bool | exists (hash_t key) const |
| Returns true if key is in set. | |
| void | add (hash_t key) |
| Adds a key. | |
| void | clear () |
| Clears the table. | |
| void | operator= (const HashSet &other) |
| Copys other's data, overwriting everything in this table. | |
Private Member Functions | |
| void | CopyFrom (const HashSet &other) |
Private Attributes | |
| unsigned | m_bits |
| See bits(). | |
| unsigned | m_size |
| See size(). | |
| unsigned | m_mask |
| Equal to size() - 1. | |
| unsigned | m_count |
| See count(). | |
| boost::scoped_array< int > | m_used |
| Index into m_allocated at which data for this slot is located; index is equal to EMPTY_SLOT if unused. | |
| boost::scoped_array< Data > | m_allocated |
| Allocated space for entries in the table. | |
| std::vector< int > | m_changelog |
| History of slots that have been filled. | |
Static Private Attributes | |
| static const int | EMPTY_SLOT = -1 |
HashSet with 2^n slots.
Deletes and dynamic resizing are not supported. Not thread-safe. Performs simple linear probing on hash collisions.
Uses a changelog for quick clears O(n) in number of added entries.
Definition at line 26 of file HashSet.hpp.
| HashSet::HashSet | ( | unsigned | bits | ) | [inline] |
Constructs a hashset with 2^bits slots.
Definition at line 105 of file HashSet.hpp.
References EMPTY_SLOT, m_changelog, m_size, and m_used.
| HashSet::HashSet | ( | const HashSet & | other | ) | [inline] |
Copy constructor.
Definition at line 119 of file HashSet.hpp.
References CopyFrom(), m_changelog, and m_size.
| HashSet::~HashSet | ( | ) | [inline] |
Destructor.
Definition at line 132 of file HashSet.hpp.
| void HashSet::add | ( | hash_t | key | ) | [inline] |
Adds a key.
WILL ABORT IF TABLE IS FULL!
Issues a warning if table becomes 1/4th full.
Make sure the table is much larger (at least 4x larger) than the maximum amount of data you ever expect to store in this table. This is to reduce the number of probes on subsequent get() calls, as well as to avoid the need for dynamic resizing of the table.
Definition at line 173 of file HashSet.hpp.
References EMPTY_SLOT, hash_t, m_allocated, m_changelog, m_count, m_mask, m_size, and m_used.
| unsigned HashSet::bits | ( | ) | const [inline] |
Returns the lg2 of the number of slots.
Definition at line 136 of file HashSet.hpp.
References m_bits.
| void HashSet::clear | ( | ) | [inline] |
Clears the table.
Definition at line 201 of file HashSet.hpp.
References EMPTY_SLOT, m_changelog, m_count, and m_used.
| void HashSet::CopyFrom | ( | const HashSet & | other | ) | [inline, private] |
Definition at line 209 of file HashSet.hpp.
References m_allocated, m_changelog, m_count, m_size, and m_used.
Referenced by HashSet(), and operator=().
| unsigned HashSet::count | ( | ) | const [inline] |
| bool HashSet::exists | ( | hash_t | key | ) | const [inline] |
Returns true if key is in set.
Performs linear probing to find key.
Definition at line 152 of file HashSet.hpp.
References EMPTY_SLOT, hash_t, m_allocated, m_mask, m_size, and m_used.
| void HashSet::operator= | ( | const HashSet & | other | ) | [inline] |
Copys other's data, overwriting everything in this table.
Definition at line 221 of file HashSet.hpp.
References CopyFrom().
| unsigned HashSet::size | ( | ) | const [inline] |
const int HashSet::EMPTY_SLOT = -1 [static, private] |
boost::scoped_array<Data> HashSet::m_allocated [private] |
Allocated space for entries in the table.
Definition at line 97 of file HashSet.hpp.
Referenced by add(), CopyFrom(), and exists().
unsigned HashSet::m_bits [private] |
std::vector<int> HashSet::m_changelog [private] |
History of slots that have been filled.
Definition at line 100 of file HashSet.hpp.
Referenced by add(), clear(), CopyFrom(), and HashSet().
unsigned HashSet::m_count [private] |
See count().
Definition at line 89 of file HashSet.hpp.
Referenced by add(), clear(), CopyFrom(), and count().
unsigned HashSet::m_mask [private] |
unsigned HashSet::m_size [private] |
See size().
Definition at line 83 of file HashSet.hpp.
Referenced by add(), CopyFrom(), exists(), HashSet(), and size().
boost::scoped_array<int> HashSet::m_used [private] |
Index into m_allocated at which data for this slot is located; index is equal to EMPTY_SLOT if unused.
Definition at line 94 of file HashSet.hpp.
Referenced by add(), clear(), CopyFrom(), exists(), and HashSet().