]>
git.proxmox.com Git - mirror_ovs.git/blob - lib/simap.c
2 * Copyright (c) 2009, 2010, 2011, 2012, 2017 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.
21 static size_t hash_name(const char *, size_t length
);
22 static struct simap_node
*simap_find__(const struct simap
*,
23 const char *name
, size_t name_len
,
25 static struct simap_node
*simap_add_nocopy__(struct simap
*,
26 char *name
, unsigned int data
,
28 static int compare_nodes_by_name(const void *a_
, const void *b_
);
30 /* Initializes 'simap' as an empty string-to-integer map. */
32 simap_init(struct simap
*simap
)
34 hmap_init(&simap
->map
);
37 /* Frees all the data that 'simap' contains. */
39 simap_destroy(struct simap
*simap
)
43 hmap_destroy(&simap
->map
);
47 /* Exchanges the contents of 'a' and 'b'. */
49 simap_swap(struct simap
*a
, struct simap
*b
)
51 hmap_swap(&a
->map
, &b
->map
);
54 /* Adjusts 'simap' so that it is still valid after it has been moved around in
55 * memory (e.g. due to realloc()). */
57 simap_moved(struct simap
*simap
)
59 hmap_moved(&simap
->map
);
62 /* Removes all of the mappings from 'simap' and frees them. */
64 simap_clear(struct simap
*simap
)
66 struct simap_node
*node
, *next
;
68 SIMAP_FOR_EACH_SAFE (node
, next
, simap
) {
69 hmap_remove(&simap
->map
, &node
->node
);
75 /* Returns true if 'simap' contains no mappings, false if it contains at least
78 simap_is_empty(const struct simap
*simap
)
80 return hmap_is_empty(&simap
->map
);
83 /* Returns the number of mappings in 'simap'. */
85 simap_count(const struct simap
*simap
)
87 return hmap_count(&simap
->map
);
90 /* Inserts a mapping from 'name' to 'data' into 'simap', replacing any
91 * existing mapping for 'name'. Returns true if a new mapping was added,
92 * false if an existing mapping's value was replaced.
94 * The caller retains ownership of 'name'. */
96 simap_put(struct simap
*simap
, const char *name
, unsigned int data
)
98 size_t length
= strlen(name
);
99 size_t hash
= hash_name(name
, length
);
100 struct simap_node
*node
;
102 node
= simap_find__(simap
, name
, length
, hash
);
107 simap_add_nocopy__(simap
, xmemdup0(name
, length
), data
, hash
);
112 /* Increases the data value in the mapping for 'name' by 'amt', or inserts a
113 * mapping from 'name' to 'amt' if no such mapping exists. Returns the
114 * new total data value for the mapping.
116 * If 'amt' is zero, this function does nothing and returns 0. That is, this
117 * function won't create a mapping with a initial value of 0.
119 * The caller retains ownership of 'name'. */
121 simap_increase(struct simap
*simap
, const char *name
, unsigned int amt
)
124 size_t length
= strlen(name
);
125 size_t hash
= hash_name(name
, length
);
126 struct simap_node
*node
;
128 node
= simap_find__(simap
, name
, length
, hash
);
132 node
= simap_add_nocopy__(simap
, xmemdup0(name
, length
),
141 /* Deletes 'node' from 'simap' and frees its associated memory. */
143 simap_delete(struct simap
*simap
, struct simap_node
*node
)
145 hmap_remove(&simap
->map
, &node
->node
);
150 /* Searches for 'name' in 'simap'. If found, deletes it and returns true. If
151 * not found, returns false without modifying 'simap'. */
153 simap_find_and_delete(struct simap
*simap
, const char *name
)
155 struct simap_node
*node
= simap_find(simap
, name
);
157 simap_delete(simap
, node
);
163 /* Searches 'simap' for a mapping with the given 'name'. Returns it, if found,
164 * or a null pointer if not. */
166 simap_find(const struct simap
*simap
, const char *name
)
168 return simap_find_len(simap
, name
, strlen(name
));
171 /* Searches 'simap' for a mapping whose name is the first 'name_len' bytes
172 * starting at 'name'. Returns it, if found, or a null pointer if not. */
174 simap_find_len(const struct simap
*simap
, const char *name
, size_t len
)
176 return simap_find__(simap
, name
, len
, hash_name(name
, len
));
179 /* Searches 'simap' for a mapping with the given 'name'. Returns the
180 * associated data value, if found, otherwise zero. */
182 simap_get(const struct simap
*simap
, const char *name
)
184 struct simap_node
*node
= simap_find(simap
, name
);
185 return node
? node
->data
: 0;
188 /* Returns true if 'simap' contains a copy of 'name', false otherwise. */
190 simap_contains(const struct simap
*simap
, const char *name
)
192 return simap_find(simap
, name
) != NULL
;
195 /* Returns an array that contains a pointer to each mapping in 'simap',
196 * ordered alphabetically by name. The returned array has simap_count(simap)
199 * The caller is responsible for freeing the returned array (with free()). It
200 * should not free the individual "simap_node"s in the array, because they are
201 * still part of 'simap'. */
202 const struct simap_node
**
203 simap_sort(const struct simap
*simap
)
205 if (simap_is_empty(simap
)) {
208 const struct simap_node
**nodes
;
209 struct simap_node
*node
;
212 n
= simap_count(simap
);
213 nodes
= xmalloc(n
* sizeof *nodes
);
215 SIMAP_FOR_EACH (node
, simap
) {
220 qsort(nodes
, n
, sizeof *nodes
, compare_nodes_by_name
);
226 /* Returns true if the two maps are equal, meaning that they have the same set
227 * of key-value pairs, otherwise false. */
229 simap_equal(const struct simap
*a
, const struct simap
*b
)
231 if (simap_count(a
) != simap_count(b
)) {
235 const struct simap_node
*an
;
236 SIMAP_FOR_EACH (an
, a
) {
237 const struct simap_node
*bn
= simap_find(b
, an
->name
);
238 if (!bn
|| an
->data
!= bn
->data
) {
246 hash_name(const char *name
, size_t length
)
248 return hash_bytes(name
, length
, 0);
251 static struct simap_node
*
252 simap_find__(const struct simap
*simap
, const char *name
, size_t name_len
,
255 struct simap_node
*node
;
257 HMAP_FOR_EACH_WITH_HASH (node
, node
, hash
, &simap
->map
) {
258 if (!strncmp(node
->name
, name
, name_len
) && !node
->name
[name_len
]) {
265 static struct simap_node
*
266 simap_add_nocopy__(struct simap
*simap
, char *name
, unsigned int data
,
269 struct simap_node
*node
= xmalloc(sizeof *node
);
272 hmap_insert(&simap
->map
, &node
->node
, hash
);
277 compare_nodes_by_name(const void *a_
, const void *b_
)
279 const struct simap_node
*const *a
= a_
;
280 const struct simap_node
*const *b
= b_
;
281 return strcmp((*a
)->name
, (*b
)->name
);