Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2011, 2012, 2013, 2015, 2016 Nicira, Inc.
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 : :
21 : : #include "hash.h"
22 : :
23 : : static uint32_t
24 : 5891963 : hash_name__(const char *name, size_t length)
25 : : {
26 : 5891963 : return hash_bytes(name, length, 0);
27 : : }
28 : :
29 : : static uint32_t
30 : 948313 : hash_name(const char *name)
31 : : {
32 : 948313 : return hash_name__(name, strlen(name));
33 : : }
34 : :
35 : : static struct sset_node *
36 : 5891971 : sset_find__(const struct sset *set, const char *name, size_t hash)
37 : : {
38 : : struct sset_node *node;
39 : :
40 [ + + ][ - + ]: 5891971 : HMAP_FOR_EACH_WITH_HASH (node, hmap_node, hash, &set->map) {
41 [ + - ]: 928971 : if (!strcmp(node->name, name)) {
42 : 928971 : return node;
43 : : }
44 : : }
45 : 4963000 : return NULL;
46 : : }
47 : :
48 : : static struct sset_node *
49 : 4927612 : sset_add__(struct sset *set, const char *name, size_t length, size_t hash)
50 : : {
51 : 4927612 : struct sset_node *node = xmalloc(length + sizeof *node);
52 : 4927612 : memcpy(node->name, name, length + 1);
53 : 4927612 : hmap_insert(&set->map, &node->hmap_node, hash);
54 : 4927612 : return node;
55 : : }
56 : :
57 : : /* Initializes 'set' as an empty set of strings. */
58 : : void
59 : 1845411 : sset_init(struct sset *set)
60 : : {
61 : 1845411 : hmap_init(&set->map);
62 : 1845411 : }
63 : :
64 : : /* Destroys 'sets'. */
65 : : void
66 : 1886280 : sset_destroy(struct sset *set)
67 : : {
68 [ + - ]: 1886280 : if (set) {
69 : 1886280 : sset_clear(set);
70 : 1886280 : hmap_destroy(&set->map);
71 : : }
72 : 1886280 : }
73 : :
74 : : /* Initializes 'set' to contain the same strings as 'orig'. */
75 : : void
76 : 11 : sset_clone(struct sset *set, const struct sset *orig)
77 : : {
78 : : struct sset_node *node;
79 : :
80 : 11 : sset_init(set);
81 [ + + ][ - + ]: 22 : HMAP_FOR_EACH (node, hmap_node, &orig->map) {
82 : 11 : sset_add__(set, node->name, strlen(node->name),
83 : : node->hmap_node.hash);
84 : : }
85 : 11 : }
86 : :
87 : : /* Exchanges the contents of 'a' and 'b'. */
88 : : void
89 : 110 : sset_swap(struct sset *a, struct sset *b)
90 : : {
91 : 110 : hmap_swap(&a->map, &b->map);
92 : 110 : }
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 : 0 : sset_moved(struct sset *set)
98 : : {
99 : 0 : hmap_moved(&set->map);
100 : 0 : }
101 : :
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 : 25 : sset_from_delimited_string(struct sset *set, const char *s_,
108 : : const char *delimiters)
109 : : {
110 : 25 : sset_init(set);
111 : :
112 : 25 : char *s = xstrdup(s_);
113 : 25 : char *token, *save_ptr = NULL;
114 [ + + ]: 53 : for (token = strtok_r(s, delimiters, &save_ptr); token != NULL;
115 : 28 : token = strtok_r(NULL, delimiters, &save_ptr)) {
116 : 28 : sset_add(set, token);
117 : : }
118 : 25 : free(s);
119 : 25 : }
120 : :
121 : : /* Returns true if 'set' contains no strings, false if it contains at least one
122 : : * string. */
123 : : bool
124 : 173525 : sset_is_empty(const struct sset *set)
125 : : {
126 : 173525 : return hmap_is_empty(&set->map);
127 : : }
128 : :
129 : : /* Returns the number of strings in 'set'. */
130 : : size_t
131 : 785911 : sset_count(const struct sset *set)
132 : : {
133 : 785911 : 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 : 4943650 : sset_add(struct sset *set, const char *name)
140 : : {
141 : 4943650 : size_t length = strlen(name);
142 : 4943650 : uint32_t hash = hash_name__(name, length);
143 : :
144 : 9887300 : return (sset_find__(set, name, hash)
145 : : ? NULL
146 [ + + ]: 4943650 : : 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 : 786 : sset_add_and_free(struct sset *set, char *name)
155 : : {
156 : 786 : struct sset_node *node = sset_add(set, name);
157 : 786 : free(name);
158 : 786 : return node;
159 : : }
160 : :
161 : : /* Adds 'name' to 'set'. Assert-fails if a copy of 'name' was already in
162 : : * 'set'. */
163 : : void
164 : 0 : sset_add_assert(struct sset *set, const char *name)
165 : : {
166 : 0 : bool added OVS_UNUSED = sset_add(set, name);
167 [ # # ]: 0 : ovs_assert(added);
168 : 0 : }
169 : :
170 : : /* Adds a copy of each of the 'n' names in 'names' to 'set'. */
171 : : void
172 : 23 : sset_add_array(struct sset *set, char **names, size_t n)
173 : : {
174 : : size_t i;
175 : :
176 [ + + ]: 48 : for (i = 0; i < n; i++) {
177 : 25 : sset_add(set, names[i]);
178 : : }
179 : 23 : }
180 : :
181 : : /* Removes all of the strings from 'set'. */
182 : : void
183 : 2119991 : sset_clear(struct sset *set)
184 : : {
185 : : const char *name, *next;
186 : :
187 [ + + ][ + + ]: 7035101 : SSET_FOR_EACH_SAFE (name, next, set) {
[ + + ][ + + ]
188 : 4915110 : sset_delete(set, SSET_NODE_FROM_NAME(name));
189 : : }
190 : 2119991 : }
191 : :
192 : : /* Deletes 'node' from 'set' and frees 'node'. */
193 : : void
194 : 4925071 : sset_delete(struct sset *set, struct sset_node *node)
195 : : {
196 : 4925071 : hmap_remove(&set->map, &node->hmap_node);
197 : 4925071 : free(node);
198 : 4925071 : }
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 : 12956 : sset_find_and_delete(struct sset *set, const char *name)
204 : : {
205 : 12956 : struct sset_node *node = sset_find(set, name);
206 [ + + ]: 12956 : if (node) {
207 : 9958 : sset_delete(set, node);
208 : : }
209 : 12956 : 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 : 400 : sset_find_and_delete_assert(struct sset *set, const char *name)
216 : : {
217 : 400 : bool deleted OVS_UNUSED = sset_find_and_delete(set, name);
218 [ - + ]: 400 : ovs_assert(deleted);
219 : 400 : }
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 : 1 : sset_pop(struct sset *set)
231 : : {
232 [ + - ]: 1 : const char *name = SSET_FIRST(set);
233 : 1 : char *copy = xstrdup(name);
234 : 1 : sset_delete(set, SSET_NODE_FROM_NAME(name));
235 : 1 : 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 : 948313 : sset_find(const struct sset *set, const char *name)
242 : : {
243 : 948313 : 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 : 934146 : sset_contains(const struct sset *set, const char *name)
249 : : {
250 : 934146 : return sset_find(set, name) != NULL;
251 : : }
252 : :
253 : : /* Returns true if 'a' and 'b' contain the same strings, false otherwise. */
254 : : bool
255 : 6 : sset_equals(const struct sset *a, const struct sset *b)
256 : : {
257 : : struct sset_node *node;
258 : :
259 [ - + ]: 6 : if (sset_count(a) != sset_count(b)) {
260 : 0 : return false;
261 : : }
262 : :
263 [ + + ][ - + ]: 12 : HMAP_FOR_EACH (node, hmap_node, &a->map) {
264 [ + + ]: 8 : if (!sset_find__(b, node->name, node->hmap_node.hash)) {
265 : 2 : return false;
266 : : }
267 : : }
268 : :
269 : 4 : return true;
270 : : }
271 : :
272 : : /* Returns the next node in 'set' in hash order, or NULL if no nodes remain in
273 : : * 'set'. Uses '*pos' to determine where to begin iteration, and updates
274 : : * '*pos' to pass on the next iteration into them before returning.
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 : : *
279 : : * Before beginning iteration, set '*pos' to all zeros. */
280 : : struct sset_node *
281 : 38936 : sset_at_position(const struct sset *set, struct sset_position *pos)
282 : : {
283 : : struct hmap_node *hmap_node;
284 : :
285 : 38936 : hmap_node = hmap_at_position(&set->map, &pos->pos);
286 : 38936 : return SSET_NODE_FROM_HMAP_NODE(hmap_node);
287 : : }
288 : :
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 : 110 : sset_intersect(struct sset *a, const struct sset *b)
293 : : {
294 : : const char *name, *next;
295 : :
296 [ + - ][ + + ]: 330 : SSET_FOR_EACH_SAFE (name, next, a) {
[ + + ][ + + ]
297 [ - + ]: 220 : if (!sset_contains(b, name)) {
298 : 0 : sset_delete(a, SSET_NODE_FROM_NAME(name));
299 : : }
300 : : }
301 : 110 : }
302 : :
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
305 : : * longer needed, but the strings in the array belong to 'set' and thus must
306 : : * not be modified or freed. */
307 : : const char **
308 : 8706 : sset_array(const struct sset *set)
309 : : {
310 : 8706 : size_t n = sset_count(set);
311 : : const char **array;
312 : : const char *s;
313 : : size_t i;
314 : :
315 : 8706 : array = xmalloc(sizeof *array * (n + 1));
316 : 8706 : i = 0;
317 [ + + ][ + + ]: 66734 : SSET_FOR_EACH (s, set) {
[ + + ]
318 : 58028 : array[i++] = s;
319 : : }
320 [ - + ]: 8706 : ovs_assert(i == n);
321 : 8706 : array[n] = NULL;
322 : :
323 : 8706 : return array;
324 : : }
325 : :
326 : : static int
327 : 3 : compare_string_pointers(const void *a_, const void *b_)
328 : : {
329 : 3 : const char *const *a = a_;
330 : 3 : const char *const *b = b_;
331 : :
332 : 3 : return strcmp(*a, *b);
333 : : }
334 : :
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 : 6 : sset_sort(const struct sset *set)
341 : : {
342 : 6 : const char **array = sset_array(set);
343 : 6 : qsort(array, sset_count(set), sizeof *array, compare_string_pointers);
344 : 6 : return array;
345 : : }
|
