]>
Commit | Line | Data |
---|---|---|
951f3164 JE |
1 | /* |
2 | * test-treap.c: code to exercise the svn importer's treap structure | |
3 | */ | |
4 | ||
5 | #include "cache.h" | |
6 | #include "vcs-svn/obj_pool.h" | |
7 | #include "vcs-svn/trp.h" | |
8 | ||
9 | struct int_node { | |
10 | uintmax_t n; | |
11 | struct trp_node children; | |
12 | }; | |
13 | ||
14 | obj_pool_gen(node, struct int_node, 3) | |
15 | ||
16 | static int node_cmp(struct int_node *a, struct int_node *b) | |
17 | { | |
18 | return (a->n > b->n) - (a->n < b->n); | |
19 | } | |
20 | ||
21 | trp_gen(static, treap_, struct int_node, children, node, node_cmp) | |
22 | ||
23 | static void strtonode(struct int_node *item, const char *s) | |
24 | { | |
25 | char *end; | |
26 | item->n = strtoumax(s, &end, 10); | |
27 | if (*s == '\0' || (*end != '\n' && *end != '\0')) | |
28 | die("invalid integer: %s", s); | |
29 | } | |
30 | ||
31 | int main(int argc, char *argv[]) | |
32 | { | |
33 | struct strbuf sb = STRBUF_INIT; | |
34 | struct trp_root root = { ~0 }; | |
35 | uint32_t item; | |
36 | ||
37 | if (argc != 1) | |
38 | usage("test-treap < ints"); | |
39 | ||
40 | while (strbuf_getline(&sb, stdin, '\n') != EOF) { | |
97a5e345 JN |
41 | struct int_node *node = node_pointer(node_alloc(1)); |
42 | ||
43 | item = node_offset(node); | |
44 | strtonode(node, sb.buf); | |
45 | node = treap_insert(&root, node_pointer(item)); | |
46 | if (node_offset(node) != item) | |
47 | die("inserted %"PRIu32" in place of %"PRIu32"", | |
48 | node_offset(node), item); | |
951f3164 JE |
49 | } |
50 | ||
51 | item = node_offset(treap_first(&root)); | |
52 | while (~item) { | |
53 | uint32_t next; | |
54 | struct int_node *tmp = node_pointer(node_alloc(1)); | |
55 | ||
56 | tmp->n = node_pointer(item)->n; | |
57 | next = node_offset(treap_next(&root, node_pointer(item))); | |
58 | ||
59 | treap_remove(&root, node_pointer(item)); | |
60 | item = node_offset(treap_nsearch(&root, tmp)); | |
61 | ||
62 | if (item != next && (!~item || node_pointer(item)->n != tmp->n)) | |
63 | die("found %"PRIuMAX" in place of %"PRIuMAX"", | |
64 | ~item ? node_pointer(item)->n : ~(uintmax_t) 0, | |
65 | ~next ? node_pointer(next)->n : ~(uintmax_t) 0); | |
66 | printf("%"PRIuMAX"\n", tmp->n); | |
67 | } | |
68 | node_reset(); | |
69 | return 0; | |
70 | } |