1 /*
2  * Copyright (c) 2018 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/queue.h>
18 
19 #include <stdlib.h>
20 #include <string.h>
21 #include <sha1.h>
22 #include <stdio.h>
23 #include <zlib.h>
24 #include <limits.h>
25 #include <time.h>
26 
27 #include "got_object.h"
28 #include "got_error.h"
29 
30 #include "got_lib_delta.h"
31 #include "got_lib_zbuf.h"
32 #include "got_lib_object.h"
33 #include "got_lib_object_idset.h"
34 
35 #ifndef nitems
36 #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
37 #endif
38 
39 struct got_object_idset_element {
40 	TAILQ_ENTRY(got_object_idset_element) entry;
41 	struct got_object_id id;
42 	void *data;	/* API user data */
43 };
44 
45 struct got_object_idset {
46 	/*
47 	 * A set is implemented as a collection of 256 lists.
48 	 * The value of the first byte of an object ID determines
49 	 * which of these lists an object ID is stored in.
50 	 */
51 	TAILQ_HEAD(, got_object_idset_element) entries[0xff + 1];
52 	int nelem;
53 #define GOT_OBJECT_IDSET_MAX_ELEM INT_MAX
54 };
55 
56 struct got_object_idset *
57 got_object_idset_alloc(void)
58 {
59 	struct got_object_idset *set;
60 	int i;
61 
62 	set = calloc(1, sizeof(*set));
63 	if (set == NULL)
64 		return NULL;
65 
66 	for (i = 0; i < nitems(set->entries); i++)
67 		TAILQ_INIT(&set->entries[i]);
68 
69 	return set;
70 }
71 
72 void
73 got_object_idset_free(struct got_object_idset *set)
74 {
75 	struct got_object_idset_element *entry;
76 	int i;
77 
78 	for (i = 0; i < nitems(set->entries); i++) {
79 		while (!TAILQ_EMPTY(&set->entries[i])) {
80 			entry = TAILQ_FIRST(&set->entries[i]);
81 			TAILQ_REMOVE(&set->entries[i], entry, entry);
82 			/* User data should be freed by caller. */
83 			free(entry);
84 		}
85 	}
86 	free(set);
87 }
88 
89 const struct got_error *
90 got_object_idset_add(void **existing_data,
91     struct got_object_idset *set, struct got_object_id *id, void *data)
92 {
93 	struct got_object_idset_element *new, *entry;
94 	uint8_t i = id->sha1[0];
95 
96 	if (existing_data)
97 		*existing_data = NULL;
98 
99 	if (set->nelem >= GOT_OBJECT_IDSET_MAX_ELEM)
100 		return got_error(GOT_ERR_NO_SPACE);
101 
102 	new = calloc(1, sizeof(*new));
103 	if (new == NULL)
104 		return got_error_from_errno();
105 
106 	memcpy(&new->id, id, sizeof(new->id));
107 	new->data = data;
108 
109 	if (TAILQ_EMPTY(&set->entries[i])) {
110 		TAILQ_INSERT_HEAD(&set->entries[i], new, entry);
111 		set->nelem++;
112 		return NULL;
113 	}
114 
115 	/*
116 	 * Keep the list sorted by ID so that iterations of
117 	 * the set occur in a predictable order.
118 	 */
119 	TAILQ_FOREACH(entry, &set->entries[i], entry) {
120 		int cmp = got_object_id_cmp(&new->id, &entry->id);
121 		struct got_object_idset_element *next;
122 
123 		if (cmp == 0) {
124 			free(new);
125 			if (existing_data)
126 				*existing_data = entry->data;
127 			return got_error(GOT_ERR_OBJ_EXISTS);
128 		} else if (cmp < 0) {
129 			TAILQ_INSERT_BEFORE(entry, new, entry);
130 			set->nelem++;
131 			return NULL;
132 		}
133 
134 		next = TAILQ_NEXT(entry, entry);
135 		if (next == NULL) {
136 			TAILQ_INSERT_AFTER(&set->entries[i], entry, new, entry);
137 			set->nelem++;
138 			return NULL;
139 		} else if (got_object_id_cmp(&new->id, &next->id) > 0) {
140 			TAILQ_INSERT_BEFORE(next, new, entry);
141 			set->nelem++;
142 			return NULL;
143 		}
144 	}
145 
146 	return got_error(GOT_ERR_BAD_OBJ_ID); /* should not get here */
147 }
148 
149 void *
150 got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
151 {
152 	struct got_object_idset_element *entry;
153 	uint8_t i = id->sha1[0];
154 
155 	TAILQ_FOREACH(entry, &set->entries[i], entry) {
156 		if (got_object_id_cmp(&entry->id, id) == 0)
157 			return entry->data;
158 	}
159 
160 	return NULL;
161 }
162 
163 const struct got_error *
164 got_object_idset_remove(void **data, struct got_object_idset *set,
165     struct got_object_id *id)
166 {
167 	struct got_object_idset_element *entry, *tmp;
168 	uint8_t i = id->sha1[0];
169 
170 	if (set->nelem == 0)
171 		return got_error(GOT_ERR_NO_OBJ);
172 
173 	TAILQ_FOREACH_SAFE(entry, &set->entries[i], entry, tmp) {
174 		if (got_object_id_cmp(&entry->id, id) == 0) {
175 			TAILQ_REMOVE(&set->entries[i], entry, entry);
176 			if (data)
177 				*data = entry->data;
178 			free(entry);
179 			set->nelem--;
180 			return NULL;
181 		}
182 	}
183 
184 	return got_error(GOT_ERR_NO_OBJ);
185 }
186 
187 const struct got_error *
188 got_object_idset_remove_random(void **data, struct got_object_idset *set)
189 {
190 	struct got_object_idset_element *entry, *tmp;
191 	int i, n;
192 
193 	*data = NULL;
194 
195 	if (set->nelem == 0)
196 		return got_error(GOT_ERR_NO_OBJ);
197 
198 	n = arc4random_uniform(set->nelem);
199 	for (i = 0; i < nitems(set->entries); i++) {
200 		TAILQ_FOREACH_SAFE(entry, &set->entries[i], entry, tmp) {
201 			if (--n == 0) {
202 				TAILQ_REMOVE(&set->entries[i], entry, entry);
203 				*data = entry->data;
204 				free(entry);
205 				set->nelem--;
206 				return NULL;
207 			}
208 		}
209 
210 	}
211 
212 	return got_error(GOT_ERR_NO_OBJ);
213 }
214 
215 int
216 got_object_idset_contains(struct got_object_idset *set,
217     struct got_object_id *id)
218 {
219 	struct got_object_idset_element *entry;
220 	uint8_t i = id->sha1[0];
221 
222 	TAILQ_FOREACH(entry, &set->entries[i], entry) {
223 		if (got_object_id_cmp(&entry->id, id) == 0)
224 			return 1;
225 	}
226 
227 	return 0;
228 }
229 
230 void got_object_idset_for_each(struct got_object_idset *set,
231     void (*cb)(struct got_object_id *, void *, void *), void *arg)
232 {
233 	struct got_object_idset_element *entry;
234 	int i;
235 
236 	for (i = 0; i < nitems(set->entries); i++) {
237 		TAILQ_FOREACH(entry, &set->entries[i], entry)
238 			cb(&entry->id, entry->data, arg);
239 	}
240 }
241 
242 int
243 got_object_idset_num_elements(struct got_object_idset *set)
244 {
245 	return set->nelem;
246 }