Werner's Miscellanea
Sign in or create your account | Project List | Help
Werner's Miscellanea Git Source Tree
Root/
Source at commit b89bcdfd93a60417649340a18ca3bb573b1d9691 created 13 years 4 months ago. By Werner Almesberger, qpkg: also consider conflicts introduced by package about to be added | |
---|---|
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 | |
23 | static struct id *free_id = NULL; |
24 | |
25 | |
26 | /* ----- ID comparison (regular string compare) ---------------------------- */ |
27 | |
28 | |
29 | static 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 | |
41 | int comp_id(const void *a, const void *b) |
42 | { |
43 | return do_comp_id(a, b); |
44 | } |
45 | |
46 | |
47 | /* ----- Version comparison ------------------------------------------------ */ |
48 | |
49 | |
50 | static 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 | |
66 | int 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 | |
111 | struct 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 | |
122 | struct 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 | |
138 | const 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 |
Branches:
master