1 |
commit: cf086cd6b3c452729f68fd9ce3411e28976ae94e |
2 |
Author: Fabian Groffen <grobian <AT> gentoo <DOT> org> |
3 |
AuthorDate: Sat Sep 21 19:48:29 2019 +0000 |
4 |
Commit: Fabian Groffen <grobian <AT> gentoo <DOT> org> |
5 |
CommitDate: Sat Sep 21 19:48:29 2019 +0000 |
6 |
URL: https://gitweb.gentoo.org/proj/portage-utils.git/commit/?id=cf086cd6 |
7 |
|
8 |
libq/set: add funcs for key/value support |
9 |
|
10 |
Signed-off-by: Fabian Groffen <grobian <AT> gentoo.org> |
11 |
|
12 |
libq/set.c | 103 ++++++++++++++++++++++++++++++++++++++++++++++++++-------- |
13 |
libq/set.h | 10 ++++-- |
14 |
libq/xarray.h | 4 +-- |
15 |
3 files changed, 100 insertions(+), 17 deletions(-) |
16 |
|
17 |
diff --git a/libq/set.c b/libq/set.c |
18 |
index f2c9394..a934a0d 100644 |
19 |
--- a/libq/set.c |
20 |
+++ b/libq/set.c |
21 |
@@ -18,7 +18,7 @@ |
22 |
#include "set.h" |
23 |
|
24 |
static unsigned int |
25 |
-fnv1a32(char *s) |
26 |
+fnv1a32(const char *s) |
27 |
{ |
28 |
unsigned int ret = 2166136261UL; |
29 |
for (; *s != '\0'; s++) |
30 |
@@ -33,7 +33,7 @@ create_set(void) |
31 |
return xzalloc(sizeof(set)); |
32 |
} |
33 |
|
34 |
-/* add elem to a set (unpure: could add duplicates) */ |
35 |
+/* add elem to a set (unpure: could add duplicates, basically hash) */ |
36 |
set * |
37 |
add_set(const char *name, set *q) |
38 |
{ |
39 |
@@ -47,6 +47,7 @@ add_set(const char *name, set *q) |
40 |
ll->next = NULL; |
41 |
ll->name = xstrdup(name); |
42 |
ll->hash = fnv1a32(ll->name); |
43 |
+ ll->val = NULL; |
44 |
|
45 |
pos = ll->hash % _SET_HASH_SIZE; |
46 |
if (q->buckets[pos] == NULL) { |
47 |
@@ -61,11 +62,10 @@ add_set(const char *name, set *q) |
48 |
return q; |
49 |
} |
50 |
|
51 |
-/* add elem to set if it doesn't exist yet (pure definition of set) */ |
52 |
+/* add elem to set if it doesn't exist yet (pure definition of hash) */ |
53 |
set * |
54 |
add_set_unique(const char *name, set *q, bool *unique) |
55 |
{ |
56 |
- char *mname = xstrdup(name); |
57 |
unsigned int hash; |
58 |
int pos; |
59 |
elem *ll; |
60 |
@@ -75,20 +75,20 @@ add_set_unique(const char *name, set *q, bool *unique) |
61 |
if (q == NULL) |
62 |
q = create_set(); |
63 |
|
64 |
- hash = fnv1a32(mname); |
65 |
+ hash = fnv1a32(name); |
66 |
pos = hash % _SET_HASH_SIZE; |
67 |
|
68 |
if (q->buckets[pos] == NULL) { |
69 |
q->buckets[pos] = ll = xmalloc(sizeof(*ll)); |
70 |
ll->next = NULL; |
71 |
- ll->name = mname; |
72 |
+ ll->name = xstrdup(name); |
73 |
ll->hash = hash; |
74 |
+ ll->val = NULL; |
75 |
uniq = true; |
76 |
} else { |
77 |
ll = NULL; |
78 |
for (w = q->buckets[pos]; w != NULL; ll = w, w = w->next) { |
79 |
- if (w->hash == hash && strcmp(w->name, mname) == 0) { |
80 |
- free(mname); |
81 |
+ if (w->hash == hash && strcmp(w->name, name) == 0) { |
82 |
uniq = false; |
83 |
break; |
84 |
} |
85 |
@@ -96,8 +96,9 @@ add_set_unique(const char *name, set *q, bool *unique) |
86 |
if (w == NULL) { |
87 |
ll = ll->next = xmalloc(sizeof(*ll)); |
88 |
ll->next = NULL; |
89 |
- ll->name = mname; |
90 |
+ ll->name = xstrdup(name); |
91 |
ll->hash = hash; |
92 |
+ ll->val = NULL; |
93 |
uniq = true; |
94 |
} |
95 |
} |
96 |
@@ -109,22 +110,60 @@ add_set_unique(const char *name, set *q, bool *unique) |
97 |
return q; |
98 |
} |
99 |
|
100 |
+/* add ptr to set with name as key, return existing value when key |
101 |
+ * already exists or NULL otherwise */ |
102 |
+void * |
103 |
+add_set_value(const char *name, void *ptr, set *q) |
104 |
+{ |
105 |
+ unsigned int hash; |
106 |
+ int pos; |
107 |
+ elem *ll; |
108 |
+ elem *w; |
109 |
+ |
110 |
+ hash = fnv1a32(name); |
111 |
+ pos = hash % _SET_HASH_SIZE; |
112 |
+ |
113 |
+ if (q->buckets[pos] == NULL) { |
114 |
+ q->buckets[pos] = ll = xmalloc(sizeof(*ll)); |
115 |
+ ll->next = NULL; |
116 |
+ ll->name = xstrdup(name); |
117 |
+ ll->hash = hash; |
118 |
+ ll->val = ptr; |
119 |
+ } else { |
120 |
+ ll = NULL; |
121 |
+ for (w = q->buckets[pos]; w != NULL; ll = w, w = w->next) { |
122 |
+ if (w->hash == hash && strcmp(w->name, name) == 0) |
123 |
+ return w->val; |
124 |
+ } |
125 |
+ if (w == NULL) { |
126 |
+ ll = ll->next = xmalloc(sizeof(*ll)); |
127 |
+ ll->next = NULL; |
128 |
+ ll->name = xstrdup(name); |
129 |
+ ll->hash = hash; |
130 |
+ ll->val = ptr; |
131 |
+ } |
132 |
+ } |
133 |
+ |
134 |
+ q->len++; |
135 |
+ return NULL; |
136 |
+} |
137 |
+ |
138 |
/* returns whether s is in set */ |
139 |
bool |
140 |
-contains_set(char *s, set *q) |
141 |
+contains_set(const char *name, set *q) |
142 |
{ |
143 |
unsigned int hash; |
144 |
int pos; |
145 |
elem *w; |
146 |
bool found; |
147 |
|
148 |
- hash = fnv1a32(s); |
149 |
+ hash = fnv1a32(name); |
150 |
pos = hash % _SET_HASH_SIZE; |
151 |
|
152 |
found = false; |
153 |
if (q->buckets[pos] != NULL) { |
154 |
for (w = q->buckets[pos]; w != NULL; w = w->next) { |
155 |
- if (w->hash == hash && strcmp(w->name, s) == 0) { |
156 |
+ if (w->hash == hash && strcmp(w->name, name) == 0) { |
157 |
found = true; |
158 |
break; |
159 |
} |
160 |
@@ -134,9 +173,31 @@ contains_set(char *s, set *q) |
161 |
return found; |
162 |
} |
163 |
|
164 |
+/* returns the value for name, or NULL if not found (cannot |
165 |
+ * differentiate between value NULL and unset) */ |
166 |
+void * |
167 |
+get_set(const char *name, set *q) |
168 |
+{ |
169 |
+ unsigned int hash; |
170 |
+ int pos; |
171 |
+ elem *w; |
172 |
+ |
173 |
+ hash = fnv1a32(name); |
174 |
+ pos = hash % _SET_HASH_SIZE; |
175 |
+ |
176 |
+ if (q->buckets[pos] != NULL) { |
177 |
+ for (w = q->buckets[pos]; w != NULL; w = w->next) { |
178 |
+ if (w->hash == hash && strcmp(w->name, name) == 0) |
179 |
+ return w->val; |
180 |
+ } |
181 |
+ } |
182 |
+ |
183 |
+ return NULL; |
184 |
+} |
185 |
+ |
186 |
/* remove elem from a set. matches ->name and frees name,item */ |
187 |
set * |
188 |
-del_set(char *s, set *q, bool *removed) |
189 |
+del_set(const char *s, set *q, bool *removed) |
190 |
{ |
191 |
unsigned int hash; |
192 |
int pos; |
193 |
@@ -191,6 +252,22 @@ list_set(set *q, char ***l) |
194 |
return q->len; |
195 |
} |
196 |
|
197 |
+size_t |
198 |
+values_set(set *q, array_t *ret) |
199 |
+{ |
200 |
+ int i; |
201 |
+ elem *w; |
202 |
+ array_t blank = array_init_decl; |
203 |
+ |
204 |
+ *ret = blank; |
205 |
+ for (i = 0; i < _SET_HASH_SIZE; i++) { |
206 |
+ for (w = q->buckets[i]; w != NULL; w = w->next) |
207 |
+ xarraypush_ptr(ret, w->val); |
208 |
+ } |
209 |
+ |
210 |
+ return q->len; |
211 |
+} |
212 |
+ |
213 |
/* clear out a set */ |
214 |
void |
215 |
clear_set(set *q) |
216 |
|
217 |
diff --git a/libq/set.h b/libq/set.h |
218 |
index 7ca5f65..00ef909 100644 |
219 |
--- a/libq/set.h |
220 |
+++ b/libq/set.h |
221 |
@@ -10,12 +10,15 @@ |
222 |
#include <stdbool.h> |
223 |
#include <unistd.h> |
224 |
|
225 |
+#include "xarray.h" |
226 |
+ |
227 |
typedef struct elem_t elem; |
228 |
typedef struct set_t set; |
229 |
|
230 |
struct elem_t { |
231 |
char *name; |
232 |
unsigned int hash; /* FNV1a32 */ |
233 |
+ void *val; |
234 |
elem *next; |
235 |
}; |
236 |
|
237 |
@@ -28,9 +31,12 @@ struct set_t { |
238 |
set *create_set(void); |
239 |
set *add_set(const char *name, set *q); |
240 |
set *add_set_unique(const char *name, set *q, bool *unique); |
241 |
-bool contains_set(char *s, set *q); |
242 |
-set *del_set(char *s, set *q, bool *removed); |
243 |
+void *add_set_value(const char *name, void *ptr, set *q); |
244 |
+bool contains_set(const char *name, set *q); |
245 |
+void *get_set(const char *name, set *q); |
246 |
+set *del_set(const char *s, set *q, bool *removed); |
247 |
size_t list_set(set *q, char ***l); |
248 |
+size_t values_set(set *q, array_t *ret); |
249 |
void free_set(set *q); |
250 |
void clear_set(set *q); |
251 |
|
252 |
|
253 |
diff --git a/libq/xarray.h b/libq/xarray.h |
254 |
index 22ee47a..71dfecb 100644 |
255 |
--- a/libq/xarray.h |
256 |
+++ b/libq/xarray.h |
257 |
@@ -26,9 +26,9 @@ typedef struct { |
258 |
*/ |
259 |
/* TODO: remove ele = NULL after checking all consumers don't rely on this */ |
260 |
#define array_for_each(arr, n, ele) \ |
261 |
- for (n = 0, ele = NULL; n < array_cnt(arr) && (ele = arr->eles[n]); n++) |
262 |
+ for (n = 0, ele = NULL; n < array_cnt(arr) && (ele = (arr)->eles[n]); n++) |
263 |
#define array_for_each_rev(arr, n, ele) \ |
264 |
- for (n = array_cnt(arr); n-- > 0 && (ele = arr->eles[n]); /*nothing*/) |
265 |
+ for (n = array_cnt(arr); n-- > 0 && (ele = (arr)->eles[n]); /*nothing*/) |
266 |
#define array_get_elem(arr, n) (arr->eles[n]) |
267 |
#define array_init_decl { .eles = NULL, .num = 0, } |
268 |
#define array_cnt(arr) (arr)->num |