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