sat-math: Introduce macro version of SAT_MUL.
[openvswitch] / lib / sset.c
1 /*
2  * Copyright (c) 2011 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
19 #include "sset.h"
20
21 #include <assert.h>
22
23 #include "hash.h"
24
25 static uint32_t
26 hash_name__(const char *name, size_t length)
27 {
28     return hash_bytes(name, length, 0);
29 }
30
31 static uint32_t
32 hash_name(const char *name)
33 {
34     return hash_name__(name, strlen(name));
35 }
36
37 static struct sset_node *
38 sset_find__(const struct sset *set, const char *name, size_t hash)
39 {
40     struct sset_node *node;
41
42     HMAP_FOR_EACH_WITH_HASH (node, hmap_node, hash, &set->map) {
43         if (!strcmp(node->name, name)) {
44             return node;
45         }
46     }
47     return NULL;
48 }
49
50 static struct sset_node *
51 sset_add__(struct sset *set, const char *name, size_t length, size_t hash)
52 {
53     struct sset_node *node = xmalloc(length + sizeof *node);
54     memcpy(node->name, name, length + 1);
55     hmap_insert(&set->map, &node->hmap_node, hash);
56     return node;
57 }
58
59 /* Initializes 'set' as an empty set of strings. */
60 void
61 sset_init(struct sset *set)
62 {
63     hmap_init(&set->map);
64 }
65
66 /* Destroys 'sets'. */
67 void
68 sset_destroy(struct sset *set)
69 {
70     if (set) {
71         sset_clear(set);
72         hmap_destroy(&set->map);
73     }
74 }
75
76 /* Initializes 'set' to contain the same strings as 'orig'. */
77 void
78 sset_clone(struct sset *set, const struct sset *orig)
79 {
80     struct sset_node *node;
81
82     sset_init(set);
83     HMAP_FOR_EACH (node, hmap_node, &orig->map) {
84         sset_add__(set, node->name, strlen(node->name),
85                    node->hmap_node.hash);
86     }
87 }
88
89 /* Exchanges the contents of 'a' and 'b'. */
90 void
91 sset_swap(struct sset *a, struct sset *b)
92 {
93     hmap_swap(&a->map, &b->map);
94 }
95
96 /* Adjusts 'set' so that it is still valid after it has been moved around in
97  * memory (e.g. due to realloc()). */
98 void
99 sset_moved(struct sset *set)
100 {
101     hmap_moved(&set->map);
102 }
103
104 /* Returns true if 'set' contains no strings, false if it contains at least one
105  * string. */
106 bool
107 sset_is_empty(const struct sset *set)
108 {
109     return hmap_is_empty(&set->map);
110 }
111
112 /* Returns the number of strings in 'set'. */
113 size_t
114 sset_count(const struct sset *set)
115 {
116     return hmap_count(&set->map);
117 }
118
119 /* Adds 'name' to 'set'.  If 'name' is new, returns the new sset_node;
120  * otherwise (if a copy of 'name' already existed in 'set'), returns NULL. */
121 struct sset_node *
122 sset_add(struct sset *set, const char *name)
123 {
124     size_t length = strlen(name);
125     uint32_t hash = hash_name__(name, length);
126
127     return (sset_find__(set, name, hash)
128             ? NULL
129             : sset_add__(set, name, length, hash));
130 }
131
132 /* Adds a copy of 'name' to 'set' and frees 'name'.
133  *
134  * If 'name' is new, returns the new sset_node; otherwise (if a copy of 'name'
135  * already existed in 'set'), returns NULL. */
136 struct sset_node *
137 sset_add_and_free(struct sset *set, char *name)
138 {
139     struct sset_node *node = sset_add(set, name);
140     free(name);
141     return node;
142 }
143
144 /* Adds 'name' to 'set'.  Assert-fails if a copy of 'name' was already in
145  * 'set'. */
146 void
147 sset_add_assert(struct sset *set, const char *name)
148 {
149     bool added OVS_UNUSED = sset_add(set, name);
150     assert(added);
151 }
152
153 /* Adds a copy of each of the 'n' names in 'names' to 'set'. */
154 void
155 sset_add_array(struct sset *set, char **names, size_t n)
156 {
157     size_t i;
158
159     for (i = 0; i < n; i++) {
160         sset_add(set, names[i]);
161     }
162 }
163
164 /* Removes all of the strings from 'set'. */
165 void
166 sset_clear(struct sset *set)
167 {
168     const char *name, *next;
169
170     SSET_FOR_EACH_SAFE (name, next, set) {
171         sset_delete(set, SSET_NODE_FROM_NAME(name));
172     }
173 }
174
175 /* Deletes 'node' from 'set' and frees 'node'. */
176 void
177 sset_delete(struct sset *set, struct sset_node *node)
178 {
179     hmap_remove(&set->map, &node->hmap_node);
180     free(node);
181 }
182
183 /* Searches for 'name' in 'set'.  If found, deletes it and returns true.  If
184  * not found, returns false without modifying 'set'. */
185 bool
186 sset_find_and_delete(struct sset *set, const char *name)
187 {
188     struct sset_node *node = sset_find(set, name);
189     if (node) {
190         sset_delete(set, node);
191     }
192     return node != NULL;
193 }
194
195 /* Searches for 'name' in 'set' and deletes it.  Assert-fails if 'name' is not
196  * in 'set'. */
197 void
198 sset_find_and_delete_assert(struct sset *set, const char *name)
199 {
200     bool deleted OVS_UNUSED = sset_find_and_delete(set, name);
201     assert(deleted);
202 }
203
204 /* Removes a string from 'set' and returns a copy of it.  The caller must free
205  * the returned string (with free()).
206  *
207  * 'set' must not be empty.
208  *
209  * This is not a very good way to iterate through an sset: it copies each name
210  * and it takes O(n**2) time to remove all the names.  Use SSET_FOR_EACH_SAFE
211  * instead, if you can. */
212 char *
213 sset_pop(struct sset *set)
214 {
215     const char *name = SSET_FIRST(set);
216     char *copy = xstrdup(name);
217     sset_delete(set, SSET_NODE_FROM_NAME(name));
218     return copy;
219 }
220
221 /* Searches for 'name' in 'set'.  Returns its node, if found, otherwise a null
222  * pointer. */
223 struct sset_node *
224 sset_find(const struct sset *set, const char *name)
225 {
226     return sset_find__(set, name, hash_name(name));
227 }
228
229 /* Returns true if 'set' contains a copy of 'name', false otherwise. */
230 bool
231 sset_contains(const struct sset *set, const char *name)
232 {
233     return sset_find(set, name) != NULL;
234 }
235
236 /* Returns true if 'a' and 'b' contain the same strings, false otherwise. */
237 bool
238 sset_equals(const struct sset *a, const struct sset *b)
239 {
240     struct sset_node *node;
241
242     if (sset_count(a) != sset_count(b)) {
243         return false;
244     }
245
246     HMAP_FOR_EACH (node, hmap_node, &a->map) {
247         if (!sset_find__(b, node->name, node->hmap_node.hash)) {
248             return false;
249         }
250     }
251
252     return true;
253 }