Werner's Miscellanea
Sign in or create your account | Project List | Help
Werner's Miscellanea Git Source Tree
Root/
Source at commit 2787a45c436c35fc6fd0ed452903ad045fe9571d created 9 years 23 days ago. By Werner Almesberger, qpkg: added James S. Plank's red-black trees | |
---|---|
1 | #include <string.h> |
2 | |
3 | #include "util.h" |
4 | #include "id.h" |
5 | |
6 | |
7 | #define NODE2ID(n) ((struct id *) n) |
8 | |
9 | |
10 | static struct id *free_id = NULL; |
11 | |
12 | |
13 | int comp_id(const struct id *a, const struct id *b) |
14 | { |
15 | int len = a->len < b->len ? a->len : b->len; |
16 | int cmp; |
17 | |
18 | cmp = memcmp(a->s, b->s, len); |
19 | if (cmp) |
20 | return cmp; |
21 | return a->len < b->len ? -1 : a->len > b->len; |
22 | } |
23 | |
24 | |
25 | struct tree *make_tree(int (*comp)(const struct id *a, const struct id *b)) |
26 | { |
27 | struct tree *tree; |
28 | |
29 | tree = alloc_type(struct tree); |
30 | tree->comp = comp; |
31 | tree->root = NULL; |
32 | return tree; |
33 | } |
34 | |
35 | |
36 | static struct node *add_node(struct tree *tree, struct node *node) |
37 | { |
38 | struct node **p, *last; |
39 | int cmp; |
40 | |
41 | p = &tree->root; |
42 | last = NULL; |
43 | while (*p) { |
44 | last = *p; |
45 | cmp = tree->comp(NODE2ID(node), NODE2ID(*p)); |
46 | if (cmp < 0) |
47 | p = &(*p)->left; |
48 | else if (cmp > 0) |
49 | p = &(*p)->right; |
50 | else |
51 | return *p; |
52 | } |
53 | *p = node; |
54 | node->up = last; |
55 | node->left = node->right = NULL; |
56 | return NULL; |
57 | } |
58 | |
59 | |
60 | struct id *make_id(struct tree *tree, const char *s, size_t len) |
61 | { |
62 | struct id *id; |
63 | struct node *node; |
64 | |
65 | if (!free_id) |
66 | free_id = alloc_type(struct id); |
67 | id = free_id; |
68 | id->s = s; |
69 | id->len = len; |
70 | id->value = NULL; |
71 | node = add_node(tree, &id->node); |
72 | if (node) |
73 | return NODE2ID(node); |
74 | free_id = NULL; |
75 | return id; |
76 | } |
77 | |
78 | |
79 | const struct id *find_id(const struct tree *tree, const char *s, size_t len) |
80 | { |
81 | struct id id = { |
82 | .s = s, |
83 | .len = len |
84 | }; |
85 | const struct node *n = tree->root; |
86 | int cmp; |
87 | |
88 | while (n) { |
89 | cmp = tree->comp(&id, NODE2ID(n)); |
90 | if (cmp < 0) |
91 | n = n->left; |
92 | else if (cmp > 0) |
93 | n = n->right; |
94 | else |
95 | return NODE2ID(n); |
96 | } |
97 | return NULL; |
98 | } |
99 | |
100 | |
101 | const struct id *first_id(const struct tree *tree) |
102 | { |
103 | const struct node *n = tree->root; |
104 | |
105 | if (!n) |
106 | return NULL; |
107 | while (n->left) |
108 | n = n->left; |
109 | return NODE2ID(n); |
110 | } |
111 | |
112 | |
113 | const struct id *next_id(const struct id *id) |
114 | { |
115 | const struct node *n = &id->node; |
116 | |
117 | if (n->right) { |
118 | n = n->right; |
119 | while (n->left) |
120 | n = n->left; |
121 | return NODE2ID(n); |
122 | } |
123 | while (n->up) { |
124 | if (n == n->up->left) |
125 | return NODE2ID(n->up); |
126 | n = n->up; |
127 | } |
128 | return NULL; |
129 | } |
130 |
Branches:
master