2 * Copyright (c) 2019 Stefan Sperling <stsp@openbsd.org>
4 * Permission to use, copy, modify, and distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
24 #include "got_error.h"
25 #include "got_lib_pathset.h"
28 #define MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
31 struct got_pathset_element {
32 RB_ENTRY(got_pathset_element) entry;
34 void *data; /* API user data */
37 RB_HEAD(got_pathset_tree, got_pathset_element);
40 cmp_elements(const struct got_pathset_element *e1,
41 const struct got_pathset_element *e2)
43 size_t len1 = strlen(e1->path);
44 size_t len2 = strlen(e2->path);
45 size_t min_len = MIN(len1, len2);
48 /* Skip over common prefix. */
49 while (i < min_len && e1->path[i] == e2->path[i])
52 /* Are the paths exactly equal? */
53 if (len1 == len2 && i >= min_len)
56 /* Order children in subdirectories directly after their parents. */
57 if (e1->path[i] == '/' && e2->path[i] == '\0')
59 if (e2->path[i] == '/' && e1->path[i] == '\0')
61 if (e1->path[i] == '/')
63 if (e2->path[i] == '/')
66 /* Next character following the common prefix determines order. */
67 return (unsigned char)e1->path[i] < (unsigned char)e2->path[i] ? -1 : 1;
70 RB_PROTOTYPE(got_pathset_tree, got_pathset_element, entry, cmp_elements);
73 struct got_pathset_tree entries;
75 #define GOT_PATHSET_MAX_ELEM INT_MAX
79 got_pathset_alloc(void)
81 struct got_pathset *set;
83 set = malloc(sizeof(*set));
87 RB_INIT(&set->entries);
94 free_element(struct got_pathset_element *entry)
101 got_pathset_free(struct got_pathset *set)
103 struct got_pathset_element *entry;
105 while ((entry = RB_MIN(got_pathset_tree, &set->entries))) {
106 RB_REMOVE(got_pathset_tree, &set->entries, entry);
107 /* User data should be freed by caller. */
114 const struct got_error *
115 got_pathset_add(struct got_pathset *set, const char *path, void *data)
117 struct got_pathset_element *new;
119 if (set->totelem >= GOT_PATHSET_MAX_ELEM)
120 return got_error(GOT_ERR_NO_SPACE);
122 new = malloc(sizeof(*new));
124 return got_error_from_errno();
126 new->path = strdup(path);
127 if (new->path == NULL)
128 return got_error_from_errno();
132 RB_INSERT(got_pathset_tree, &set->entries, new);
137 static struct got_pathset_element *
138 find_element(struct got_pathset *set, const char *path)
140 struct got_pathset_element key, *entry;
141 key.path = strdup(path);
142 entry = RB_FIND(got_pathset_tree, &set->entries, &key);
148 got_pathset_get(struct got_pathset *set, const char *path)
150 struct got_pathset_element *entry = find_element(set, path);
151 return entry ? entry->data : NULL;
154 const struct got_error *
155 got_pathset_remove(void **data, struct got_pathset *set, const char *path)
157 struct got_pathset_element *entry;
162 if (set->totelem == 0)
163 return got_error(GOT_ERR_NO_OBJ);
166 entry = RB_ROOT(&set->entries);
168 entry = find_element(set, path);
170 return got_error(GOT_ERR_NO_OBJ);
172 RB_REMOVE(got_pathset_tree, &set->entries, entry);
181 got_pathset_contains(struct got_pathset *set, const char *path)
183 struct got_pathset_element *entry = find_element(set, path);
184 return entry ? 1 : 0;
187 const struct got_error *
188 got_pathset_for_each_safe(struct got_pathset *set,
189 const struct got_error *(*cb)(const char *, void *, void *), void *arg)
191 const struct got_error *err;
192 struct got_pathset_element *entry, *tmp;
194 RB_FOREACH_SAFE(entry, got_pathset_tree, &set->entries, tmp) {
195 err = (*cb)(entry->path, entry->data, arg);
202 const struct got_error *
203 got_pathset_for_each_reverse_safe(struct got_pathset *set,
204 const struct got_error *(*cb)(const char *, void *, void *), void *arg)
206 const struct got_error *err;
207 struct got_pathset_element *entry, *tmp;
209 RB_FOREACH_REVERSE_SAFE(entry, got_pathset_tree, &set->entries, tmp) {
210 err = (*cb)(entry->path, entry->data, arg);
218 got_pathset_num_elements(struct got_pathset *set)
223 RB_GENERATE(got_pathset_tree, got_pathset_element, entry, cmp_elements);