socket-util: Move get_max_fds() to process.c.
[sliver-openvswitch.git] / lib / svec.c
1 /*
2  * Copyright (c) 2008, 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 "svec.h"
19 #include <ctype.h>
20 #include <stdlib.h>
21 #include <string.h>
22 #include "dynamic-string.h"
23 #include "util.h"
24 #include "vlog.h"
25
26 VLOG_DEFINE_THIS_MODULE(svec);
27
28 void
29 svec_init(struct svec *svec)
30 {
31     svec->names = NULL;
32     svec->n = 0;
33     svec->allocated = 0;
34 }
35
36 void
37 svec_clone(struct svec *svec, const struct svec *other)
38 {
39     svec_init(svec);
40     svec_append(svec, other);
41 }
42
43 void
44 svec_destroy(struct svec *svec)
45 {
46     svec_clear(svec);
47     free(svec->names);
48 }
49
50 void
51 svec_clear(struct svec *svec)
52 {
53     size_t i;
54
55     for (i = 0; i < svec->n; i++) {
56         free(svec->names[i]);
57     }
58     svec->n = 0;
59 }
60
61 bool
62 svec_is_empty(const struct svec *svec)
63 {
64     return svec->n == 0;
65 }
66
67 void
68 svec_add(struct svec *svec, const char *name)
69 {
70     svec_add_nocopy(svec, xstrdup(name));
71 }
72
73 void
74 svec_del(struct svec *svec, const char *name)
75 {
76     size_t offset;
77
78     offset = svec_find(svec, name);
79     if (offset != SIZE_MAX) {
80         free(svec->names[offset]);
81         memmove(&svec->names[offset], &svec->names[offset + 1],
82                 sizeof *svec->names * (svec->n - offset - 1));
83         svec->n--;
84     }
85 }
86
87 static void
88 svec_expand(struct svec *svec)
89 {
90     if (svec->n >= svec->allocated) {
91         svec->names = x2nrealloc(svec->names, &svec->allocated,
92                                  sizeof *svec->names);
93     }
94 }
95
96 void
97 svec_add_nocopy(struct svec *svec, char *name)
98 {
99     svec_expand(svec);
100     svec->names[svec->n++] = name;
101 }
102
103 void
104 svec_append(struct svec *svec, const struct svec *other)
105 {
106     size_t i;
107     for (i = 0; i < other->n; i++) {
108         svec_add(svec, other->names[i]);
109     }
110 }
111
112 void
113 svec_terminate(struct svec *svec)
114 {
115     svec_expand(svec);
116     svec->names[svec->n] = NULL;
117 }
118
119 static int
120 compare_strings(const void *a_, const void *b_)
121 {
122     char *const *a = a_;
123     char *const *b = b_;
124     return strcmp(*a, *b);
125 }
126
127 void
128 svec_sort(struct svec *svec)
129 {
130     qsort(svec->names, svec->n, sizeof *svec->names, compare_strings);
131 }
132
133 void
134 svec_sort_unique(struct svec *svec)
135 {
136     svec_sort(svec);
137     svec_unique(svec);
138 }
139
140 void
141 svec_unique(struct svec *svec)
142 {
143     ovs_assert(svec_is_sorted(svec));
144     if (svec->n > 1) {
145         /* This algorithm is lazy and sub-optimal, but it's "obviously correct"
146          * and asymptotically optimal . */
147         struct svec tmp;
148         size_t i;
149
150         svec_init(&tmp);
151         svec_add(&tmp, svec->names[0]);
152         for (i = 1; i < svec->n; i++) {
153             if (strcmp(svec->names[i - 1], svec->names[i])) {
154                 svec_add(&tmp, svec->names[i]);
155             }
156         }
157         svec_swap(&tmp, svec);
158         svec_destroy(&tmp);
159     }
160 }
161
162 void
163 svec_compact(struct svec *svec)
164 {
165     size_t i, j;
166
167     for (i = j = 0; i < svec->n; i++) {
168         if (svec->names[i] != NULL) {
169             svec->names[j++] = svec->names[i];
170         }
171     }
172     svec->n = j;
173 }
174
175 void
176 svec_diff(const struct svec *a, const struct svec *b,
177           struct svec *a_only, struct svec *both, struct svec *b_only)
178 {
179     size_t i, j;
180
181     ovs_assert(svec_is_sorted(a));
182     ovs_assert(svec_is_sorted(b));
183     if (a_only) {
184         svec_init(a_only);
185     }
186     if (both) {
187         svec_init(both);
188     }
189     if (b_only) {
190         svec_init(b_only);
191     }
192     for (i = j = 0; i < a->n && j < b->n; ) {
193         int cmp = strcmp(a->names[i], b->names[j]);
194         if (cmp < 0) {
195             if (a_only) {
196                 svec_add(a_only, a->names[i]);
197             }
198             i++;
199         } else if (cmp > 0) {
200             if (b_only) {
201                 svec_add(b_only, b->names[j]);
202             }
203             j++;
204         } else {
205             if (both) {
206                 svec_add(both, a->names[i]);
207             }
208             i++;
209             j++;
210         }
211     }
212     if (a_only) {
213         for (; i < a->n; i++) {
214             svec_add(a_only, a->names[i]);
215         }
216     }
217     if (b_only) {
218         for (; j < b->n; j++) {
219             svec_add(b_only, b->names[j]);
220         }
221     }
222 }
223
224 bool
225 svec_contains(const struct svec *svec, const char *name)
226 {
227     return svec_find(svec, name) != SIZE_MAX;
228 }
229
230 size_t
231 svec_find(const struct svec *svec, const char *name)
232 {
233     char **p;
234
235     ovs_assert(svec_is_sorted(svec));
236     p = bsearch(&name, svec->names, svec->n, sizeof *svec->names,
237                 compare_strings);
238     return p ? p - svec->names : SIZE_MAX;
239 }
240
241 bool
242 svec_is_sorted(const struct svec *svec)
243 {
244     size_t i;
245
246     for (i = 1; i < svec->n; i++) {
247         if (strcmp(svec->names[i - 1], svec->names[i]) > 0) {
248             return false;
249         }
250     }
251     return true;
252 }
253
254 bool
255 svec_is_unique(const struct svec *svec)
256 {
257     return svec_get_duplicate(svec) == NULL;
258 }
259
260 const char *
261 svec_get_duplicate(const struct svec *svec)
262 {
263     ovs_assert(svec_is_sorted(svec));
264     if (svec->n > 1) {
265         size_t i;
266         for (i = 1; i < svec->n; i++) {
267             if (!strcmp(svec->names[i - 1], svec->names[i])) {
268                 return svec->names[i];
269             }
270         }
271     }
272     return NULL;
273 }
274
275 void
276 svec_swap(struct svec *a, struct svec *b)
277 {
278     struct svec tmp = *a;
279     *a = *b;
280     *b = tmp;
281 }
282
283 void
284 svec_print(const struct svec *svec, const char *title)
285 {
286     size_t i;
287
288     printf("%s:\n", title);
289     for (i = 0; i < svec->n; i++) {
290         printf("\"%s\"\n", svec->names[i]);
291     }
292 }
293
294 /* Breaks 'words' into words at white space, respecting shell-like quoting
295  * conventions, and appends the words to 'svec'. */
296 void
297 svec_parse_words(struct svec *svec, const char *words)
298 {
299     struct ds word = DS_EMPTY_INITIALIZER;
300     const char *p, *q;
301
302     for (p = words; *p != '\0'; p = q) {
303         int quote = 0;
304
305         while (isspace((unsigned char) *p)) {
306             p++;
307         }
308         if (*p == '\0') {
309             break;
310         }
311
312         ds_clear(&word);
313         for (q = p; *q != '\0'; q++) {
314             if (*q == quote) {
315                 quote = 0;
316             } else if (*q == '\'' || *q == '"') {
317                 quote = *q;
318             } else if (*q == '\\' && (!quote || quote == '"')) {
319                 q++;
320                 if (*q == '\0') {
321                     VLOG_WARN("%s: ends in trailing backslash", words);
322                     break;
323                 }
324                 ds_put_char(&word, *q);
325             } else if (isspace((unsigned char) *q) && !quote) {
326                 q++;
327                 break;
328             } else {
329                 ds_put_char(&word, *q);
330             }
331         }
332         svec_add(svec, ds_cstr(&word));
333         if (quote) {
334             VLOG_WARN("%s: word ends inside quoted string", words);
335         }
336     }
337     ds_destroy(&word);
338 }
339
340 bool
341 svec_equal(const struct svec *a, const struct svec *b)
342 {
343     size_t i;
344
345     if (a->n != b->n) {
346         return false;
347     }
348     for (i = 0; i < a->n; i++) {
349         if (strcmp(a->names[i], b->names[i])) {
350             return false;
351         }
352     }
353     return true;
354 }
355
356 char *
357 svec_join(const struct svec *svec,
358           const char *delimiter, const char *terminator)
359 {
360     struct ds ds;
361     size_t i;
362
363     ds_init(&ds);
364     for (i = 0; i < svec->n; i++) {
365         if (i) {
366             ds_put_cstr(&ds, delimiter);
367         }
368         ds_put_cstr(&ds, svec->names[i]);
369     }
370     ds_put_cstr(&ds, terminator);
371     return ds_cstr(&ds);
372 }
373
374 const char *
375 svec_back(const struct svec *svec)
376 {
377     ovs_assert(svec->n);
378     return svec->names[svec->n - 1];
379 }
380
381 void
382 svec_pop_back(struct svec *svec)
383 {
384     ovs_assert(svec->n);
385     free(svec->names[--svec->n]);
386 }