2 * Copyright (c) 2022 Stefan Sperling <stsp@openbsd.org>
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.
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.
17 #include <sys/queue.h>
31 #include "got_object.h"
32 #include "got_error.h"
34 #include "got_lib_delta.h"
35 #include "got_lib_inflate.h"
36 #include "got_lib_object.h"
37 #include "got_lib_object_qid.h"
38 #include "got_lib_object_idset.h"
39 #include "got_lib_object_parse.h"
41 #define GOT_OBJECT_IDSET_MIN_BUCKETS 64
43 struct got_object_idset {
44 struct got_object_id_queue *ids;
48 #define GOT_OBJECT_IDSET_F_TRAVERSAL 0x01
49 #define GOT_OBJECT_IDSET_F_NOMEM 0x02
53 struct got_object_idset *
54 got_object_idset_alloc(void)
56 struct got_object_idset *set;
59 set = malloc(sizeof(*set));
63 set->ids = calloc(GOT_OBJECT_IDSET_MIN_BUCKETS, sizeof(set->ids[0]));
64 if (set->ids == NULL) {
68 for (i = 0; i < GOT_OBJECT_IDSET_MIN_BUCKETS; i++)
69 STAILQ_INIT(&set->ids[i]);
72 set->nbuckets = GOT_OBJECT_IDSET_MIN_BUCKETS;
74 arc4random_buf(&set->key, sizeof(set->key));
79 got_object_idset_free(struct got_object_idset *set)
82 struct got_object_qid *qid;
84 for (i = 0; i < set->nbuckets; i++) {
85 while (!STAILQ_EMPTY(&set->ids[i])) {
86 qid = STAILQ_FIRST(&set->ids[i]);
87 STAILQ_REMOVE(&set->ids[i], qid, got_object_qid, entry);
88 got_object_qid_free(qid);
91 /* User data should be freed by caller. */
97 idset_hash(struct got_object_idset *set, struct got_object_id *id)
99 return SipHash24(&set->key, id->sha1, sizeof(id->sha1));
102 static const struct got_error *
103 idset_resize(struct got_object_idset *set, size_t nbuckets)
105 struct got_object_id_queue *ids;
108 ids = calloc(nbuckets, sizeof(ids[0]));
111 return got_error_from_errno("calloc");
112 /* Proceed with our current amount of hash buckets. */
113 set->flags |= GOT_OBJECT_IDSET_F_NOMEM;
117 for (i = 0; i < nbuckets; i++)
118 STAILQ_INIT(&ids[i]);
120 arc4random_buf(&set->key, sizeof(set->key));
122 for (i = 0; i < set->nbuckets; i++) {
123 while (!STAILQ_EMPTY(&set->ids[i])) {
124 struct got_object_qid *qid;
126 qid = STAILQ_FIRST(&set->ids[i]);
127 STAILQ_REMOVE(&set->ids[i], qid, got_object_qid, entry);
128 idx = idset_hash(set, &qid->id) % nbuckets;
129 STAILQ_INSERT_HEAD(&ids[idx], qid, entry);
135 set->nbuckets = nbuckets;
139 static const struct got_error *
140 idset_grow(struct got_object_idset *set)
144 if (set->flags & GOT_OBJECT_IDSET_F_NOMEM)
147 if (set->nbuckets >= UINT_MAX / 2)
150 nbuckets = set->nbuckets * 2;
152 return idset_resize(set, nbuckets);
155 const struct got_error *
156 got_object_idset_add(struct got_object_idset *set, struct got_object_id *id,
159 const struct got_error *err;
160 struct got_object_qid *qid;
162 struct got_object_id_queue *head;
164 /* This function may resize the set. */
165 if (set->flags & GOT_OBJECT_IDSET_F_TRAVERSAL)
166 return got_error_msg(GOT_ERR_NOT_IMPL,
167 "cannot add elements to idset during traversal");
169 if (set->totelem == UINT_MAX)
170 return got_error(GOT_ERR_NO_SPACE);
172 err = got_object_qid_alloc_partial(&qid);
175 memcpy(&qid->id, id, sizeof(qid->id));
178 idx = idset_hash(set, id) % set->nbuckets;
179 head = &set->ids[idx];
180 STAILQ_INSERT_HEAD(head, qid, entry);
183 if (set->nbuckets < set->totelem)
184 err = idset_grow(set);
189 static struct got_object_qid *
190 find_element(struct got_object_idset *set, struct got_object_id *id)
192 uint64_t idx = idset_hash(set, id) % set->nbuckets;
193 struct got_object_id_queue *head = &set->ids[idx];
194 struct got_object_qid *qid;
196 STAILQ_FOREACH(qid, head, entry) {
197 if (got_object_id_cmp(&qid->id, id) == 0)
205 got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
207 struct got_object_qid *qid = find_element(set, id);
208 return qid ? qid->data : NULL;
211 const struct got_error *
212 got_object_idset_remove(void **data, struct got_object_idset *set,
213 struct got_object_id *id)
216 struct got_object_id_queue *head;
217 struct got_object_qid *qid;
222 if (set->totelem == 0)
223 return got_error(GOT_ERR_NO_OBJ);
226 /* Remove a "random" element. */
227 for (idx = 0; idx < set->nbuckets; idx++) {
228 head = &set->ids[idx];
229 qid = STAILQ_FIRST(head);
234 idx = idset_hash(set, id) % set->nbuckets;
235 head = &set->ids[idx];
236 STAILQ_FOREACH(qid, head, entry) {
237 if (got_object_id_cmp(&qid->id, id) == 0)
241 return got_error_no_obj(id);
246 STAILQ_REMOVE(head, qid, got_object_qid, entry);
247 got_object_qid_free(qid);
254 got_object_idset_contains(struct got_object_idset *set,
255 struct got_object_id *id)
257 struct got_object_qid *qid = find_element(set, id);
261 const struct got_error *
262 got_object_idset_for_each(struct got_object_idset *set,
263 const struct got_error *(*cb)(struct got_object_id *, void *, void *),
266 const struct got_error *err = NULL;
267 struct got_object_id_queue *head;
268 struct got_object_qid *qid, *tmp;
271 set->flags |= GOT_OBJECT_IDSET_F_TRAVERSAL;
272 for (i = 0; i < set->nbuckets; i++) {
274 STAILQ_FOREACH_SAFE(qid, head, entry, tmp) {
275 err = (*cb)(&qid->id, qid->data, arg);
281 set->flags &= ~GOT_OBJECT_IDSET_F_TRAVERSAL;
286 got_object_idset_num_elements(struct got_object_idset *set)