]>
git.proxmox.com Git - mirror_ovs.git/blob - lib/shash.c
2 * Copyright (c) 2009, 2010, 2011, 2012 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.
18 #include "openvswitch/shash.h"
21 static struct shash_node
*shash_find__(const struct shash
*,
22 const char *name
, size_t name_len
,
26 hash_name(const char *name
)
28 return hash_string(name
, 0);
32 shash_init(struct shash
*sh
)
38 shash_destroy(struct shash
*sh
)
42 hmap_destroy(&sh
->map
);
46 /* Like shash_destroy(), but also free() each node's 'data'. */
48 shash_destroy_free_data(struct shash
*sh
)
51 shash_clear_free_data(sh
);
52 hmap_destroy(&sh
->map
);
57 shash_swap(struct shash
*a
, struct shash
*b
)
59 hmap_swap(&a
->map
, &b
->map
);
63 shash_moved(struct shash
*sh
)
69 shash_clear(struct shash
*sh
)
71 struct shash_node
*node
, *next
;
73 SHASH_FOR_EACH_SAFE (node
, next
, sh
) {
74 hmap_remove(&sh
->map
, &node
->node
);
80 /* Like shash_clear(), but also free() each node's 'data'. */
82 shash_clear_free_data(struct shash
*sh
)
84 struct shash_node
*node
, *next
;
86 SHASH_FOR_EACH_SAFE (node
, next
, sh
) {
87 hmap_remove(&sh
->map
, &node
->node
);
95 shash_is_empty(const struct shash
*shash
)
97 return hmap_is_empty(&shash
->map
);
101 shash_count(const struct shash
*shash
)
103 return hmap_count(&shash
->map
);
106 static struct shash_node
*
107 shash_add_nocopy__(struct shash
*sh
, char *name
, const void *data
, size_t hash
)
109 struct shash_node
*node
= xmalloc(sizeof *node
);
111 node
->data
= CONST_CAST(void *, data
);
112 hmap_insert(&sh
->map
, &node
->node
, hash
);
116 /* It is the caller's responsibility to avoid duplicate names, if that is
119 shash_add_nocopy(struct shash
*sh
, char *name
, const void *data
)
121 return shash_add_nocopy__(sh
, name
, data
, hash_name(name
));
124 /* It is the caller's responsibility to avoid duplicate names, if that is
127 shash_add(struct shash
*sh
, const char *name
, const void *data
)
129 return shash_add_nocopy(sh
, xstrdup(name
), data
);
133 shash_add_once(struct shash
*sh
, const char *name
, const void *data
)
135 if (!shash_find(sh
, name
)) {
136 shash_add(sh
, name
, data
);
144 shash_add_assert(struct shash
*sh
, const char *name
, const void *data
)
146 bool added OVS_UNUSED
= shash_add_once(sh
, name
, data
);
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. */
154 shash_replace(struct shash
*sh
, const char *name
, const void *data
)
156 size_t hash
= hash_name(name
);
157 struct shash_node
*node
;
159 node
= shash_find__(sh
, name
, strlen(name
), hash
);
161 shash_add_nocopy__(sh
, xstrdup(name
), data
, hash
);
164 void *old_data
= node
->data
;
165 node
->data
= CONST_CAST(void *, data
);
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. */
173 shash_delete(struct shash
*sh
, struct shash_node
*node
)
175 free(shash_steal(sh
, node
));
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
182 shash_steal(struct shash
*sh
, struct shash_node
*node
)
184 char *name
= node
->name
;
186 hmap_remove(&sh
->map
, &node
->node
);
191 static struct shash_node
*
192 shash_find__(const struct shash
*sh
, const char *name
, size_t name_len
,
195 struct shash_node
*node
;
197 HMAP_FOR_EACH_WITH_HASH (node
, node
, hash
, &sh
->map
) {
198 if (!strncmp(node
->name
, name
, name_len
) && !node
->name
[name_len
]) {
205 /* If there are duplicates, returns a random element. */
207 shash_find(const struct shash
*sh
, const char *name
)
209 return shash_find__(sh
, name
, strlen(name
), hash_name(name
));
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. */
215 shash_find_len(const struct shash
*sh
, const char *name
, size_t len
)
217 return shash_find__(sh
, name
, len
, hash_bytes(name
, len
, 0));
221 shash_find_data(const struct shash
*sh
, const char *name
)
223 struct shash_node
*node
= shash_find(sh
, name
);
224 return node
? node
->data
: NULL
;
228 shash_find_and_delete(struct shash
*sh
, const char *name
)
230 struct shash_node
*node
= shash_find(sh
, name
);
232 void *data
= node
->data
;
233 shash_delete(sh
, node
);
241 shash_find_and_delete_assert(struct shash
*sh
, const char *name
)
243 void *data
= shash_find_and_delete(sh
, name
);
244 ovs_assert(data
!= NULL
);
249 shash_first(const struct shash
*shash
)
251 struct hmap_node
*node
= hmap_first(&shash
->map
);
252 return node
? CONTAINER_OF(node
, struct shash_node
, node
) : NULL
;
256 compare_nodes_by_name(const void *a_
, const void *b_
)
258 const struct shash_node
*const *a
= a_
;
259 const struct shash_node
*const *b
= b_
;
260 return strcmp((*a
)->name
, (*b
)->name
);
263 const struct shash_node
**
264 shash_sort(const struct shash
*sh
)
266 if (shash_is_empty(sh
)) {
269 const struct shash_node
**nodes
;
270 struct shash_node
*node
;
274 nodes
= xmalloc(n
* sizeof *nodes
);
276 SHASH_FOR_EACH (node
, sh
) {
281 qsort(nodes
, n
, sizeof *nodes
, compare_nodes_by_name
);
287 /* Returns true if 'a' and 'b' contain the same keys (regardless of their
288 * values), false otherwise. */
290 shash_equal_keys(const struct shash
*a
, const struct shash
*b
)
292 struct shash_node
*node
;
294 if (hmap_count(&a
->map
) != hmap_count(&b
->map
)) {
297 SHASH_FOR_EACH (node
, a
) {
298 if (!shash_find(b
, node
->name
)) {
305 /* Chooses and returns a randomly selected node from 'sh', which must not be
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. */
311 shash_random_node(struct shash
*sh
)
313 return CONTAINER_OF(hmap_random_node(&sh
->map
), struct shash_node
, node
);