]>
Commit | Line | Data |
---|---|---|
f391294f | 1 | /* |
63a10e1e | 2 | * Copyright (c) 2011, 2012, 2013, 2015, 2016 Nicira, Inc. |
f391294f BP |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); | |
5 | * you may not use this file except in compliance with the License. | |
6 | * You may obtain a copy of the License at: | |
7 | * | |
8 | * http://www.apache.org/licenses/LICENSE-2.0 | |
9 | * | |
10 | * Unless required by applicable law or agreed to in writing, software | |
11 | * distributed under the License is distributed on an "AS IS" BASIS, | |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
13 | * See the License for the specific language governing permissions and | |
14 | * limitations under the License. | |
15 | */ | |
16 | ||
17 | #include <config.h> | |
18 | ||
19 | #include "sset.h" | |
20 | ||
3ae9a07a | 21 | #include "openvswitch/dynamic-string.h" |
f391294f BP |
22 | #include "hash.h" |
23 | ||
24 | static uint32_t | |
25 | hash_name__(const char *name, size_t length) | |
26 | { | |
27 | return hash_bytes(name, length, 0); | |
28 | } | |
29 | ||
30 | static uint32_t | |
31 | hash_name(const char *name) | |
32 | { | |
33 | return hash_name__(name, strlen(name)); | |
34 | } | |
35 | ||
36 | static struct sset_node * | |
37 | sset_find__(const struct sset *set, const char *name, size_t hash) | |
38 | { | |
39 | struct sset_node *node; | |
40 | ||
41 | HMAP_FOR_EACH_WITH_HASH (node, hmap_node, hash, &set->map) { | |
42 | if (!strcmp(node->name, name)) { | |
43 | return node; | |
44 | } | |
45 | } | |
46 | return NULL; | |
47 | } | |
48 | ||
49 | static struct sset_node * | |
50 | sset_add__(struct sset *set, const char *name, size_t length, size_t hash) | |
51 | { | |
52 | struct sset_node *node = xmalloc(length + sizeof *node); | |
53 | memcpy(node->name, name, length + 1); | |
54 | hmap_insert(&set->map, &node->hmap_node, hash); | |
55 | return node; | |
56 | } | |
57 | ||
58 | /* Initializes 'set' as an empty set of strings. */ | |
59 | void | |
60 | sset_init(struct sset *set) | |
61 | { | |
62 | hmap_init(&set->map); | |
63 | } | |
64 | ||
65 | /* Destroys 'sets'. */ | |
66 | void | |
67 | sset_destroy(struct sset *set) | |
68 | { | |
69 | if (set) { | |
70 | sset_clear(set); | |
71 | hmap_destroy(&set->map); | |
72 | } | |
73 | } | |
74 | ||
75 | /* Initializes 'set' to contain the same strings as 'orig'. */ | |
76 | void | |
77 | sset_clone(struct sset *set, const struct sset *orig) | |
78 | { | |
79 | struct sset_node *node; | |
80 | ||
81 | sset_init(set); | |
82 | HMAP_FOR_EACH (node, hmap_node, &orig->map) { | |
83 | sset_add__(set, node->name, strlen(node->name), | |
84 | node->hmap_node.hash); | |
85 | } | |
86 | } | |
87 | ||
88 | /* Exchanges the contents of 'a' and 'b'. */ | |
89 | void | |
90 | sset_swap(struct sset *a, struct sset *b) | |
91 | { | |
92 | hmap_swap(&a->map, &b->map); | |
93 | } | |
94 | ||
95 | /* Adjusts 'set' so that it is still valid after it has been moved around in | |
96 | * memory (e.g. due to realloc()). */ | |
97 | void | |
98 | sset_moved(struct sset *set) | |
99 | { | |
100 | hmap_moved(&set->map); | |
101 | } | |
102 | ||
63a10e1e BP |
103 | /* Initializes 'set' with substrings of 's' that are delimited by any of the |
104 | * characters in 'delimiters'. For example, | |
105 | * sset_from_delimited_string(&set, "a b,c", " ,"); | |
106 | * initializes 'set' with three strings "a", "b", and "c". */ | |
107 | void | |
108 | sset_from_delimited_string(struct sset *set, const char *s_, | |
109 | const char *delimiters) | |
110 | { | |
111 | sset_init(set); | |
112 | ||
113 | char *s = xstrdup(s_); | |
114 | char *token, *save_ptr = NULL; | |
115 | for (token = strtok_r(s, delimiters, &save_ptr); token != NULL; | |
116 | token = strtok_r(NULL, delimiters, &save_ptr)) { | |
117 | sset_add(set, token); | |
118 | } | |
119 | free(s); | |
120 | } | |
121 | ||
3ae9a07a BP |
122 | /* Returns a malloc()'d string that consists of the concatenation of all of the |
123 | * strings in 'sset' in lexicographic order, each separated from the next by | |
124 | * 'delimiter' and followed by 'terminator'. For example: | |
125 | * | |
126 | * sset_join(("a", "b", "c"), ", ", ".") -> "a, b, c." | |
127 | * sset_join(("xyzzy"), ", ", ".") -> "xyzzy." | |
128 | * sset_join((""), ", ", ".") -> "." | |
129 | * | |
130 | * The caller is responsible for freeing the returned string (with free()). | |
131 | */ | |
132 | char * | |
133 | sset_join(const struct sset *sset, | |
134 | const char *delimiter, const char *terminator) | |
135 | { | |
136 | struct ds s = DS_EMPTY_INITIALIZER; | |
137 | ||
138 | const char **names = sset_sort(sset); | |
139 | for (size_t i = 0; i < sset_count(sset); i++) { | |
140 | if (i) { | |
141 | ds_put_cstr(&s, delimiter); | |
142 | } | |
143 | ds_put_cstr(&s, names[i]); | |
144 | } | |
145 | free(names); | |
146 | ||
147 | ds_put_cstr(&s, terminator); | |
148 | ||
149 | return ds_steal_cstr(&s); | |
150 | } | |
151 | ||
f391294f BP |
152 | /* Returns true if 'set' contains no strings, false if it contains at least one |
153 | * string. */ | |
154 | bool | |
155 | sset_is_empty(const struct sset *set) | |
156 | { | |
157 | return hmap_is_empty(&set->map); | |
158 | } | |
159 | ||
160 | /* Returns the number of strings in 'set'. */ | |
161 | size_t | |
162 | sset_count(const struct sset *set) | |
163 | { | |
164 | return hmap_count(&set->map); | |
165 | } | |
166 | ||
167 | /* Adds 'name' to 'set'. If 'name' is new, returns the new sset_node; | |
168 | * otherwise (if a copy of 'name' already existed in 'set'), returns NULL. */ | |
169 | struct sset_node * | |
170 | sset_add(struct sset *set, const char *name) | |
171 | { | |
172 | size_t length = strlen(name); | |
173 | uint32_t hash = hash_name__(name, length); | |
174 | ||
175 | return (sset_find__(set, name, hash) | |
176 | ? NULL | |
177 | : sset_add__(set, name, length, hash)); | |
178 | } | |
179 | ||
180 | /* Adds a copy of 'name' to 'set' and frees 'name'. | |
181 | * | |
182 | * If 'name' is new, returns the new sset_node; otherwise (if a copy of 'name' | |
183 | * already existed in 'set'), returns NULL. */ | |
184 | struct sset_node * | |
185 | sset_add_and_free(struct sset *set, char *name) | |
186 | { | |
187 | struct sset_node *node = sset_add(set, name); | |
188 | free(name); | |
189 | return node; | |
190 | } | |
191 | ||
192 | /* Adds 'name' to 'set'. Assert-fails if a copy of 'name' was already in | |
193 | * 'set'. */ | |
194 | void | |
195 | sset_add_assert(struct sset *set, const char *name) | |
196 | { | |
500db308 | 197 | ovs_assert(sset_add(set, name)); |
f391294f BP |
198 | } |
199 | ||
200 | /* Adds a copy of each of the 'n' names in 'names' to 'set'. */ | |
201 | void | |
202 | sset_add_array(struct sset *set, char **names, size_t n) | |
203 | { | |
204 | size_t i; | |
205 | ||
206 | for (i = 0; i < n; i++) { | |
207 | sset_add(set, names[i]); | |
208 | } | |
209 | } | |
210 | ||
211 | /* Removes all of the strings from 'set'. */ | |
212 | void | |
213 | sset_clear(struct sset *set) | |
214 | { | |
215 | const char *name, *next; | |
216 | ||
217 | SSET_FOR_EACH_SAFE (name, next, set) { | |
218 | sset_delete(set, SSET_NODE_FROM_NAME(name)); | |
219 | } | |
220 | } | |
221 | ||
222 | /* Deletes 'node' from 'set' and frees 'node'. */ | |
223 | void | |
224 | sset_delete(struct sset *set, struct sset_node *node) | |
225 | { | |
226 | hmap_remove(&set->map, &node->hmap_node); | |
227 | free(node); | |
228 | } | |
229 | ||
230 | /* Searches for 'name' in 'set'. If found, deletes it and returns true. If | |
231 | * not found, returns false without modifying 'set'. */ | |
232 | bool | |
233 | sset_find_and_delete(struct sset *set, const char *name) | |
234 | { | |
235 | struct sset_node *node = sset_find(set, name); | |
236 | if (node) { | |
237 | sset_delete(set, node); | |
238 | } | |
239 | return node != NULL; | |
240 | } | |
241 | ||
242 | /* Searches for 'name' in 'set' and deletes it. Assert-fails if 'name' is not | |
243 | * in 'set'. */ | |
244 | void | |
245 | sset_find_and_delete_assert(struct sset *set, const char *name) | |
246 | { | |
500db308 | 247 | ovs_assert(sset_find_and_delete(set, name)); |
f391294f BP |
248 | } |
249 | ||
250 | /* Removes a string from 'set' and returns a copy of it. The caller must free | |
251 | * the returned string (with free()). | |
252 | * | |
253 | * 'set' must not be empty. | |
254 | * | |
255 | * This is not a very good way to iterate through an sset: it copies each name | |
256 | * and it takes O(n**2) time to remove all the names. Use SSET_FOR_EACH_SAFE | |
257 | * instead, if you can. */ | |
258 | char * | |
259 | sset_pop(struct sset *set) | |
260 | { | |
261 | const char *name = SSET_FIRST(set); | |
262 | char *copy = xstrdup(name); | |
263 | sset_delete(set, SSET_NODE_FROM_NAME(name)); | |
264 | return copy; | |
265 | } | |
266 | ||
267 | /* Searches for 'name' in 'set'. Returns its node, if found, otherwise a null | |
268 | * pointer. */ | |
269 | struct sset_node * | |
270 | sset_find(const struct sset *set, const char *name) | |
271 | { | |
272 | return sset_find__(set, name, hash_name(name)); | |
273 | } | |
274 | ||
275 | /* Returns true if 'set' contains a copy of 'name', false otherwise. */ | |
276 | bool | |
277 | sset_contains(const struct sset *set, const char *name) | |
278 | { | |
279 | return sset_find(set, name) != NULL; | |
280 | } | |
281 | ||
282 | /* Returns true if 'a' and 'b' contain the same strings, false otherwise. */ | |
283 | bool | |
284 | sset_equals(const struct sset *a, const struct sset *b) | |
285 | { | |
286 | struct sset_node *node; | |
287 | ||
288 | if (sset_count(a) != sset_count(b)) { | |
289 | return false; | |
290 | } | |
291 | ||
292 | HMAP_FOR_EACH (node, hmap_node, &a->map) { | |
293 | if (!sset_find__(b, node->name, node->hmap_node.hash)) { | |
294 | return false; | |
295 | } | |
296 | } | |
297 | ||
298 | return true; | |
299 | } | |
6822daf2 JP |
300 | |
301 | /* Returns the next node in 'set' in hash order, or NULL if no nodes remain in | |
bfbcebc2 DDP |
302 | * 'set'. Uses '*pos' to determine where to begin iteration, and updates |
303 | * '*pos' to pass on the next iteration into them before returning. | |
6822daf2 JP |
304 | * |
305 | * It's better to use plain SSET_FOR_EACH and related functions, since they are | |
306 | * faster and better at dealing with ssets that change during iteration. | |
307 | * | |
bfbcebc2 | 308 | * Before beginning iteration, set '*pos' to all zeros. */ |
6822daf2 | 309 | struct sset_node * |
bfbcebc2 | 310 | sset_at_position(const struct sset *set, struct sset_position *pos) |
6822daf2 JP |
311 | { |
312 | struct hmap_node *hmap_node; | |
313 | ||
bfbcebc2 | 314 | hmap_node = hmap_at_position(&set->map, &pos->pos); |
6822daf2 JP |
315 | return SSET_NODE_FROM_HMAP_NODE(hmap_node); |
316 | } | |
808311f6 | 317 | |
a4686ba3 BP |
318 | /* Replaces 'a' by the intersection of 'a' and 'b'. That is, removes from 'a' |
319 | * all of the strings that are not also in 'b'. */ | |
320 | void | |
321 | sset_intersect(struct sset *a, const struct sset *b) | |
322 | { | |
323 | const char *name, *next; | |
324 | ||
325 | SSET_FOR_EACH_SAFE (name, next, a) { | |
326 | if (!sset_contains(b, name)) { | |
327 | sset_delete(a, SSET_NODE_FROM_NAME(name)); | |
328 | } | |
329 | } | |
330 | } | |
331 | ||
842733c3 MG |
332 | /* Returns a null-terminated array of pointers to the strings in 'set', in no |
333 | * particular order. The caller must free the returned array when it is no | |
808311f6 BP |
334 | * longer needed, but the strings in the array belong to 'set' and thus must |
335 | * not be modified or freed. */ | |
336 | const char ** | |
842733c3 | 337 | sset_array(const struct sset *set) |
808311f6 BP |
338 | { |
339 | size_t n = sset_count(set); | |
340 | const char **array; | |
341 | const char *s; | |
342 | size_t i; | |
343 | ||
344 | array = xmalloc(sizeof *array * (n + 1)); | |
345 | i = 0; | |
346 | SSET_FOR_EACH (s, set) { | |
347 | array[i++] = s; | |
348 | } | |
349 | ovs_assert(i == n); | |
350 | array[n] = NULL; | |
351 | ||
842733c3 MG |
352 | return array; |
353 | } | |
354 | ||
355 | static int | |
356 | compare_string_pointers(const void *a_, const void *b_) | |
357 | { | |
358 | const char *const *a = a_; | |
359 | const char *const *b = b_; | |
360 | ||
361 | return strcmp(*a, *b); | |
362 | } | |
808311f6 | 363 | |
842733c3 MG |
364 | /* Returns a null-terminated array of pointers to the strings in 'set', sorted |
365 | * alphabetically. The caller must free the returned array when it is no | |
366 | * longer needed, but the strings in the array belong to 'set' and thus must | |
367 | * not be modified or freed. */ | |
368 | const char ** | |
369 | sset_sort(const struct sset *set) | |
370 | { | |
371 | const char **array = sset_array(set); | |
372 | qsort(array, sset_count(set), sizeof *array, compare_string_pointers); | |
808311f6 BP |
373 | return array; |
374 | } |