1 aaa0878e 2019-01-08 stsp /*
  2 aaa0878e 2019-01-08 stsp  * Copyright (c) 2019 Stefan Sperling <stsp@openbsd.org>
  3 aaa0878e 2019-01-08 stsp  *
  4 aaa0878e 2019-01-08 stsp  * Permission to use, copy, modify, and distribute this software for any
  5 aaa0878e 2019-01-08 stsp  * purpose with or without fee is hereby granted, provided that the above
  6 aaa0878e 2019-01-08 stsp  * copyright notice and this permission notice appear in all copies.
  7 aaa0878e 2019-01-08 stsp  *
  8 aaa0878e 2019-01-08 stsp  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  9 aaa0878e 2019-01-08 stsp  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 10 aaa0878e 2019-01-08 stsp  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 11 aaa0878e 2019-01-08 stsp  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 12 aaa0878e 2019-01-08 stsp  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 13 aaa0878e 2019-01-08 stsp  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 14 aaa0878e 2019-01-08 stsp  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 15 aaa0878e 2019-01-08 stsp  */
 16 aaa0878e 2019-01-08 stsp 
 17 aaa0878e 2019-01-08 stsp #include <sys/tree.h>
 18 aaa0878e 2019-01-08 stsp 
 19 aaa0878e 2019-01-08 stsp #include <stdlib.h>
 20 aaa0878e 2019-01-08 stsp #include <string.h>
 21 aaa0878e 2019-01-08 stsp #include <stdio.h>
 22 aaa0878e 2019-01-08 stsp #include <limits.h>
 23 aaa0878e 2019-01-08 stsp 
 24 aaa0878e 2019-01-08 stsp #include "got_error.h"
 25 aaa0878e 2019-01-08 stsp #include "got_lib_pathset.h"
 26 aaa0878e 2019-01-08 stsp 
 27 aaa0878e 2019-01-08 stsp #ifndef MIN
 28 aaa0878e 2019-01-08 stsp #define	MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
 29 aaa0878e 2019-01-08 stsp #endif
 30 aaa0878e 2019-01-08 stsp 
 31 aaa0878e 2019-01-08 stsp struct got_pathset_element {
 32 aaa0878e 2019-01-08 stsp 	RB_ENTRY(got_pathset_element)	entry;
 33 aaa0878e 2019-01-08 stsp 	char *path;
 34 aaa0878e 2019-01-08 stsp 	void *data;	/* API user data */
 35 aaa0878e 2019-01-08 stsp };
 36 aaa0878e 2019-01-08 stsp 
 37 aaa0878e 2019-01-08 stsp RB_HEAD(got_pathset_tree, got_pathset_element);
 38 aaa0878e 2019-01-08 stsp 
 39 aaa0878e 2019-01-08 stsp static int
 40 aaa0878e 2019-01-08 stsp cmp_elements(const struct got_pathset_element *e1,
 41 aaa0878e 2019-01-08 stsp     const struct got_pathset_element *e2)
 42 aaa0878e 2019-01-08 stsp {
 43 aaa0878e 2019-01-08 stsp 	size_t len1 = strlen(e1->path);
 44 aaa0878e 2019-01-08 stsp 	size_t len2 = strlen(e2->path);
 45 aaa0878e 2019-01-08 stsp 	size_t min_len = MIN(len1, len2);
 46 aaa0878e 2019-01-08 stsp 	size_t i = 0;
 47 aaa0878e 2019-01-08 stsp 
 48 aaa0878e 2019-01-08 stsp 	/* Skip over common prefix. */
 49 aaa0878e 2019-01-08 stsp 	while (i < min_len && e1->path[i] == e2->path[i])
 50 aaa0878e 2019-01-08 stsp 		i++;
 51 aaa0878e 2019-01-08 stsp 
 52 aaa0878e 2019-01-08 stsp 	/* Are the paths exactly equal? */
 53 aaa0878e 2019-01-08 stsp 	if (len1 == len2 && i >= min_len)
 54 aaa0878e 2019-01-08 stsp 		return 0;
 55 aaa0878e 2019-01-08 stsp 
 56 aaa0878e 2019-01-08 stsp 	/* Order children in subdirectories directly after their parents. */
 57 aaa0878e 2019-01-08 stsp 	if (e1->path[i] == '/' && e2->path[i] == '\0')
 58 aaa0878e 2019-01-08 stsp 		return 1;
 59 aaa0878e 2019-01-08 stsp 	if (e2->path[i] == '/' && e1->path[i] == '\0')
 60 aaa0878e 2019-01-08 stsp 		return -1;
 61 aaa0878e 2019-01-08 stsp 	if (e1->path[i] == '/')
 62 aaa0878e 2019-01-08 stsp 		return -1;
 63 aaa0878e 2019-01-08 stsp 	if (e2->path[i] == '/')
 64 aaa0878e 2019-01-08 stsp 		return 1;
 65 aaa0878e 2019-01-08 stsp 
 66 aaa0878e 2019-01-08 stsp 	/* Next character following the common prefix determines order. */
 67 aaa0878e 2019-01-08 stsp 	return (unsigned char)e1->path[i] < (unsigned char)e2->path[i] ? -1 : 1;
 68 aaa0878e 2019-01-08 stsp }
 69 aaa0878e 2019-01-08 stsp 
 70 aaa0878e 2019-01-08 stsp RB_PROTOTYPE(got_pathset_tree, got_pathset_element, entry, cmp_elements);
 71 aaa0878e 2019-01-08 stsp 
 72 aaa0878e 2019-01-08 stsp struct got_pathset {
 73 aaa0878e 2019-01-08 stsp 	struct got_pathset_tree entries;
 74 aaa0878e 2019-01-08 stsp 	int totelem;
 75 aaa0878e 2019-01-08 stsp #define GOT_OBJECT_IDSET_MAX_ELEM INT_MAX
 76 aaa0878e 2019-01-08 stsp };
 77 aaa0878e 2019-01-08 stsp 
 78 aaa0878e 2019-01-08 stsp struct got_pathset *
 79 aaa0878e 2019-01-08 stsp got_pathset_alloc(void)
 80 aaa0878e 2019-01-08 stsp {
 81 aaa0878e 2019-01-08 stsp 	struct got_pathset *set;
 82 aaa0878e 2019-01-08 stsp 
 83 aaa0878e 2019-01-08 stsp 	set = malloc(sizeof(*set));
 84 aaa0878e 2019-01-08 stsp 	if (set == NULL)
 85 aaa0878e 2019-01-08 stsp 		return NULL;
 86 aaa0878e 2019-01-08 stsp 
 87 aaa0878e 2019-01-08 stsp 	RB_INIT(&set->entries);
 88 aaa0878e 2019-01-08 stsp 	set->totelem = 0;
 89 aaa0878e 2019-01-08 stsp 
 90 aaa0878e 2019-01-08 stsp 	return set;
 91 aaa0878e 2019-01-08 stsp }
 92 aaa0878e 2019-01-08 stsp 
 93 aaa0878e 2019-01-08 stsp static void
 94 aaa0878e 2019-01-08 stsp free_element(struct got_pathset_element *entry)
 95 aaa0878e 2019-01-08 stsp {
 96 aaa0878e 2019-01-08 stsp 	free(entry->path);
 97 aaa0878e 2019-01-08 stsp 	free(entry);
 98 aaa0878e 2019-01-08 stsp }
 99 aaa0878e 2019-01-08 stsp 
100 aaa0878e 2019-01-08 stsp void
101 aaa0878e 2019-01-08 stsp got_pathset_free(struct got_pathset *set)
102 aaa0878e 2019-01-08 stsp {
103 aaa0878e 2019-01-08 stsp 	struct got_pathset_element *entry;
104 aaa0878e 2019-01-08 stsp 
105 aaa0878e 2019-01-08 stsp 	while ((entry = RB_MIN(got_pathset_tree, &set->entries))) {
106 aaa0878e 2019-01-08 stsp 		RB_REMOVE(got_pathset_tree, &set->entries, entry);
107 aaa0878e 2019-01-08 stsp 		/* User data should be freed by caller. */
108 aaa0878e 2019-01-08 stsp 		free_element(entry);
109 aaa0878e 2019-01-08 stsp 	}
110 aaa0878e 2019-01-08 stsp 
111 aaa0878e 2019-01-08 stsp 	free(set);
112 aaa0878e 2019-01-08 stsp }
113 aaa0878e 2019-01-08 stsp 
114 aaa0878e 2019-01-08 stsp const struct got_error *
115 aaa0878e 2019-01-08 stsp got_pathset_add(struct got_pathset *set, const char *path, void *data)
116 aaa0878e 2019-01-08 stsp {
117 aaa0878e 2019-01-08 stsp 	struct got_pathset_element *new;
118 aaa0878e 2019-01-08 stsp 
119 aaa0878e 2019-01-08 stsp 	if (set->totelem >= GOT_OBJECT_IDSET_MAX_ELEM)
120 aaa0878e 2019-01-08 stsp 		return got_error(GOT_ERR_NO_SPACE);
121 aaa0878e 2019-01-08 stsp 
122 aaa0878e 2019-01-08 stsp 	new = malloc(sizeof(*new));
123 aaa0878e 2019-01-08 stsp 	if (new == NULL)
124 aaa0878e 2019-01-08 stsp 		return got_error_from_errno();
125 aaa0878e 2019-01-08 stsp 
126 aaa0878e 2019-01-08 stsp 	new->path = strdup(path);
127 aaa0878e 2019-01-08 stsp 	if (new->path == NULL)
128 aaa0878e 2019-01-08 stsp 		return got_error_from_errno();
129 aaa0878e 2019-01-08 stsp 		
130 aaa0878e 2019-01-08 stsp 	new->data = data;
131 aaa0878e 2019-01-08 stsp 
132 aaa0878e 2019-01-08 stsp 	RB_INSERT(got_pathset_tree, &set->entries, new);
133 aaa0878e 2019-01-08 stsp 	set->totelem++;
134 aaa0878e 2019-01-08 stsp 	return NULL;
135 aaa0878e 2019-01-08 stsp }
136 aaa0878e 2019-01-08 stsp 
137 aaa0878e 2019-01-08 stsp static struct got_pathset_element *
138 aaa0878e 2019-01-08 stsp find_element(struct got_pathset *set, const char *path)
139 aaa0878e 2019-01-08 stsp {
140 aaa0878e 2019-01-08 stsp 	struct got_pathset_element key, *entry;
141 aaa0878e 2019-01-08 stsp 	key.path = strdup(path);
142 aaa0878e 2019-01-08 stsp 	entry = RB_FIND(got_pathset_tree, &set->entries, &key);
143 aaa0878e 2019-01-08 stsp 	free(key.path);
144 aaa0878e 2019-01-08 stsp 	return entry;
145 aaa0878e 2019-01-08 stsp }
146 aaa0878e 2019-01-08 stsp 
147 aaa0878e 2019-01-08 stsp void *
148 aaa0878e 2019-01-08 stsp got_pathset_get(struct got_pathset *set, const char *path)
149 aaa0878e 2019-01-08 stsp {
150 aaa0878e 2019-01-08 stsp 	struct got_pathset_element *entry = find_element(set, path);
151 aaa0878e 2019-01-08 stsp 	return entry ? entry->data : NULL;
152 aaa0878e 2019-01-08 stsp }
153 aaa0878e 2019-01-08 stsp 
154 aaa0878e 2019-01-08 stsp const struct got_error *
155 aaa0878e 2019-01-08 stsp got_pathset_remove(void **data, struct got_pathset *set, const char *path)
156 aaa0878e 2019-01-08 stsp {
157 aaa0878e 2019-01-08 stsp 	struct got_pathset_element *entry;
158 aaa0878e 2019-01-08 stsp 
159 aaa0878e 2019-01-08 stsp 	if (data)
160 aaa0878e 2019-01-08 stsp 		*data = NULL;
161 aaa0878e 2019-01-08 stsp 
162 aaa0878e 2019-01-08 stsp 	if (set->totelem == 0)
163 aaa0878e 2019-01-08 stsp 		return got_error(GOT_ERR_NO_OBJ);
164 aaa0878e 2019-01-08 stsp 
165 aaa0878e 2019-01-08 stsp 	if (path == NULL)
166 aaa0878e 2019-01-08 stsp 		entry = RB_ROOT(&set->entries);
167 aaa0878e 2019-01-08 stsp 	else
168 aaa0878e 2019-01-08 stsp 		entry = find_element(set, path);
169 aaa0878e 2019-01-08 stsp 	if (entry == NULL)
170 aaa0878e 2019-01-08 stsp 		return got_error(GOT_ERR_NO_OBJ);
171 aaa0878e 2019-01-08 stsp 
172 aaa0878e 2019-01-08 stsp 	RB_REMOVE(got_pathset_tree, &set->entries, entry);
173 aaa0878e 2019-01-08 stsp 	if (data)
174 aaa0878e 2019-01-08 stsp 		*data = entry->data;
175 aaa0878e 2019-01-08 stsp 	free_element(entry);
176 aaa0878e 2019-01-08 stsp 	set->totelem--;
177 aaa0878e 2019-01-08 stsp 	return NULL;
178 aaa0878e 2019-01-08 stsp }
179 aaa0878e 2019-01-08 stsp 
180 aaa0878e 2019-01-08 stsp int
181 aaa0878e 2019-01-08 stsp got_pathset_contains(struct got_pathset *set, const char *path)
182 aaa0878e 2019-01-08 stsp {
183 aaa0878e 2019-01-08 stsp 	struct got_pathset_element *entry = find_element(set, path);
184 aaa0878e 2019-01-08 stsp 	return entry ? 1 : 0;
185 aaa0878e 2019-01-08 stsp }
186 aaa0878e 2019-01-08 stsp 
187 aaa0878e 2019-01-08 stsp const struct got_error *
188 aaa0878e 2019-01-08 stsp got_pathset_for_each(struct got_pathset *set,
189 aaa0878e 2019-01-08 stsp     const struct got_error *(*cb)(const char *, void *, void *), void *arg)
190 aaa0878e 2019-01-08 stsp {
191 aaa0878e 2019-01-08 stsp 	const struct got_error *err;
192 aaa0878e 2019-01-08 stsp 	struct got_pathset_element *entry, *tmp;
193 aaa0878e 2019-01-08 stsp 
194 aaa0878e 2019-01-08 stsp 	RB_FOREACH_SAFE(entry, got_pathset_tree, &set->entries, tmp) {
195 aaa0878e 2019-01-08 stsp 		err = (*cb)(entry->path, entry->data, arg);
196 aaa0878e 2019-01-08 stsp 		if (err)
197 aaa0878e 2019-01-08 stsp 			return err;
198 aaa0878e 2019-01-08 stsp 	}
199 aaa0878e 2019-01-08 stsp 	return NULL;
200 aaa0878e 2019-01-08 stsp }
201 aaa0878e 2019-01-08 stsp 
202 efaf56b7 2019-01-08 stsp const struct got_error *
203 efaf56b7 2019-01-08 stsp got_pathset_for_each_reverse(struct got_pathset *set,
204 efaf56b7 2019-01-08 stsp     const struct got_error *(*cb)(const char *, void *, void *), void *arg)
205 efaf56b7 2019-01-08 stsp {
206 efaf56b7 2019-01-08 stsp 	const struct got_error *err;
207 efaf56b7 2019-01-08 stsp 	struct got_pathset_element *entry, *tmp;
208 efaf56b7 2019-01-08 stsp 
209 efaf56b7 2019-01-08 stsp 	RB_FOREACH_REVERSE_SAFE(entry, got_pathset_tree, &set->entries, tmp) {
210 efaf56b7 2019-01-08 stsp 		err = (*cb)(entry->path, entry->data, arg);
211 efaf56b7 2019-01-08 stsp 		if (err)
212 efaf56b7 2019-01-08 stsp 			return err;
213 efaf56b7 2019-01-08 stsp 	}
214 efaf56b7 2019-01-08 stsp 	return NULL;
215 efaf56b7 2019-01-08 stsp }
216 efaf56b7 2019-01-08 stsp 
217 aaa0878e 2019-01-08 stsp int
218 aaa0878e 2019-01-08 stsp got_pathset_num_elements(struct got_pathset *set)
219 aaa0878e 2019-01-08 stsp {
220 aaa0878e 2019-01-08 stsp 	return set->totelem;
221 aaa0878e 2019-01-08 stsp }
222 aaa0878e 2019-01-08 stsp 
223 aaa0878e 2019-01-08 stsp RB_GENERATE(got_pathset_tree, got_pathset_element, entry, cmp_elements);