Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2009, 2010, 2011, 2012 Nicira, Inc.
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"
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 : 19993 : simap_init(struct simap *simap)
33 : : {
34 : 19993 : hmap_init(&simap->map);
35 : 19993 : }
36 : :
37 : : /* Frees all the data that 'simap' contains. */
38 : : void
39 : 29821 : simap_destroy(struct simap *simap)
40 : : {
41 [ + - ]: 29821 : if (simap) {
42 : 29821 : simap_clear(simap);
43 : 29821 : hmap_destroy(&simap->map);
44 : : }
45 : 29821 : }
46 : :
47 : : /* Exchanges the contents of 'a' and 'b'. */
48 : : void
49 : 18244 : simap_swap(struct simap *a, struct simap *b)
50 : : {
51 : 18244 : hmap_swap(&a->map, &b->map);
52 : 18244 : }
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 : 0 : simap_moved(struct simap *simap)
58 : : {
59 : 0 : hmap_moved(&simap->map);
60 : 0 : }
61 : :
62 : : /* Removes all of the mappings from 'simap' and frees them. */
63 : : void
64 : 29821 : simap_clear(struct simap *simap)
65 : : {
66 : : struct simap_node *node, *next;
67 : :
68 [ + + ][ - + ]: 73783 : SIMAP_FOR_EACH_SAFE (node, next, simap) {
[ + + ]
69 : 43962 : hmap_remove(&simap->map, &node->node);
70 : 43962 : free(node->name);
71 : 43962 : free(node);
72 : : }
73 : 29821 : }
74 : :
75 : : /* Returns true if 'simap' contains no mappings, false if it contains at least
76 : : * one. */
77 : : bool
78 : 145 : simap_is_empty(const struct simap *simap)
79 : : {
80 : 145 : return hmap_is_empty(&simap->map);
81 : : }
82 : :
83 : : /* Returns the number of mappings in 'simap'. */
84 : : size_t
85 : 289 : simap_count(const struct simap *simap)
86 : : {
87 : 289 : 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 : 49237 : simap_put(struct simap *simap, const char *name, unsigned int data)
97 : : {
98 : 49237 : size_t length = strlen(name);
99 : 49237 : size_t hash = hash_name(name, length);
100 : : struct simap_node *node;
101 : :
102 : 49237 : node = simap_find__(simap, name, length, hash);
103 [ + + ]: 49237 : if (node) {
104 : 266 : node->data = data;
105 : 266 : return false;
106 : : } else {
107 : 48971 : simap_add_nocopy__(simap, xmemdup0(name, length), data, hash);
108 : 48971 : 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 : 37888 : simap_increase(struct simap *simap, const char *name, unsigned int amt)
122 : : {
123 [ + + ]: 37888 : if (amt) {
124 : 819 : size_t length = strlen(name);
125 : 819 : size_t hash = hash_name(name, length);
126 : : struct simap_node *node;
127 : :
128 : 819 : node = simap_find__(simap, name, length, hash);
129 [ + + ]: 819 : if (node) {
130 : 281 : node->data += amt;
131 : : } else {
132 : 538 : node = simap_add_nocopy__(simap, xmemdup0(name, length),
133 : : amt, hash);
134 : : }
135 : 819 : return node->data;
136 : : } else {
137 : 37069 : return 0;
138 : : }
139 : : }
140 : :
141 : : /* Deletes 'node' from 'simap' and frees its associated memory. */
142 : : void
143 : 3181 : simap_delete(struct simap *simap, struct simap_node *node)
144 : : {
145 : 3181 : hmap_remove(&simap->map, &node->node);
146 : 3181 : free(node->name);
147 : 3181 : free(node);
148 : 3181 : }
149 : :
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 : 35 : simap_find_and_delete(struct simap *simap, const char *name)
154 : : {
155 : 35 : struct simap_node *node = simap_find(simap, name);
156 [ + - ]: 35 : if (node) {
157 : 35 : simap_delete(simap, node);
158 : 35 : return true;
159 : : }
160 : 0 : return false;
161 : : }
162 : :
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 : 456107 : simap_find(const struct simap *simap, const char *name)
167 : : {
168 : 456107 : 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 : 456378 : simap_find_len(const struct simap *simap, const char *name, size_t len)
175 : : {
176 : 456378 : 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 : 337739 : simap_get(const struct simap *simap, const char *name)
183 : : {
184 : 337739 : struct simap_node *node = simap_find(simap, name);
185 [ + + ]: 337739 : return node ? node->data : 0;
186 : : }
187 : :
188 : : /* Returns true if 'simap' contains a copy of 'name', false otherwise. */
189 : : bool
190 : 66376 : simap_contains(const struct simap *simap, const char *name)
191 : : {
192 : 66376 : return simap_find(simap, name) != NULL;
193 : : }
194 : :
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 : 145 : simap_sort(const struct simap *simap)
204 : : {
205 [ + + ]: 145 : if (simap_is_empty(simap)) {
206 : 1 : return NULL;
207 : : } else {
208 : : const struct simap_node **nodes;
209 : : struct simap_node *node;
210 : : size_t i, n;
211 : :
212 : 144 : n = simap_count(simap);
213 : 144 : nodes = xmalloc(n * sizeof *nodes);
214 : 144 : i = 0;
215 [ + + ][ - + ]: 754 : SIMAP_FOR_EACH (node, simap) {
216 : 610 : nodes[i++] = node;
217 : : }
218 [ - + ]: 144 : ovs_assert(i == n);
219 : :
220 : 144 : qsort(nodes, n, sizeof *nodes, compare_nodes_by_name);
221 : :
222 : 144 : return nodes;
223 : : }
224 : : }
225 : :
226 : : static size_t
227 : 506434 : hash_name(const char *name, size_t length)
228 : : {
229 : 506434 : return hash_bytes(name, length, 0);
230 : : }
231 : :
232 : : static struct simap_node *
233 : 506434 : simap_find__(const struct simap *simap, const char *name, size_t name_len,
234 : : size_t hash)
235 : : {
236 : : struct simap_node *node;
237 : :
238 [ + + ][ - + ]: 506434 : HMAP_FOR_EACH_WITH_HASH (node, node, hash, &simap->map) {
239 [ + - ][ + - ]: 238066 : if (!strncmp(node->name, name, name_len) && !node->name[name_len]) {
240 : 238066 : return node;
241 : : }
242 : : }
243 : 268368 : return NULL;
244 : : }
245 : :
246 : : static struct simap_node *
247 : 49509 : simap_add_nocopy__(struct simap *simap, char *name, unsigned int data,
248 : : size_t hash)
249 : : {
250 : 49509 : struct simap_node *node = xmalloc(sizeof *node);
251 : 49509 : node->name = name;
252 : 49509 : node->data = data;
253 : 49509 : hmap_insert(&simap->map, &node->node, hash);
254 : 49509 : return node;
255 : : }
256 : :
257 : : static int
258 : 739 : compare_nodes_by_name(const void *a_, const void *b_)
259 : : {
260 : 739 : const struct simap_node *const *a = a_;
261 : 739 : const struct simap_node *const *b = b_;
262 : 739 : return strcmp((*a)->name, (*b)->name);
263 : : }
|
