31a61d21 |
1 | /* |
2 | * tree234.h: header defining functions in tree234.c. |
3 | */ |
4 | |
5 | #ifndef TREE234_H |
6 | #define TREE234_H |
7 | |
8 | /* |
9 | * These typedefs are notionally opaque outside tree234.c itself. |
10 | */ |
11 | typedef struct node234_Tag node234; |
12 | typedef struct tree234_Tag tree234; |
13 | typedef struct enum234_Tag enum234; |
14 | |
15 | /* |
16 | * enum234 must be declared here because client code needs to be |
17 | * able to create automatic instances of it. This declaration does |
18 | * not constitute licence to use its internals outside tree234.c. |
19 | * The contents of this structure may change without notice. YOU |
20 | * HAVE BEEN WARNED. |
21 | */ |
22 | struct enum234_Tag { |
23 | node234 *node; |
24 | int posn; |
25 | }; |
26 | |
27 | typedef int (*cmpfn234)(void *, void *); |
28 | |
29 | /* |
30 | * Create a 2-3-4 tree. |
31 | */ |
32 | tree234 *newtree234(cmpfn234 cmp); |
33 | |
34 | /* |
35 | * Free a 2-3-4 tree (not including freeing the elements). |
36 | */ |
37 | void freetree234(tree234 *t); |
38 | |
39 | /* |
40 | * Add an element e to a 2-3-4 tree t. Returns e on success, or if |
41 | * an existing element compares equal, returns that. |
42 | */ |
43 | void *add234(tree234 *t, void *e); |
44 | |
45 | /* |
46 | * Find an element e in a 2-3-4 tree t. Returns NULL if not found. |
47 | * e is always passed as the first argument to cmp, so cmp can be |
48 | * an asymmetric function if desired. cmp can also be passed as |
49 | * NULL, in which case the compare function from the tree proper |
50 | * will be used. |
51 | */ |
52 | void *find234(tree234 *t, void *e, cmpfn234 cmp); |
53 | |
54 | /* |
55 | * Delete an element e in a 2-3-4 tree. Does not free the element, |
56 | * merely removes all links to it from the tree nodes. |
57 | */ |
88dff7c0 |
58 | void del234(tree234 *t, void *e); |
31a61d21 |
59 | |
60 | /* |
61 | * Iterate over the elements of a tree234, in order. |
62 | * |
63 | * enum234 e; |
64 | * for (p = first234(tree, &e); p; p = next234(&e)) consume(p); |
65 | */ |
66 | void *first234(tree234 *t, enum234 *e); |
67 | void *next234(enum234 *e); |
68 | |
3d5c1aa6 |
69 | #endif /* TREE234_H */ |