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