1 54be8251 2018-06-04 stsp /*
  2 5d56da81 2019-01-13 stsp  * Copyright (c) 2018, 2019 Stefan Sperling <stsp@openbsd.org>
  3 54be8251 2018-06-04 stsp  *
  4 54be8251 2018-06-04 stsp  * Permission to use, copy, modify, and distribute this software for any
  5 54be8251 2018-06-04 stsp  * purpose with or without fee is hereby granted, provided that the above
  6 54be8251 2018-06-04 stsp  * copyright notice and this permission notice appear in all copies.
  7 54be8251 2018-06-04 stsp  *
  8 54be8251 2018-06-04 stsp  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  9 54be8251 2018-06-04 stsp  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 10 54be8251 2018-06-04 stsp  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 11 54be8251 2018-06-04 stsp  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 12 54be8251 2018-06-04 stsp  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 13 54be8251 2018-06-04 stsp  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 14 54be8251 2018-06-04 stsp  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 15 54be8251 2018-06-04 stsp  */
 16 54be8251 2018-06-04 stsp 
 17 54be8251 2018-06-04 stsp #include <sys/queue.h>
 18 984e8a45 2018-11-05 stsp #include <sys/tree.h>
 19 54be8251 2018-06-04 stsp 
 20 54be8251 2018-06-04 stsp #include <stdlib.h>
 21 54be8251 2018-06-04 stsp #include <string.h>
 22 54be8251 2018-06-04 stsp #include <sha1.h>
 23 54be8251 2018-06-04 stsp #include <stdio.h>
 24 54be8251 2018-06-04 stsp #include <zlib.h>
 25 c6f420bf 2018-06-04 stsp #include <limits.h>
 26 788c352e 2018-06-16 stsp #include <time.h>
 27 54be8251 2018-06-04 stsp 
 28 54be8251 2018-06-04 stsp #include "got_object.h"
 29 54be8251 2018-06-04 stsp #include "got_error.h"
 30 54be8251 2018-06-04 stsp 
 31 54be8251 2018-06-04 stsp #include "got_lib_delta.h"
 32 63581804 2018-07-09 stsp #include "got_lib_inflate.h"
 33 54be8251 2018-06-04 stsp #include "got_lib_object.h"
 34 54be8251 2018-06-04 stsp #include "got_lib_object_idset.h"
 35 54be8251 2018-06-04 stsp 
 36 54be8251 2018-06-04 stsp struct got_object_idset_element {
 37 e336e3d6 2018-11-05 stsp 	RB_ENTRY(got_object_idset_element)	entry;
 38 54be8251 2018-06-04 stsp 	struct got_object_id id;
 39 54be8251 2018-06-04 stsp 	void *data;	/* API user data */
 40 54be8251 2018-06-04 stsp };
 41 54be8251 2018-06-04 stsp 
 42 e336e3d6 2018-11-05 stsp RB_HEAD(got_object_idset_tree, got_object_idset_element);
 43 984e8a45 2018-11-05 stsp 
 44 984e8a45 2018-11-05 stsp static int
 45 984e8a45 2018-11-05 stsp cmp_elements(const struct got_object_idset_element *e1,
 46 984e8a45 2018-11-05 stsp     const struct got_object_idset_element *e2)
 47 984e8a45 2018-11-05 stsp {
 48 984e8a45 2018-11-05 stsp 	return got_object_id_cmp(&e1->id, &e2->id);
 49 984e8a45 2018-11-05 stsp }
 50 984e8a45 2018-11-05 stsp 
 51 e336e3d6 2018-11-05 stsp RB_PROTOTYPE(got_object_idset_tree, got_object_idset_element, entry,
 52 984e8a45 2018-11-05 stsp     cmp_elements);
 53 984e8a45 2018-11-05 stsp 
 54 54be8251 2018-06-04 stsp struct got_object_idset {
 55 984e8a45 2018-11-05 stsp 	struct got_object_idset_tree entries;
 56 2bd394ff 2018-06-22 stsp 	int totelem;
 57 069f84d5 2018-06-11 stsp #define GOT_OBJECT_IDSET_MAX_ELEM INT_MAX
 58 54be8251 2018-06-04 stsp };
 59 54be8251 2018-06-04 stsp 
 60 54be8251 2018-06-04 stsp struct got_object_idset *
 61 60f2eee1 2018-07-08 stsp got_object_idset_alloc(void)
 62 54be8251 2018-06-04 stsp {
 63 54be8251 2018-06-04 stsp 	struct got_object_idset *set;
 64 54be8251 2018-06-04 stsp 
 65 984e8a45 2018-11-05 stsp 	set = malloc(sizeof(*set));
 66 54be8251 2018-06-04 stsp 	if (set == NULL)
 67 54be8251 2018-06-04 stsp 		return NULL;
 68 54be8251 2018-06-04 stsp 
 69 e336e3d6 2018-11-05 stsp 	RB_INIT(&set->entries);
 70 984e8a45 2018-11-05 stsp 	set->totelem = 0;
 71 54be8251 2018-06-04 stsp 
 72 54be8251 2018-06-04 stsp 	return set;
 73 54be8251 2018-06-04 stsp }
 74 54be8251 2018-06-04 stsp 
 75 54be8251 2018-06-04 stsp void
 76 54be8251 2018-06-04 stsp got_object_idset_free(struct got_object_idset *set)
 77 54be8251 2018-06-04 stsp {
 78 54be8251 2018-06-04 stsp 	struct got_object_idset_element *entry;
 79 54be8251 2018-06-04 stsp 
 80 e336e3d6 2018-11-05 stsp 	while ((entry = RB_MIN(got_object_idset_tree, &set->entries))) {
 81 e336e3d6 2018-11-05 stsp 		RB_REMOVE(got_object_idset_tree, &set->entries, entry);
 82 984e8a45 2018-11-05 stsp 		/* User data should be freed by caller. */
 83 984e8a45 2018-11-05 stsp 		free(entry);
 84 54be8251 2018-06-04 stsp 	}
 85 984e8a45 2018-11-05 stsp 
 86 54be8251 2018-06-04 stsp 	free(set);
 87 54be8251 2018-06-04 stsp }
 88 54be8251 2018-06-04 stsp 
 89 54be8251 2018-06-04 stsp const struct got_error *
 90 b36429ab 2018-11-05 stsp got_object_idset_add(struct got_object_idset *set, struct got_object_id *id,
 91 b36429ab 2018-11-05 stsp     void *data)
 92 54be8251 2018-06-04 stsp {
 93 b36429ab 2018-11-05 stsp 	struct got_object_idset_element *new;
 94 54be8251 2018-06-04 stsp 
 95 2bd394ff 2018-06-22 stsp 	if (set->totelem >= GOT_OBJECT_IDSET_MAX_ELEM)
 96 c6f420bf 2018-06-04 stsp 		return got_error(GOT_ERR_NO_SPACE);
 97 c6f420bf 2018-06-04 stsp 
 98 294f39b0 2018-11-05 stsp 	new = malloc(sizeof(*new));
 99 54be8251 2018-06-04 stsp 	if (new == NULL)
100 638f9024 2019-05-13 stsp 		return got_error_from_errno("malloc");
101 54be8251 2018-06-04 stsp 
102 54be8251 2018-06-04 stsp 	memcpy(&new->id, id, sizeof(new->id));
103 54be8251 2018-06-04 stsp 	new->data = data;
104 54be8251 2018-06-04 stsp 
105 e336e3d6 2018-11-05 stsp 	RB_INSERT(got_object_idset_tree, &set->entries, new);
106 b36429ab 2018-11-05 stsp 	set->totelem++;
107 b36429ab 2018-11-05 stsp 	return NULL;
108 54be8251 2018-06-04 stsp }
109 54be8251 2018-06-04 stsp 
110 984e8a45 2018-11-05 stsp static struct got_object_idset_element *
111 984e8a45 2018-11-05 stsp find_element(struct got_object_idset *set, struct got_object_id *id)
112 54be8251 2018-06-04 stsp {
113 60f2eee1 2018-07-08 stsp 	struct got_object_idset_element *entry;
114 54be8251 2018-06-04 stsp 
115 e336e3d6 2018-11-05 stsp 	entry = RB_ROOT(&set->entries);
116 984e8a45 2018-11-05 stsp 	while (entry) {
117 984e8a45 2018-11-05 stsp 		int cmp = got_object_id_cmp(id, &entry->id);
118 984e8a45 2018-11-05 stsp 		if (cmp < 0)
119 e336e3d6 2018-11-05 stsp 			entry = RB_LEFT(entry, entry);
120 984e8a45 2018-11-05 stsp 		else if (cmp > 0)
121 e336e3d6 2018-11-05 stsp 			entry = RB_RIGHT(entry, entry);
122 984e8a45 2018-11-05 stsp 		else
123 984e8a45 2018-11-05 stsp 			break;
124 54be8251 2018-06-04 stsp 	}
125 54be8251 2018-06-04 stsp 
126 984e8a45 2018-11-05 stsp 	return entry;
127 54be8251 2018-06-04 stsp }
128 54be8251 2018-06-04 stsp 
129 984e8a45 2018-11-05 stsp void *
130 984e8a45 2018-11-05 stsp got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
131 984e8a45 2018-11-05 stsp {
132 984e8a45 2018-11-05 stsp 	struct got_object_idset_element *entry = find_element(set, id);
133 984e8a45 2018-11-05 stsp 	return entry ? entry->data : NULL;
134 984e8a45 2018-11-05 stsp }
135 984e8a45 2018-11-05 stsp 
136 54be8251 2018-06-04 stsp const struct got_error *
137 e7c810ea 2018-06-22 stsp got_object_idset_remove(void **data, struct got_object_idset *set,
138 54be8251 2018-06-04 stsp     struct got_object_id *id)
139 54be8251 2018-06-04 stsp {
140 984e8a45 2018-11-05 stsp 	struct got_object_idset_element *entry;
141 54be8251 2018-06-04 stsp 
142 441e144c 2018-06-22 stsp 	if (data)
143 441e144c 2018-06-22 stsp 		*data = NULL;
144 441e144c 2018-06-22 stsp 
145 984e8a45 2018-11-05 stsp 	if (set->totelem == 0)
146 c6f420bf 2018-06-04 stsp 		return got_error(GOT_ERR_NO_OBJ);
147 c6f420bf 2018-06-04 stsp 
148 0ae61b79 2022-03-21 stsp 	if (id == NULL) {
149 e336e3d6 2018-11-05 stsp 		entry = RB_ROOT(&set->entries);
150 0ae61b79 2022-03-21 stsp 		if (entry == NULL)
151 0ae61b79 2022-03-21 stsp 			return got_error(GOT_ERR_NO_OBJ);
152 0ae61b79 2022-03-21 stsp 	} else {
153 f054b67a 2018-11-05 stsp 		entry = find_element(set, id);
154 0ae61b79 2022-03-21 stsp 		if (entry == NULL)
155 0ae61b79 2022-03-21 stsp 			return got_error_no_obj(id);
156 0ae61b79 2022-03-21 stsp 	}
157 54be8251 2018-06-04 stsp 
158 e336e3d6 2018-11-05 stsp 	RB_REMOVE(got_object_idset_tree, &set->entries, entry);
159 984e8a45 2018-11-05 stsp 	if (data)
160 984e8a45 2018-11-05 stsp 		*data = entry->data;
161 984e8a45 2018-11-05 stsp 	free(entry);
162 984e8a45 2018-11-05 stsp 	set->totelem--;
163 984e8a45 2018-11-05 stsp 	return NULL;
164 54be8251 2018-06-04 stsp }
165 54be8251 2018-06-04 stsp 
166 54be8251 2018-06-04 stsp int
167 54be8251 2018-06-04 stsp got_object_idset_contains(struct got_object_idset *set,
168 54be8251 2018-06-04 stsp     struct got_object_id *id)
169 54be8251 2018-06-04 stsp {
170 984e8a45 2018-11-05 stsp 	struct got_object_idset_element *entry = find_element(set, id);
171 984e8a45 2018-11-05 stsp 	return entry ? 1 : 0;
172 54be8251 2018-06-04 stsp }
173 54be8251 2018-06-04 stsp 
174 cb103d04 2018-11-07 stsp const struct got_error *
175 cb103d04 2018-11-07 stsp got_object_idset_for_each(struct got_object_idset *set,
176 cb103d04 2018-11-07 stsp     const struct got_error *(*cb)(struct got_object_id *, void *, void *),
177 cb103d04 2018-11-07 stsp     void *arg)
178 54be8251 2018-06-04 stsp {
179 cb103d04 2018-11-07 stsp 	const struct got_error *err;
180 9489f1f7 2018-11-11 stsp 	struct got_object_idset_element *entry, *tmp;
181 54be8251 2018-06-04 stsp 
182 9489f1f7 2018-11-11 stsp 	RB_FOREACH_SAFE(entry, got_object_idset_tree, &set->entries, tmp) {
183 cb103d04 2018-11-07 stsp 		err = (*cb)(&entry->id, entry->data, arg);
184 cb103d04 2018-11-07 stsp 		if (err)
185 cb103d04 2018-11-07 stsp 			return err;
186 cb103d04 2018-11-07 stsp 	}
187 cb103d04 2018-11-07 stsp 	return NULL;
188 54be8251 2018-06-04 stsp }
189 c6f420bf 2018-06-04 stsp 
190 069f84d5 2018-06-11 stsp int
191 c6f420bf 2018-06-04 stsp got_object_idset_num_elements(struct got_object_idset *set)
192 c6f420bf 2018-06-04 stsp {
193 2bd394ff 2018-06-22 stsp 	return set->totelem;
194 c6f420bf 2018-06-04 stsp }
195 984e8a45 2018-11-05 stsp 
196 67fd6849 2022-02-13 stsp struct got_object_idset_element *
197 67fd6849 2022-02-13 stsp got_object_idset_get_element(struct got_object_idset *set, struct got_object_id *id)
198 67fd6849 2022-02-13 stsp {
199 67fd6849 2022-02-13 stsp 	return find_element(set, id);
200 67fd6849 2022-02-13 stsp }
201 67fd6849 2022-02-13 stsp 
202 67fd6849 2022-02-13 stsp void *
203 67fd6849 2022-02-13 stsp got_object_idset_get_element_data(struct got_object_idset_element *entry)
204 67fd6849 2022-02-13 stsp {
205 67fd6849 2022-02-13 stsp 	return entry->data;
206 67fd6849 2022-02-13 stsp }
207 67fd6849 2022-02-13 stsp 
208 67fd6849 2022-02-13 stsp const struct got_error *
209 67fd6849 2022-02-13 stsp got_object_idset_for_each_element(struct got_object_idset *set,
210 67fd6849 2022-02-13 stsp     const struct got_error *(*cb)(struct got_object_idset_element *, void *),
211 67fd6849 2022-02-13 stsp     void *arg)
212 67fd6849 2022-02-13 stsp {
213 67fd6849 2022-02-13 stsp 	const struct got_error *err;
214 67fd6849 2022-02-13 stsp 	struct got_object_idset_element *entry, *tmp;
215 67fd6849 2022-02-13 stsp 
216 67fd6849 2022-02-13 stsp 	RB_FOREACH_SAFE(entry, got_object_idset_tree, &set->entries, tmp) {
217 67fd6849 2022-02-13 stsp 		err = (*cb)(entry, arg);
218 67fd6849 2022-02-13 stsp 		if (err)
219 67fd6849 2022-02-13 stsp 			return err;
220 67fd6849 2022-02-13 stsp 	}
221 67fd6849 2022-02-13 stsp 	return NULL;
222 67fd6849 2022-02-13 stsp }
223 67fd6849 2022-02-13 stsp 
224 67fd6849 2022-02-13 stsp void
225 67fd6849 2022-02-13 stsp got_object_idset_remove_element(struct got_object_idset *set,
226 67fd6849 2022-02-13 stsp     struct got_object_idset_element *entry)
227 67fd6849 2022-02-13 stsp {
228 67fd6849 2022-02-13 stsp 	RB_REMOVE(got_object_idset_tree, &set->entries, entry);
229 67fd6849 2022-02-13 stsp 	free(entry);
230 67fd6849 2022-02-13 stsp 	set->totelem--;
231 67fd6849 2022-02-13 stsp }
232 67fd6849 2022-02-13 stsp 
233 e336e3d6 2018-11-05 stsp RB_GENERATE(got_object_idset_tree, got_object_idset_element, entry,
234 984e8a45 2018-11-05 stsp     cmp_elements);