Interface to splay tree which allows access to a set of sorted elements in O(log n) amortized time.
See http://en.wikipedia.org/wiki/Splay_tree for a description.
| 1. | include “C-kern/api/ds/typeadapt.h” before including this file. |
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 of Splaytree.
Implementation file of Splaytree impl.
typedef struct splaytree_t splaytree_t
Export splaytree_t into global namespace.
typedef struct splaytree_iterator_t splaytree_iterator_t
Export splaytree_iterator_t.
typedef struct lrtree_node_t splaytree_node_t
Rename lrtree_node_t into splaytree_node_t.
| test | |
| unittest_ds_inmem_splaytree | Tests all functions of splaytree_t. |
int unittest_ds_inmem_splaytree( void )
Tests all functions of splaytree_t.
struct splaytree_iterator_t
Iterates over elements contained in splaytree_t. The iterator supports removing or deleting of the current node.
splaytree_t tree ;
fill_tree(&tree) ;
foreach (_splaytree, &tree, node) {
if (need_to_remove(node)) {
err = remove_splaytree(&tree, node)) ;
}
}| lifetime | |
| splaytree_iterator_FREE | Static initializer. |
| initfirst_splaytreeiterator | Initializes an iterator for splaytree_t. |
| initlast_splaytreeiterator | Initializes an iterator of splaytree_t. |
| free_splaytreeiterator | Frees an iterator of splaytree_t. |
| iterate | |
| next_splaytreeiterator | Returns next node of tree in ascending order. |
| prev_splaytreeiterator | Returns next node of tree in descending order. |
int initfirst_splaytreeiterator( /*out*/splaytree_iterator_t * iter, splaytree_t * tree, uint16_t nodeoffset, typeadapt_t * typeadp )
Initializes an iterator for splaytree_t.
int initlast_splaytreeiterator( /*out*/splaytree_iterator_t * iter, splaytree_t * tree, uint16_t nodeoffset, typeadapt_t * typeadp )
Initializes an iterator of splaytree_t.
int free_splaytreeiterator( splaytree_iterator_t * iter )
Frees an iterator of splaytree_t.
bool next_splaytreeiterator( splaytree_iterator_t * iter, /*out*/splaytree_node_t ** node )
Returns next node of tree in ascending order. The first call after initfirst_splaytreeiterator returns the node with the lowest key. In case no next node exists false is returned and parameter node is not changed.
bool prev_splaytreeiterator( splaytree_iterator_t * iter, /*out*/splaytree_node_t ** node )
Returns next node of tree in descending order. The first call after initlast_splaytreeiterator returns the node with the highest key. In case no previous node exists false is returned and parameter node is not changed.
struct splaytree_t
Implements a splay tree index. The structure contains a root pointer. No other information is maintained.
The service typeadapt_lifetime_it.delete_object of typeadapt_t.lifetime is used in free_splaytree and removenodes_splaytree. The service typeadapt_comparator_it.cmp_key_object of typeadapt_t.comparator is used in find_splaytree and remove_splaytree. The service typeadapt_comparator_it.cmp_object of typeadapt_t.comparator is used in invariant_splaytree.
| root | Points to the root object which has no parent. |
| lifetime | |
| splaytree_FREE | Static initializer: After assigning you can call free_splaytree without harm. |
| splaytree_INIT | Static initializer. |
| init_splaytree | Inits an empty tree object. |
| free_splaytree | Frees all resources. |
| query | |
| getinistate_splaytree | Returns the current state of splaytree_t for later use in splaytree_INIT. |
| isempty_splaytree | Returns true if tree contains no elements. |
| foreach-support | |
| iteratortype_splaytree | Declaration to associate splaytree_iterator_t with splaytree_t. |
| iteratedtype_splaytree | Declaration to associate splaytree_node_t with splaytree_t. |
| search | |
| find_splaytree | Searches for a node with equal key. |
| change | |
| insert_splaytree | Inserts a new node into the tree only if it is unique. |
| remove_splaytree | Removes a node from the tree. |
| removenodes_splaytree | Removes all nodes from the tree. |
| test | |
| invariant_splaytree | Checks that all nodes are stored in correct search order. |
| generic | |
| genericcast_splaytree | Casts tree into <slaytree_t> if that is possible. |
| splaytree_IMPLEMENT | Generates interface of splaytree_t storing elements of type object_t. |
#define splaytree_FREE splaytree_INIT( )
Static initializer: After assigning you can call free_splaytree without harm.
#define splaytree_INIT( root ) { root }
Static initializer. You can use splaytree_INIT with the returned values prvided by getinistate_splaytree.
int free_splaytree( splaytree_t * tree, uint16_t nodeoffset, typeadapt_t * typeadp )
Frees all resources. For every removed node the typeadapter callback typeadapt_lifetime_it.delete_object is called. See typeadapt_t how to construct a typeadapter.
static inline void getinistate_splaytree( const splaytree_t * tree, /*out*/splaytree_node_t ** root )
Returns the current state of splaytree_t for later use in splaytree_INIT.
typedef splaytree_iterator_t iteratortype_splaytree
Declaration to associate splaytree_iterator_t with splaytree_t.
typedef splaytree_node_t * iteratedtype_splaytree
Declaration to associate splaytree_node_t with splaytree_t.
int insert_splaytree( splaytree_t * tree, splaytree_node_t * new_node, uint16_t nodeoffset, typeadapt_t * typeadp )
Inserts a new node into the tree only if it is unique. If another node exists with the same key as new_key nothing is inserted and the function returns EEXIST. If no other node is found new_node is inserted The caller has to allocate the new node and has to transfer ownership.
int removenodes_splaytree( splaytree_t * tree, uint16_t nodeoffset, typeadapt_t * typeadp )
Removes all nodes from the tree. For every removed node typeadapt_lifetime_it.delete_object is called.
splaytree_t * genericcast_splaytree( void * tree )
Casts tree into <slaytree_t> if that is possible. The generic object tree must have a root pointer to splaytree_node_t.
void splaytree_IMPLEMENT( IDNAME _fsuffix, TYPENAME object_t, TYPENAME key_t, IDNAME nodename ) ;
Generates interface of splaytree_t storing elements of type object_t.
| _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 tree. The object must contain a field of type splaytree_node_t. |
| key_t | The type of key the objects are sorted by. |
| nodename | The access path of the field splaytree_node_t in type object_t. |
#define free_splaytreeiterator( iter ) ((iter)->next = 0, 0)
Implements splaytree_iterator_t.free_splaytreeiterator as NOP.
#define genericcast_splaytree( tree ) ( __extension__ ({ static_assert(offsetof(splaytree_t, root) == 0, "first member") ; static_assert((typeof((tree)->root))0 == (splaytree_node_t*)0, "ensure same type") ; (splaytree_t*) &(tree)->root ; }))
Implements splaytree_t.genericcast_splaytree.
static inline void getinistate_splaytree( const splaytree_t * tree, /*out*/splaytree_node_t ** root )
Implements splaytree_t.getinistate_splaytree.
#define init_splaytree( tree ) ((void)(*(tree) = (splaytree_t) splaytree_INIT(0)))
Implements splaytree_t.init_splaytree.
#define isempty_splaytree( tree ) (0 == (tree)->root)
Implements splaytree_t.isempty_splaytree.
#define splaytree_IMPLEMENT( _fsuffix, object_t, key_t, nodename ) typedef splaytree_iterator_t iteratortype##_fsuffix ; typedef object_t * iteratedtype##_fsuffix ; static inline int initfirst##_fsuffix##iterator(splaytree_iterator_t * iter, splaytree_t * tree, typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline int initlast##_fsuffix##iterator(splaytree_iterator_t * iter, splaytree_t * tree, typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline int free##_fsuffix##iterator(splaytree_iterator_t * iter) __attribute__ ((always_inline)) ; static inline bool next##_fsuffix##iterator(splaytree_iterator_t * iter, object_t ** node) __attribute__ ((always_inline)) ; static inline bool prev##_fsuffix##iterator(splaytree_iterator_t * iter, object_t ** node) __attribute__ ((always_inline)) ; static inline void init##_fsuffix(/*out*/splaytree_t * tree) __attribute__ ((always_inline)) ; static inline int free##_fsuffix(splaytree_t * tree, typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline void getinistate##_fsuffix(const splaytree_t * tree, /*out*/object_t ** root) __attribute__ ((always_inline)) ; static inline bool isempty##_fsuffix(const splaytree_t * tree) __attribute__ ((always_inline)) ; static inline int find##_fsuffix(splaytree_t * tree, const key_t key, /*out*/object_t ** found_node, typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline int insert##_fsuffix(splaytree_t * tree, object_t * new_node, typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline int remove##_fsuffix(splaytree_t * tree, object_t * node, typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline int removenodes##_fsuffix(splaytree_t * tree, typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline int invariant##_fsuffix(splaytree_t * tree, typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline splaytree_node_t * asnode##_fsuffix(object_t * object) { static_assert(&((object_t*)0)->nodename == (splaytree_node_t*)offsetof(object_t, nodename), "correct type") ; return (splaytree_node_t *) ((uintptr_t)object + offsetof(object_t, nodename)) ; } static inline object_t * asobject##_fsuffix(splaytree_node_t * node) { return (object_t *) ((uintptr_t)node - offsetof(object_t, nodename)) ; } static inline object_t * asobjectnull##_fsuffix(splaytree_node_t * node) { return node ? (object_t *) ((uintptr_t)node - offsetof(object_t, nodename)) : 0 ; } static inline void init##_fsuffix(/*out*/splaytree_t * tree) { init_splaytree(tree) ; } static inline int free##_fsuffix(splaytree_t * tree, typeadapt_t * typeadp) { return free_splaytree(tree, offsetof(object_t, nodename), typeadp) ; } static inline void getinistate##_fsuffix(const splaytree_t * tree, /*out*/object_t ** root) { splaytree_node_t * rootnode ; getinistate_splaytree(tree, &rootnode) ; *root = asobjectnull##_fsuffix(rootnode) ; } static inline bool isempty##_fsuffix(const splaytree_t * tree) { return isempty_splaytree(tree) ; } static inline int find##_fsuffix(splaytree_t * tree, const key_t key, /*out*/object_t ** found_node, typeadapt_t * typeadp) { int err = find_splaytree(tree, (void*)key, (splaytree_node_t**)found_node, offsetof(object_t, nodename), typeadp) ; if (err == 0) *found_node = asobject##_fsuffix(*(splaytree_node_t**)found_node) ; return err ; } static inline int insert##_fsuffix(splaytree_t * tree, object_t * new_node, typeadapt_t * typeadp) { return insert_splaytree(tree, asnode##_fsuffix(new_node), offsetof(object_t, nodename), typeadp) ; } static inline int remove##_fsuffix(splaytree_t * tree, object_t * node, typeadapt_t * typeadp) { int err = remove_splaytree(tree, asnode##_fsuffix(node), offsetof(object_t, nodename), typeadp) ; return err ; } static inline int removenodes##_fsuffix(splaytree_t * tree, typeadapt_t * typeadp) { return removenodes_splaytree(tree, offsetof(object_t, nodename), typeadp) ; } static inline int invariant##_fsuffix(splaytree_t * tree, typeadapt_t * typeadp) { return invariant_splaytree(tree, offsetof(object_t, nodename), typeadp) ; } static inline int initfirst##_fsuffix##iterator(splaytree_iterator_t * iter, splaytree_t * tree, typeadapt_t * typeadp) { return initfirst_splaytreeiterator(iter, tree, offsetof(object_t, nodename), typeadp) ; } static inline int initlast##_fsuffix##iterator(splaytree_iterator_t * iter, splaytree_t * tree, typeadapt_t * typeadp) { return initlast_splaytreeiterator(iter, tree, offsetof(object_t, nodename), typeadp) ; } static inline int free##_fsuffix##iterator(splaytree_iterator_t * iter) { return free_splaytreeiterator(iter) ; } static inline bool next##_fsuffix##iterator(splaytree_iterator_t * iter, object_t ** node) { bool isNext = next_splaytreeiterator(iter, (splaytree_node_t**)node) ; if (isNext) *node = asobject##_fsuffix(*(splaytree_node_t**)node) ; return isNext ; } static inline bool prev##_fsuffix##iterator(splaytree_iterator_t * iter, object_t ** node) { bool isNext = prev_splaytreeiterator(iter, (splaytree_node_t**)node) ; if (isNext) *node = asobject##_fsuffix(*(splaytree_node_t**)node) ; return isNext ; }
Implements splaytree_t.splaytree_IMPLEMENT.
Export splaytree_t into global namespace.
typedef struct splaytree_t splaytree_t
Implements a splay tree index.
struct splaytree_t
Export splaytree_iterator_t.
typedef struct splaytree_iterator_t splaytree_iterator_t
Iterates over elements contained in splaytree_t.
struct splaytree_iterator_t
Rename lrtree_node_t into splaytree_node_t.
typedef struct lrtree_node_t splaytree_node_t
Management overhead of objects which wants to be stored in a splaytree_t.
struct lrtree_node_t
Tests all functions of splaytree_t.
int unittest_ds_inmem_splaytree( void )
Static initializer.
#define splaytree_iterator_FREE { 0, 0, 0, 0 }
Initializes an iterator for splaytree_t.
int initfirst_splaytreeiterator( /*out*/splaytree_iterator_t * iter, splaytree_t * tree, uint16_t nodeoffset, typeadapt_t * typeadp )
Initializes an iterator of splaytree_t.
int initlast_splaytreeiterator( /*out*/splaytree_iterator_t * iter, splaytree_t * tree, uint16_t nodeoffset, typeadapt_t * typeadp )
Frees an iterator of splaytree_t.
int free_splaytreeiterator( splaytree_iterator_t * iter )
Returns next node of tree in ascending order.
bool next_splaytreeiterator( splaytree_iterator_t * iter, /*out*/splaytree_node_t ** node )
Returns next node of tree in descending order.
bool prev_splaytreeiterator( splaytree_iterator_t * iter, /*out*/splaytree_node_t ** node )
Points to the root object which has no parent.
splaytree_node_t * root
Static initializer: After assigning you can call free_splaytree without harm.
#define splaytree_FREE splaytree_INIT( )
Frees all resources.
int free_splaytree( splaytree_t * tree, uint16_t nodeoffset, typeadapt_t * typeadp )
Static initializer.
#define splaytree_INIT( root ) { root }
Inits an empty tree object.
void init_splaytree( /*out*/splaytree_t * tree )
Returns the current state of splaytree_t for later use in splaytree_INIT.
static inline void getinistate_splaytree( const splaytree_t * tree, /*out*/splaytree_node_t ** root )
Returns true if tree contains no elements.
bool isempty_splaytree( const splaytree_t * tree )
Declaration to associate splaytree_iterator_t with splaytree_t.
typedef splaytree_iterator_t iteratortype_splaytree
Declaration to associate splaytree_node_t with splaytree_t.
typedef splaytree_node_t * iteratedtype_splaytree
Searches for a node with equal key.
int find_splaytree( splaytree_t * tree, const void * key, /*out*/splaytree_node_t ** found_node, uint16_t nodeoffset, typeadapt_t * typeadp )
Inserts a new node into the tree only if it is unique.
int insert_splaytree( splaytree_t * tree, splaytree_node_t * new_node, uint16_t nodeoffset, typeadapt_t * typeadp )
Removes a node from the tree.
int remove_splaytree( splaytree_t * tree, splaytree_node_t * node, uint16_t nodeoffset, typeadapt_t * typeadp )
Removes all nodes from the tree.
int removenodes_splaytree( splaytree_t * tree, uint16_t nodeoffset, typeadapt_t * typeadp )
Checks that all nodes are stored in correct search order.
int invariant_splaytree( splaytree_t * tree, uint16_t nodeoffset, typeadapt_t * typeadp )
Casts tree into slaytree_t if that is possible.
splaytree_t * genericcast_splaytree( void * tree )
Generates interface of splaytree_t storing elements of type object_t.
void splaytree_IMPLEMENT( IDNAME _fsuffix, TYPENAME object_t, TYPENAME key_t, IDNAME nodename ) ;
Implements splaytree_iterator_t.free_splaytreeiterator as NOP.
#define free_splaytreeiterator( iter ) ((iter)->next = 0, 0)
Implements splaytree_t.genericcast_splaytree.
#define genericcast_splaytree( tree ) ( __extension__ ({ static_assert(offsetof(splaytree_t, root) == 0, "first member") ; static_assert((typeof((tree)->root))0 == (splaytree_node_t*)0, "ensure same type") ; (splaytree_t*) &(tree)->root ; }))
Implements splaytree_t.getinistate_splaytree.
static inline void getinistate_splaytree( const splaytree_t * tree, /*out*/splaytree_node_t ** root )
Implements splaytree_t.init_splaytree.
#define init_splaytree( tree ) ((void)(*(tree) = (splaytree_t) splaytree_INIT(0)))
Implements splaytree_t.isempty_splaytree.
#define isempty_splaytree( tree ) (0 == (tree)->root)
Implements splaytree_t.splaytree_IMPLEMENT.
#define splaytree_IMPLEMENT( _fsuffix, object_t, key_t, nodename ) typedef splaytree_iterator_t iteratortype##_fsuffix ; typedef object_t * iteratedtype##_fsuffix ; static inline int initfirst##_fsuffix##iterator(splaytree_iterator_t * iter, splaytree_t * tree, typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline int initlast##_fsuffix##iterator(splaytree_iterator_t * iter, splaytree_t * tree, typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline int free##_fsuffix##iterator(splaytree_iterator_t * iter) __attribute__ ((always_inline)) ; static inline bool next##_fsuffix##iterator(splaytree_iterator_t * iter, object_t ** node) __attribute__ ((always_inline)) ; static inline bool prev##_fsuffix##iterator(splaytree_iterator_t * iter, object_t ** node) __attribute__ ((always_inline)) ; static inline void init##_fsuffix(/*out*/splaytree_t * tree) __attribute__ ((always_inline)) ; static inline int free##_fsuffix(splaytree_t * tree, typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline void getinistate##_fsuffix(const splaytree_t * tree, /*out*/object_t ** root) __attribute__ ((always_inline)) ; static inline bool isempty##_fsuffix(const splaytree_t * tree) __attribute__ ((always_inline)) ; static inline int find##_fsuffix(splaytree_t * tree, const key_t key, /*out*/object_t ** found_node, typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline int insert##_fsuffix(splaytree_t * tree, object_t * new_node, typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline int remove##_fsuffix(splaytree_t * tree, object_t * node, typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline int removenodes##_fsuffix(splaytree_t * tree, typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline int invariant##_fsuffix(splaytree_t * tree, typeadapt_t * typeadp) __attribute__ ((always_inline)) ; static inline splaytree_node_t * asnode##_fsuffix(object_t * object) { static_assert(&((object_t*)0)->nodename == (splaytree_node_t*)offsetof(object_t, nodename), "correct type") ; return (splaytree_node_t *) ((uintptr_t)object + offsetof(object_t, nodename)) ; } static inline object_t * asobject##_fsuffix(splaytree_node_t * node) { return (object_t *) ((uintptr_t)node - offsetof(object_t, nodename)) ; } static inline object_t * asobjectnull##_fsuffix(splaytree_node_t * node) { return node ? (object_t *) ((uintptr_t)node - offsetof(object_t, nodename)) : 0 ; } static inline void init##_fsuffix(/*out*/splaytree_t * tree) { init_splaytree(tree) ; } static inline int free##_fsuffix(splaytree_t * tree, typeadapt_t * typeadp) { return free_splaytree(tree, offsetof(object_t, nodename), typeadp) ; } static inline void getinistate##_fsuffix(const splaytree_t * tree, /*out*/object_t ** root) { splaytree_node_t * rootnode ; getinistate_splaytree(tree, &rootnode) ; *root = asobjectnull##_fsuffix(rootnode) ; } static inline bool isempty##_fsuffix(const splaytree_t * tree) { return isempty_splaytree(tree) ; } static inline int find##_fsuffix(splaytree_t * tree, const key_t key, /*out*/object_t ** found_node, typeadapt_t * typeadp) { int err = find_splaytree(tree, (void*)key, (splaytree_node_t**)found_node, offsetof(object_t, nodename), typeadp) ; if (err == 0) *found_node = asobject##_fsuffix(*(splaytree_node_t**)found_node) ; return err ; } static inline int insert##_fsuffix(splaytree_t * tree, object_t * new_node, typeadapt_t * typeadp) { return insert_splaytree(tree, asnode##_fsuffix(new_node), offsetof(object_t, nodename), typeadp) ; } static inline int remove##_fsuffix(splaytree_t * tree, object_t * node, typeadapt_t * typeadp) { int err = remove_splaytree(tree, asnode##_fsuffix(node), offsetof(object_t, nodename), typeadp) ; return err ; } static inline int removenodes##_fsuffix(splaytree_t * tree, typeadapt_t * typeadp) { return removenodes_splaytree(tree, offsetof(object_t, nodename), typeadp) ; } static inline int invariant##_fsuffix(splaytree_t * tree, typeadapt_t * typeadp) { return invariant_splaytree(tree, offsetof(object_t, nodename), typeadp) ; } static inline int initfirst##_fsuffix##iterator(splaytree_iterator_t * iter, splaytree_t * tree, typeadapt_t * typeadp) { return initfirst_splaytreeiterator(iter, tree, offsetof(object_t, nodename), typeadp) ; } static inline int initlast##_fsuffix##iterator(splaytree_iterator_t * iter, splaytree_t * tree, typeadapt_t * typeadp) { return initlast_splaytreeiterator(iter, tree, offsetof(object_t, nodename), typeadp) ; } static inline int free##_fsuffix##iterator(splaytree_iterator_t * iter) { return free_splaytreeiterator(iter) ; } static inline bool next##_fsuffix##iterator(splaytree_iterator_t * iter, object_t ** node) { bool isNext = next_splaytreeiterator(iter, (splaytree_node_t**)node) ; if (isNext) *node = asobject##_fsuffix(*(splaytree_node_t**)node) ; return isNext ; } static inline bool prev##_fsuffix##iterator(splaytree_iterator_t * iter, object_t ** node) { bool isNext = prev_splaytreeiterator(iter, (splaytree_node_t**)node) ; if (isNext) *node = asobject##_fsuffix(*(splaytree_node_t**)node) ; return isNext ; }
Function frees memory and associated resources of object.
int ( * delete_object ) (struct typeadapt_t * typeadp, struct typeadapt_object_t ** object)
Interface to adapt the lifetime of an object type.
typeadapt_lifetime_it lifetime
Compares key with an object.
int ( * cmp_key_object ) (struct typeadapt_t * typeadp, const void * lkey, const struct typeadapt_object_t * robject)
Interface to adapt comparison of key and object.
typeadapt_comparator_it comparator
Compares two objects.
int ( * cmp_object ) (struct typeadapt_t * typeadp, const struct typeadapt_object_t * lobject, const struct typeadapt_object_t * robject)