/src/openvswitch/lib/svec.c

Source (jump to first uncovered line)
/*
 * Copyright (c) 2008, 2009, 2010, 2011, 2012 Nicira, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <config.h>
#include "svec.h"
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include "openvswitch/dynamic-string.h"
#include "random.h"
#include "util.h"
#include "openvswitch/vlog.h"

VLOG_DEFINE_THIS_MODULE(svec);

void
svec_init(struct svec *svec)
{
    svec->names = NULL;
    svec->n = 0;
    svec->allocated = 0;
}

void
svec_clone(struct svec *svec, const struct svec *other)
{
    svec_init(svec);
    svec_append(svec, other);
}

void
svec_destroy(struct svec *svec)
{
    svec_clear(svec);
    free(svec->names);
}

void
svec_clear(struct svec *svec)
{
    size_t i;

    for (i = 0; i < svec->n; i++) {
        free(svec->names[i]);
    }
    svec->n = 0;
}

bool
svec_is_empty(const struct svec *svec)
{
    return svec->n == 0;
}

void
svec_add(struct svec *svec, const char *name)
{
    svec_add_nocopy(svec, xstrdup(name));
}

void
svec_del(struct svec *svec, const char *name)
{
    size_t offset;

    offset = svec_find(svec, name);
    if (offset != SIZE_MAX) {
        free(svec->names[offset]);
        memmove(&svec->names[offset], &svec->names[offset + 1],
                sizeof *svec->names * (svec->n - offset - 1));
        svec->n--;
    }
}

static void
svec_expand(struct svec *svec)
{
    if (svec->n >= svec->allocated) {
        svec->names = x2nrealloc(svec->names, &svec->allocated,
                                 sizeof *svec->names);
    }
}

void
svec_add_nocopy(struct svec *svec, char *name)
{
    svec_expand(svec);
    svec->names[svec->n++] = name;
}

void
svec_append(struct svec *svec, const struct svec *other)
{
    size_t i;
    for (i = 0; i < other->n; i++) {
        svec_add(svec, other->names[i]);
    }
}

void
svec_terminate(struct svec *svec)
{
    svec_expand(svec);
    svec->names[svec->n] = NULL;
}

static int
compare_strings(const void *a_, const void *b_)
{
    char *const *a = a_;
    char *const *b = b_;
    return strcmp(*a, *b);
}

void
svec_sort(struct svec *svec)
{
    if (svec->n) {
        qsort(svec->names, svec->n, sizeof *svec->names, compare_strings);
    }
}

void
svec_sort_unique(struct svec *svec)
{
    svec_sort(svec);
    svec_unique(svec);
}

void
svec_unique(struct svec *svec)
{
    ovs_assert(svec_is_sorted(svec));
    if (svec->n > 1) {
        /* This algorithm is lazy and sub-optimal, but it's "obviously correct"
         * and asymptotically optimal . */
        struct svec tmp;
        size_t i;

        svec_init(&tmp);
        svec_add(&tmp, svec->names[0]);
        for (i = 1; i < svec->n; i++) {
            if (strcmp(svec->names[i - 1], svec->names[i])) {
                svec_add(&tmp, svec->names[i]);
            }
        }
        svec_swap(&tmp, svec);
        svec_destroy(&tmp);
    }
}

void
svec_compact(struct svec *svec)
{
    size_t i, j;

    for (i = j = 0; i < svec->n; i++) {
        if (svec->names[i] != NULL) {
            svec->names[j++] = svec->names[i];
        }
    }
    svec->n = j;
}

static void
swap_strings(char **a, char **b)
{
    char *tmp = *a;
    *a = *b;
    *b = tmp;
}

void
svec_shuffle(struct svec *svec)
{
    for (size_t i = 0; i < svec->n; i++) {
        size_t j = i + random_range(svec->n - i);
        swap_strings(&svec->names[i], &svec->names[j]);
    }
}

void
svec_diff(const struct svec *a, const struct svec *b,
          struct svec *a_only, struct svec *both, struct svec *b_only)
{
    size_t i, j;

    ovs_assert(svec_is_sorted(a));
    ovs_assert(svec_is_sorted(b));
    if (a_only) {
        svec_init(a_only);
    }
    if (both) {
        svec_init(both);
    }
    if (b_only) {
        svec_init(b_only);
    }
    for (i = j = 0; i < a->n && j < b->n; ) {
        int cmp = strcmp(a->names[i], b->names[j]);
        if (cmp < 0) {
            if (a_only) {
                svec_add(a_only, a->names[i]);
            }
            i++;
        } else if (cmp > 0) {
            if (b_only) {
                svec_add(b_only, b->names[j]);
            }
            j++;
        } else {
            if (both) {
                svec_add(both, a->names[i]);
            }
            i++;
            j++;
        }
    }
    if (a_only) {
        for (; i < a->n; i++) {
            svec_add(a_only, a->names[i]);
        }
    }
    if (b_only) {
        for (; j < b->n; j++) {
            svec_add(b_only, b->names[j]);
        }
    }
}

bool
svec_contains(const struct svec *svec, const char *name)
{
    return svec_find(svec, name) != SIZE_MAX;
}

bool
svec_contains_unsorted(const struct svec *svec, const char *name)
{
    for (size_t i = 0; i < svec->n; i++) {
        if (!strcmp(svec->names[i], name)) {
            return true;
        }
    }
    return false;
}

size_t
svec_find(const struct svec *svec, const char *name)
{
    char **p;

    ovs_assert(svec_is_sorted(svec));
    p = bsearch(&name, svec->names, svec->n, sizeof *svec->names,
                compare_strings);
    return p ? p - svec->names : SIZE_MAX;
}

bool
svec_is_sorted(const struct svec *svec)
{
    size_t i;

    for (i = 1; i < svec->n; i++) {
        if (strcmp(svec->names[i - 1], svec->names[i]) > 0) {
            return false;
        }
    }
    return true;
}

bool
svec_is_unique(const struct svec *svec)
{
    return svec_get_duplicate(svec) == NULL;
}

const char *
svec_get_duplicate(const struct svec *svec)
{
    ovs_assert(svec_is_sorted(svec));
    if (svec->n > 1) {
        size_t i;
        for (i = 1; i < svec->n; i++) {
            if (!strcmp(svec->names[i - 1], svec->names[i])) {
                return svec->names[i];
            }
        }
    }
    return NULL;
}

void
svec_swap(struct svec *a, struct svec *b)
{
    struct svec tmp = *a;
    *a = *b;
    *b = tmp;
}

void
svec_print(const struct svec *svec, const char *title)
{
    size_t i;

    printf("%s:\n", title);
    for (i = 0; i < svec->n; i++) {
        printf("\"%s\"\n", svec->names[i]);
    }
}

/* Breaks 'words' into words at white space, respecting shell-like quoting
 * conventions, and appends the words to 'svec'. */
void
svec_parse_words(struct svec *svec, const char *words)
{
    struct ds word = DS_EMPTY_INITIALIZER;
    const char *p, *q;

    for (p = words; *p != '\0'; p = q) {
        int quote = 0;

        while (isspace((unsigned char) *p)) {
            p++;
        }
        if (*p == '\0') {
            break;
        }

        ds_clear(&word);
        for (q = p; *q != '\0'; q++) {
            if (*q == quote) {
                quote = 0;
            } else if (*q == '\'' || *q == '"') {
                quote = *q;
            } else if (*q == '\\' && (!quote || quote == '"')) {
                q++;
                if (*q == '\0') {
                    VLOG_WARN("%s: ends in trailing backslash", words);
                    break;
                }
                ds_put_char(&word, *q);
            } else if (isspace((unsigned char) *q) && !quote) {
                q++;
                break;
            } else {
                ds_put_char(&word, *q);
            }
        }
        svec_add(svec, ds_cstr(&word));
        if (quote) {
            VLOG_WARN("%s: word ends inside quoted string", words);
        }
    }
    ds_destroy(&word);
}

bool
svec_equal(const struct svec *a, const struct svec *b)
{
    size_t i;

    if (a->n != b->n) {
        return false;
    }
    for (i = 0; i < a->n; i++) {
        if (strcmp(a->names[i], b->names[i])) {
            return false;
        }
    }
    return true;
}

char *
svec_join(const struct svec *svec,
          const char *delimiter, const char *terminator)
{
    struct ds ds;
    size_t i;

    ds_init(&ds);
    for (i = 0; i < svec->n; i++) {
        if (i) {
            ds_put_cstr(&ds, delimiter);
        }
        ds_put_cstr(&ds, svec->names[i]);
    }
    ds_put_cstr(&ds, terminator);
    return ds_cstr(&ds);
}

const char *
svec_back(const struct svec *svec)
{
    ovs_assert(svec->n);
    return svec->names[svec->n - 1];
}

void
svec_pop_back(struct svec *svec)
{
    ovs_assert(svec->n);
    free(svec->names[--svec->n]);
}

Coverage Report

Created: 2025-07-01 06:51

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