Revert DSCP update changes.
[openvswitch] / 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 <assert.h>
20 #include "hash.h"
21
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,
25                                        size_t hash);
26 static struct simap_node *simap_add_nocopy__(struct simap *,
27                                              char *name, unsigned int data,
28                                              size_t hash);
29 static int compare_nodes_by_name(const void *a_, const void *b_);
30
31 /* Initializes 'simap' as an empty string-to-integer map. */
32 void
33 simap_init(struct simap *simap)
34 {
35     hmap_init(&simap->map);
36 }
37
38 /* Frees all the data that 'simap' contains. */
39 void
40 simap_destroy(struct simap *simap)
41 {
42     if (simap) {
43         simap_clear(simap);
44         hmap_destroy(&simap->map);
45     }
46 }
47
48 /* Exchanges the contents of 'a' and 'b'. */
49 void
50 simap_swap(struct simap *a, struct simap *b)
51 {
52     hmap_swap(&a->map, &b->map);
53 }
54
55 /* Adjusts 'simap' so that it is still valid after it has been moved around in
56  * memory (e.g. due to realloc()). */
57 void
58 simap_moved(struct simap *simap)
59 {
60     hmap_moved(&simap->map);
61 }
62
63 /* Removes all of the mappings from 'simap' and frees them. */
64 void
65 simap_clear(struct simap *simap)
66 {
67     struct simap_node *node, *next;
68
69     SIMAP_FOR_EACH_SAFE (node, next, simap) {
70         hmap_remove(&simap->map, &node->node);
71         free(node->name);
72         free(node);
73     }
74 }
75
76 /* Returns true if 'simap' contains no mappings, false if it contains at least
77  * one. */
78 bool
79 simap_is_empty(const struct simap *simap)
80 {
81     return hmap_is_empty(&simap->map);
82 }
83
84 /* Returns the number of mappings in 'simap'. */
85 size_t
86 simap_count(const struct simap *simap)
87 {
88     return hmap_count(&simap->map);
89 }
90
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.
94  *
95  * The caller retains ownership of 'name'. */
96 bool
97 simap_put(struct simap *simap, const char *name, unsigned int data)
98 {
99     size_t length = strlen(name);
100     size_t hash = hash_name(name, length);
101     struct simap_node *node;
102
103     node = simap_find__(simap, name, length, hash);
104     if (node) {
105         node->data = data;
106         return false;
107     } else {
108         simap_add_nocopy__(simap, xmemdup0(name, length), data, hash);
109         return true;
110     }
111 }
112
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.
116  *
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.
119  *
120  * The caller retains ownership of 'name'. */
121 unsigned int
122 simap_increase(struct simap *simap, const char *name, unsigned int amt)
123 {
124     if (amt) {
125         size_t length = strlen(name);
126         size_t hash = hash_name(name, length);
127         struct simap_node *node;
128
129         node = simap_find__(simap, name, length, hash);
130         if (node) {
131             node->data += amt;
132         } else {
133             node = simap_add_nocopy__(simap, xmemdup0(name, length),
134                                       amt, hash);
135         }
136         return node->data;
137     } else {
138         return 0;
139     }
140 }
141
142 /* Deletes 'node' from 'simap' and frees its associated memory. */
143 void
144 simap_delete(struct simap *simap, struct simap_node *node)
145 {
146     hmap_remove(&simap->map, &node->node);
147     free(node->name);
148     free(node);
149 }
150
151 /* Searches 'simap' for a mapping with the given 'name'.  Returns it, if found,
152  * or a null pointer if not. */
153 struct simap_node *
154 simap_find(const struct simap *simap, const char *name)
155 {
156     return simap_find_len(simap, name, strlen(name));
157 }
158
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. */
161 struct simap_node *
162 simap_find_len(const struct simap *simap, const char *name, size_t len)
163 {
164     return simap_find__(simap, name, len, hash_name(name, len));
165 }
166
167 /* Searches 'simap' for a mapping with the given 'name'.  Returns the
168  * associated data value, if found, otherwise zero. */
169 unsigned int
170 simap_get(const struct simap *simap, const char *name)
171 {
172     struct simap_node *node = simap_find(simap, name);
173     return node ? node->data : 0;
174 }
175
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)
178  * elements.
179  *
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)
185 {
186     if (simap_is_empty(simap)) {
187         return NULL;
188     } else {
189         const struct simap_node **nodes;
190         struct simap_node *node;
191         size_t i, n;
192
193         n = simap_count(simap);
194         nodes = xmalloc(n * sizeof *nodes);
195         i = 0;
196         SIMAP_FOR_EACH (node, simap) {
197             nodes[i++] = node;
198         }
199         assert(i == n);
200
201         qsort(nodes, n, sizeof *nodes, compare_nodes_by_name);
202
203         return nodes;
204     }
205 }
206 \f
207 static size_t
208 hash_name(const char *name, size_t length)
209 {
210     return hash_bytes(name, length, 0);
211 }
212
213 static struct simap_node *
214 simap_find__(const struct simap *simap, const char *name, size_t name_len,
215              size_t hash)
216 {
217     struct simap_node *node;
218
219     HMAP_FOR_EACH_WITH_HASH (node, node, hash, &simap->map) {
220         if (!strncmp(node->name, name, name_len) && !node->name[name_len]) {
221             return node;
222         }
223     }
224     return NULL;
225 }
226
227 static struct simap_node *
228 simap_add_nocopy__(struct simap *simap, char *name, unsigned int data,
229                    size_t hash)
230 {
231     struct simap_node *node = xmalloc(sizeof *node);
232     node->name = name;
233     node->data = data;
234     hmap_insert(&simap->map, &node->node, hash);
235     return node;
236 }
237
238 static int
239 compare_nodes_by_name(const void *a_, const void *b_)
240 {
241     const struct simap_node *const *a = a_;
242     const struct simap_node *const *b = b_;
243     return strcmp((*a)->name, (*b)->name);
244 }