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
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;
248 Data copy(size, NULL);
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;
302 const _HashFcn&
hash,
const _EqualKey&
equal) :
323 if (
this != &other) {
344 Data tmp(data.size());
348 for (
size_type i = 0; i < data.size(); ++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;
390 BucketNode* head =
d_data[i];
391 while (head != NULL) {
392 BucketNode* next = head->d_next;
436 for (BucketNode* node =
d_data[index]; node != NULL; node = node->d_next) {
438 return std::make_pair(
end(),
false);
459 for (BucketNode* node =
d_data[index]; node != NULL; node = node->d_next) {
461 return node->d_value;
468 return d_data[index]->d_value;
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;
583 while (
d_data[index] == NULL) {
599 while (
d_data[index] == NULL) {
667 if (
this != &other) {
699 "hash operator++ 2");
731 return !(*
this == other);
780 if (
this != &other) {
843 return !(*
this == other);
value_type * operator->() const
hash_table(size_type initial_capacity, const _HashFcn &hash, const _EqualKey &equal)
Data structure of expressions in CVC3.
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)