Root/qpkg/id.h

Source at commit 2787a45c436c35fc6fd0ed452903ad045fe9571d created 9 years 17 days 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
7struct 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
14struct node {
15    struct node *up, *left, *right;
16};
17
18struct tree {
19    int (*comp)(const struct id *a, const struct id *b);
20    struct node *root;
21};
22
23struct id {
24    struct node node;
25    const char *s;
26    size_t len;
27    void *value;
28};
29
30
31int comp_id(const struct id *a, const struct id *b);
32
33struct tree *make_tree(int (*comp)(const struct id *a, const struct id *b));
34struct id *make_id(struct tree *tree, const char *s, size_t len);
35const struct id *find_id(const struct tree *tree, const char *s, size_t len);
36const struct id *first_id(const struct tree *tree);
37const struct id *next_id(const struct id *id);
38
39#endif /* !ID_H */
40

Archive Download this file

Branches:
master



interactive