Root/qpkg/id.c

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
10static struct id *free_id = NULL;
11
12
13int 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
25struct 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
36static 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
60struct 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
79const 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
101const 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
113const 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

Archive Download this file

Branches:
master



interactive