1 /*
2  * Copyright (c) 2019 Stefan Sperling <stsp@openbsd.org>
3  *
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.
7  *
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.
15  */
16 
17 #include <sys/tree.h>
18 
19 #include <stdlib.h>
20 #include <string.h>
21 #include <stdio.h>
22 #include <limits.h>
23 
24 #include "got_error.h"
25 #include "got_lib_pathset.h"
26 
27 #ifndef MIN
28 #define	MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
29 #endif
30 
31 struct got_pathset_element {
32 	RB_ENTRY(got_pathset_element)	entry;
33 	char *path;
34 	void *data;	/* API user data */
35 };
36 
37 RB_HEAD(got_pathset_tree, got_pathset_element);
38 
39 static int
40 cmp_elements(const struct got_pathset_element *e1,
41     const struct got_pathset_element *e2)
42 {
43 	size_t len1 = strlen(e1->path);
44 	size_t len2 = strlen(e2->path);
45 	size_t min_len = MIN(len1, len2);
46 	size_t i = 0;
47 
48 	/* Skip over common prefix. */
49 	while (i < min_len && e1->path[i] == e2->path[i])
50 		i++;
51 
52 	/* Are the paths exactly equal? */
53 	if (len1 == len2 && i >= min_len)
54 		return 0;
55 
56 	/* Order children in subdirectories directly after their parents. */
57 	if (e1->path[i] == '/' && e2->path[i] == '\0')
58 		return 1;
59 	if (e2->path[i] == '/' && e1->path[i] == '\0')
60 		return -1;
61 	if (e1->path[i] == '/')
62 		return -1;
63 	if (e2->path[i] == '/')
64 		return 1;
65 
66 	/* Next character following the common prefix determines order. */
67 	return (unsigned char)e1->path[i] < (unsigned char)e2->path[i] ? -1 : 1;
68 }
69 
70 RB_PROTOTYPE(got_pathset_tree, got_pathset_element, entry, cmp_elements);
71 
72 struct got_pathset {
73 	struct got_pathset_tree entries;
74 	int totelem;
75 #define GOT_OBJECT_IDSET_MAX_ELEM INT_MAX
76 };
77 
78 struct got_pathset *
79 got_pathset_alloc(void)
80 {
81 	struct got_pathset *set;
82 
83 	set = malloc(sizeof(*set));
84 	if (set == NULL)
85 		return NULL;
86 
87 	RB_INIT(&set->entries);
88 	set->totelem = 0;
89 
90 	return set;
91 }
92 
93 static void
94 free_element(struct got_pathset_element *entry)
95 {
96 	free(entry->path);
97 	free(entry);
98 }
99 
100 void
101 got_pathset_free(struct got_pathset *set)
102 {
103 	struct got_pathset_element *entry;
104 
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. */
108 		free_element(entry);
109 	}
110 
111 	free(set);
112 }
113 
114 const struct got_error *
115 got_pathset_add(struct got_pathset *set, const char *path, void *data)
116 {
117 	struct got_pathset_element *new;
118 
119 	if (set->totelem >= GOT_OBJECT_IDSET_MAX_ELEM)
120 		return got_error(GOT_ERR_NO_SPACE);
121 
122 	new = malloc(sizeof(*new));
123 	if (new == NULL)
124 		return got_error_from_errno();
125 
126 	new->path = strdup(path);
127 	if (new->path == NULL)
128 		return got_error_from_errno();
129 		
130 	new->data = data;
131 
132 	RB_INSERT(got_pathset_tree, &set->entries, new);
133 	set->totelem++;
134 	return NULL;
135 }
136 
137 static struct got_pathset_element *
138 find_element(struct got_pathset *set, const char *path)
139 {
140 	struct got_pathset_element key, *entry;
141 	key.path = strdup(path);
142 	entry = RB_FIND(got_pathset_tree, &set->entries, &key);
143 	free(key.path);
144 	return entry;
145 }
146 
147 void *
148 got_pathset_get(struct got_pathset *set, const char *path)
149 {
150 	struct got_pathset_element *entry = find_element(set, path);
151 	return entry ? entry->data : NULL;
152 }
153 
154 const struct got_error *
155 got_pathset_remove(void **data, struct got_pathset *set, const char *path)
156 {
157 	struct got_pathset_element *entry;
158 
159 	if (data)
160 		*data = NULL;
161 
162 	if (set->totelem == 0)
163 		return got_error(GOT_ERR_NO_OBJ);
164 
165 	if (path == NULL)
166 		entry = RB_ROOT(&set->entries);
167 	else
168 		entry = find_element(set, path);
169 	if (entry == NULL)
170 		return got_error(GOT_ERR_NO_OBJ);
171 
172 	RB_REMOVE(got_pathset_tree, &set->entries, entry);
173 	if (data)
174 		*data = entry->data;
175 	free_element(entry);
176 	set->totelem--;
177 	return NULL;
178 }
179 
180 int
181 got_pathset_contains(struct got_pathset *set, const char *path)
182 {
183 	struct got_pathset_element *entry = find_element(set, path);
184 	return entry ? 1 : 0;
185 }
186 
187 const struct got_error *
188 got_pathset_for_each(struct got_pathset *set,
189     const struct got_error *(*cb)(const char *, void *, void *), void *arg)
190 {
191 	const struct got_error *err;
192 	struct got_pathset_element *entry, *tmp;
193 
194 	RB_FOREACH_SAFE(entry, got_pathset_tree, &set->entries, tmp) {
195 		err = (*cb)(entry->path, entry->data, arg);
196 		if (err)
197 			return err;
198 	}
199 	return NULL;
200 }
201 
202 const struct got_error *
203 got_pathset_for_each_reverse(struct got_pathset *set,
204     const struct got_error *(*cb)(const char *, void *, void *), void *arg)
205 {
206 	const struct got_error *err;
207 	struct got_pathset_element *entry, *tmp;
208 
209 	RB_FOREACH_REVERSE_SAFE(entry, got_pathset_tree, &set->entries, tmp) {
210 		err = (*cb)(entry->path, entry->data, arg);
211 		if (err)
212 			return err;
213 	}
214 	return NULL;
215 }
216 
217 int
218 got_pathset_num_elements(struct got_pathset *set)
219 {
220 	return set->totelem;
221 }
222 
223 RB_GENERATE(got_pathset_tree, got_pathset_element, entry, cmp_elements);