1 /*
2  * Copyright (c) 2018, 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 
18 #include <stdlib.h>
19 #include <string.h>
20 #include <stdio.h>
21 #include <zlib.h>
22 #include <limits.h>
23 #include <time.h>
24 
25 #include "got_compat.h"
26 
27 #include "got_object.h"
28 #include "got_error.h"
29 
30 #include "got_lib_delta.h"
31 #include "got_lib_inflate.h"
32 #include "got_lib_object.h"
33 #include "got_lib_object_idset.h"
34 
35 struct got_object_idset_element {
36 	RB_ENTRY(got_object_idset_element)	entry;
37 	struct got_object_id id;
38 	void *data;	/* API user data */
39 };
40 
41 RB_HEAD(got_object_idset_tree, got_object_idset_element);
42 
43 static int
44 cmp_elements(const struct got_object_idset_element *e1,
45     const struct got_object_idset_element *e2)
46 {
47 	return got_object_id_cmp(&e1->id, &e2->id);
48 }
49 
50 RB_PROTOTYPE(got_object_idset_tree, got_object_idset_element, entry,
51     cmp_elements);
52 
53 struct got_object_idset {
54 	struct got_object_idset_tree entries;
55 	int totelem;
56 #define GOT_OBJECT_IDSET_MAX_ELEM INT_MAX
57 };
58 
59 struct got_object_idset *
60 got_object_idset_alloc(void)
61 {
62 	struct got_object_idset *set;
63 
64 	set = malloc(sizeof(*set));
65 	if (set == NULL)
66 		return NULL;
67 
68 	RB_INIT(&set->entries);
69 	set->totelem = 0;
70 
71 	return set;
72 }
73 
74 void
75 got_object_idset_free(struct got_object_idset *set)
76 {
77 	struct got_object_idset_element *entry;
78 
79 	while ((entry = RB_MIN(got_object_idset_tree, &set->entries))) {
80 		RB_REMOVE(got_object_idset_tree, &set->entries, entry);
81 		/* User data should be freed by caller. */
82 		free(entry);
83 	}
84 
85 	free(set);
86 }
87 
88 const struct got_error *
89 got_object_idset_add(struct got_object_idset *set, struct got_object_id *id,
90     void *data)
91 {
92 	struct got_object_idset_element *new;
93 
94 	if (set->totelem >= GOT_OBJECT_IDSET_MAX_ELEM)
95 		return got_error(GOT_ERR_NO_SPACE);
96 
97 	new = malloc(sizeof(*new));
98 	if (new == NULL)
99 		return got_error_from_errno("malloc");
100 
101 	memcpy(&new->id, id, sizeof(new->id));
102 	new->data = data;
103 
104 	if (RB_INSERT(got_object_idset_tree, &set->entries, new) != NULL) {
105 		free(new);
106 		return got_error(GOT_ERR_OBJ_EXISTS);
107 	}
108 
109 	set->totelem++;
110 	return NULL;
111 }
112 
113 static struct got_object_idset_element *
114 find_element(struct got_object_idset *set, struct got_object_id *id)
115 {
116 	struct got_object_idset_element *entry;
117 
118 	entry = RB_ROOT(&set->entries);
119 	while (entry) {
120 		int cmp = got_object_id_cmp(id, &entry->id);
121 		if (cmp < 0)
122 			entry = RB_LEFT(entry, entry);
123 		else if (cmp > 0)
124 			entry = RB_RIGHT(entry, entry);
125 		else
126 			break;
127 	}
128 
129 	return entry;
130 }
131 
132 void *
133 got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
134 {
135 	struct got_object_idset_element *entry = find_element(set, id);
136 	return entry ? entry->data : NULL;
137 }
138 
139 const struct got_error *
140 got_object_idset_remove(void **data, struct got_object_idset *set,
141     struct got_object_id *id)
142 {
143 	struct got_object_idset_element *entry;
144 
145 	if (data)
146 		*data = NULL;
147 
148 	if (set->totelem == 0)
149 		return got_error(GOT_ERR_NO_OBJ);
150 
151 	if (id == NULL) {
152 		entry = RB_ROOT(&set->entries);
153 		if (entry == NULL)
154 			return got_error(GOT_ERR_NO_OBJ);
155 	} else {
156 		entry = find_element(set, id);
157 		if (entry == NULL)
158 			return got_error_no_obj(id);
159 	}
160 
161 	RB_REMOVE(got_object_idset_tree, &set->entries, entry);
162 	if (data)
163 		*data = entry->data;
164 	free(entry);
165 	set->totelem--;
166 	return NULL;
167 }
168 
169 int
170 got_object_idset_contains(struct got_object_idset *set,
171     struct got_object_id *id)
172 {
173 	struct got_object_idset_element *entry = find_element(set, id);
174 	return entry ? 1 : 0;
175 }
176 
177 const struct got_error *
178 got_object_idset_for_each(struct got_object_idset *set,
179     const struct got_error *(*cb)(struct got_object_id *, void *, void *),
180     void *arg)
181 {
182 	const struct got_error *err;
183 	struct got_object_idset_element *entry, *tmp;
184 
185 	RB_FOREACH_SAFE(entry, got_object_idset_tree, &set->entries, tmp) {
186 		err = (*cb)(&entry->id, entry->data, arg);
187 		if (err)
188 			return err;
189 	}
190 	return NULL;
191 }
192 
193 int
194 got_object_idset_num_elements(struct got_object_idset *set)
195 {
196 	return set->totelem;
197 }
198 
199 struct got_object_idset_element *
200 got_object_idset_get_element(struct got_object_idset *set, struct got_object_id *id)
201 {
202 	return find_element(set, id);
203 }
204 
205 void *
206 got_object_idset_get_element_data(struct got_object_idset_element *entry)
207 {
208 	return entry->data;
209 }
210 
211 const struct got_error *
212 got_object_idset_for_each_element(struct got_object_idset *set,
213     const struct got_error *(*cb)(struct got_object_idset_element *, void *),
214     void *arg)
215 {
216 	const struct got_error *err;
217 	struct got_object_idset_element *entry, *tmp;
218 
219 	RB_FOREACH_SAFE(entry, got_object_idset_tree, &set->entries, tmp) {
220 		err = (*cb)(entry, arg);
221 		if (err)
222 			return err;
223 	}
224 	return NULL;
225 }
226 
227 void
228 got_object_idset_remove_element(struct got_object_idset *set,
229     struct got_object_idset_element *entry)
230 {
231 	RB_REMOVE(got_object_idset_tree, &set->entries, entry);
232 	free(entry);
233 	set->totelem--;
234 }
235 
236 RB_GENERATE(got_object_idset_tree, got_object_idset_element, entry,
237     cmp_elements);