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