]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
ebc56baa | 2 | * Copyright (c) 2009, 2010, 2011, 2012 Nicira, Inc. |
064af421 | 3 | * |
a14bc59f BP |
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: | |
064af421 | 7 | * |
a14bc59f BP |
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. | |
064af421 BP |
15 | */ |
16 | ||
17 | #include <config.h> | |
ee89ea7b | 18 | #include "openvswitch/shash.h" |
064af421 BP |
19 | #include "hash.h" |
20 | ||
1c6d8802 | 21 | static struct shash_node *shash_find__(const struct shash *, |
e74a239d BP |
22 | const char *name, size_t name_len, |
23 | size_t hash); | |
1c6d8802 | 24 | |
064af421 BP |
25 | static size_t |
26 | hash_name(const char *name) | |
27 | { | |
28 | return hash_string(name, 0); | |
29 | } | |
30 | ||
31 | void | |
32 | shash_init(struct shash *sh) | |
33 | { | |
34 | hmap_init(&sh->map); | |
35 | } | |
36 | ||
37 | void | |
38 | shash_destroy(struct shash *sh) | |
39 | { | |
40 | if (sh) { | |
41 | shash_clear(sh); | |
d855aead | 42 | hmap_destroy(&sh->map); |
064af421 BP |
43 | } |
44 | } | |
45 | ||
a90b56b7 BP |
46 | /* Like shash_destroy(), but also free() each node's 'data'. */ |
47 | void | |
48 | shash_destroy_free_data(struct shash *sh) | |
49 | { | |
50 | if (sh) { | |
51 | shash_clear_free_data(sh); | |
52 | hmap_destroy(&sh->map); | |
53 | } | |
54 | } | |
55 | ||
37e7f427 BP |
56 | void |
57 | shash_swap(struct shash *a, struct shash *b) | |
58 | { | |
59 | hmap_swap(&a->map, &b->map); | |
60 | } | |
61 | ||
baa8f41b BP |
62 | void |
63 | shash_moved(struct shash *sh) | |
64 | { | |
65 | hmap_moved(&sh->map); | |
66 | } | |
67 | ||
064af421 BP |
68 | void |
69 | shash_clear(struct shash *sh) | |
70 | { | |
71 | struct shash_node *node, *next; | |
72 | ||
fd30311c | 73 | SHASH_FOR_EACH_SAFE (node, next, sh) { |
064af421 BP |
74 | hmap_remove(&sh->map, &node->node); |
75 | free(node->name); | |
76 | free(node); | |
77 | } | |
78 | } | |
79 | ||
a90b56b7 BP |
80 | /* Like shash_clear(), but also free() each node's 'data'. */ |
81 | void | |
82 | shash_clear_free_data(struct shash *sh) | |
83 | { | |
84 | struct shash_node *node, *next; | |
85 | ||
86 | SHASH_FOR_EACH_SAFE (node, next, sh) { | |
87 | hmap_remove(&sh->map, &node->node); | |
88 | free(node->data); | |
89 | free(node->name); | |
90 | free(node); | |
91 | } | |
92 | } | |
93 | ||
732dcb37 BP |
94 | bool |
95 | shash_is_empty(const struct shash *shash) | |
96 | { | |
97 | return hmap_is_empty(&shash->map); | |
98 | } | |
99 | ||
c01da229 BP |
100 | size_t |
101 | shash_count(const struct shash *shash) | |
102 | { | |
103 | return hmap_count(&shash->map); | |
104 | } | |
105 | ||
1c6d8802 BP |
106 | static struct shash_node * |
107 | shash_add_nocopy__(struct shash *sh, char *name, const void *data, size_t hash) | |
064af421 BP |
108 | { |
109 | struct shash_node *node = xmalloc(sizeof *node); | |
ce5a3e38 | 110 | node->name = name; |
ebc56baa | 111 | node->data = CONST_CAST(void *, data); |
1c6d8802 | 112 | hmap_insert(&sh->map, &node->node, hash); |
78299b0a | 113 | return node; |
064af421 BP |
114 | } |
115 | ||
1c6d8802 BP |
116 | /* It is the caller's responsibility to avoid duplicate names, if that is |
117 | * desirable. */ | |
118 | struct shash_node * | |
119 | shash_add_nocopy(struct shash *sh, char *name, const void *data) | |
120 | { | |
121 | return shash_add_nocopy__(sh, name, data, hash_name(name)); | |
122 | } | |
123 | ||
ce5a3e38 BP |
124 | /* It is the caller's responsibility to avoid duplicate names, if that is |
125 | * desirable. */ | |
126 | struct shash_node * | |
127 | shash_add(struct shash *sh, const char *name, const void *data) | |
128 | { | |
129 | return shash_add_nocopy(sh, xstrdup(name), data); | |
130 | } | |
131 | ||
76343538 BP |
132 | bool |
133 | shash_add_once(struct shash *sh, const char *name, const void *data) | |
134 | { | |
135 | if (!shash_find(sh, name)) { | |
136 | shash_add(sh, name, data); | |
137 | return true; | |
138 | } else { | |
139 | return false; | |
140 | } | |
141 | } | |
142 | ||
4a1ee6ae BP |
143 | void |
144 | shash_add_assert(struct shash *sh, const char *name, const void *data) | |
145 | { | |
146 | bool added OVS_UNUSED = shash_add_once(sh, name, data); | |
cb22974d | 147 | ovs_assert(added); |
4a1ee6ae BP |
148 | } |
149 | ||
79903dd1 BP |
150 | /* Searches for 'name' in 'sh'. If it does not already exist, adds it along |
151 | * with 'data' and returns NULL. If it does already exist, replaces its data | |
152 | * by 'data' and returns the data that it formerly contained. */ | |
153 | void * | |
154 | shash_replace(struct shash *sh, const char *name, const void *data) | |
155 | { | |
156 | size_t hash = hash_name(name); | |
157 | struct shash_node *node; | |
158 | ||
e74a239d | 159 | node = shash_find__(sh, name, strlen(name), hash); |
79903dd1 BP |
160 | if (!node) { |
161 | shash_add_nocopy__(sh, xstrdup(name), data, hash); | |
162 | return NULL; | |
163 | } else { | |
164 | void *old_data = node->data; | |
ebc56baa | 165 | node->data = CONST_CAST(void *, data); |
79903dd1 BP |
166 | return old_data; |
167 | } | |
168 | } | |
169 | ||
4f222648 BP |
170 | /* Deletes 'node' from 'sh' and frees the node's name. The caller is still |
171 | * responsible for freeing the node's data, if necessary. */ | |
064af421 BP |
172 | void |
173 | shash_delete(struct shash *sh, struct shash_node *node) | |
174 | { | |
4f222648 BP |
175 | free(shash_steal(sh, node)); |
176 | } | |
177 | ||
178 | /* Deletes 'node' from 'sh'. Neither the node's name nor its data is freed; | |
179 | * instead, ownership is transferred to the caller. Returns the node's | |
180 | * name. */ | |
181 | char * | |
182 | shash_steal(struct shash *sh, struct shash_node *node) | |
183 | { | |
184 | char *name = node->name; | |
185 | ||
064af421 | 186 | hmap_remove(&sh->map, &node->node); |
064af421 | 187 | free(node); |
4f222648 | 188 | return name; |
064af421 BP |
189 | } |
190 | ||
1c6d8802 | 191 | static struct shash_node * |
e74a239d BP |
192 | shash_find__(const struct shash *sh, const char *name, size_t name_len, |
193 | size_t hash) | |
064af421 BP |
194 | { |
195 | struct shash_node *node; | |
196 | ||
4e8e4213 | 197 | HMAP_FOR_EACH_WITH_HASH (node, node, hash, &sh->map) { |
e74a239d | 198 | if (!strncmp(node->name, name, name_len) && !node->name[name_len]) { |
064af421 BP |
199 | return node; |
200 | } | |
201 | } | |
202 | return NULL; | |
203 | } | |
204 | ||
1c6d8802 BP |
205 | /* If there are duplicates, returns a random element. */ |
206 | struct shash_node * | |
207 | shash_find(const struct shash *sh, const char *name) | |
208 | { | |
e74a239d BP |
209 | return shash_find__(sh, name, strlen(name), hash_name(name)); |
210 | } | |
211 | ||
212 | /* Finds and returns a shash_node within 'sh' that has the given 'name' that is | |
213 | * exactly 'len' bytes long. Returns NULL if no node in 'sh' has that name. */ | |
214 | struct shash_node * | |
215 | shash_find_len(const struct shash *sh, const char *name, size_t len) | |
216 | { | |
217 | return shash_find__(sh, name, len, hash_bytes(name, len, 0)); | |
1c6d8802 BP |
218 | } |
219 | ||
064af421 BP |
220 | void * |
221 | shash_find_data(const struct shash *sh, const char *name) | |
222 | { | |
223 | struct shash_node *node = shash_find(sh, name); | |
224 | return node ? node->data : NULL; | |
225 | } | |
7efc68eb | 226 | |
837e8097 BP |
227 | void * |
228 | shash_find_and_delete(struct shash *sh, const char *name) | |
229 | { | |
230 | struct shash_node *node = shash_find(sh, name); | |
231 | if (node) { | |
232 | void *data = node->data; | |
233 | shash_delete(sh, node); | |
234 | return data; | |
235 | } else { | |
236 | return NULL; | |
237 | } | |
238 | } | |
239 | ||
4a1ee6ae BP |
240 | void * |
241 | shash_find_and_delete_assert(struct shash *sh, const char *name) | |
242 | { | |
243 | void *data = shash_find_and_delete(sh, name); | |
cb22974d | 244 | ovs_assert(data != NULL); |
4a1ee6ae BP |
245 | return data; |
246 | } | |
247 | ||
7efc68eb BP |
248 | struct shash_node * |
249 | shash_first(const struct shash *shash) | |
250 | { | |
251 | struct hmap_node *node = hmap_first(&shash->map); | |
252 | return node ? CONTAINER_OF(node, struct shash_node, node) : NULL; | |
253 | } | |
254 | ||
07423999 BP |
255 | static int |
256 | compare_nodes_by_name(const void *a_, const void *b_) | |
257 | { | |
258 | const struct shash_node *const *a = a_; | |
259 | const struct shash_node *const *b = b_; | |
260 | return strcmp((*a)->name, (*b)->name); | |
261 | } | |
262 | ||
263 | const struct shash_node ** | |
264 | shash_sort(const struct shash *sh) | |
265 | { | |
266 | if (shash_is_empty(sh)) { | |
267 | return NULL; | |
268 | } else { | |
269 | const struct shash_node **nodes; | |
270 | struct shash_node *node; | |
271 | size_t i, n; | |
272 | ||
273 | n = shash_count(sh); | |
274 | nodes = xmalloc(n * sizeof *nodes); | |
275 | i = 0; | |
276 | SHASH_FOR_EACH (node, sh) { | |
277 | nodes[i++] = node; | |
278 | } | |
cb22974d | 279 | ovs_assert(i == n); |
07423999 BP |
280 | |
281 | qsort(nodes, n, sizeof *nodes, compare_nodes_by_name); | |
282 | ||
283 | return nodes; | |
284 | } | |
285 | } | |
37e7f427 BP |
286 | |
287 | /* Returns true if 'a' and 'b' contain the same keys (regardless of their | |
288 | * values), false otherwise. */ | |
289 | bool | |
290 | shash_equal_keys(const struct shash *a, const struct shash *b) | |
291 | { | |
292 | struct shash_node *node; | |
293 | ||
294 | if (hmap_count(&a->map) != hmap_count(&b->map)) { | |
295 | return false; | |
296 | } | |
297 | SHASH_FOR_EACH (node, a) { | |
298 | if (!shash_find(b, node->name)) { | |
299 | return false; | |
300 | } | |
301 | } | |
302 | return true; | |
303 | } | |
f2f7be86 BP |
304 | |
305 | /* Chooses and returns a randomly selected node from 'sh', which must not be | |
306 | * empty. | |
307 | * | |
308 | * I wouldn't depend on this algorithm to be fair, since I haven't analyzed it. | |
309 | * But it does at least ensure that any node in 'sh' can be chosen. */ | |
310 | struct shash_node * | |
311 | shash_random_node(struct shash *sh) | |
312 | { | |
313 | return CONTAINER_OF(hmap_random_node(&sh->map), struct shash_node, node); | |
314 | } |