]>
Commit | Line | Data |
---|---|---|
f391294f | 1 | /* |
808311f6 | 2 | * Copyright (c) 2011, 2012, 2013 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 | |
254 | * 'set'. Uses '*bucketp' and '*offsetp' to determine where to begin | |
255 | * iteration, and stores new values to pass on the next iteration into them | |
256 | * before returning. | |
257 | * | |
258 | * It's better to use plain SSET_FOR_EACH and related functions, since they are | |
259 | * faster and better at dealing with ssets that change during iteration. | |
260 | * | |
261 | * Before beginning iteration, store 0 into '*bucketp' and '*offsetp'. | |
262 | */ | |
263 | struct sset_node * | |
264 | sset_at_position(const struct sset *set, uint32_t *bucketp, uint32_t *offsetp) | |
265 | { | |
266 | struct hmap_node *hmap_node; | |
267 | ||
268 | hmap_node = hmap_at_position(&set->map, bucketp, offsetp); | |
269 | return SSET_NODE_FROM_HMAP_NODE(hmap_node); | |
270 | } | |
808311f6 BP |
271 | |
272 | static int | |
273 | compare_string_pointers(const void *a_, const void *b_) | |
274 | { | |
275 | const char *const *a = a_; | |
276 | const char *const *b = b_; | |
277 | ||
278 | return strcmp(*a, *b); | |
279 | } | |
280 | ||
281 | /* Returns a null-terminated array of pointers to the strings in 'set', sorted | |
282 | * alphabetically. The caller must free the returned array when it is no | |
283 | * longer needed, but the strings in the array belong to 'set' and thus must | |
284 | * not be modified or freed. */ | |
285 | const char ** | |
286 | sset_sort(const struct sset *set) | |
287 | { | |
288 | size_t n = sset_count(set); | |
289 | const char **array; | |
290 | const char *s; | |
291 | size_t i; | |
292 | ||
293 | array = xmalloc(sizeof *array * (n + 1)); | |
294 | i = 0; | |
295 | SSET_FOR_EACH (s, set) { | |
296 | array[i++] = s; | |
297 | } | |
298 | ovs_assert(i == n); | |
299 | array[n] = NULL; | |
300 | ||
301 | qsort(array, n, sizeof *array, compare_string_pointers); | |
302 | ||
303 | return array; | |
304 | } |