From fbc37e7db420382d57964d7f8ba422373f50d9b3 Mon Sep 17 00:00:00 2001 From: Warren Dukes Date: Thu, 24 Feb 2005 02:41:06 +0000 Subject: add 2-3 tree header file git-svn-id: https://svn.musicpd.org/mpd/trunk@2982 09075e82-0dd4-0310-85a5-a0d7c8717e4f --- src/tree.h | 51 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 51 insertions(+) create mode 100644 src/tree.h (limited to 'src') diff --git a/src/tree.h b/src/tree.h new file mode 100644 index 000000000..deb420bc8 --- /dev/null +++ b/src/tree.h @@ -0,0 +1,51 @@ +#ifndef TREE_H +#define TREE_H + +typedef struct _TreeNode { + void * data[2]; + struct _TreeNode * children[3]; + struct _TreeNode * parent; +} TreeNode; + +typedef struct _Tree { + TreeNode headNode; + TreeFreeDataFunc * freeFunc; + TreeCompareDataFunc * compareFunc; +} Tree; + +typedef enum _TreeIteratorType { + PREORDER, + INORDER, + POSTORDER +} TreeIteratorType; + +typedef struct _TreeIterator { + Data * data; + /* private data */ + TreeIteratorType type; + TreeNode * currentNode; + int pos; +} TreeIterator; + +typedef int TreeCompareDataFunc(void * left, void * right); + +typedef int TreeFreeDataFunc(void * data); + +Tree * newTree(TreeFreeDataFunc * freeFunc, TreeCompareDataFunc * compareFunc); + +void freeTree(Tree * tree); + +int insertInTree(Tree * tree, void * data); + +int deleteFromTree(Tree * tree, void * needle); + +void * findInTree(Tree * tree, void * needle); + +TreeIterator * newTreeIterator(Tree * tree, TreeIteratorType type); + +/* will return the same pointer passed in on success + * if NULL is returned, this indicates the end of tree + */ +TreeIterator * nextTreeIterator(TreeIterator * iter); + +#endif // TREE_H -- cgit v1.2.3