Implements Splaytree.
| Splaytree impl | Implements Splaytree. |
| Copyright | This program is free software. |
| Files | |
| C-kern/ | Header file of Splaytree. |
| C-kern/ | Implementation file of Splaytree impl. |
| splaytree_t | |
| helper | |
| KEYCOMPARE | Casts node to type typeadapt_object_t and calls callcmpkeyobj_typeadapt. |
| OBJCOMPARE | Casts node to type typeadapt_object_t and calls callcmpobj_typeadapt. |
| test | |
| invariant_splaytree | Checks that nodes of left subtree are smaller and nodes in right subtree are higher than root node. |
| lifetime | |
| change | |
| recursivesplay_splaytree | Searches for a node X with key ‘key’ and makes it the new root of the tree. |
| splaykey_splaytree | Searches for a node X with key ‘key’ and makes it the new root of the tree. |
| splaynode_splaytree | Same as splaykey_splaytree except node is used as key. |
| search | |
| iterate | |
| test |
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.
| helper | |
| KEYCOMPARE | Casts node to type typeadapt_object_t and calls callcmpkeyobj_typeadapt. |
| OBJCOMPARE | Casts node to type typeadapt_object_t and calls callcmpobj_typeadapt. |
| test | |
| invariant_splaytree | Checks that nodes of left subtree are smaller and nodes in right subtree are higher than root node. |
| lifetime | |
| change | |
| recursivesplay_splaytree | Searches for a node X with key ‘key’ and makes it the new root of the tree. |
| splaykey_splaytree | Searches for a node X with key ‘key’ and makes it the new root of the tree. |
| splaynode_splaytree | Same as splaykey_splaytree except node is used as key. |
| search | |
| iterate | |
| test |
#define KEYCOMPARE( key, node ) callcmpkeyobj_typeadapt(typeadp, key, memberasobject_typeadaptnodeoffset(nodeoffset, node))
Casts node to type typeadapt_object_t and calls callcmpkeyobj_typeadapt. This macro expects variable name tree to point to splaytree_t.
#define OBJCOMPARE( keyobject, node ) callcmpobj_typeadapt(typeadp, keyobject, memberasobject_typeadaptnodeoffset(nodeoffset, node))
Casts node to type typeadapt_object_t and calls callcmpobj_typeadapt. This macro expects variable name tree to point to splaytree_t.
static splaytree_node_t * recursivesplay_splaytree( splaytree_t * tree, splaytree_node_t * root, const void * key, uint16_t nodeoffset, typeadapt_t * typeadp )
Searches for a node X with key ‘key’ and makes it the new root of the tree. If the node is not in the tree the last node (with no left or right child) is used instead. The rotations done to move X to the top are called ‘splaying’. See http://en.wikipedia.org/wiki/Splay_tree for a description of splay trees.
This is a straight forward recursive implementation and it used only for test purposes.
static int splaykey_splaytree( splaytree_t * tree, const void * key, uint16_t nodeoffset, typeadapt_t * typeadp )
Searches for a node X with key ‘key’ and makes it the new root of the tree. If the node is not in the tree the last node (with no left or right child) is used instead. The rotations done to move X to the top are called ‘splaying’. See http://en.wikipedia.org/wiki/Splay_tree for a description of splay trees.
| This version splays from top to down without recursion | it is the production version. The result is compared with recursivesplay_splaytree. |
static int splaynode_splaytree( splaytree_t * tree, const splaytree_node_t * keynode, /*out*/int * rootcmp, uint16_t nodeoffset, typeadapt_t * typeadp )
Same as splaykey_splaytree except node is used as key.
Casts node to type typeadapt_object_t and calls callcmpkeyobj_typeadapt.
#define KEYCOMPARE( key, node ) callcmpkeyobj_typeadapt(typeadp, key, memberasobject_typeadaptnodeoffset(nodeoffset, node))
Declares abstract object type.
typedef struct typeadapt_object_t typeadapt_object_t
Implements typeadapt_t.callcmpkeyobj_typeadapt.
#define callcmpkeyobj_typeadapt( typeadp, ... ) callcmpkeyobj_typeadaptcomparator(&(typeadp)->comparator, typeadp, __VA_ARGS__)
Casts node to type typeadapt_object_t and calls callcmpobj_typeadapt.
#define OBJCOMPARE( keyobject, node ) callcmpobj_typeadapt(typeadp, keyobject, memberasobject_typeadaptnodeoffset(nodeoffset, node))
Implements typeadapt_t.callcmpobj_typeadapt.
#define callcmpobj_typeadapt( typeadp, ... ) callcmpobj_typeadaptcomparator(&(typeadp)->comparator, typeadp, __VA_ARGS__)
Checks that nodes of left subtree are smaller and nodes in right subtree are higher than root node.
int invariant_splaytree( splaytree_t * tree, uint16_t nodeoffset, typeadapt_t * typeadp )
Searches for a node X with key ‘key’ and makes it the new root of the tree.
static splaytree_node_t * recursivesplay_splaytree( splaytree_t * tree, splaytree_node_t * root, const void * key, uint16_t nodeoffset, typeadapt_t * typeadp )
Searches for a node X with key ‘key’ and makes it the new root of the tree.
static int splaykey_splaytree( splaytree_t * tree, const void * key, uint16_t nodeoffset, typeadapt_t * typeadp )
Same as splaykey_splaytree except node is used as key.
static int splaynode_splaytree( splaytree_t * tree, const splaytree_node_t * keynode, /*out*/int * rootcmp, uint16_t nodeoffset, typeadapt_t * typeadp )