c78e8df8c21e67d202dad59dca5e566ff77ce938
[ccan] / ccan / avl / avl.h
1 /*
2  * Copyright (c) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
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 #ifndef CCAN_AVL_H
18 #define CCAN_AVL_H
19
20 #include <stdbool.h>
21 #include <stddef.h>
22
23 typedef struct AVL           AVL;
24 typedef struct AvlNode       AvlNode;
25 typedef struct AvlIter       AvlIter;
26
27 typedef int (*AvlCompare)(const void *, const void *);
28
29 AVL *avl_new(AvlCompare compare);
30         /* Create a new AVL tree sorted with the given comparison function. */
31
32 void avl_free(AVL *avl);
33         /* Free an AVL tree. */
34
35 void *avl_lookup(const AVL *avl, const void *key);
36         /* O(log n). Lookup a value at a key.  Return NULL if the key is not present. */
37
38 #define avl_member(avl, key) (!!avl_lookup_node(avl, key))
39         /* O(log n). See if a key is present. */
40
41 size_t avl_count(const AVL *avl);
42         /* O(1). Return the number of elements in the tree. */
43
44 bool avl_insert(AVL *avl, const void *key, const void *value);
45         /*
46          * O(log n). Insert a key/value pair, or replace it if already present.
47          *
48          * Return false if the insertion replaced an existing key/value.
49          */
50
51 bool avl_remove(AVL *avl, const void *key);
52         /*
53          * O(log n). Remove a key/value pair (if present).
54          *
55          * Return true if it was removed.
56          */
57
58 bool avl_check_invariants(AVL *avl);
59         /* For testing purposes.  This function will always return true :-) */
60
61
62 /************************* Traversal *************************/
63
64 #define avl_foreach(iter, avl)         avl_traverse(iter, avl, FORWARD)
65         /*
66          * O(n). Traverse an AVL tree in order.
67          *
68          * Example:
69          *
70          * AvlIter i;
71          *
72          * avl_foreach(i, avl)
73          *     printf("%s -> %s\n", i.key, i.value);
74          */
75
76 #define avl_foreach_reverse(iter, avl) avl_traverse(iter, avl, BACKWARD)
77         /* O(n). Traverse an AVL tree in reverse order. */
78
79 typedef enum AvlDirection {FORWARD = 0, BACKWARD = 1} AvlDirection;
80
81 struct AvlIter {
82         void         *key;
83         void         *value;
84         AvlNode      *node;
85         
86         /* private */
87         AvlNode      *stack[100];
88         int           stack_index;
89         AvlDirection  direction;
90 };
91
92 void avl_iter_begin(AvlIter *iter, AVL *avl, AvlDirection dir);
93 void avl_iter_next(AvlIter *iter);
94 #define avl_traverse(iter, avl, direction)        \
95         for (avl_iter_begin(&(iter), avl, direction); \
96              (iter).node != NULL;                     \
97              avl_iter_next(&iter))
98
99
100 /***************** Internal data structures ******************/
101
102 struct AVL {
103         AvlCompare  compare;
104         AvlNode    *root;
105         size_t      count;
106 };
107
108 struct AvlNode {
109         const void *key;
110         const void *value;
111         
112         AvlNode    *lr[2];
113         int         balance; /* -1, 0, or 1 */
114 };
115
116 AvlNode *avl_lookup_node(const AVL *avl, const void *key);
117         /* O(log n). Lookup an AVL node by key.  Return NULL if not present. */
118
119 #endif