commit ebb5aef76cc773b22f7e4198e467705d8532c3bd
parent 5f67edad2ec70060fffbc3b6a23f8b7e7abbae38
Author: Remy Noulin <loader2x@gmail.com>
Date: Sun, 30 Dec 2018 16:32:00 +0100
improve documentation
README.md | 23 +++++++-
main.c | 3 ++
wavl.h | 179 +++++++++++++++++++++++++++++++++++++++++++++++++++++---------
3 files changed, 178 insertions(+), 27 deletions(-)
Diffstat:
| M | README.md | | | 23 | +++++++++++++++++++++-- |
| M | main.c | | | 3 | +++ |
| M | wavl.h | | | 179 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----------- |
3 files changed, 178 insertions(+), 27 deletions(-)
diff --git a/README.md b/README.md
@@ -1,2 +1,21 @@
-# tree
-tree data structures
+# Sheepy
+This is a sheepy package for [sheepy](https://github.com/RemyNoulin/sheepy) and using [libsheepy](https://github.com/RemyNoulin/libsheepy)
+
+# Tree data structures
+
+All the trees in this package are type-safe. The types are selected when the tree is defined.
+
+## WAVL Tree
+
+`wavl.h` implements a weak AVL tree, see [wavlTree](https://github.com/RemyNoulin/wavlTree).
+
+The nodes are stored in a vector for better performance.
+
+# Usage
+
+Install with spm: `spm install tree`
+
+Include header file:
+- `#include "shpPackages/tree/tree.h"`
+
+Usage examples are on the top of the headers and in `main.c`.
diff --git a/main.c b/main.c
@@ -23,6 +23,9 @@ void freeKV(u32* /* keyType */ key, u32* /* valueType*/ value) {
wavlFunctions(/* scope */, w /* wt wavl tree type*/, W /* function suffix: initW...*/, u32 /* keyType*/, u32 /* valueType */, -1 /* null key */, -1 /* null value */);
+#undef FREEFUNC
+#undef CMPFUNC
+
int main(int ARGC, char** ARGV) {
argc = ARGC; argv = ARGV;
diff --git a/wavl.h b/wavl.h
@@ -3,11 +3,93 @@
#include "libsheepyObject.h"
/**
+ * \file
*
- * allocating node in dVector is slightly faster (in the order of 10% when the memory is not already map in the process)
+ * WAVL tree
+ *
+ * WAVL tree is type-safe binary search tree with characteristics from the AVL and red black trees.
+ *
+ * The iterator traverses the tree in sorted order (by key and CMPFUNC).
+ *
+ * The maximum number of nodes is 2^32
+ *
+ * The tree nodes are stored in a dVector, since allocating node in dVector is slightly faster
+ * (in the order of 10% when the memory is not already map in the process)
* than the version allocating nodes with malloc. (826ms vs 870ms for 10M elements)
*
- * TODO add leftMost, rightMost pointer in tree
+ * wavlDef defines 2 types for the tree:
+ *
+ * - 'typeName't is the type for the tree itself
+ * - 'typeName'Nodet is the node type in the tree
+ *
+ * The public functions follow the same pattern as the hashtable API in the hashtable sheepy package.
+ *
+ * init, empty, isEmpty, free, add, addOrFind, find, find, get, getKey, del, addOrFindNode, getNode, delNode behave
+ * like the ones for the hashtable.
+ *
+ * There are a few tree specific functions:
+ *
+ * height, iterStart, hasNext, next, prev, delCurrent
+ *
+ * The key and value in the node are accessed with:
+ * node->key
+ * node->value
+ *
+ * Before implementing the functions with wavlFunctions, define CMPFUNC and FREEFUNC
+ *
+ * - CMPFUNC compares 2 keys, prototype: int cmp(keyType k1, keyType k2);
+ * return -1 when k1 < k2, 0 when k1 = k2 and 1 when k1 > k2
+ * - FREEFUNC frees key and value in a node, prototype: void freeKV(keyType *k, valueType *v);
+ *
+ * Redefine dVectorBits to change the size of the segments in dVector and tweak the memory usage and performance
+ *
+ * Example:
+ * // define WAVL tree: u32 key and u32 value
+ * wavlDef(, w, W, u32, u32);
+ *
+ * // declare tree
+ * wt tree;
+ *
+ * // free KV function
+ * void freeKV(u32* key, u32* value) {
+ * }
+ *
+ * // implement WAVL tree functions
+ * #define FREEFUNC freeKV
+ * #define CMPFUNC CMP
+ *
+ * wavlFunctions(, w, W, u32, u32, -1, -1);
+ *
+ * #undef FREEFUNC
+ * #undef CMPFUNC
+ *
+ * // initialize tree
+ * initW(&tree);
+ *
+ * // add key value pair
+ * addW(&tree, 0, 0);
+ *
+ * // get value for key
+ * var n = getW(&tree, 0);
+ * logVarG(n);
+ *
+ * // iterator from the lowest key to the highest key
+ * iterStartW(&tree, getFirstEntryW(&tree));
+ * wNodet *node;
+ * while(node = nextW(&tree)) {
+ * logVarG(node->key);
+ * logVarG(node->value);
+ * }
+ *
+ * // delete a key value pair
+ * delW(&tree, 10);
+ *
+ * // free tree
+ * freeW(&tree);
+ *
+ *
+ *
+ * To traverse the tree and print all key value pairs, implement one of these functions:
*
* void printTree(typeName##Nodet *X) {
* if (!X) return;
@@ -36,25 +118,37 @@
* printf("value %d, rank %d\n", X->value, X->rank);
* inOrderTraversal(X->right);
* }
+ *
+ * TODO add leftMost, rightMost pointer in tree
*/
-// init
-// height
-// empty FREEFUNC
-// isEmpty
-// free
-// add CMPFUNC
-// addOrFind
-// find
-// get
-// g##suffixetKey
-// del
-// addOrFindNode
-// getNode
-// delNode
-
-// iterator
-
+/**
+ * function declarations for tailored WAVL tree
+ *
+ * wavlDef defines:
+ *
+ * - 'typeName't is the type for the tree itself
+ * - 'typeName'Nodet is the node type in the tree
+ * - prototypes
+ *
+ * this macro is placed most of the time in a header file
+ *
+ * the function names are:
+ * function'suffix'
+ *
+ * the scope parameter is the function scope and can be 'empty' for global functions, 'static' for local functions, ...
+ *
+ * RETURN VALUES:
+ * height: tree height or -1 when empty
+ * isEmpty, add, hasNext, delCurrent: true success, false failure
+ * addOrFind, addOrFindNode: value or node pointer
+ * *isnew is set to true when the returned value pointer is in a new node
+ * find, getNode, next, prev: value or node pointer
+ * NULL failure
+ * get, getKey: value or key
+ * nullValueV or nullKeyV failure
+ *
+ */
#define wavlDef(scope, typeName, suffix, keyType, valueType)\
wavlNodeT(typeName##Nodet, keyType, valueType);\
wavlTreeT(typeName##t, typeName##Nodet, keyType, valueType);\
@@ -71,19 +165,32 @@
scope void del##suffix(typeName##t *tree, keyType key);\
scope typeName##Nodet* addOrFindNode##suffix(typeName##t *tree, keyType key, bool *isnew);\
scope typeName##Nodet* getNode##suffix(typeName##t *tree, keyType key);\
- scope typeName##Nodet *getFirstEntry##suffix(typeName##t *tree);\
- scope typeName##Nodet *getLastEntry##suffix(typeName##t *tree);\
+ scope typeName##Nodet* getFirstEntry##suffix(typeName##t *tree);\
+ scope typeName##Nodet* getLastEntry##suffix(typeName##t *tree);\
scope void delNode##suffix(typeName##t *tree, typeName##Nodet *node);\
scope void iterStart##suffix(typeName##t *tree, typeName##Nodet *first);\
scope bool hasNext##suffix(typeName##t *tree);\
- scope typeName##Nodet *next##suffix(typeName##t *tree);\
- scope typeName##Nodet *prev##suffix(typeName##t *tree);\
- scope bool removeCurrent##suffix(typeName##t *tree)
+ scope typeName##Nodet* next##suffix(typeName##t *tree);\
+ scope typeName##Nodet* prev##suffix(typeName##t *tree);\
+ scope bool delCurrent##suffix(typeName##t *tree)
+/**
+ * function implementations
+ *
+ * this macros implements the tree functions
+ *
+ * this macro is placed most of the time in a source file
+ *
+ * the compare function and free function must be implemented before this macro
+ * CMPFUNC and FREEFUNC must be defined before this macro
+ *
+ */
#define wavlFunctions(scope, typeName, suffix, keyType, valueType, nullKeyV, nullValueV)\
+ /* initialize tree */\
scope void init##suffix(typeName##t *tree) {\
wavlInit(tree, nullKeyV, nullValueV);\
}\
+ /* allocate a new node */\
internal typeName##Nodet* newNode##suffix(typeName##t *tree, keyType k, typeName##Nodet *parent) {\
ret wavlNewNode(tree, k, parent);\
}\
@@ -93,6 +200,7 @@
}\
ret (1 + maxV(nodeHeight##suffix(node->left), nodeHeight##suffix(node->right)));\
}\
+ /* tree height */\
scope int height##suffix(typeName##t *tree) {\
ret nodeHeight##suffix(tree->root) - 1;\
}\
@@ -103,6 +211,7 @@
FREEFUNC(&node->key, &node->value);\
dVectorAppend(&tree->freeNodeList, node->index);\
}\
+ /* free all nodes in tree */\
scope void empty##suffix(typeName##t *tree) {\
freeNodes##suffix(tree, tree->root);\
tree->modCount++;\
@@ -110,9 +219,11 @@
tree->root = NULL;\
tree->rotations = 0;\
}\
+ /* true when tree is empty */\
scope bool isEmpty##suffix(typeName##t *tree) {\
ret tree->root == NULL;\
}\
+ /* free all nodes and tree internal buffer, after this the tree is not usable anymore */\
scope void free##suffix(typeName##t *tree) {\
empty##suffix(tree);\
dVectorFree(&tree->treeNodes);\
@@ -127,22 +238,27 @@
}\
ret isnew;\
}\
+ /* insert or find key, when the key is not found a new node is created, return value pointer in node otherwise */\
scope valueType* addOrFind##suffix(typeName##t *tree, keyType key, bool *isnew) {\
var node = addOrFindNode##suffix(tree, key, isnew);\
return &node->value;\
}\
+ /* find key, return value pointer or NULL upon failure */\
scope valueType* find##suffix(typeName##t *tree, keyType key) {\
var node = getNode##suffix(tree, key);\
ret !node ? NULL : &node->value;\
}\
+ /* get value for key, return value or nullValue upon failure */\
scope valueType get##suffix(typeName##t *tree, keyType key) {\
var node = getNode##suffix(tree, key);\
ret !node ? tree->nullValue : node->value;\
}\
+ /* get key in node, return key or nullKey upon failure */\
scope keyType getKey##suffix(typeName##t *tree, keyType key) {\
var node = getNode##suffix(tree, key);\
ret !node ? tree->nullKey : node->key;\
}\
+ /* delete key and value using FREEFUNC */\
scope void del##suffix(typeName##t *tree, keyType key) {\
var node = getNode##suffix(tree, key);\
if (!node) ret;\
@@ -244,6 +360,7 @@
P = node->parent;\
}\
}\
+ /* insert or find key, when the key is not found a new node is created, return node pointer */\
scope typeName##Nodet* addOrFindNode##suffix(typeName##t *tree, keyType key, bool *isnew) {\
var O = tree->root;\
if (!O) {\
@@ -298,6 +415,7 @@
\
ret e;\
}\
+ /* get node pointer for key, return node pointer or NULL upon failure */\
scope typeName##Nodet* getNode##suffix(typeName##t *tree, keyType key) {\
var p = tree->root;\
while (p) {\
@@ -395,6 +513,7 @@
deltaRank = parent->rank - node->rank;\
}\
}\
+ /* get node pointer for lowest key */\
scope typeName##Nodet *getFirstEntry##suffix(typeName##t *tree) {\
typeName##Nodet *P = tree->root;\
if (P) {\
@@ -403,6 +522,7 @@
}\
ret P;\
}\
+ /* get node pointer for highest key */\
scope typeName##Nodet *getLastEntry##suffix(typeName##t *tree) {\
typeName##Nodet *P = tree->root;\
if (P) {\
@@ -449,6 +569,7 @@
ret P;\
}\
}\
+ /* delete node */\
scope void delNode##suffix(typeName##t *tree, typeName##Nodet *node) {\
tree->modCount++;\
tree->count--;\
@@ -515,14 +636,17 @@
balanceAfterDeleteWAVL##suffix(tree, fixPoint, sibling, rk);\
}\
}\
+ /* start iteration */\
scope void iterStart##suffix(typeName##t *tree, typeName##Nodet *first) {\
tree->expectedModCount = tree->modCount;\
tree->lastReturned = NULL;\
tree->next = first;\
}\
+ /* has next node */\
scope bool hasNext##suffix(typeName##t *tree) {\
ret tree->next != NULL;\
}\
+ /* get next node in iteration */\
scope typeName##Nodet *next##suffix(typeName##t *tree) {\
typeName##Nodet *e = tree->next;\
if (!e) ret NULL;\
@@ -531,6 +655,7 @@
tree->lastReturned = e;\
ret e;\
}\
+ /* get previous node in iteration */\
scope typeName##Nodet *prev##suffix(typeName##t *tree) {\
typeName##Nodet *e = tree->next;\
if (!e) ret NULL;\
@@ -539,7 +664,8 @@
tree->lastReturned = e;\
ret e;\
}\
- scope bool removeCurrent##suffix(typeName##t *tree) {\
+ /* delete current node in iteration, it is possible to continue the iteration after this */\
+ scope bool delCurrent##suffix(typeName##t *tree) {\
if (!tree->lastReturned) ret false;\
if (tree->modCount != tree->expectedModCount) ret false;\
/* // deleted entries are replaced by their successors */\
@@ -552,6 +678,9 @@
}
+// Internal macros
+// use the function implementations instead
+
#define wavlNodeT(typeName, keyType, valueType)\
typ struct typeName typeName;\
struct typeName {\
