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