]>
git.proxmox.com Git - ovs.git/blob - lib/shash.c
2 * Copyright (c) 2009, 2010, 2011 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.
22 static struct shash_node
*shash_find__(const struct shash
*,
23 const char *name
, size_t name_len
,
27 hash_name(const char *name
)
29 return hash_string(name
, 0);
33 shash_init(struct shash
*sh
)
39 shash_destroy(struct shash
*sh
)
43 hmap_destroy(&sh
->map
);
47 /* Like shash_destroy(), but also free() each node's 'data'. */
49 shash_destroy_free_data(struct shash
*sh
)
52 shash_clear_free_data(sh
);
53 hmap_destroy(&sh
->map
);
58 shash_swap(struct shash
*a
, struct shash
*b
)
60 hmap_swap(&a
->map
, &b
->map
);
64 shash_moved(struct shash
*sh
)
70 shash_clear(struct shash
*sh
)
72 struct shash_node
*node
, *next
;
74 SHASH_FOR_EACH_SAFE (node
, next
, sh
) {
75 hmap_remove(&sh
->map
, &node
->node
);
81 /* Like shash_clear(), but also free() each node's 'data'. */
83 shash_clear_free_data(struct shash
*sh
)
85 struct shash_node
*node
, *next
;
87 SHASH_FOR_EACH_SAFE (node
, next
, sh
) {
88 hmap_remove(&sh
->map
, &node
->node
);
96 shash_is_empty(const struct shash
*shash
)
98 return hmap_is_empty(&shash
->map
);
102 shash_count(const struct shash
*shash
)
104 return hmap_count(&shash
->map
);
107 static struct shash_node
*
108 shash_add_nocopy__(struct shash
*sh
, char *name
, const void *data
, size_t hash
)
110 struct shash_node
*node
= xmalloc(sizeof *node
);
112 node
->data
= (void *) data
;
113 hmap_insert(&sh
->map
, &node
->node
, hash
);
117 /* It is the caller's responsibility to avoid duplicate names, if that is
120 shash_add_nocopy(struct shash
*sh
, char *name
, const void *data
)
122 return shash_add_nocopy__(sh
, name
, data
, hash_name(name
));
125 /* It is the caller's responsibility to avoid duplicate names, if that is
128 shash_add(struct shash
*sh
, const char *name
, const void *data
)
130 return shash_add_nocopy(sh
, xstrdup(name
), data
);
134 shash_add_once(struct shash
*sh
, const char *name
, const void *data
)
136 if (!shash_find(sh
, name
)) {
137 shash_add(sh
, name
, data
);
145 shash_add_assert(struct shash
*sh
, const char *name
, const void *data
)
147 bool added OVS_UNUSED
= shash_add_once(sh
, name
, data
);
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. */
155 shash_replace(struct shash
*sh
, const char *name
, const void *data
)
157 size_t hash
= hash_name(name
);
158 struct shash_node
*node
;
160 node
= shash_find__(sh
, name
, strlen(name
), hash
);
162 shash_add_nocopy__(sh
, xstrdup(name
), data
, hash
);
165 void *old_data
= node
->data
;
166 node
->data
= (void *) data
;
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. */
174 shash_delete(struct shash
*sh
, struct shash_node
*node
)
176 free(shash_steal(sh
, node
));
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
183 shash_steal(struct shash
*sh
, struct shash_node
*node
)
185 char *name
= node
->name
;
187 hmap_remove(&sh
->map
, &node
->node
);
192 static struct shash_node
*
193 shash_find__(const struct shash
*sh
, const char *name
, size_t name_len
,
196 struct shash_node
*node
;
198 HMAP_FOR_EACH_WITH_HASH (node
, node
, hash
, &sh
->map
) {
199 if (!strncmp(node
->name
, name
, name_len
) && !node
->name
[name_len
]) {
206 /* If there are duplicates, returns a random element. */
208 shash_find(const struct shash
*sh
, const char *name
)
210 return shash_find__(sh
, name
, strlen(name
), hash_name(name
));
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. */
216 shash_find_len(const struct shash
*sh
, const char *name
, size_t len
)
218 return shash_find__(sh
, name
, len
, hash_bytes(name
, len
, 0));
222 shash_find_data(const struct shash
*sh
, const char *name
)
224 struct shash_node
*node
= shash_find(sh
, name
);
225 return node
? node
->data
: NULL
;
229 shash_find_and_delete(struct shash
*sh
, const char *name
)
231 struct shash_node
*node
= shash_find(sh
, name
);
233 void *data
= node
->data
;
234 shash_delete(sh
, node
);
242 shash_find_and_delete_assert(struct shash
*sh
, const char *name
)
244 void *data
= shash_find_and_delete(sh
, name
);
245 assert(data
!= NULL
);
250 shash_first(const struct shash
*shash
)
252 struct hmap_node
*node
= hmap_first(&shash
->map
);
253 return node
? CONTAINER_OF(node
, struct shash_node
, node
) : NULL
;
257 compare_nodes_by_name(const void *a_
, const void *b_
)
259 const struct shash_node
*const *a
= a_
;
260 const struct shash_node
*const *b
= b_
;
261 return strcmp((*a
)->name
, (*b
)->name
);
264 const struct shash_node
**
265 shash_sort(const struct shash
*sh
)
267 if (shash_is_empty(sh
)) {
270 const struct shash_node
**nodes
;
271 struct shash_node
*node
;
275 nodes
= xmalloc(n
* sizeof *nodes
);
277 SHASH_FOR_EACH (node
, sh
) {
282 qsort(nodes
, n
, sizeof *nodes
, compare_nodes_by_name
);
288 /* Returns true if 'a' and 'b' contain the same keys (regardless of their
289 * values), false otherwise. */
291 shash_equal_keys(const struct shash
*a
, const struct shash
*b
)
293 struct shash_node
*node
;
295 if (hmap_count(&a
->map
) != hmap_count(&b
->map
)) {
298 SHASH_FOR_EACH (node
, a
) {
299 if (!shash_find(b
, node
->name
)) {
306 /* Chooses and returns a randomly selected node from 'sh', which must not be
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. */
312 shash_random_node(struct shash
*sh
)
314 return CONTAINER_OF(hmap_random_node(&sh
->map
), struct shash_node
, node
);
317 /* String-to-string maps (smaps). */
319 /* Frees 'smap', including its keys and string values. */
321 smap_destroy(struct shash
*smap
)
323 shash_destroy_free_data(smap
);
326 /* Returns true if string-to-string maps 'a' and 'b' contain the same keys and
327 * values, false otherwise. */
329 smap_equal(const struct shash
*a
, const struct shash
*b
)
331 struct shash_node
*a_node
;
333 if (shash_count(a
) != shash_count(b
)) {
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
)) {
349 /* Initializes 'dst' as a clone of 'src'. */
351 smap_clone(struct shash
*dst
, const struct shash
*src
)
353 struct shash_node
*node
;
356 SHASH_FOR_EACH (node
, src
) {
357 shash_add_nocopy__(dst
, xstrdup(node
->name
), xstrdup(node
->data
),
362 /* Adds 'key' with string 'value' to 'smap', making a copy of each.
364 * It is the caller's responsibility to avoid duplicate names, if that is
367 smap_add(struct shash
*smap
, const char *key
, const char *value
)
369 shash_add(smap
, key
, xstrdup(value
));