]>
Commit | Line | Data |
---|---|---|
951f3164 JE |
1 | Motivation |
2 | ========== | |
3 | ||
4 | Treaps provide a memory-efficient binary search tree structure. | |
5 | Insertion/deletion/search are about as about as fast in the average | |
6 | case as red-black trees and the chances of worst-case behavior are | |
7 | vanishingly small, thanks to (pseudo-)randomness. The bad worst-case | |
8 | behavior is a small price to pay, given that treaps are much simpler | |
9 | to implement. | |
10 | ||
11 | API | |
12 | === | |
13 | ||
14 | The trp API generates a data structure and functions to handle a | |
15 | large growing set of objects stored in a pool. | |
16 | ||
17 | The caller: | |
18 | ||
19 | . Specifies parameters for the generated functions with the | |
20 | trp_gen(static, foo_, ...) macro. | |
21 | ||
22 | . Allocates a `struct trp_root` variable and sets it to {~0}. | |
23 | ||
97a5e345 JN |
24 | . Adds new nodes to the set using `foo_insert`. Any pointers |
25 | to existing nodes cannot be relied upon any more, so the caller | |
26 | might retrieve them anew with `foo_pointer`. | |
951f3164 JE |
27 | |
28 | . Can find a specific item in the set using `foo_search`. | |
29 | ||
30 | . Can iterate over items in the set using `foo_first` and `foo_next`. | |
31 | ||
32 | . Can remove an item from the set using `foo_remove`. | |
33 | ||
34 | Example: | |
35 | ||
36 | ---- | |
37 | struct ex_node { | |
38 | const char *s; | |
39 | struct trp_node ex_link; | |
40 | }; | |
41 | static struct trp_root ex_base = {~0}; | |
42 | obj_pool_gen(ex, struct ex_node, 4096); | |
43 | trp_gen(static, ex_, struct ex_node, ex_link, ex, strcmp) | |
44 | struct ex_node *item; | |
45 | ||
46 | item = ex_pointer(ex_alloc(1)); | |
47 | item->s = "hello"; | |
48 | ex_insert(&ex_base, item); | |
49 | item = ex_pointer(ex_alloc(1)); | |
50 | item->s = "goodbye"; | |
51 | ex_insert(&ex_base, item); | |
52 | for (item = ex_first(&ex_base); item; item = ex_next(&ex_base, item)) | |
53 | printf("%s\n", item->s); | |
54 | ---- | |
55 | ||
56 | Functions | |
57 | --------- | |
58 | ||
59 | trp_gen(attr, foo_, node_type, link_field, pool, cmp):: | |
60 | ||
61 | Generate a type-specific treap implementation. | |
62 | + | |
63 | . The storage class for generated functions will be 'attr' (e.g., `static`). | |
64 | . Generated function names are prefixed with 'foo_' (e.g., `treap_`). | |
65 | . Treap nodes will be of type 'node_type' (e.g., `struct treap_node`). | |
66 | This type must be a struct with at least one `struct trp_node` field | |
67 | to point to its children. | |
68 | . The field used to access child nodes will be 'link_field'. | |
69 | . All treap nodes must lie in the 'pool' object pool. | |
70 | . Treap nodes must be totally ordered by the 'cmp' relation, with the | |
71 | following prototype: | |
72 | + | |
73 | int (*cmp)(node_type \*a, node_type \*b) | |
74 | + | |
75 | and returning a value less than, equal to, or greater than zero | |
76 | according to the result of comparison. | |
77 | ||
97a5e345 | 78 | node_type {asterisk}foo_insert(struct trp_root *treap, node_type \*node):: |
951f3164 JE |
79 | |
80 | Insert node into treap. If inserted multiple times, | |
81 | a node will appear in the treap multiple times. | |
97a5e345 JN |
82 | + |
83 | The return value is the address of the node within the treap, | |
84 | which might differ from `node` if `pool_alloc` had to call | |
85 | `realloc` to expand the pool. | |
951f3164 JE |
86 | |
87 | void foo_remove(struct trp_root *treap, node_type \*node):: | |
88 | ||
89 | Remove node from treap. Caller must ensure node is | |
90 | present in treap before using this function. | |
91 | ||
92 | node_type *foo_search(struct trp_root \*treap, node_type \*key):: | |
93 | ||
94 | Search for a node that matches key. If no match is found, | |
95 | result is NULL. | |
96 | ||
97 | node_type *foo_nsearch(struct trp_root \*treap, node_type \*key):: | |
98 | ||
99 | Like `foo_search`, but if if the key is missing return what | |
100 | would be key's successor, were key in treap (NULL if no | |
101 | successor). | |
102 | ||
103 | node_type *foo_first(struct trp_root \*treap):: | |
104 | ||
105 | Find the first item from the treap, in sorted order. | |
106 | ||
107 | node_type *foo_next(struct trp_root \*treap, node_type \*node):: | |
108 | ||
109 | Find the next item. |