tdb2: copy tdb1's changed expansion logic.
[ccan] / ccan / avl / avl.h
1 /*
2  * Copyright (C) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
3  * 
4  * Permission is hereby granted, free of charge, to any person obtaining a copy
5  * of this software and associated documentation files (the "Software"), to deal
6  * in the Software without restriction, including without limitation the rights
7  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8  * copies of the Software, and to permit persons to whom the Software is
9  * furnished to do so, subject to the following conditions:
10  * 
11  * The above copyright notice and this permission notice shall be included in
12  * all copies or substantial portions of the Software.
13  * 
14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20  * THE SOFTWARE.
21  */
22
23 #ifndef CCAN_AVL_H
24 #define CCAN_AVL_H
25
26 #include <stdbool.h>
27 #include <stddef.h>
28
29 typedef struct AVL           AVL;
30 typedef struct AvlNode       AvlNode;
31 typedef struct AvlIter       AvlIter;
32
33 typedef int (*AvlCompare)(const void *, const void *);
34
35 AVL *avl_new(AvlCompare compare);
36         /* Create a new AVL tree sorted with the given comparison function. */
37
38 void avl_free(AVL *avl);
39         /* Free an AVL tree. */
40
41 void *avl_lookup(const AVL *avl, const void *key);
42         /* O(log n). Lookup a value at a key.  Return NULL if the key is not present. */
43
44 #define avl_member(avl, key) (!!avl_lookup_node(avl, key))
45         /* O(log n). See if a key is present. */
46
47 size_t avl_count(const AVL *avl);
48         /* O(1). Return the number of elements in the tree. */
49
50 bool avl_insert(AVL *avl, const void *key, const void *value);
51         /*
52          * O(log n). Insert a key/value pair, or replace it if already present.
53          *
54          * Return false if the insertion replaced an existing key/value.
55          */
56
57 bool avl_remove(AVL *avl, const void *key);
58         /*
59          * O(log n). Remove a key/value pair (if present).
60          *
61          * Return true if it was removed.
62          */
63
64 bool avl_check_invariants(AVL *avl);
65         /* For testing purposes.  This function will always return true :-) */
66
67
68 /************************* Traversal *************************/
69
70 #define avl_foreach(iter, avl)         avl_traverse(iter, avl, FORWARD)
71         /*
72          * O(n). Traverse an AVL tree in order.
73          *
74          * Example:
75          *
76          * AvlIter i;
77          *
78          * avl_foreach(i, avl)
79          *     printf("%s -> %s\n", i.key, i.value);
80          */
81
82 #define avl_foreach_reverse(iter, avl) avl_traverse(iter, avl, BACKWARD)
83         /* O(n). Traverse an AVL tree in reverse order. */
84
85 typedef enum AvlDirection {FORWARD = 0, BACKWARD = 1} AvlDirection;
86
87 struct AvlIter {
88         void         *key;
89         void         *value;
90         AvlNode      *node;
91         
92         /* private */
93         AvlNode      *stack[100];
94         int           stack_index;
95         AvlDirection  direction;
96 };
97
98 void avl_iter_begin(AvlIter *iter, AVL *avl, AvlDirection dir);
99 void avl_iter_next(AvlIter *iter);
100 #define avl_traverse(iter, avl, direction)        \
101         for (avl_iter_begin(&(iter), avl, direction); \
102              (iter).node != NULL;                     \
103              avl_iter_next(&iter))
104
105
106 /***************** Internal data structures ******************/
107
108 struct AVL {
109         AvlCompare  compare;
110         AvlNode    *root;
111         size_t      count;
112 };
113
114 struct AvlNode {
115         const void *key;
116         const void *value;
117         
118         AvlNode    *lr[2];
119         int         balance; /* -1, 0, or 1 */
120 };
121
122 AvlNode *avl_lookup_node(const AVL *avl, const void *key);
123         /* O(log n). Lookup an AVL node by key.  Return NULL if not present. */
124
125 #endif