ofproto: Update documentation
[sliver-openvswitch.git] / lib / simap.c
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 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
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
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
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
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         }
218         ovs_assert(i == n);
219
220         qsort(nodes, n, sizeof *nodes, compare_nodes_by_name);
221
222         return nodes;
223     }
224 }
225 \f
226 static size_t
227 hash_name(const char *name, size_t length)
228 {
229     return hash_bytes(name, length, 0);
230 }
231
232 static struct simap_node *
233 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     HMAP_FOR_EACH_WITH_HASH (node, node, hash, &simap->map) {
239         if (!strncmp(node->name, name, name_len) && !node->name[name_len]) {
240             return node;
241         }
242     }
243     return NULL;
244 }
245
246 static struct simap_node *
247 simap_add_nocopy__(struct simap *simap, char *name, unsigned int data,
248                    size_t hash)
249 {
250     struct simap_node *node = xmalloc(sizeof *node);
251     node->name = name;
252     node->data = data;
253     hmap_insert(&simap->map, &node->node, hash);
254     return node;
255 }
256
257 static int
258 compare_nodes_by_name(const void *a_, const void *b_)
259 {
260     const struct simap_node *const *a = a_;
261     const struct simap_node *const *b = b_;
262     return strcmp((*a)->name, (*b)->name);
263 }