]>
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 ovs_assert(shash_add_once(sh
, name
, data
));
149 /* Searches for 'name' in 'sh'. If it does not already exist, adds it along
150 * with 'data' and returns NULL. If it does already exist, replaces its data
151 * by 'data' and returns the data that it formerly contained. */
153 shash_replace(struct shash
*sh
, const char *name
, const void *data
)
155 size_t hash
= hash_name(name
);
156 struct shash_node
*node
;
158 node
= shash_find__(sh
, name
, strlen(name
), hash
);
160 shash_add_nocopy__(sh
, xstrdup(name
), data
, hash
);
163 void *old_data
= node
->data
;
164 node
->data
= CONST_CAST(void *, data
);
169 /* Searches for 'name' in 'sh'. If it does not already exist, adds it along
170 * with 'data' and returns NULL. If it does already exist, replaces its data
171 * by 'data' and returns the data that it formerly contained.
173 * Takes ownership of 'name'. */
175 shash_replace_nocopy(struct shash
*sh
, char *name
, const void *data
)
177 size_t hash
= hash_name(name
);
178 struct shash_node
*node
;
180 node
= shash_find__(sh
, name
, strlen(name
), hash
);
182 shash_add_nocopy__(sh
, name
, data
, hash
);
186 void *old_data
= node
->data
;
187 node
->data
= CONST_CAST(void *, data
);
192 /* Deletes 'node' from 'sh' and frees the node's name. The caller is still
193 * responsible for freeing the node's data, if necessary. */
195 shash_delete(struct shash
*sh
, struct shash_node
*node
)
197 free(shash_steal(sh
, node
));
200 /* Deletes 'node' from 'sh'. Neither the node's name nor its data is freed;
201 * instead, ownership is transferred to the caller. Returns the node's
204 shash_steal(struct shash
*sh
, struct shash_node
*node
)
206 char *name
= node
->name
;
208 hmap_remove(&sh
->map
, &node
->node
);
213 static struct shash_node
*
214 shash_find__(const struct shash
*sh
, const char *name
, size_t name_len
,
217 struct shash_node
*node
;
219 HMAP_FOR_EACH_WITH_HASH (node
, node
, hash
, &sh
->map
) {
220 if (!strncmp(node
->name
, name
, name_len
) && !node
->name
[name_len
]) {
227 /* If there are duplicates, returns a random element. */
229 shash_find(const struct shash
*sh
, const char *name
)
231 return shash_find__(sh
, name
, strlen(name
), hash_name(name
));
234 /* Finds and returns a shash_node within 'sh' that has the given 'name' that is
235 * exactly 'len' bytes long. Returns NULL if no node in 'sh' has that name. */
237 shash_find_len(const struct shash
*sh
, const char *name
, size_t len
)
239 return shash_find__(sh
, name
, len
, hash_bytes(name
, len
, 0));
243 shash_find_data(const struct shash
*sh
, const char *name
)
245 struct shash_node
*node
= shash_find(sh
, name
);
246 return node
? node
->data
: NULL
;
250 shash_find_and_delete(struct shash
*sh
, const char *name
)
252 struct shash_node
*node
= shash_find(sh
, name
);
254 void *data
= node
->data
;
255 shash_delete(sh
, node
);
263 shash_find_and_delete_assert(struct shash
*sh
, const char *name
)
265 void *data
= shash_find_and_delete(sh
, name
);
266 ovs_assert(data
!= NULL
);
271 shash_first(const struct shash
*shash
)
273 struct hmap_node
*node
= hmap_first(&shash
->map
);
274 return node
? CONTAINER_OF(node
, struct shash_node
, node
) : NULL
;
278 compare_nodes_by_name(const void *a_
, const void *b_
)
280 const struct shash_node
*const *a
= a_
;
281 const struct shash_node
*const *b
= b_
;
282 return strcmp((*a
)->name
, (*b
)->name
);
285 const struct shash_node
**
286 shash_sort(const struct shash
*sh
)
288 if (shash_is_empty(sh
)) {
291 const struct shash_node
**nodes
;
292 struct shash_node
*node
;
296 nodes
= xmalloc(n
* sizeof *nodes
);
298 SHASH_FOR_EACH (node
, sh
) {
303 qsort(nodes
, n
, sizeof *nodes
, compare_nodes_by_name
);
309 /* Returns true if 'a' and 'b' contain the same keys (regardless of their
310 * values), false otherwise. */
312 shash_equal_keys(const struct shash
*a
, const struct shash
*b
)
314 struct shash_node
*node
;
316 if (hmap_count(&a
->map
) != hmap_count(&b
->map
)) {
319 SHASH_FOR_EACH (node
, a
) {
320 if (!shash_find(b
, node
->name
)) {
327 /* Chooses and returns a randomly selected node from 'sh', which must not be
330 * I wouldn't depend on this algorithm to be fair, since I haven't analyzed it.
331 * But it does at least ensure that any node in 'sh' can be chosen. */
333 shash_random_node(struct shash
*sh
)
335 return CONTAINER_OF(hmap_random_node(&sh
->map
), struct shash_node
, node
);