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.
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 'simap' for a mapping with the given 'name'. Returns it, if found,
151 * or a null pointer if not. */
153 simap_find(const struct simap *simap, const char *name)
155 return simap_find_len(simap, name, strlen(name));
158 /* Searches 'simap' for a mapping whose name is the first 'name_len' bytes
159 * starting at 'name'. Returns it, if found, or a null pointer if not. */
161 simap_find_len(const struct simap *simap, const char *name, size_t len)
163 return simap_find__(simap, name, len, hash_name(name, len));
166 /* Searches 'simap' for a mapping with the given 'name'. Returns the
167 * associated data value, if found, otherwise zero. */
169 simap_get(const struct simap *simap, const char *name)
171 struct simap_node *node = simap_find(simap, name);
172 return node ? node->data : 0;
175 /* Returns an array that contains a pointer to each mapping in 'simap',
176 * ordered alphabetically by name. The returned array has simap_count(simap)
179 * The caller is responsible for freeing the returned array (with free()). It
180 * should not free the individual "simap_node"s in the array, because they are
181 * still part of 'simap'. */
182 const struct simap_node **
183 simap_sort(const struct simap *simap)
185 if (simap_is_empty(simap)) {
188 const struct simap_node **nodes;
189 struct simap_node *node;
192 n = simap_count(simap);
193 nodes = xmalloc(n * sizeof *nodes);
195 SIMAP_FOR_EACH (node, simap) {
200 qsort(nodes, n, sizeof *nodes, compare_nodes_by_name);
207 hash_name(const char *name, size_t length)
209 return hash_bytes(name, length, 0);
212 static struct simap_node *
213 simap_find__(const struct simap *simap, const char *name, size_t name_len,
216 struct simap_node *node;
218 HMAP_FOR_EACH_WITH_HASH (node, node, hash, &simap->map) {
219 if (!strncmp(node->name, name, name_len) && !node->name[name_len]) {
226 static struct simap_node *
227 simap_add_nocopy__(struct simap *simap, char *name, unsigned int data,
230 struct simap_node *node = xmalloc(sizeof *node);
233 hmap_insert(&simap->map, &node->node, hash);
238 compare_nodes_by_name(const void *a_, const void *b_)
240 const struct simap_node *const *a = a_;
241 const struct simap_node *const *b = b_;
242 return strcmp((*a)->name, (*b)->name);