1 /*
2 * Copyright (c) 2007-2009 Marko Kreen, Skype Technologies OÜ
3 *
4 * Permission to use, copy, modify, and/or distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
7 *
8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15 */
16
17 /** @file
18 *
19 * AA-Tree - Binary tree with embeddable nodes.
20 *
21 * AA-Tree (Arne Andersson tree) is a simplified Red-Black tree.
22 */
23
24 #ifndef _USUAL_AATREE_H_
25 #define _USUAL_AATREE_H_
26
27 #include <usual/base.h>
28
29 struct AATree;
30 struct AANode;
31
32 /** Callback for node comparision against value */
33 typedef int (*aatree_cmp_f)(uintptr_t, struct AANode *node);
34
35 /** Callback for walking the tree */
36 typedef void (*aatree_walker_f)(struct AANode *n, void *arg);
37
38 /**
39 * Tree header, for storing helper functions.
40 */
41 struct AATree {
42 struct AANode *root;
43 int count;
44 aatree_cmp_f node_cmp;
45 aatree_walker_f release_cb;
46 };
47
48 /**
49 * Tree node. Embeddable, parent structure should be taken
50 * with container_of().
51 *
52 * Techinally, the full level is not needed and 2-lowest
53 * bits of either ->left or ->right would be enough
54 * to keep track of structure. Currently this is not
55 * done to keep code simple.
56 */
57 struct AANode {
58 struct AANode *left; /**< smaller values */
59 struct AANode *right; /**< larger values */
60 int level; /**< number of black nodes to leaf */
61 };
62
63 /**
64 * Walk order types.
65 */
66 enum AATreeWalkType {
67 AA_WALK_IN_ORDER = 0, /* left->self->right */
68 AA_WALK_PRE_ORDER = 1, /* self->left->right */
69 AA_WALK_POST_ORDER = 2, /* left->right->self */
70 };
71
72 /** Initialize structure */
73 void aatree_init(struct AATree *tree, aatree_cmp_f cmpfn, aatree_walker_f release_cb);
74
75 /** Search for node */
76 struct AANode *aatree_search(struct AATree *tree, uintptr_t value);
77
78 /** Insert new node */
79 void aatree_insert(struct AATree *tree, uintptr_t value, struct AANode *node);
80
81 /** Remote node */
82 void aatree_remove(struct AATree *tree, uintptr_t value);
83
84 /** Walk over all nodes */
85 void aatree_walk(struct AATree *tree, enum AATreeWalkType wtype, aatree_walker_f walker, void *arg);
86
87 /** Free */
88 void aatree_destroy(struct AATree *tree);
89
90 /** Check if terminal node. */
aatree_is_nil_node(const struct AANode * node)91 static inline int aatree_is_nil_node(const struct AANode *node)
92 {
93 return (node->left == node);
94 }
95
96 #endif
97