50 #ifndef _cvc3__hash__hash_table_h_
51 #define _cvc3__hash__hash_table_h_
62 #ifdef _CVC3_DEBUG_MODE
63 #define DebugAssert(cond, str) if(!(cond)) \
64 CVC3::debugError(__FILE__, __LINE__, #cond, str)
66 extern CVC_DLL void debugError(
const std::string& file,
int line,
67 const std::string& cond,
const std::string& msg);
70 #define DebugAssert(cond, str)
83 53ul, 97ul, 193ul, 389ul, 769ul,
84 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
85 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
86 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
87 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
88 1610612741ul, 3221225473ul, 4294967291ul
94 const size_type* last = prime_list + (
size_type)num_primes;
95 const size_type* pos = std::lower_bound(first, last, n);
96 return pos == last ? *(last - 1) : *pos;
119 template <
class _Key,
class _Value,
120 class _HashFcn,
class _EqualKey,
class _ExtractKey>
150 typedef std::vector<Bucket*>
Data;
194 size_type
hash(
const key_type& key)
const {
199 bool equal(
const key_type& key1,
const key_type& key2)
const {
214 return (
hash(key) % d_data.size());
226 DebugAssert(index < d_data.size(),
"hash_table::getBucketByIndex");
227 return d_data.at(index);
231 DebugAssert(index < d_data.size(),
"hash_table::getBucketByIndex (const)");
232 return d_data.at(index);
248 Data copy(size, NULL);
251 for (size_type i = 0; i < d_data.size(); ++i) {
253 BucketNode* bucket = d_data[i];
254 while (bucket != NULL) {
256 BucketNode* current = bucket;
257 bucket = bucket->d_next;
261 BucketNode* new_bucket = copy[new_index];
262 current->d_next = new_bucket;
263 copy[new_index] = current;
278 d_hash(_HashFcn()), d_equal(_EqualKey()), d_extractKey(_ExtractKey()),
279 d_size(0), d_data(16)
286 d_hash(_HashFcn()), d_equal(_EqualKey()), d_extractKey(_ExtractKey()),
287 d_size(0), d_data(initial_capacity)
294 d_hash(hash), d_equal(_EqualKey()), d_extractKey(_ExtractKey()),
295 d_size(0), d_data(initial_capacity)
302 const _HashFcn&
hash,
const _EqualKey&
equal) :
303 d_hash(hash), d_equal(equal), d_extractKey(_ExtractKey()),
304 d_size(0), d_data(initial_capacity)
311 d_hash(other.d_hash), d_equal(other.d_equal), d_extractKey(other.d_extractKey),
312 d_size(other.d_size), d_data(0)
323 if (
this != &other) {
344 Data tmp(data.size());
348 for (size_type i = 0; i < data.size(); ++i) {
350 DebugAssert(i < d_data.size(),
"hash_table::operator=");
353 Bucket* source = data[i];
354 if (source != NULL) {
356 Bucket* target =
new BucketNode(NULL, source->d_value);
358 source = source->d_next;
361 while (source != NULL) {
362 target->d_next =
new BucketNode(NULL, source->d_value);
363 target = target->d_next;
364 source = source->d_next;
371 std::swap(d_hash, other.
d_hash);
372 std::swap(d_equal, other.
d_equal);
374 std::swap(d_size, other.
d_size);
375 d_data.swap(other.
d_data);
380 for (size_type i = 0; i < d_data.size(); ++i) {
389 for (size_type i = 0; i < d_data.size(); ++i) {
390 BucketNode* head = d_data[i];
391 while (head != NULL) {
392 BucketNode* next = head->d_next;
428 std::pair<iterator, bool>
insert(
const value_type& value) {
436 for (BucketNode* node = d_data[index]; node != NULL; node = node->d_next) {
438 return std::make_pair(
end(),
false);
444 d_data[index] =
new BucketNode(d_data[index], value);
445 return std::make_pair(
iterator(
this, d_data[index]),
true);
459 for (BucketNode* node = d_data[index]; node != NULL; node = node->d_next) {
461 return node->d_value;
467 d_data[index] =
new BucketNode(d_data[index], value);
468 return d_data[index]->d_value;
475 size_type
erase(
const key_type& key) {
479 BucketNode* prev = NULL;
480 for (BucketNode* node = d_data[index]; node != NULL; node = node->d_next) {
486 d_data[index] = node->d_next;
490 prev->d_next = node->d_next;
512 BucketNode* prev = NULL;
513 for (BucketNode* node = d_data[index]; node != NULL; node = node->d_next) {
519 d_data[index] = node->d_next;
523 prev->d_next = node->d_next;
545 size_type
count(
const _Key& key)
const {
556 return (d_size == 0);
566 return d_data.size();
571 return (
float(d_size) /
float(d_data.size()));
583 while (d_data[index] == NULL) {
587 return iterator(
this, d_data[index]);
599 while (d_data[index] == NULL) {
650 : d_hash_table(hash_table), d_node(node)
657 : d_hash_table(NULL), d_node(NULL)
662 : d_hash_table(other.d_hash_table), d_node(other.d_node)
667 if (
this != &other) {
687 while (d_node == NULL) {
692 if (index == d_hash_table->
d_data.size()) {
695 *
this = d_hash_table->
end();
699 "hash operator++ 2");
726 return (d_node == other.
d_node);
731 return !(*
this == other);
758 : d_hash_table(hash_table), d_node(node)
765 : d_hash_table(NULL), d_node(NULL)
770 : d_hash_table(other.d_hash_table), d_node(other.d_node)
775 : d_hash_table(other.d_hash_table), d_node(other.d_node)
780 if (
this != &other) {
800 while (d_node == NULL) {
805 if (index == d_hash_table->
d_data.size()) {
808 *
this = d_hash_table->
end();
811 DebugAssert(index < d_hash_table->d_data.size(),
"");
838 return (d_node == other.
d_node);
843 return !(*
this == other);
value_type * operator->() const
hash_table(size_type initial_capacity, const _HashFcn &hash, const _EqualKey &equal)
value_type & operator*() const
iterator(const iterator &other)
hash_table(size_type initial_capacity, const _HashFcn &hash)
void swap(hash_table &other)
const_iterator find(const key_type &key) const
iterator & operator=(const iterator &other)
const value_type * operator->() const
bool operator!=(const iterator &other) const
const Bucket * getBucketByKey(const key_type &key) const
iterator begin()
iterators
static const size_type prime_list[num_primes]
const_iterator end() const
bool operator!=(const const_iterator &other) const
float load_factor() const
BucketNode(BucketNode *next, const value_type &value)
#define DebugAssert(cond, str)
const BucketNode * d_node
size_type hash(const key_type &key) const
methods
hash_table * d_hash_table
variables
const_iterator begin() const
const_iterator operator++(int)
const key_type & extractKey(const value_type &value) const
void assignTable(const Data &data)
const_iterator(hash_table const *hash_table, const BucketNode *node)
methods
Abstraction over different operating systems.
const_iterator(const iterator &other)
size_type count(const _Key &key) const
bool equal(const key_type &key1, const key_type &key2) const
const size_type num_primes
primes for increasing the hash table size
bool operator==(const const_iterator &other) const
iterator find(const key_type &key)
operations
bool operator==(const iterator &other) const
const_iterator erase(const const_iterator &iter)
size_type getBucketIndex(const key_type &key) const
bucket retrieval
const hash_table * d_hash_table
variables
hash_table(size_type initial_capacity)
size_type bucket_count() const
hash_table(const hash_table &other)
Data::const_iterator data_const_iter
size_type next_prime(size_type n)
value_type & find_or_insert(const value_type &value)
iterator(hash_table *hash_table, BucketNode *node)
methods
const_iterator & operator=(const const_iterator &other)
friend class const_iterator
hash_table & operator=(const hash_table &other)
std::vector< Bucket * > Data
bool contains(const key_type &key) const
status
Bucket * getBucketByKey(const key_type &key)
const value_type & operator*() const
Hash::size_type size_type
types
const_iterator(const const_iterator &other)
std::pair< iterator, bool > insert(const value_type &value)
size_type erase(const key_type &key)
const Bucket * getBucketByIndex(const size_type index) const
const_iterator & operator++()
Bucket * getBucketByIndex(const size_type index)