ofproto-dpif: Factor out VLAN splinter flow adjustment into new function.
[openvswitch] / lib / shash.c
1 /*
2  * Copyright (c) 2009, 2010, 2011 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 #include "shash.h"
19 #include <assert.h>
20 #include "hash.h"
21
22 static struct shash_node *shash_find__(const struct shash *,
23                                        const char *name, size_t name_len,
24                                        size_t hash);
25
26 static size_t
27 hash_name(const char *name)
28 {
29     return hash_string(name, 0);
30 }
31
32 void
33 shash_init(struct shash *sh)
34 {
35     hmap_init(&sh->map);
36 }
37
38 void
39 shash_destroy(struct shash *sh)
40 {
41     if (sh) {
42         shash_clear(sh);
43         hmap_destroy(&sh->map);
44     }
45 }
46
47 /* Like shash_destroy(), but also free() each node's 'data'. */
48 void
49 shash_destroy_free_data(struct shash *sh)
50 {
51     if (sh) {
52         shash_clear_free_data(sh);
53         hmap_destroy(&sh->map);
54     }
55 }
56
57 void
58 shash_swap(struct shash *a, struct shash *b)
59 {
60     hmap_swap(&a->map, &b->map);
61 }
62
63 void
64 shash_moved(struct shash *sh)
65 {
66     hmap_moved(&sh->map);
67 }
68
69 void
70 shash_clear(struct shash *sh)
71 {
72     struct shash_node *node, *next;
73
74     SHASH_FOR_EACH_SAFE (node, next, sh) {
75         hmap_remove(&sh->map, &node->node);
76         free(node->name);
77         free(node);
78     }
79 }
80
81 /* Like shash_clear(), but also free() each node's 'data'. */
82 void
83 shash_clear_free_data(struct shash *sh)
84 {
85     struct shash_node *node, *next;
86
87     SHASH_FOR_EACH_SAFE (node, next, sh) {
88         hmap_remove(&sh->map, &node->node);
89         free(node->data);
90         free(node->name);
91         free(node);
92     }
93 }
94
95 bool
96 shash_is_empty(const struct shash *shash)
97 {
98     return hmap_is_empty(&shash->map);
99 }
100
101 size_t
102 shash_count(const struct shash *shash)
103 {
104     return hmap_count(&shash->map);
105 }
106
107 static struct shash_node *
108 shash_add_nocopy__(struct shash *sh, char *name, const void *data, size_t hash)
109 {
110     struct shash_node *node = xmalloc(sizeof *node);
111     node->name = name;
112     node->data = (void *) data;
113     hmap_insert(&sh->map, &node->node, hash);
114     return node;
115 }
116
117 /* It is the caller's responsibility to avoid duplicate names, if that is
118  * desirable. */
119 struct shash_node *
120 shash_add_nocopy(struct shash *sh, char *name, const void *data)
121 {
122     return shash_add_nocopy__(sh, name, data, hash_name(name));
123 }
124
125 /* It is the caller's responsibility to avoid duplicate names, if that is
126  * desirable. */
127 struct shash_node *
128 shash_add(struct shash *sh, const char *name, const void *data)
129 {
130     return shash_add_nocopy(sh, xstrdup(name), data);
131 }
132
133 bool
134 shash_add_once(struct shash *sh, const char *name, const void *data)
135 {
136     if (!shash_find(sh, name)) {
137         shash_add(sh, name, data);
138         return true;
139     } else {
140         return false;
141     }
142 }
143
144 void
145 shash_add_assert(struct shash *sh, const char *name, const void *data)
146 {
147     bool added OVS_UNUSED = shash_add_once(sh, name, data);
148     assert(added);
149 }
150
151 /* Searches for 'name' in 'sh'.  If it does not already exist, adds it along
152  * with 'data' and returns NULL.  If it does already exist, replaces its data
153  * by 'data' and returns the data that it formerly contained. */
154 void *
155 shash_replace(struct shash *sh, const char *name, const void *data)
156 {
157     size_t hash = hash_name(name);
158     struct shash_node *node;
159
160     node = shash_find__(sh, name, strlen(name), hash);
161     if (!node) {
162         shash_add_nocopy__(sh, xstrdup(name), data, hash);
163         return NULL;
164     } else {
165         void *old_data = node->data;
166         node->data = (void *) data;
167         return old_data;
168     }
169 }
170
171 /* Deletes 'node' from 'sh' and frees the node's name.  The caller is still
172  * responsible for freeing the node's data, if necessary. */
173 void
174 shash_delete(struct shash *sh, struct shash_node *node)
175 {
176     free(shash_steal(sh, node));
177 }
178
179 /* Deletes 'node' from 'sh'.  Neither the node's name nor its data is freed;
180  * instead, ownership is transferred to the caller.  Returns the node's
181  * name. */
182 char *
183 shash_steal(struct shash *sh, struct shash_node *node)
184 {
185     char *name = node->name;
186
187     hmap_remove(&sh->map, &node->node);
188     free(node);
189     return name;
190 }
191
192 static struct shash_node *
193 shash_find__(const struct shash *sh, const char *name, size_t name_len,
194              size_t hash)
195 {
196     struct shash_node *node;
197
198     HMAP_FOR_EACH_WITH_HASH (node, node, hash, &sh->map) {
199         if (!strncmp(node->name, name, name_len) && !node->name[name_len]) {
200             return node;
201         }
202     }
203     return NULL;
204 }
205
206 /* If there are duplicates, returns a random element. */
207 struct shash_node *
208 shash_find(const struct shash *sh, const char *name)
209 {
210     return shash_find__(sh, name, strlen(name), hash_name(name));
211 }
212
213 /* Finds and returns a shash_node within 'sh' that has the given 'name' that is
214  * exactly 'len' bytes long.  Returns NULL if no node in 'sh' has that name. */
215 struct shash_node *
216 shash_find_len(const struct shash *sh, const char *name, size_t len)
217 {
218     return shash_find__(sh, name, len, hash_bytes(name, len, 0));
219 }
220
221 void *
222 shash_find_data(const struct shash *sh, const char *name)
223 {
224     struct shash_node *node = shash_find(sh, name);
225     return node ? node->data : NULL;
226 }
227
228 void *
229 shash_find_and_delete(struct shash *sh, const char *name)
230 {
231     struct shash_node *node = shash_find(sh, name);
232     if (node) {
233         void *data = node->data;
234         shash_delete(sh, node);
235         return data;
236     } else {
237         return NULL;
238     }
239 }
240
241 void *
242 shash_find_and_delete_assert(struct shash *sh, const char *name)
243 {
244     void *data = shash_find_and_delete(sh, name);
245     assert(data != NULL);
246     return data;
247 }
248
249 struct shash_node *
250 shash_first(const struct shash *shash)
251 {
252     struct hmap_node *node = hmap_first(&shash->map);
253     return node ? CONTAINER_OF(node, struct shash_node, node) : NULL;
254 }
255
256 static int
257 compare_nodes_by_name(const void *a_, const void *b_)
258 {
259     const struct shash_node *const *a = a_;
260     const struct shash_node *const *b = b_;
261     return strcmp((*a)->name, (*b)->name);
262 }
263
264 const struct shash_node **
265 shash_sort(const struct shash *sh)
266 {
267     if (shash_is_empty(sh)) {
268         return NULL;
269     } else {
270         const struct shash_node **nodes;
271         struct shash_node *node;
272         size_t i, n;
273
274         n = shash_count(sh);
275         nodes = xmalloc(n * sizeof *nodes);
276         i = 0;
277         SHASH_FOR_EACH (node, sh) {
278             nodes[i++] = node;
279         }
280         assert(i == n);
281
282         qsort(nodes, n, sizeof *nodes, compare_nodes_by_name);
283
284         return nodes;
285     }
286 }
287
288 /* Returns true if 'a' and 'b' contain the same keys (regardless of their
289  * values), false otherwise. */
290 bool
291 shash_equal_keys(const struct shash *a, const struct shash *b)
292 {
293     struct shash_node *node;
294
295     if (hmap_count(&a->map) != hmap_count(&b->map)) {
296         return false;
297     }
298     SHASH_FOR_EACH (node, a) {
299         if (!shash_find(b, node->name)) {
300             return false;
301         }
302     }
303     return true;
304 }
305
306 /* Chooses and returns a randomly selected node from 'sh', which must not be
307  * empty.
308  *
309  * I wouldn't depend on this algorithm to be fair, since I haven't analyzed it.
310  * But it does at least ensure that any node in 'sh' can be chosen. */
311 struct shash_node *
312 shash_random_node(struct shash *sh)
313 {
314     return CONTAINER_OF(hmap_random_node(&sh->map), struct shash_node, node);
315 }
316 \f
317 /* String-to-string maps (smaps). */
318
319 /* Frees 'smap', including its keys and string values. */
320 void
321 smap_destroy(struct shash *smap)
322 {
323     shash_destroy_free_data(smap);
324 }
325
326 /* Returns true if string-to-string maps 'a' and 'b' contain the same keys and
327  * values, false otherwise. */
328 bool
329 smap_equal(const struct shash *a, const struct shash *b)
330 {
331     struct shash_node *a_node;
332
333     if (shash_count(a) != shash_count(b)) {
334         return false;
335     }
336
337     SHASH_FOR_EACH (a_node, a) {
338         uint32_t hash = a_node->node.hash;
339         size_t len = strlen(a_node->name);
340         struct shash_node *b_node = shash_find__(b, a_node->name, len, hash);
341         if (!b_node || strcmp(a_node->data, b_node->data)) {
342             return false;
343         }
344     }
345
346     return true;
347 }
348
349 /* Initializes 'dst' as a clone of 'src'. */
350 void
351 smap_clone(struct shash *dst, const struct shash *src)
352 {
353     struct shash_node *node;
354
355     shash_init(dst);
356     SHASH_FOR_EACH (node, src) {
357         shash_add_nocopy__(dst, xstrdup(node->name), xstrdup(node->data),
358                            node->node.hash);
359     }
360 }
361
362 /* Adds 'key' with string 'value' to 'smap', making a copy of each.
363  *
364  * It is the caller's responsibility to avoid duplicate names, if that is
365  * desirable. */
366 void
367 smap_add(struct shash *smap, const char *key, const char *value)
368 {
369     shash_add(smap, key, xstrdup(value));
370 }