]>
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 | ||
24 | . Adds new nodes to the set using `foo_insert`. | |
25 | ||
26 | . Can find a specific item in the set using `foo_search`. | |
27 | ||
28 | . Can iterate over items in the set using `foo_first` and `foo_next`. | |
29 | ||
30 | . Can remove an item from the set using `foo_remove`. | |
31 | ||
32 | Example: | |
33 | ||
34 | ---- | |
35 | struct ex_node { | |
36 | const char *s; | |
37 | struct trp_node ex_link; | |
38 | }; | |
39 | static struct trp_root ex_base = {~0}; | |
40 | obj_pool_gen(ex, struct ex_node, 4096); | |
41 | trp_gen(static, ex_, struct ex_node, ex_link, ex, strcmp) | |
42 | struct ex_node *item; | |
43 | ||
44 | item = ex_pointer(ex_alloc(1)); | |
45 | item->s = "hello"; | |
46 | ex_insert(&ex_base, item); | |
47 | item = ex_pointer(ex_alloc(1)); | |
48 | item->s = "goodbye"; | |
49 | ex_insert(&ex_base, item); | |
50 | for (item = ex_first(&ex_base); item; item = ex_next(&ex_base, item)) | |
51 | printf("%s\n", item->s); | |
52 | ---- | |
53 | ||
54 | Functions | |
55 | --------- | |
56 | ||
57 | trp_gen(attr, foo_, node_type, link_field, pool, cmp):: | |
58 | ||
59 | Generate a type-specific treap implementation. | |
60 | + | |
61 | . The storage class for generated functions will be 'attr' (e.g., `static`). | |
62 | . Generated function names are prefixed with 'foo_' (e.g., `treap_`). | |
63 | . Treap nodes will be of type 'node_type' (e.g., `struct treap_node`). | |
64 | This type must be a struct with at least one `struct trp_node` field | |
65 | to point to its children. | |
66 | . The field used to access child nodes will be 'link_field'. | |
67 | . All treap nodes must lie in the 'pool' object pool. | |
68 | . Treap nodes must be totally ordered by the 'cmp' relation, with the | |
69 | following prototype: | |
70 | + | |
71 | int (*cmp)(node_type \*a, node_type \*b) | |
72 | + | |
73 | and returning a value less than, equal to, or greater than zero | |
74 | according to the result of comparison. | |
75 | ||
76 | void foo_insert(struct trp_root *treap, node_type \*node):: | |
77 | ||
78 | Insert node into treap. If inserted multiple times, | |
79 | a node will appear in the treap multiple times. | |
80 | ||
81 | void foo_remove(struct trp_root *treap, node_type \*node):: | |
82 | ||
83 | Remove node from treap. Caller must ensure node is | |
84 | present in treap before using this function. | |
85 | ||
86 | node_type *foo_search(struct trp_root \*treap, node_type \*key):: | |
87 | ||
88 | Search for a node that matches key. If no match is found, | |
89 | result is NULL. | |
90 | ||
91 | node_type *foo_nsearch(struct trp_root \*treap, node_type \*key):: | |
92 | ||
93 | Like `foo_search`, but if if the key is missing return what | |
94 | would be key's successor, were key in treap (NULL if no | |
95 | successor). | |
96 | ||
97 | node_type *foo_first(struct trp_root \*treap):: | |
98 | ||
99 | Find the first item from the treap, in sorted order. | |
100 | ||
101 | node_type *foo_next(struct trp_root \*treap, node_type \*node):: | |
102 | ||
103 | Find the next item. |