]>
Commit | Line | Data |
---|---|---|
f391294f | 1 | /* |
842733c3 | 2 | * Copyright (c) 2011, 2012, 2013, 2015 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 | ||
102 | /* Returns true if 'set' contains no strings, false if it contains at least one | |
103 | * string. */ | |
104 | bool | |
105 | sset_is_empty(const struct sset *set) | |
106 | { | |
107 | return hmap_is_empty(&set->map); | |
108 | } | |
109 | ||
110 | /* Returns the number of strings in 'set'. */ | |
111 | size_t | |
112 | sset_count(const struct sset *set) | |
113 | { | |
114 | return hmap_count(&set->map); | |
115 | } | |
116 | ||
117 | /* Adds 'name' to 'set'. If 'name' is new, returns the new sset_node; | |
118 | * otherwise (if a copy of 'name' already existed in 'set'), returns NULL. */ | |
119 | struct sset_node * | |
120 | sset_add(struct sset *set, const char *name) | |
121 | { | |
122 | size_t length = strlen(name); | |
123 | uint32_t hash = hash_name__(name, length); | |
124 | ||
125 | return (sset_find__(set, name, hash) | |
126 | ? NULL | |
127 | : sset_add__(set, name, length, hash)); | |
128 | } | |
129 | ||
130 | /* Adds a copy of 'name' to 'set' and frees 'name'. | |
131 | * | |
132 | * If 'name' is new, returns the new sset_node; otherwise (if a copy of 'name' | |
133 | * already existed in 'set'), returns NULL. */ | |
134 | struct sset_node * | |
135 | sset_add_and_free(struct sset *set, char *name) | |
136 | { | |
137 | struct sset_node *node = sset_add(set, name); | |
138 | free(name); | |
139 | return node; | |
140 | } | |
141 | ||
142 | /* Adds 'name' to 'set'. Assert-fails if a copy of 'name' was already in | |
143 | * 'set'. */ | |
144 | void | |
145 | sset_add_assert(struct sset *set, const char *name) | |
146 | { | |
147 | bool added OVS_UNUSED = sset_add(set, name); | |
cb22974d | 148 | ovs_assert(added); |
f391294f BP |
149 | } |
150 | ||
151 | /* Adds a copy of each of the 'n' names in 'names' to 'set'. */ | |
152 | void | |
153 | sset_add_array(struct sset *set, char **names, size_t n) | |
154 | { | |
155 | size_t i; | |
156 | ||
157 | for (i = 0; i < n; i++) { | |
158 | sset_add(set, names[i]); | |
159 | } | |
160 | } | |
161 | ||
162 | /* Removes all of the strings from 'set'. */ | |
163 | void | |
164 | sset_clear(struct sset *set) | |
165 | { | |
166 | const char *name, *next; | |
167 | ||
168 | SSET_FOR_EACH_SAFE (name, next, set) { | |
169 | sset_delete(set, SSET_NODE_FROM_NAME(name)); | |
170 | } | |
171 | } | |
172 | ||
173 | /* Deletes 'node' from 'set' and frees 'node'. */ | |
174 | void | |
175 | sset_delete(struct sset *set, struct sset_node *node) | |
176 | { | |
177 | hmap_remove(&set->map, &node->hmap_node); | |
178 | free(node); | |
179 | } | |
180 | ||
181 | /* Searches for 'name' in 'set'. If found, deletes it and returns true. If | |
182 | * not found, returns false without modifying 'set'. */ | |
183 | bool | |
184 | sset_find_and_delete(struct sset *set, const char *name) | |
185 | { | |
186 | struct sset_node *node = sset_find(set, name); | |
187 | if (node) { | |
188 | sset_delete(set, node); | |
189 | } | |
190 | return node != NULL; | |
191 | } | |
192 | ||
193 | /* Searches for 'name' in 'set' and deletes it. Assert-fails if 'name' is not | |
194 | * in 'set'. */ | |
195 | void | |
196 | sset_find_and_delete_assert(struct sset *set, const char *name) | |
197 | { | |
198 | bool deleted OVS_UNUSED = sset_find_and_delete(set, name); | |
cb22974d | 199 | ovs_assert(deleted); |
f391294f BP |
200 | } |
201 | ||
202 | /* Removes a string from 'set' and returns a copy of it. The caller must free | |
203 | * the returned string (with free()). | |
204 | * | |
205 | * 'set' must not be empty. | |
206 | * | |
207 | * This is not a very good way to iterate through an sset: it copies each name | |
208 | * and it takes O(n**2) time to remove all the names. Use SSET_FOR_EACH_SAFE | |
209 | * instead, if you can. */ | |
210 | char * | |
211 | sset_pop(struct sset *set) | |
212 | { | |
213 | const char *name = SSET_FIRST(set); | |
214 | char *copy = xstrdup(name); | |
215 | sset_delete(set, SSET_NODE_FROM_NAME(name)); | |
216 | return copy; | |
217 | } | |
218 | ||
219 | /* Searches for 'name' in 'set'. Returns its node, if found, otherwise a null | |
220 | * pointer. */ | |
221 | struct sset_node * | |
222 | sset_find(const struct sset *set, const char *name) | |
223 | { | |
224 | return sset_find__(set, name, hash_name(name)); | |
225 | } | |
226 | ||
227 | /* Returns true if 'set' contains a copy of 'name', false otherwise. */ | |
228 | bool | |
229 | sset_contains(const struct sset *set, const char *name) | |
230 | { | |
231 | return sset_find(set, name) != NULL; | |
232 | } | |
233 | ||
234 | /* Returns true if 'a' and 'b' contain the same strings, false otherwise. */ | |
235 | bool | |
236 | sset_equals(const struct sset *a, const struct sset *b) | |
237 | { | |
238 | struct sset_node *node; | |
239 | ||
240 | if (sset_count(a) != sset_count(b)) { | |
241 | return false; | |
242 | } | |
243 | ||
244 | HMAP_FOR_EACH (node, hmap_node, &a->map) { | |
245 | if (!sset_find__(b, node->name, node->hmap_node.hash)) { | |
246 | return false; | |
247 | } | |
248 | } | |
249 | ||
250 | return true; | |
251 | } | |
6822daf2 JP |
252 | |
253 | /* Returns the next node in 'set' in hash order, or NULL if no nodes remain in | |
bfbcebc2 DDP |
254 | * 'set'. Uses '*pos' to determine where to begin iteration, and updates |
255 | * '*pos' to pass on the next iteration into them before returning. | |
6822daf2 JP |
256 | * |
257 | * It's better to use plain SSET_FOR_EACH and related functions, since they are | |
258 | * faster and better at dealing with ssets that change during iteration. | |
259 | * | |
bfbcebc2 | 260 | * Before beginning iteration, set '*pos' to all zeros. */ |
6822daf2 | 261 | struct sset_node * |
bfbcebc2 | 262 | sset_at_position(const struct sset *set, struct sset_position *pos) |
6822daf2 JP |
263 | { |
264 | struct hmap_node *hmap_node; | |
265 | ||
bfbcebc2 | 266 | hmap_node = hmap_at_position(&set->map, &pos->pos); |
6822daf2 JP |
267 | return SSET_NODE_FROM_HMAP_NODE(hmap_node); |
268 | } | |
808311f6 | 269 | |
a4686ba3 BP |
270 | /* Replaces 'a' by the intersection of 'a' and 'b'. That is, removes from 'a' |
271 | * all of the strings that are not also in 'b'. */ | |
272 | void | |
273 | sset_intersect(struct sset *a, const struct sset *b) | |
274 | { | |
275 | const char *name, *next; | |
276 | ||
277 | SSET_FOR_EACH_SAFE (name, next, a) { | |
278 | if (!sset_contains(b, name)) { | |
279 | sset_delete(a, SSET_NODE_FROM_NAME(name)); | |
280 | } | |
281 | } | |
282 | } | |
283 | ||
842733c3 MG |
284 | /* Returns a null-terminated array of pointers to the strings in 'set', in no |
285 | * particular order. The caller must free the returned array when it is no | |
808311f6 BP |
286 | * longer needed, but the strings in the array belong to 'set' and thus must |
287 | * not be modified or freed. */ | |
288 | const char ** | |
842733c3 | 289 | sset_array(const struct sset *set) |
808311f6 BP |
290 | { |
291 | size_t n = sset_count(set); | |
292 | const char **array; | |
293 | const char *s; | |
294 | size_t i; | |
295 | ||
296 | array = xmalloc(sizeof *array * (n + 1)); | |
297 | i = 0; | |
298 | SSET_FOR_EACH (s, set) { | |
299 | array[i++] = s; | |
300 | } | |
301 | ovs_assert(i == n); | |
302 | array[n] = NULL; | |
303 | ||
842733c3 MG |
304 | return array; |
305 | } | |
306 | ||
307 | static int | |
308 | compare_string_pointers(const void *a_, const void *b_) | |
309 | { | |
310 | const char *const *a = a_; | |
311 | const char *const *b = b_; | |
312 | ||
313 | return strcmp(*a, *b); | |
314 | } | |
808311f6 | 315 | |
842733c3 MG |
316 | /* Returns a null-terminated array of pointers to the strings in 'set', sorted |
317 | * alphabetically. The caller must free the returned array when it is no | |
318 | * longer needed, but the strings in the array belong to 'set' and thus must | |
319 | * not be modified or freed. */ | |
320 | const char ** | |
321 | sset_sort(const struct sset *set) | |
322 | { | |
323 | const char **array = sset_array(set); | |
324 | qsort(array, sset_count(set), sizeof *array, compare_string_pointers); | |
808311f6 BP |
325 | return array; |
326 | } |