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