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.
22 static size_t hash_name(const char *, size_t length);
23 static struct simap_node *simap_find__(const struct simap *,
24 const char *name, size_t name_len,
26 static struct simap_node *simap_add_nocopy__(struct simap *,
27 char *name, unsigned int data,
29 static int compare_nodes_by_name(const void *a_, const void *b_);
31 /* Initializes 'simap' as an empty string-to-integer map. */
33 simap_init(struct simap *simap)
35 hmap_init(&simap->map);
38 /* Frees all the data that 'simap' contains. */
40 simap_destroy(struct simap *simap)
44 hmap_destroy(&simap->map);
48 /* Exchanges the contents of 'a' and 'b'. */
50 simap_swap(struct simap *a, struct simap *b)
52 hmap_swap(&a->map, &b->map);
55 /* Adjusts 'simap' so that it is still valid after it has been moved around in
56 * memory (e.g. due to realloc()). */
58 simap_moved(struct simap *simap)
60 hmap_moved(&simap->map);
63 /* Removes all of the mappings from 'simap' and frees them. */
65 simap_clear(struct simap *simap)
67 struct simap_node *node, *next;
69 SIMAP_FOR_EACH_SAFE (node, next, simap) {
70 hmap_remove(&simap->map, &node->node);
76 /* Returns true if 'simap' contains no mappings, false if it contains at least
79 simap_is_empty(const struct simap *simap)
81 return hmap_is_empty(&simap->map);
84 /* Returns the number of mappings in 'simap'. */
86 simap_count(const struct simap *simap)
88 return hmap_count(&simap->map);
91 /* Inserts a mapping from 'name' to 'data' into 'simap', replacing any
92 * existing mapping for 'name'. Returns true if a new mapping was added,
93 * false if an existing mapping's value was replaced.
95 * The caller retains ownership of 'name'. */
97 simap_put(struct simap *simap, const char *name, unsigned int data)
99 size_t length = strlen(name);
100 size_t hash = hash_name(name, length);
101 struct simap_node *node;
103 node = simap_find__(simap, name, length, hash);
108 simap_add_nocopy__(simap, xmemdup0(name, length), data, hash);
113 /* Increases the data value in the mapping for 'name' by 'amt', or inserts a
114 * mapping from 'name' to 'amt' if no such mapping exists. Returns the
115 * new total data value for the mapping.
117 * If 'amt' is zero, this function does nothing and returns 0. That is, this
118 * function won't create a mapping with a initial value of 0.
120 * The caller retains ownership of 'name'. */
122 simap_increase(struct simap *simap, const char *name, unsigned int amt)
125 size_t length = strlen(name);
126 size_t hash = hash_name(name, length);
127 struct simap_node *node;
129 node = simap_find__(simap, name, length, hash);
133 node = simap_add_nocopy__(simap, xmemdup0(name, length),
142 /* Deletes 'node' from 'simap' and frees its associated memory. */
144 simap_delete(struct simap *simap, struct simap_node *node)
146 hmap_remove(&simap->map, &node->node);
151 /* Searches 'simap' for a mapping with the given 'name'. Returns it, if found,
152 * or a null pointer if not. */
154 simap_find(const struct simap *simap, const char *name)
156 return simap_find_len(simap, name, strlen(name));
159 /* Searches 'simap' for a mapping whose name is the first 'name_len' bytes
160 * starting at 'name'. Returns it, if found, or a null pointer if not. */
162 simap_find_len(const struct simap *simap, const char *name, size_t len)
164 return simap_find__(simap, name, len, hash_name(name, len));
167 /* Searches 'simap' for a mapping with the given 'name'. Returns the
168 * associated data value, if found, otherwise zero. */
170 simap_get(const struct simap *simap, const char *name)
172 struct simap_node *node = simap_find(simap, name);
173 return node ? node->data : 0;
176 /* Returns an array that contains a pointer to each mapping in 'simap',
177 * ordered alphabetically by name. The returned array has simap_count(simap)
180 * The caller is responsible for freeing the returned array (with free()). It
181 * should not free the individual "simap_node"s in the array, because they are
182 * still part of 'simap'. */
183 const struct simap_node **
184 simap_sort(const struct simap *simap)
186 if (simap_is_empty(simap)) {
189 const struct simap_node **nodes;
190 struct simap_node *node;
193 n = simap_count(simap);
194 nodes = xmalloc(n * sizeof *nodes);
196 SIMAP_FOR_EACH (node, simap) {
201 qsort(nodes, n, sizeof *nodes, compare_nodes_by_name);
208 hash_name(const char *name, size_t length)
210 return hash_bytes(name, length, 0);
213 static struct simap_node *
214 simap_find__(const struct simap *simap, const char *name, size_t name_len,
217 struct simap_node *node;
219 HMAP_FOR_EACH_WITH_HASH (node, node, hash, &simap->map) {
220 if (!strncmp(node->name, name, name_len) && !node->name[name_len]) {
227 static struct simap_node *
228 simap_add_nocopy__(struct simap *simap, char *name, unsigned int data,
231 struct simap_node *node = xmalloc(sizeof *node);
234 hmap_insert(&simap->map, &node->node, hash);
239 compare_nodes_by_name(const void *a_, const void *b_)
241 const struct simap_node *const *a = a_;
242 const struct simap_node *const *b = b_;
243 return strcmp((*a)->name, (*b)->name);