Werner's Miscellanea
Sign in or create your account | Project List | Help
Werner's Miscellanea Git Source Tree
Root/
Source at commit 2787a45c436c35fc6fd0ed452903ad045fe9571d created 13 years 4 months ago. By Werner Almesberger, qpkg: added James S. Plank's red-black trees | |
---|---|
1 | #ifndef ID_H |
2 | #define ID_H |
3 | |
4 | #include <sys/types.h> |
5 | |
6 | |
7 | struct id; |
8 | |
9 | /* |
10 | * @@@ basic binary trees are not a good choice. should use rb. |
11 | * To ease future migration, we separate the node structure from the rest. |
12 | */ |
13 | |
14 | struct node { |
15 | struct node *up, *left, *right; |
16 | }; |
17 | |
18 | struct tree { |
19 | int (*comp)(const struct id *a, const struct id *b); |
20 | struct node *root; |
21 | }; |
22 | |
23 | struct id { |
24 | struct node node; |
25 | const char *s; |
26 | size_t len; |
27 | void *value; |
28 | }; |
29 | |
30 | |
31 | int comp_id(const struct id *a, const struct id *b); |
32 | |
33 | struct tree *make_tree(int (*comp)(const struct id *a, const struct id *b)); |
34 | struct id *make_id(struct tree *tree, const char *s, size_t len); |
35 | const struct id *find_id(const struct tree *tree, const char *s, size_t len); |
36 | const struct id *first_id(const struct tree *tree); |
37 | const struct id *next_id(const struct id *id); |
38 | |
39 | #endif /* !ID_H */ |
40 |
Branches:
master