Offers a container which organizes stored nodes as a hash table.
| 1. | include “C-kern/api/ds/typeadapt.h” before including this file. |
| Extendible-Hashing | Offers a container which organizes stored nodes as a hash table. |
| Copyright | This program is free software. |
| Files | |
| C-kern/ | Header file Extendible-Hashing. |
| C-kern/ | Implementation file Extendible-Hashing impl. |
| Types | |
| struct exthash_t | Export exthash_t into global namespace. |
| struct exthash_iterator_t | Export exthash_iterator_t into global namespace. |
| struct exthash_node_t | Rename lrptree_node_t into exthash_node_t. |
| Functions | |
| test | |
| unittest_ds_inmem_exthash | Test exthash_t functionality. |
| exthash_iterator_t | Iterates over elements contained in exthash_t. |
| lifetime | |
| exthash_iterator_FREE | Static initializer. |
| initfirst_exthashiterator | Initializes an iterator for exthash_t. |
| free_exthashiterator | Frees an iterator of exthash_t. |
| iterate | |
| next_exthashiterator | Returns next node of htable not sorted in any order. |
| exthash_node_t | |
| lifetime | |
| exthash_node_INIT | Static initializer. |
| exthash_t | Implements a hash table which doubles in size if needed. |
| hashtable | Pointer to table of size pow(2,level). |
| nr_nodes | The number of stored nodes in the hash table. |
| nodeadp | Offers lifetime + keycomparator + gethash services to handle stored nodes. |
| level | Determines the hash table size as pow(2,level). |
| maxlevel | Determines the max size of the hash table. |
| lifetime | |
| exthash_FREE | Static initializer. |
| init_exthash | Allocates a hash table of at least size 1. |
| free_exthash | Calls removenodes_exthash and frees the hash table memory. |
| query | |
| isempty_exthash | Returns true if the table contains no element. |
| nrelements_exthash | Returns the nr of elements stored in the hash table. |
| foreach-support | |
| iteratortype_exthash | Declaration to associate exthash_iterator_t with exthash_t. |
| iteratedtype_exthash | Declaration to associate exthash_node_t with exthash_t. |
| search | |
| find_exthash | Searches for a node with equal key. |
| change | |
| insert_exthash | Inserts a new node into the hash table if it is unique. |
| remove_exthash | Removes a node from the hash table. |
| removenodes_exthash | Removes all nodes from the hash table. |
| generic | |
| exthash_IMPLEMENT | Adapts interface of exthash_t to nodes of type object_t. |
| test | |
| invariant_exthash | Checks that every bucket points to a correct red black tree. |
| inline implementation | |
| Macros | |
| free_exthashiterator | Implements exthash_iterator_t.free_exthashiterator. |
| isempty_exthash | Implements exthash_t.isempty_exthash. |
| nrelements_exthash | Implements exthash_t.nrelements_exthash. |
| exthash_IMPLEMENT | Implements exthash_t.exthash_IMPLEMENT. |
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 the Free Software Foundation; either version 2 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
© 2012 Jörg Seebohn
Header file Extendible-Hashing.
Implementation file Extendible-Hashing impl.
typedef struct exthash_t exthash_t
Export exthash_t into global namespace.
typedef struct exthash_iterator_t exthash_iterator_t
Export exthash_iterator_t into global namespace.
Rename lrptree_node_t into exthash_node_t.
| test | |
| unittest_ds_inmem_exthash | Test exthash_t functionality. |
int unittest_ds_inmem_exthash( void )
Test exthash_t functionality.
struct exthash_iterator_t
Iterates over elements contained in exthash_t. The iterator supports removing or deleting of the current node.
exthash_t htable ;
fill_tree(&htable) ;
foreach (_exthash, &htable, node) {
if (need_to_remove(node)) {
err = remove_exthash(&htable, node)) ;
}
}| lifetime | |
| exthash_iterator_FREE | Static initializer. |
| initfirst_exthashiterator | Initializes an iterator for exthash_t. |
| free_exthashiterator | Frees an iterator of exthash_t. |
| iterate | |
| next_exthashiterator | Returns next node of htable not sorted in any order. |
int initfirst_exthashiterator( /*out*/exthash_iterator_t * iter, exthash_t * htable )
Initializes an iterator for exthash_t.
int free_exthashiterator( exthash_iterator_t * iter )
Frees an iterator of exthash_t.
bool next_exthashiterator( exthash_iterator_t * iter, /*out*/exthash_node_t ** node )
Returns next node of htable not sorted in any order. The first call after initfirst_exthashiterator returns the node with the lowest key. In case no next node exists false is returned and parameter node is not changed.
| lifetime | |
| exthash_node_INIT | Static initializer. |
struct exthash_t
Implements a hash table which doubles in size if needed. The table never shrinks. A hash value is an unsigned integer (32 or 64 bit) which is computed from a key. Its value modulo the hash table size is used as index into the hash table. If the hash values are evenly distributed the access time is O(1). In case all keys hash to the same value the worst case has time O(log n).
Internally nodes are stored in a table which contains only one pointer. The pointer is the root of a tree and all nodes stored in the same bucket are organized in a tree structure. The memory for nodes is allocated by the user of the container.
To reduce the time needed for doubling the hash table the newly created table entries share its content with the old entries. See also Algorithm in Extendible-Hashing impl.
The service delete_object of typeadapt_t.lifetime is used in free_exthash and removenodes_exthash. The service cmp_key_object of typeadapt_t.comparator is used in find_exthash. The service cmp_object of typeadapt_t.comparator is used in invariant_exthash, insert_exthash, and remove_exthash. The service hashobject of typeadapt_t.gethash is used in insert_exthash and remove_exthash. The service hashkey of typeadapt_t.gethash is used in find_exthash.
| hashtable | Pointer to table of size pow(2,level). |
| nr_nodes | The number of stored nodes in the hash table. |
| nodeadp | Offers lifetime + keycomparator + gethash services to handle stored nodes. |
| level | Determines the hash table size as pow(2,level). |
| maxlevel | Determines the max size of the hash table. |
| lifetime | |
| exthash_FREE | Static initializer. |
| init_exthash | Allocates a hash table of at least size 1. |
| free_exthash | Calls removenodes_exthash and frees the hash table memory. |
| query | |
| isempty_exthash | Returns true if the table contains no element. |
| nrelements_exthash | Returns the nr of elements stored in the hash table. |
| foreach-support | |
| iteratortype_exthash | Declaration to associate exthash_iterator_t with exthash_t. |
| iteratedtype_exthash | Declaration to associate exthash_node_t with exthash_t. |
| search | |
| find_exthash | Searches for a node with equal key. |
| change | |
| insert_exthash | Inserts a new node into the hash table if it is unique. |
| remove_exthash | Removes a node from the hash table. |
| removenodes_exthash | Removes all nodes from the hash table. |
| generic | |
| exthash_IMPLEMENT | Adapts interface of exthash_t to nodes of type object_t. |
| test | |
| invariant_exthash | Checks that every bucket points to a correct red black tree. |
exthash_node_t ** hashtable
Pointer to table of size pow(2,level). See also level. The directory contains a pointer to the stored node and no buckets. The nodes are organized as a tree and the hashtable entry points to the root of the tree. If a pointer is set to 0 the tree is empty. If it set to the value (intptr_t)-1 it shares the same tree as the entry of the next smaller level.
#define exthash_FREE { 0, 0, typeadapt_member_FREE, 0, 0}
Static initializer. Makes calling free_exthash safe.
int free_exthash( exthash_t * htable )
Calls removenodes_exthash and frees the hash table memory.
typedef exthash_iterator_t iteratortype_exthash
Declaration to associate exthash_iterator_t with exthash_t.
typedef exthash_node_t * iteratedtype_exthash
Declaration to associate exthash_node_t with exthash_t.
int insert_exthash( exthash_t * htable, exthash_node_t * new_node )
Inserts a new node into the hash table if it is unique. If another node exists with the same key as new_node nothing is inserted and the function returns EEXIST. The caller has to allocate the new node and has to transfer ownership.
int removenodes_exthash( exthash_t * htable )
Removes all nodes from the hash table. For every removed node typeadapt_lifetime_it.delete_object is called.
void exthash_IMPLEMENT( IDNAME _fsuffix, TYPENAME object_t, TYPENAME key_t, IDNAME nodename ) ;
Adapts interface of exthash_t to nodes of type object_t. The generated wrapper functions has the suffix _fsuffix which is provided as first parameter. They are defined as static inline.
| _fsuffix | The suffix name of all generated tree interface functions, e.g. “init##_fsuffix”. |
| object_t | The type of object which can be stored and retrieved from this table. The object must contain a field of type exthash_node_t. |
| key_t | The type of key the objects are sorted by. |
| nodename | The access path of the field exthash_node_t in type object_t. |
#define free_exthashiterator( iter ) ((iter)->next = 0, 0)
Implements exthash_iterator_t.free_exthashiterator.
#define isempty_exthash( htable ) (0 == ((htable)->nr_nodes))
Implements exthash_t.isempty_exthash.
#define nrelements_exthash( htable ) ((htable)->nr_nodes)
Implements exthash_t.nrelements_exthash.
#define exthash_IMPLEMENT( _fsuffix, object_t, key_t, nodename ) typedef exthash_iterator_t iteratortype##_fsuffix ; typedef object_t * iteratedtype##_fsuffix ; static inline int initfirst##_fsuffix##iterator(exthash_iterator_t * iter, exthash_t * htable) __attribute__ ((always_inline)) ; static inline int free##_fsuffix##iterator(exthash_iterator_t * iter) __attribute__ ((always_inline)) ; static inline bool next##_fsuffix##iterator(exthash_iterator_t * iter, object_t ** node) __attribute__ ((always_inline)) ; static inline int init##_fsuffix(/*out*/exthash_t * htable, size_t initial_size, size_t max_size, const typeadapt_member_t * nodeadp) __attribute__ ((always_inline)) ; static inline int free##_fsuffix(exthash_t * htable) __attribute__ ((always_inline)) ; static inline bool isempty##_fsuffix(const exthash_t * htable) __attribute__ ((always_inline)) ; static inline size_t nrelements##_fsuffix(const exthash_t * htable) __attribute__ ((always_inline)) ; static inline int find##_fsuffix(exthash_t * htable, const key_t key, /*out*/object_t ** found_node) __attribute__ ((always_inline)) ; static inline int insert##_fsuffix(exthash_t * htable, object_t * new_node) __attribute__ ((always_inline)) ; static inline int remove##_fsuffix(exthash_t * htable, object_t * node) __attribute__ ((always_inline)) ; static inline int removenodes##_fsuffix(exthash_t * htable) __attribute__ ((always_inline)) ; static inline int invariant##_fsuffix(exthash_t * htable) __attribute__ ((always_inline)) ; static inline exthash_node_t * asnode##_fsuffix(object_t * object) { static_assert(&((object_t*)0)->nodename == (exthash_node_t*)offsetof(object_t, nodename), "correct type") ; return (exthash_node_t *) ((uintptr_t)object + offsetof(object_t, nodename)) ; } static inline object_t * asobject##_fsuffix(exthash_node_t * node) { return (object_t *) ((uintptr_t)node - offsetof(object_t, nodename)) ; } static inline int init##_fsuffix(/*out*/exthash_t * htable, size_t initial_size, size_t max_size, const typeadapt_member_t * nodeadp) { return init_exthash(htable, initial_size, max_size, nodeadp) ; } static inline int free##_fsuffix(exthash_t * htable) { return free_exthash(htable) ; } static inline bool isempty##_fsuffix(const exthash_t * htable) { return isempty_exthash(htable) ; } static inline size_t nrelements##_fsuffix(const exthash_t * htable) { return nrelements_exthash(htable) ; } static inline int find##_fsuffix(exthash_t * htable, const key_t key, /*out*/object_t ** found_node) { int err = find_exthash(htable, (void*)key, (exthash_node_t**)found_node) ; if (err == 0) *found_node = asobject##_fsuffix(*(exthash_node_t**)found_node) ; return err ; } static inline int insert##_fsuffix(exthash_t * htable, object_t * new_node) { return insert_exthash(htable, asnode##_fsuffix(new_node)) ; } static inline int remove##_fsuffix(exthash_t * htable, object_t * node) { int err = remove_exthash(htable, asnode##_fsuffix(node)) ; return err ; } static inline int removenodes##_fsuffix(exthash_t * htable) { return removenodes_exthash(htable) ; } static inline int invariant##_fsuffix(exthash_t * htable) { return invariant_exthash(htable) ; } static inline int initfirst##_fsuffix##iterator(exthash_iterator_t * iter, exthash_t * htable) { return initfirst_exthashiterator(iter, htable) ; } static inline int free##_fsuffix##iterator(exthash_iterator_t * iter) { return free_exthashiterator(iter) ; } static inline bool next##_fsuffix##iterator(exthash_iterator_t * iter, object_t ** node) { bool isNext = next_exthashiterator(iter, (exthash_node_t**)node) ; if (isNext) *node = asobject##_fsuffix(*(exthash_node_t**)node) ; return isNext ; }
Implements exthash_t.exthash_IMPLEMENT.
Export exthash_t into global namespace.
typedef struct exthash_t exthash_t
Implements a hash table which doubles in size if needed.
struct exthash_t
Export exthash_iterator_t into global namespace.
typedef struct exthash_iterator_t exthash_iterator_t
Iterates over elements contained in exthash_t.
struct exthash_iterator_t
Management overhead of objects which wants to be stored in a redblacktree_t.
struct lrptree_node_t
Test exthash_t functionality.
int unittest_ds_inmem_exthash( void )
Static initializer.
#define exthash_iterator_FREE { 0, 0, 0 }
Initializes an iterator for exthash_t.
int initfirst_exthashiterator( /*out*/exthash_iterator_t * iter, exthash_t * htable )
Frees an iterator of exthash_t.
int free_exthashiterator( exthash_iterator_t * iter )
Returns next node of htable not sorted in any order.
bool next_exthashiterator( exthash_iterator_t * iter, /*out*/exthash_node_t ** node )
Static initializer.
#define exthash_node_INIT lrptree_node_INIT
Pointer to table of size pow(2,level).
exthash_node_t ** hashtable
The number of stored nodes in the hash table.
size_t nr_nodes
Offers lifetime + keycomparator + gethash services to handle stored nodes.
typeadapt_member_t nodeadp
Determines the hash table size as pow(2,level).
uint8_t level
Determines the max size of the hash table.
uint8_t maxlevel
Static initializer.
#define exthash_FREE { 0, 0, typeadapt_member_FREE, 0, 0}
Allocates a hash table of at least size 1.
int init_exthash( /*out*/exthash_t * htable, size_t initial_size, size_t max_size, const typeadapt_member_t * nodeadp )
Calls removenodes_exthash and frees the hash table memory.
int free_exthash( exthash_t * htable )
Removes all nodes from the hash table.
int removenodes_exthash( exthash_t * htable )
Returns true if the table contains no element.
bool isempty_exthash( const exthash_t * htable )
Returns the nr of elements stored in the hash table.
size_t nrelements_exthash( const exthash_t * htable )
Declaration to associate exthash_iterator_t with exthash_t.
typedef exthash_iterator_t iteratortype_exthash
Declaration to associate exthash_node_t with exthash_t.
typedef exthash_node_t * iteratedtype_exthash
Searches for a node with equal key.
int find_exthash( exthash_t * htable, const void * key, /*out*/exthash_node_t ** found_node )
Inserts a new node into the hash table if it is unique.
int insert_exthash( exthash_t * htable, exthash_node_t * new_node )
Removes a node from the hash table.
int remove_exthash( exthash_t * htable, exthash_node_t * node )
Adapts interface of exthash_t to nodes of type object_t.
void exthash_IMPLEMENT( IDNAME _fsuffix, TYPENAME object_t, TYPENAME key_t, IDNAME nodename ) ;
Checks that every bucket points to a correct red black tree.
int invariant_exthash( const exthash_t * htable )
Implements exthash_iterator_t.free_exthashiterator.
#define free_exthashiterator( iter ) ((iter)->next = 0, 0)
Implements exthash_t.isempty_exthash.
#define isempty_exthash( htable ) (0 == ((htable)->nr_nodes))
Implements exthash_t.nrelements_exthash.
#define nrelements_exthash( htable ) ((htable)->nr_nodes)
Implements exthash_t.exthash_IMPLEMENT.
#define exthash_IMPLEMENT( _fsuffix, object_t, key_t, nodename ) typedef exthash_iterator_t iteratortype##_fsuffix ; typedef object_t * iteratedtype##_fsuffix ; static inline int initfirst##_fsuffix##iterator(exthash_iterator_t * iter, exthash_t * htable) __attribute__ ((always_inline)) ; static inline int free##_fsuffix##iterator(exthash_iterator_t * iter) __attribute__ ((always_inline)) ; static inline bool next##_fsuffix##iterator(exthash_iterator_t * iter, object_t ** node) __attribute__ ((always_inline)) ; static inline int init##_fsuffix(/*out*/exthash_t * htable, size_t initial_size, size_t max_size, const typeadapt_member_t * nodeadp) __attribute__ ((always_inline)) ; static inline int free##_fsuffix(exthash_t * htable) __attribute__ ((always_inline)) ; static inline bool isempty##_fsuffix(const exthash_t * htable) __attribute__ ((always_inline)) ; static inline size_t nrelements##_fsuffix(const exthash_t * htable) __attribute__ ((always_inline)) ; static inline int find##_fsuffix(exthash_t * htable, const key_t key, /*out*/object_t ** found_node) __attribute__ ((always_inline)) ; static inline int insert##_fsuffix(exthash_t * htable, object_t * new_node) __attribute__ ((always_inline)) ; static inline int remove##_fsuffix(exthash_t * htable, object_t * node) __attribute__ ((always_inline)) ; static inline int removenodes##_fsuffix(exthash_t * htable) __attribute__ ((always_inline)) ; static inline int invariant##_fsuffix(exthash_t * htable) __attribute__ ((always_inline)) ; static inline exthash_node_t * asnode##_fsuffix(object_t * object) { static_assert(&((object_t*)0)->nodename == (exthash_node_t*)offsetof(object_t, nodename), "correct type") ; return (exthash_node_t *) ((uintptr_t)object + offsetof(object_t, nodename)) ; } static inline object_t * asobject##_fsuffix(exthash_node_t * node) { return (object_t *) ((uintptr_t)node - offsetof(object_t, nodename)) ; } static inline int init##_fsuffix(/*out*/exthash_t * htable, size_t initial_size, size_t max_size, const typeadapt_member_t * nodeadp) { return init_exthash(htable, initial_size, max_size, nodeadp) ; } static inline int free##_fsuffix(exthash_t * htable) { return free_exthash(htable) ; } static inline bool isempty##_fsuffix(const exthash_t * htable) { return isempty_exthash(htable) ; } static inline size_t nrelements##_fsuffix(const exthash_t * htable) { return nrelements_exthash(htable) ; } static inline int find##_fsuffix(exthash_t * htable, const key_t key, /*out*/object_t ** found_node) { int err = find_exthash(htable, (void*)key, (exthash_node_t**)found_node) ; if (err == 0) *found_node = asobject##_fsuffix(*(exthash_node_t**)found_node) ; return err ; } static inline int insert##_fsuffix(exthash_t * htable, object_t * new_node) { return insert_exthash(htable, asnode##_fsuffix(new_node)) ; } static inline int remove##_fsuffix(exthash_t * htable, object_t * node) { int err = remove_exthash(htable, asnode##_fsuffix(node)) ; return err ; } static inline int removenodes##_fsuffix(exthash_t * htable) { return removenodes_exthash(htable) ; } static inline int invariant##_fsuffix(exthash_t * htable) { return invariant_exthash(htable) ; } static inline int initfirst##_fsuffix##iterator(exthash_iterator_t * iter, exthash_t * htable) { return initfirst_exthashiterator(iter, htable) ; } static inline int free##_fsuffix##iterator(exthash_iterator_t * iter) { return free_exthashiterator(iter) ; } static inline bool next##_fsuffix##iterator(exthash_iterator_t * iter, object_t ** node) { bool isNext = next_exthashiterator(iter, (exthash_node_t**)node) ; if (isNext) *node = asobject##_fsuffix(*(exthash_node_t**)node) ; return isNext ; }
Interface to adapt the lifetime of an object type.
typeadapt_lifetime_it lifetime
Interface to adapt comparison of key and object.
typeadapt_comparator_it comparator
Interface to adapt reading of a hash value.
typeadapt_gethash_it gethash
Function frees memory and associated resources of object.
int ( * delete_object ) (struct typeadapt_t * typeadp, struct typeadapt_object_t ** object)