]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
37e7f427 | 2 | * Copyright (c) 2009, 2010 Nicira Networks. |
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> | |
18 | #include "shash.h" | |
19 | #include <assert.h> | |
20 | #include "hash.h" | |
21 | ||
1c6d8802 BP |
22 | static struct shash_node *shash_find__(const struct shash *, |
23 | const char *name, size_t hash); | |
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; |
55213fd5 | 111 | node->data = (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); | |
147 | assert(added); | |
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 | ||
159 | node = shash_find__(sh, name, hash); | |
160 | if (!node) { | |
161 | shash_add_nocopy__(sh, xstrdup(name), data, hash); | |
162 | return NULL; | |
163 | } else { | |
164 | void *old_data = node->data; | |
165 | node->data = (void *) data; | |
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 BP |
191 | static struct shash_node * |
192 | shash_find__(const struct shash *sh, const char *name, size_t hash) | |
064af421 BP |
193 | { |
194 | struct shash_node *node; | |
195 | ||
4e8e4213 | 196 | HMAP_FOR_EACH_WITH_HASH (node, node, hash, &sh->map) { |
064af421 BP |
197 | if (!strcmp(node->name, name)) { |
198 | return node; | |
199 | } | |
200 | } | |
201 | return NULL; | |
202 | } | |
203 | ||
1c6d8802 BP |
204 | /* If there are duplicates, returns a random element. */ |
205 | struct shash_node * | |
206 | shash_find(const struct shash *sh, const char *name) | |
207 | { | |
208 | return shash_find__(sh, name, hash_name(name)); | |
209 | } | |
210 | ||
064af421 BP |
211 | void * |
212 | shash_find_data(const struct shash *sh, const char *name) | |
213 | { | |
214 | struct shash_node *node = shash_find(sh, name); | |
215 | return node ? node->data : NULL; | |
216 | } | |
7efc68eb | 217 | |
837e8097 BP |
218 | void * |
219 | shash_find_and_delete(struct shash *sh, const char *name) | |
220 | { | |
221 | struct shash_node *node = shash_find(sh, name); | |
222 | if (node) { | |
223 | void *data = node->data; | |
224 | shash_delete(sh, node); | |
225 | return data; | |
226 | } else { | |
227 | return NULL; | |
228 | } | |
229 | } | |
230 | ||
4a1ee6ae BP |
231 | void * |
232 | shash_find_and_delete_assert(struct shash *sh, const char *name) | |
233 | { | |
234 | void *data = shash_find_and_delete(sh, name); | |
235 | assert(data != NULL); | |
236 | return data; | |
237 | } | |
238 | ||
7efc68eb BP |
239 | struct shash_node * |
240 | shash_first(const struct shash *shash) | |
241 | { | |
242 | struct hmap_node *node = hmap_first(&shash->map); | |
243 | return node ? CONTAINER_OF(node, struct shash_node, node) : NULL; | |
244 | } | |
245 | ||
07423999 BP |
246 | static int |
247 | compare_nodes_by_name(const void *a_, const void *b_) | |
248 | { | |
249 | const struct shash_node *const *a = a_; | |
250 | const struct shash_node *const *b = b_; | |
251 | return strcmp((*a)->name, (*b)->name); | |
252 | } | |
253 | ||
254 | const struct shash_node ** | |
255 | shash_sort(const struct shash *sh) | |
256 | { | |
257 | if (shash_is_empty(sh)) { | |
258 | return NULL; | |
259 | } else { | |
260 | const struct shash_node **nodes; | |
261 | struct shash_node *node; | |
262 | size_t i, n; | |
263 | ||
264 | n = shash_count(sh); | |
265 | nodes = xmalloc(n * sizeof *nodes); | |
266 | i = 0; | |
267 | SHASH_FOR_EACH (node, sh) { | |
268 | nodes[i++] = node; | |
269 | } | |
270 | assert(i == n); | |
271 | ||
272 | qsort(nodes, n, sizeof *nodes, compare_nodes_by_name); | |
273 | ||
274 | return nodes; | |
275 | } | |
276 | } | |
37e7f427 BP |
277 | |
278 | /* Returns true if 'a' and 'b' contain the same keys (regardless of their | |
279 | * values), false otherwise. */ | |
280 | bool | |
281 | shash_equal_keys(const struct shash *a, const struct shash *b) | |
282 | { | |
283 | struct shash_node *node; | |
284 | ||
285 | if (hmap_count(&a->map) != hmap_count(&b->map)) { | |
286 | return false; | |
287 | } | |
288 | SHASH_FOR_EACH (node, a) { | |
289 | if (!shash_find(b, node->name)) { | |
290 | return false; | |
291 | } | |
292 | } | |
293 | return true; | |
294 | } | |
f2f7be86 BP |
295 | |
296 | /* Chooses and returns a randomly selected node from 'sh', which must not be | |
297 | * empty. | |
298 | * | |
299 | * I wouldn't depend on this algorithm to be fair, since I haven't analyzed it. | |
300 | * But it does at least ensure that any node in 'sh' can be chosen. */ | |
301 | struct shash_node * | |
302 | shash_random_node(struct shash *sh) | |
303 | { | |
304 | return CONTAINER_OF(hmap_random_node(&sh->map), struct shash_node, node); | |
305 | } |