 |
Open Graph Drawing Framework |
v. 2022.02 (Dogwood)
|
|
|
Go to the documentation of this file.
58 explicit HashElementBase(
size_t hashValue) : m_next(nullptr), m_hashValue(hashValue) { }
97 void resize(
int newTableSize);
112 int size()
const {
return m_count; }
115 int empty()
const {
return m_count==0; }
123 return *(m_table + (hashValue & m_hashMask));
165 void init(
int tableSize);
179 template<
class K,
class I>
221 size_t hash(
const K &key)
const {
return size_t(key); }
227 size_t hash(
const void * &key)
const {
return size_t(key && 0xffffffff); }
233 size_t hash(
const double &key)
const {
235 return (
size_t)((double)std::numeric_limits<size_t>::max() * frexp(key,&dummy));
242 size_t hash(
const string &key)
const;
263 template<
class K,
class I,
class H = DefHashFunc<K> >
274 explicit Hashing(
int minTableSize = 256,
const H &hashFunc = H())
299 for (; pElement; pElement = pElement->
next())
300 if (pElement->
key() == key)
return pElement;
319 pElement->
info() = info;
433 template<
class K,
class I,
class H = DefHashFunc<K> >
434 class HashConstIterator {
485 template<
class K,
class I,
class H>
489 pElement = firstElement(&pList);
The namespace for all OGDF objects.
HashConstIterator< K, I, H > begin() const
Returns an hash iterator to the first element in the list of all elements.
friend bool operator!=(const HashConstIterator< K, I, H > &it1, const HashConstIterator< K, I, H > &it2)
Inequality operator.
int empty() const
Returns if the hash table is empty.
H m_hashFunc
The hash function.
HashElementBase * firstListElement(size_t hashValue) const
Returns the first element in the list for elements with hash value hashValue.
void del(HashElementBase *pElement)
Removes the element pElement from the hash table.
HashElement< K, I > * next() const
Returns the successor element in the list.
Hashing(int minTableSize=256, const H &hashFunc=H())
Creates a hash table for given initial table size minTableSize.
Hashing< K, I, H > & operator=(const Hashing< K, I, H > &hashing)=default
Assignment operator.
int m_tableSizeHigh
The maximal number of elements at this table size.
size_t m_hashValue
The hash value.
Hashing with chaining and table doubling.
HashConstIterator(HashElement< K, I > *pElement, HashElement< K, I > **pList, const Hashing< K, I, H > *pHashing)
Creates a hash iterator pointing to element pElement in list pList of hash table pHashing.
HashElementBase * next() const
Returns the successor to this element in the list.
HashElement< K, I > * insertByNeed(const K &key, const I &info)
Inserts a new element with key key and information info into the hash table.
HashElementBase * firstElement(HashElementBase ***pList) const
Returns the first element in the list of all elements in the hash table.
virtual HashElementBase * copy(HashElementBase *pElement) const override
Returns a copy of hash element pElement.
I m_info
The information value.
HashElement< K, I > * fastInsert(const K &key, const I &info)
Inserts a new element with key key and information info into the hash table.
friend bool operator==(const HashConstIterator< K, I, H > &it1, const HashConstIterator< K, I, H > &it2)
Equality operator.
int size() const
Returns the number of elements in the hash table.
int m_count
The current number of elements.
virtual void destroy(HashElementBase *pElement) override
Deletes hash element pElement.
void insert(HashElementBase *pElement)
Inserts a new element pElement into the hash table.
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
HashElement< K, I > * firstElement(HashElement< K, I > ***pList) const
Returns the first element in the list of all elements in the hash table.
size_t hash(const K &key) const
Returns the hash value of key.
HashConstIterator()
Creates a hash iterator pointing to no element.
HashElement< K, I > * lookup(const K &key) const
Returns the hash element with key key in the hash table; returns nullptr if no such element exists.
size_t hash(const double &key) const
static void copy(const T &from, T &to)
int m_minTableSize
The minimal table size.
int m_hashMask
The current table size minus one.
bool valid() const
Returns true if the hash iterator points to an element.
int m_tableSizeLow
The minimal number of elements at this table size.
const K & key() const
Returns the key value.
void clear()
Removes all elements from the hash table.
size_t hash(const void *&key) const
int size() const
Returns the number of elements in the hash table.
void destroyAll()
Deletes all elements in hash table (but does not free m_table!).
int m_tableSize
The current table size.
void del(const K &key)
Removes the element with key key from the hash table (does nothing if no such element).
const K & key() const
Returns the key of the hash element pointed to.
bool member(const K &key) const
Returns true iff the hash table contains an element with key key.
HashElement< K, I > ** m_pList
The list containg the hash element.
Iterators for hash tables.
bool empty() const
Returns true iff the table is empty, i.e., contains no elements.
HashElementBase * m_next
The successor in the list.
HashConstIterator(const HashConstIterator< K, I, H > &it)
Copy constructor.
HashElement< K, I > * insert(const K &key, const I &info)
Inserts a new element with key key and information info into the hash table.
HashElement< K, I > * m_pElement
The hash element to which the iterator points.
const I & info() const
Returns the information of the hash element pointed to.
const Hashing< K, I, H > * m_pHashing
The associated hash table.
HashElementBase ** m_table
The hash table (an array of lists).
Basic declarations, included by all source files.
HashElement(size_t hashValue, const K &key, const I &info)
Creates a hash element with given hash value, key, and information.
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
HashElement< K, I > * nextElement(HashElement< K, I > ***pList, HashElement< K, I > *pElement) const
Returns the successor of pElement in the list of all elements in the hash table.
size_t hashValue() const
Returns the hash value of this element.
void clear()
Removes all elements from the hash table.
Representation of elements in a hash table.
const I & info() const
Returns the information value.
HashConstIterator & operator=(const HashConstIterator< K, I, H > &it)
Assignment operator.
Base class for elements within a hash table.
HashElementBase * nextElement(HashElementBase ***pList, HashElementBase *pElement) const
Returns the successor of pElement in the list of all elements in the hash table.
Base class for hashing with chaining and table doubling.
HashConstIterator< K, I, H > & operator++()
Moves this hash iterator to the next element (iterator gets invalid if no more elements).
Declaration of memory manager for allocating small pieces of memory.
HashElementBase(size_t hashValue)
Creates a hash element with hash value hashValue.
I & info()
Returns a refeence to the information value.