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_inflate.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[0xff + 1];
53 	int totelem;
54 #define GOT_OBJECT_IDSET_MAX_ELEM INT_MAX
55 };
56 
57 struct got_object_idset *
58 got_object_idset_alloc(void)
59 {
60 	struct got_object_idset *set;
61 	int i;
62 
63 	set = calloc(1, sizeof(*set));
64 	if (set == NULL)
65 		return NULL;
66 
67 	for (i = 0; i < nitems(set->entries); i++)
68 		TAILQ_INIT(&set->entries[i]);
69 
70 	return set;
71 }
72 
73 void
74 got_object_idset_free(struct got_object_idset *set)
75 {
76 	struct got_object_idset_element *entry;
77 	int i;
78 
79 	for (i = 0; i < nitems(set->entries); i++) {
80 		while (!TAILQ_EMPTY(&set->entries[i])) {
81 			entry = TAILQ_FIRST(&set->entries[i]);
82 			TAILQ_REMOVE(&set->entries[i], entry, entry);
83 			/* User data should be freed by caller. */
84 			free(entry);
85 		}
86 	}
87 	free(set);
88 }
89 
90 const struct got_error *
91 got_object_idset_add(void **existing_data,
92     struct got_object_idset *set, struct got_object_id *id, void *data)
93 {
94 	struct got_object_idset_element *new, *entry;
95 	uint8_t i = id->sha1[0];
96 
97 	if (existing_data)
98 		*existing_data = NULL;
99 
100 	if (set->totelem >= GOT_OBJECT_IDSET_MAX_ELEM)
101 		return got_error(GOT_ERR_NO_SPACE);
102 
103 	new = calloc(1, sizeof(*new));
104 	if (new == NULL)
105 		return got_error_from_errno();
106 
107 	memcpy(&new->id, id, sizeof(new->id));
108 	new->data = data;
109 
110 	if (TAILQ_EMPTY(&set->entries[i])) {
111 		TAILQ_INSERT_HEAD(&set->entries[i], new, entry);
112 		set->nelem[i]++;
113 		set->totelem++;
114 		return NULL;
115 	}
116 
117 	/*
118 	 * Keep the list sorted by ID so that iterations of
119 	 * the set occur in a predictable order.
120 	 */
121 	TAILQ_FOREACH(entry, &set->entries[i], entry) {
122 		int cmp = got_object_id_cmp(&new->id, &entry->id);
123 		struct got_object_idset_element *next;
124 
125 		if (cmp == 0) {
126 			free(new);
127 			if (existing_data)
128 				*existing_data = entry->data;
129 			return got_error(GOT_ERR_OBJ_EXISTS);
130 		} else if (cmp < 0) {
131 			TAILQ_INSERT_BEFORE(entry, new, entry);
132 			set->nelem[i]++;
133 			set->totelem++;
134 			return NULL;
135 		}
136 
137 		next = TAILQ_NEXT(entry, entry);
138 		if (next == NULL) {
139 			TAILQ_INSERT_AFTER(&set->entries[i], entry, new, entry);
140 			set->nelem[i]++;
141 			set->totelem++;
142 			return NULL;
143 		} else if (got_object_id_cmp(&new->id, &next->id) > 0) {
144 			TAILQ_INSERT_BEFORE(next, new, entry);
145 			set->nelem[i]++;
146 			set->totelem++;
147 			return NULL;
148 		}
149 	}
150 
151 	return got_error(GOT_ERR_BAD_OBJ_ID); /* should not get here */
152 }
153 
154 void *
155 got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
156 {
157 	struct got_object_idset_element *entry;
158 	uint8_t i = id->sha1[0];
159 
160 	TAILQ_FOREACH(entry, &set->entries[i], entry) {
161 		if (got_object_id_cmp(&entry->id, id) == 0)
162 			return entry->data;
163 	}
164 
165 	return NULL;
166 }
167 
168 const struct got_error *
169 got_object_idset_remove(void **data, struct got_object_idset *set,
170     struct got_object_id *id)
171 {
172 	struct got_object_idset_element *entry, *tmp;
173 	uint8_t i = id->sha1[0];
174 
175 	if (data)
176 		*data = NULL;
177 
178 	if (set->nelem[i] == 0)
179 		return got_error(GOT_ERR_NO_OBJ);
180 
181 	TAILQ_FOREACH_SAFE(entry, &set->entries[i], entry, tmp) {
182 		if (got_object_id_cmp(&entry->id, id) == 0) {
183 			TAILQ_REMOVE(&set->entries[i], entry, entry);
184 			if (data)
185 				*data = entry->data;
186 			free(entry);
187 			set->nelem[i]--;
188 			set->totelem--;
189 			return NULL;
190 		}
191 	}
192 
193 	return got_error(GOT_ERR_NO_OBJ);
194 }
195 
196 int
197 got_object_idset_contains(struct got_object_idset *set,
198     struct got_object_id *id)
199 {
200 	struct got_object_idset_element *entry;
201 	uint8_t i = id->sha1[0];
202 
203 	TAILQ_FOREACH(entry, &set->entries[i], entry) {
204 		if (got_object_id_cmp(&entry->id, id) == 0)
205 			return 1;
206 	}
207 
208 	return 0;
209 }
210 
211 void got_object_idset_for_each(struct got_object_idset *set,
212     void (*cb)(struct got_object_id *, void *, void *), void *arg)
213 {
214 	struct got_object_idset_element *entry;
215 	int i;
216 
217 	for (i = 0; i < nitems(set->entries); i++) {
218 		TAILQ_FOREACH(entry, &set->entries[i], entry)
219 			cb(&entry->id, entry->data, arg);
220 	}
221 }
222 
223 int
224 got_object_idset_num_elements(struct got_object_idset *set)
225 {
226 	return set->totelem;
227 }