2 * Copyright (c) 2008, 2009, 2010 Nicira Networks.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
23 #include "dynamic-string.h"
27 VLOG_DEFINE_THIS_MODULE(svec)
30 svec_init(struct svec *svec)
38 svec_clone(struct svec *svec, const struct svec *other)
41 svec_append(svec, other);
45 svec_destroy(struct svec *svec)
52 svec_clear(struct svec *svec)
56 for (i = 0; i < svec->n; i++) {
63 svec_is_empty(const struct svec *svec)
69 svec_add(struct svec *svec, const char *name)
71 svec_add_nocopy(svec, xstrdup(name));
75 svec_del(struct svec *svec, const char *name)
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));
89 svec_expand(struct svec *svec)
91 if (svec->n >= svec->allocated) {
92 svec->names = x2nrealloc(svec->names, &svec->allocated,
98 svec_add_nocopy(struct svec *svec, char *name)
101 svec->names[svec->n++] = name;
105 svec_append(struct svec *svec, const struct svec *other)
108 for (i = 0; i < other->n; i++) {
109 svec_add(svec, other->names[i]);
114 svec_move(struct svec *svec, struct svec *other)
117 for (i = 0; i < other->n; i++) {
118 svec_add_nocopy(svec, other->names[i]);
124 svec_terminate(struct svec *svec)
127 svec->names[svec->n] = NULL;
131 compare_strings(const void *a_, const void *b_)
135 return strcmp(*a, *b);
139 svec_sort(struct svec *svec)
141 qsort(svec->names, svec->n, sizeof *svec->names, compare_strings);
145 svec_sort_unique(struct svec *svec)
152 svec_unique(struct svec *svec)
154 assert(svec_is_sorted(svec));
156 /* This algorithm is lazy and sub-optimal, but it's "obviously correct"
157 * and asymptotically optimal . */
162 svec_add(&tmp, svec->names[0]);
163 for (i = 1; i < svec->n; i++) {
164 if (strcmp(svec->names[i - 1], svec->names[i])) {
165 svec_add(&tmp, svec->names[i]);
168 svec_swap(&tmp, svec);
174 svec_compact(struct svec *svec)
178 for (i = j = 0; i < svec->n; i++) {
179 if (svec->names[i] != NULL) {
180 svec->names[j++] = svec->names[i];
187 svec_diff(const struct svec *a, const struct svec *b,
188 struct svec *a_only, struct svec *both, struct svec *b_only)
192 assert(svec_is_sorted(a));
193 assert(svec_is_sorted(b));
203 for (i = j = 0; i < a->n && j < b->n; ) {
204 int cmp = strcmp(a->names[i], b->names[j]);
207 svec_add(a_only, a->names[i]);
210 } else if (cmp > 0) {
212 svec_add(b_only, b->names[j]);
217 svec_add(both, a->names[i]);
224 for (; i < a->n; i++) {
225 svec_add(a_only, a->names[i]);
229 for (; j < b->n; j++) {
230 svec_add(b_only, b->names[j]);
236 svec_contains(const struct svec *svec, const char *name)
238 return svec_find(svec, name) != SIZE_MAX;
242 svec_find(const struct svec *svec, const char *name)
246 assert(svec_is_sorted(svec));
247 p = bsearch(&name, svec->names, svec->n, sizeof *svec->names,
249 return p ? p - svec->names : SIZE_MAX;
253 svec_is_sorted(const struct svec *svec)
257 for (i = 1; i < svec->n; i++) {
258 if (strcmp(svec->names[i - 1], svec->names[i]) > 0) {
266 svec_is_unique(const struct svec *svec)
268 return svec_get_duplicate(svec) == NULL;
272 svec_get_duplicate(const struct svec *svec)
274 assert(svec_is_sorted(svec));
277 for (i = 1; i < svec->n; i++) {
278 if (!strcmp(svec->names[i - 1], svec->names[i])) {
279 return svec->names[i];
287 svec_swap(struct svec *a, struct svec *b)
289 struct svec tmp = *a;
295 svec_print(const struct svec *svec, const char *title)
299 printf("%s:\n", title);
300 for (i = 0; i < svec->n; i++) {
301 printf("\"%s\"\n", svec->names[i]);
305 /* Breaks 'words' into words at white space, respecting shell-like quoting
306 * conventions, and appends the words to 'svec'. */
308 svec_parse_words(struct svec *svec, const char *words)
310 struct ds word = DS_EMPTY_INITIALIZER;
313 for (p = words; *p != '\0'; p = q) {
316 while (isspace((unsigned char) *p)) {
324 for (q = p; *q != '\0'; q++) {
327 } else if (*q == '\'' || *q == '"') {
329 } else if (*q == '\\' && (!quote || quote == '"')) {
332 VLOG_WARN("%s: ends in trailing backslash", words);
335 ds_put_char(&word, *q);
336 } else if (isspace((unsigned char) *q) && !quote) {
340 ds_put_char(&word, *q);
343 svec_add(svec, ds_cstr(&word));
345 VLOG_WARN("%s: word ends inside quoted string", words);
352 svec_equal(const struct svec *a, const struct svec *b)
359 for (i = 0; i < a->n; i++) {
360 if (strcmp(a->names[i], b->names[i])) {
368 svec_join(const struct svec *svec,
369 const char *delimiter, const char *terminator)
375 for (i = 0; i < svec->n; i++) {
377 ds_put_cstr(&ds, delimiter);
379 ds_put_cstr(&ds, svec->names[i]);
381 ds_put_cstr(&ds, terminator);
385 /* Breaks 's' into tokens at any character in 'delimiters', and appends each
386 * token to 'svec'. Empty tokens are not added. */
388 svec_split(struct svec *svec, const char *s_, const char *delimiters)
390 char *s = xstrdup(s_);
391 char *save_ptr = NULL;
394 for (token = strtok_r(s, delimiters, &save_ptr); token != NULL;
395 token = strtok_r(NULL, delimiters, &save_ptr)) {
396 svec_add(svec, token);
402 svec_back(const struct svec *svec)
405 return svec->names[svec->n - 1];
409 svec_pop_back(struct svec *svec)
412 free(svec->names[--svec->n]);