ovs-vswitchd: Get rid of call to process_init().
[sliver-openvswitch.git] / lib / sset.c
1 /*
2  * Copyright (c) 2011, 2012, 2013 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 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);
148     ovs_assert(added);
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);
199     ovs_assert(deleted);
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 }
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 }
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 }