]>
git.proxmox.com Git - mirror_ovs.git/blob - lib/sset.c
2 * Copyright (c) 2011, 2012, 2013, 2015, 2016 Nicira, Inc.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
21 #include "openvswitch/dynamic-string.h"
25 hash_name__(const char *name
, size_t length
)
27 return hash_bytes(name
, length
, 0);
31 hash_name(const char *name
)
33 return hash_name__(name
, strlen(name
));
36 static struct sset_node
*
37 sset_find__(const struct sset
*set
, const char *name
, size_t hash
)
39 struct sset_node
*node
;
41 HMAP_FOR_EACH_WITH_HASH (node
, hmap_node
, hash
, &set
->map
) {
42 if (!strcmp(node
->name
, name
)) {
49 static struct sset_node
*
50 sset_add__(struct sset
*set
, const char *name
, size_t length
, size_t hash
)
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
);
58 /* Initializes 'set' as an empty set of strings. */
60 sset_init(struct sset
*set
)
65 /* Destroys 'sets'. */
67 sset_destroy(struct sset
*set
)
71 hmap_destroy(&set
->map
);
75 /* Initializes 'set' to contain the same strings as 'orig'. */
77 sset_clone(struct sset
*set
, const struct sset
*orig
)
79 struct sset_node
*node
;
82 HMAP_FOR_EACH (node
, hmap_node
, &orig
->map
) {
83 sset_add__(set
, node
->name
, strlen(node
->name
),
84 node
->hmap_node
.hash
);
88 /* Exchanges the contents of 'a' and 'b'. */
90 sset_swap(struct sset
*a
, struct sset
*b
)
92 hmap_swap(&a
->map
, &b
->map
);
95 /* Adjusts 'set' so that it is still valid after it has been moved around in
96 * memory (e.g. due to realloc()). */
98 sset_moved(struct sset
*set
)
100 hmap_moved(&set
->map
);
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". */
108 sset_from_delimited_string(struct sset
*set
, const char *s_
,
109 const char *delimiters
)
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
);
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:
126 * sset_join(("a", "b", "c"), ", ", ".") -> "a, b, c."
127 * sset_join(("xyzzy"), ", ", ".") -> "xyzzy."
128 * sset_join((""), ", ", ".") -> "."
130 * The caller is responsible for freeing the returned string (with free()).
133 sset_join(const struct sset
*sset
,
134 const char *delimiter
, const char *terminator
)
136 struct ds s
= DS_EMPTY_INITIALIZER
;
138 const char **names
= sset_sort(sset
);
139 for (size_t i
= 0; i
< sset_count(sset
); i
++) {
141 ds_put_cstr(&s
, delimiter
);
143 ds_put_cstr(&s
, names
[i
]);
147 ds_put_cstr(&s
, terminator
);
149 return ds_steal_cstr(&s
);
152 /* Returns true if 'set' contains no strings, false if it contains at least one
155 sset_is_empty(const struct sset
*set
)
157 return hmap_is_empty(&set
->map
);
160 /* Returns the number of strings in 'set'. */
162 sset_count(const struct sset
*set
)
164 return hmap_count(&set
->map
);
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. */
170 sset_add(struct sset
*set
, const char *name
)
172 size_t length
= strlen(name
);
173 uint32_t hash
= hash_name__(name
, length
);
175 return (sset_find__(set
, name
, hash
)
177 : sset_add__(set
, name
, length
, hash
));
180 /* Adds a copy of 'name' to 'set' and frees 'name'.
182 * If 'name' is new, returns the new sset_node; otherwise (if a copy of 'name'
183 * already existed in 'set'), returns NULL. */
185 sset_add_and_free(struct sset
*set
, char *name
)
187 struct sset_node
*node
= sset_add(set
, name
);
192 /* Adds 'name' to 'set'. Assert-fails if a copy of 'name' was already in
195 sset_add_assert(struct sset
*set
, const char *name
)
197 ovs_assert(sset_add(set
, name
));
200 /* Adds a copy of each of the 'n' names in 'names' to 'set'. */
202 sset_add_array(struct sset
*set
, char **names
, size_t n
)
206 for (i
= 0; i
< n
; i
++) {
207 sset_add(set
, names
[i
]);
211 /* Removes all of the strings from 'set'. */
213 sset_clear(struct sset
*set
)
215 const char *name
, *next
;
217 SSET_FOR_EACH_SAFE (name
, next
, set
) {
218 sset_delete(set
, SSET_NODE_FROM_NAME(name
));
222 /* Deletes 'node' from 'set' and frees 'node'. */
224 sset_delete(struct sset
*set
, struct sset_node
*node
)
226 hmap_remove(&set
->map
, &node
->hmap_node
);
230 /* Searches for 'name' in 'set'. If found, deletes it and returns true. If
231 * not found, returns false without modifying 'set'. */
233 sset_find_and_delete(struct sset
*set
, const char *name
)
235 struct sset_node
*node
= sset_find(set
, name
);
237 sset_delete(set
, node
);
242 /* Searches for 'name' in 'set' and deletes it. Assert-fails if 'name' is not
245 sset_find_and_delete_assert(struct sset
*set
, const char *name
)
247 ovs_assert(sset_find_and_delete(set
, name
));
250 /* Removes a string from 'set' and returns a copy of it. The caller must free
251 * the returned string (with free()).
253 * 'set' must not be empty.
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. */
259 sset_pop(struct sset
*set
)
261 const char *name
= SSET_FIRST(set
);
262 char *copy
= xstrdup(name
);
263 sset_delete(set
, SSET_NODE_FROM_NAME(name
));
267 /* Searches for 'name' in 'set'. Returns its node, if found, otherwise a null
270 sset_find(const struct sset
*set
, const char *name
)
272 return sset_find__(set
, name
, hash_name(name
));
275 /* Returns true if 'set' contains a copy of 'name', false otherwise. */
277 sset_contains(const struct sset
*set
, const char *name
)
279 return sset_find(set
, name
) != NULL
;
282 /* Returns true if 'a' and 'b' contain the same strings, false otherwise. */
284 sset_equals(const struct sset
*a
, const struct sset
*b
)
286 struct sset_node
*node
;
288 if (sset_count(a
) != sset_count(b
)) {
292 HMAP_FOR_EACH (node
, hmap_node
, &a
->map
) {
293 if (!sset_find__(b
, node
->name
, node
->hmap_node
.hash
)) {
301 /* Returns the next node in 'set' in hash order, or NULL if no nodes remain in
302 * 'set'. Uses '*pos' to determine where to begin iteration, and updates
303 * '*pos' to pass on the next iteration into them before returning.
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.
308 * Before beginning iteration, set '*pos' to all zeros. */
310 sset_at_position(const struct sset
*set
, struct sset_position
*pos
)
312 struct hmap_node
*hmap_node
;
314 hmap_node
= hmap_at_position(&set
->map
, &pos
->pos
);
315 return SSET_NODE_FROM_HMAP_NODE(hmap_node
);
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'. */
321 sset_intersect(struct sset
*a
, const struct sset
*b
)
323 const char *name
, *next
;
325 SSET_FOR_EACH_SAFE (name
, next
, a
) {
326 if (!sset_contains(b
, name
)) {
327 sset_delete(a
, SSET_NODE_FROM_NAME(name
));
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
334 * longer needed, but the strings in the array belong to 'set' and thus must
335 * not be modified or freed. */
337 sset_array(const struct sset
*set
)
339 size_t n
= sset_count(set
);
344 array
= xmalloc(sizeof *array
* (n
+ 1));
346 SSET_FOR_EACH (s
, set
) {
356 compare_string_pointers(const void *a_
, const void *b_
)
358 const char *const *a
= a_
;
359 const char *const *b
= b_
;
361 return strcmp(*a
, *b
);
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. */
369 sset_sort(const struct sset
*set
)
371 const char **array
= sset_array(set
);
372 qsort(array
, sset_count(set
), sizeof *array
, compare_string_pointers
);