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