Root/qpkg/id.c

1/*
2 * id.c - Registry of unique and alphabetically sorted identifiers
3 *
4 * Written 2010 by Werner Almesberger
5 * Copyright 2010 Werner Almesberger
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 */
12
13
14#include <string.h>
15#include <ctype.h>
16
17#include "jrb.h"
18
19#include "util.h"
20#include "id.h"
21
22
23static struct id *free_id = NULL;
24
25
26/* ----- ID comparison (regular string compare) ---------------------------- */
27
28
29static int do_comp_id(const struct id *a, const struct id *b)
30{
31    int len = a->len < b->len ? a->len : b->len;
32    int cmp;
33
34    cmp = memcmp(a->s, b->s, len);
35    if (cmp)
36        return cmp;
37    return a->len < b->len ? -1 : a->len > b->len;
38}
39
40
41int comp_id(const void *a, const void *b)
42{
43    return do_comp_id(a, b);
44}
45
46
47/* ----- Version comparison ------------------------------------------------ */
48
49
50static int epoch(const char **s, const struct id *id)
51{
52    const char *end = id->s+id->len;
53    int n = 0;
54
55    while (*s != end && isdigit(**s)) {
56        n = 10*n+**s-'0';
57        (*s)++;
58    }
59    if (*s == id->s || (*s != end && **s == ':'))
60        return n;
61    *s = id->s;
62    return 0;
63}
64
65
66int comp_versions(const struct id *va, const struct id *vb)
67{
68    int epoch_a = 0, epoch_b = 0;
69    const char *a = va->s;
70    const char *b = vb->s;
71    const char *ea = a+va->len;
72    const char *eb = b+vb->len;
73
74    epoch_a = epoch(&a, va);
75    epoch_b = epoch(&b, vb);
76    if (epoch_a != epoch_b)
77        return epoch_a-epoch_b;
78
79    while (1) {
80        if (a == ea || b == eb)
81            return (a != ea)-(b != eb);
82        if (isdigit(*a) && isdigit(*b)) {
83            int na = 0, nb = 0;
84
85            while (a != ea && isdigit(*a)) {
86                na = na*10+*a-'0';
87                a++;
88            }
89            while (b != eb && isdigit(*b)) {
90                nb = nb*10+*b-'0';
91                b++;
92            }
93            if (na == nb)
94                continue;
95
96            return na-nb;
97        }
98        if (*a > *b)
99            return 1;
100        if (*a < *b)
101            return 1;
102        a++;
103        b++;
104    }
105}
106
107
108/* ----- Tree maintenance -------------------------------------------------- */
109
110
111struct tree *make_tree(int (*comp)(const void *a, const void *b))
112{
113    struct tree *tree;
114
115    tree = alloc_type(struct tree);
116    tree->comp = comp;
117    tree->root = make_jrb();
118    return tree;
119}
120
121
122struct jrb *make_id(struct tree *tree, const char *s, size_t len)
123{
124    struct id *id;
125
126    if (!free_id)
127        free_id = alloc_type(struct id);
128    id = free_id;
129    id->s = s;
130    id->len = len;
131    id->jrb = jrb_find_or_insert(tree->root, id, NULL, tree->comp);
132    if (id->jrb->key == id)
133        free_id = NULL;
134    return id->jrb;
135}
136
137
138const struct jrb *find_id(const struct tree *tree, const char *s, size_t len)
139{
140    struct id id = {
141        .s = s,
142        .len = len
143    };
144
145    return jrb_find(tree->root, &id, tree->comp);
146}
147

Archive Download this file

Branches:
master



interactive