]>
Commit | Line | Data |
---|---|---|
44bac24b | 1 | /* |
c841e96a | 2 | * Copyright (c) 2009, 2010, 2011, 2012, 2017 Nicira, Inc. |
44bac24b BP |
3 | * |
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: | |
7 | * | |
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. | |
15 | */ | |
16 | ||
17 | #include <config.h> | |
18 | #include "simap.h" | |
44bac24b BP |
19 | #include "hash.h" |
20 | ||
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, | |
24 | size_t hash); | |
25 | static struct simap_node *simap_add_nocopy__(struct simap *, | |
26 | char *name, unsigned int data, | |
27 | size_t hash); | |
28 | static int compare_nodes_by_name(const void *a_, const void *b_); | |
29 | ||
30 | /* Initializes 'simap' as an empty string-to-integer map. */ | |
31 | void | |
32 | simap_init(struct simap *simap) | |
33 | { | |
34 | hmap_init(&simap->map); | |
35 | } | |
36 | ||
37 | /* Frees all the data that 'simap' contains. */ | |
38 | void | |
39 | simap_destroy(struct simap *simap) | |
40 | { | |
41 | if (simap) { | |
42 | simap_clear(simap); | |
43 | hmap_destroy(&simap->map); | |
44 | } | |
45 | } | |
46 | ||
47 | /* Exchanges the contents of 'a' and 'b'. */ | |
48 | void | |
49 | simap_swap(struct simap *a, struct simap *b) | |
50 | { | |
51 | hmap_swap(&a->map, &b->map); | |
52 | } | |
53 | ||
54 | /* Adjusts 'simap' so that it is still valid after it has been moved around in | |
55 | * memory (e.g. due to realloc()). */ | |
56 | void | |
57 | simap_moved(struct simap *simap) | |
58 | { | |
59 | hmap_moved(&simap->map); | |
60 | } | |
61 | ||
62 | /* Removes all of the mappings from 'simap' and frees them. */ | |
63 | void | |
64 | simap_clear(struct simap *simap) | |
65 | { | |
66 | struct simap_node *node, *next; | |
67 | ||
68 | SIMAP_FOR_EACH_SAFE (node, next, simap) { | |
69 | hmap_remove(&simap->map, &node->node); | |
70 | free(node->name); | |
71 | free(node); | |
72 | } | |
73 | } | |
74 | ||
75 | /* Returns true if 'simap' contains no mappings, false if it contains at least | |
76 | * one. */ | |
77 | bool | |
78 | simap_is_empty(const struct simap *simap) | |
79 | { | |
80 | return hmap_is_empty(&simap->map); | |
81 | } | |
82 | ||
83 | /* Returns the number of mappings in 'simap'. */ | |
84 | size_t | |
85 | simap_count(const struct simap *simap) | |
86 | { | |
87 | return hmap_count(&simap->map); | |
88 | } | |
89 | ||
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. | |
93 | * | |
94 | * The caller retains ownership of 'name'. */ | |
95 | bool | |
96 | simap_put(struct simap *simap, const char *name, unsigned int data) | |
97 | { | |
98 | size_t length = strlen(name); | |
99 | size_t hash = hash_name(name, length); | |
100 | struct simap_node *node; | |
101 | ||
102 | node = simap_find__(simap, name, length, hash); | |
103 | if (node) { | |
104 | node->data = data; | |
105 | return false; | |
106 | } else { | |
107 | simap_add_nocopy__(simap, xmemdup0(name, length), data, hash); | |
108 | return true; | |
109 | } | |
110 | } | |
111 | ||
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. | |
115 | * | |
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. | |
118 | * | |
119 | * The caller retains ownership of 'name'. */ | |
120 | unsigned int | |
121 | simap_increase(struct simap *simap, const char *name, unsigned int amt) | |
122 | { | |
123 | if (amt) { | |
124 | size_t length = strlen(name); | |
125 | size_t hash = hash_name(name, length); | |
126 | struct simap_node *node; | |
127 | ||
128 | node = simap_find__(simap, name, length, hash); | |
129 | if (node) { | |
130 | node->data += amt; | |
131 | } else { | |
132 | node = simap_add_nocopy__(simap, xmemdup0(name, length), | |
133 | amt, hash); | |
134 | } | |
135 | return node->data; | |
136 | } else { | |
137 | return 0; | |
138 | } | |
139 | } | |
140 | ||
141 | /* Deletes 'node' from 'simap' and frees its associated memory. */ | |
142 | void | |
143 | simap_delete(struct simap *simap, struct simap_node *node) | |
144 | { | |
145 | hmap_remove(&simap->map, &node->node); | |
146 | free(node->name); | |
147 | free(node); | |
148 | } | |
149 | ||
bcac5b7c KM |
150 | /* Searches for 'name' in 'simap'. If found, deletes it and returns true. If |
151 | * not found, returns false without modifying 'simap'. */ | |
152 | bool | |
153 | simap_find_and_delete(struct simap *simap, const char *name) | |
154 | { | |
155 | struct simap_node *node = simap_find(simap, name); | |
156 | if (node) { | |
157 | simap_delete(simap, node); | |
158 | return true; | |
159 | } | |
160 | return false; | |
161 | } | |
162 | ||
44bac24b BP |
163 | /* Searches 'simap' for a mapping with the given 'name'. Returns it, if found, |
164 | * or a null pointer if not. */ | |
165 | struct simap_node * | |
166 | simap_find(const struct simap *simap, const char *name) | |
167 | { | |
168 | return simap_find_len(simap, name, strlen(name)); | |
169 | } | |
170 | ||
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. */ | |
173 | struct simap_node * | |
174 | simap_find_len(const struct simap *simap, const char *name, size_t len) | |
175 | { | |
176 | return simap_find__(simap, name, len, hash_name(name, len)); | |
177 | } | |
178 | ||
179 | /* Searches 'simap' for a mapping with the given 'name'. Returns the | |
180 | * associated data value, if found, otherwise zero. */ | |
181 | unsigned int | |
182 | simap_get(const struct simap *simap, const char *name) | |
183 | { | |
184 | struct simap_node *node = simap_find(simap, name); | |
185 | return node ? node->data : 0; | |
186 | } | |
187 | ||
bcac5b7c KM |
188 | /* Returns true if 'simap' contains a copy of 'name', false otherwise. */ |
189 | bool | |
190 | simap_contains(const struct simap *simap, const char *name) | |
191 | { | |
192 | return simap_find(simap, name) != NULL; | |
193 | } | |
194 | ||
44bac24b BP |
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) | |
197 | * elements. | |
198 | * | |
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) | |
204 | { | |
205 | if (simap_is_empty(simap)) { | |
206 | return NULL; | |
207 | } else { | |
208 | const struct simap_node **nodes; | |
209 | struct simap_node *node; | |
210 | size_t i, n; | |
211 | ||
212 | n = simap_count(simap); | |
213 | nodes = xmalloc(n * sizeof *nodes); | |
214 | i = 0; | |
215 | SIMAP_FOR_EACH (node, simap) { | |
216 | nodes[i++] = node; | |
217 | } | |
cb22974d | 218 | ovs_assert(i == n); |
44bac24b BP |
219 | |
220 | qsort(nodes, n, sizeof *nodes, compare_nodes_by_name); | |
221 | ||
222 | return nodes; | |
223 | } | |
224 | } | |
c841e96a BP |
225 | |
226 | /* Returns true if the two maps are equal, meaning that they have the same set | |
227 | * of key-value pairs, otherwise false. */ | |
228 | bool | |
229 | simap_equal(const struct simap *a, const struct simap *b) | |
230 | { | |
231 | if (simap_count(a) != simap_count(b)) { | |
232 | return false; | |
233 | } | |
234 | ||
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) { | |
239 | return false; | |
240 | } | |
241 | } | |
242 | return true; | |
243 | } | |
244 | ||
44bac24b BP |
245 | static size_t |
246 | hash_name(const char *name, size_t length) | |
247 | { | |
248 | return hash_bytes(name, length, 0); | |
249 | } | |
250 | ||
251 | static struct simap_node * | |
252 | simap_find__(const struct simap *simap, const char *name, size_t name_len, | |
253 | size_t hash) | |
254 | { | |
255 | struct simap_node *node; | |
256 | ||
257 | HMAP_FOR_EACH_WITH_HASH (node, node, hash, &simap->map) { | |
258 | if (!strncmp(node->name, name, name_len) && !node->name[name_len]) { | |
259 | return node; | |
260 | } | |
261 | } | |
262 | return NULL; | |
263 | } | |
264 | ||
265 | static struct simap_node * | |
266 | simap_add_nocopy__(struct simap *simap, char *name, unsigned int data, | |
267 | size_t hash) | |
268 | { | |
269 | struct simap_node *node = xmalloc(sizeof *node); | |
270 | node->name = name; | |
271 | node->data = data; | |
272 | hmap_insert(&simap->map, &node->node, hash); | |
273 | return node; | |
274 | } | |
275 | ||
276 | static int | |
277 | compare_nodes_by_name(const void *a_, const void *b_) | |
278 | { | |
279 | const struct simap_node *const *a = a_; | |
280 | const struct simap_node *const *b = b_; | |
281 | return strcmp((*a)->name, (*b)->name); | |
282 | } |