| 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 | */ |
| 58 | void del234(tree234 *t, void *e); |
| 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 | |
| 69 | #endif /* TREE234_H */ |