2 619de35f 2022-04-22 thomas * Copyright (c) 2022 Stefan Sperling <stsp@openbsd.org>
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.
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.
17 8b925c6c 2022-07-16 thomas #include <sys/queue.h>
18 54be8251 2018-06-04 stsp #include <stdlib.h>
19 619de35f 2022-04-22 thomas #include <stdint.h>
20 54be8251 2018-06-04 stsp #include <string.h>
21 54be8251 2018-06-04 stsp #include <stdio.h>
22 54be8251 2018-06-04 stsp #include <zlib.h>
23 c6f420bf 2018-06-04 stsp #include <limits.h>
24 788c352e 2018-06-16 stsp #include <time.h>
25 619de35f 2022-04-22 thomas #include <errno.h>
27 dd038bc6 2021-09-21 thomas.ad #include "got_compat.h"
29 54be8251 2018-06-04 stsp #include "got_object.h"
30 54be8251 2018-06-04 stsp #include "got_error.h"
32 54be8251 2018-06-04 stsp #include "got_lib_delta.h"
33 63581804 2018-07-09 stsp #include "got_lib_inflate.h"
34 54be8251 2018-06-04 stsp #include "got_lib_object.h"
35 54be8251 2018-06-04 stsp #include "got_lib_object_idset.h"
36 619de35f 2022-04-22 thomas #include "got_lib_object_parse.h"
38 619de35f 2022-04-22 thomas #define GOT_OBJECT_IDSET_MIN_BUCKETS 64
40 54be8251 2018-06-04 stsp struct got_object_idset {
41 619de35f 2022-04-22 thomas struct got_object_id_queue *ids;
42 619de35f 2022-04-22 thomas size_t nbuckets;
43 619de35f 2022-04-22 thomas unsigned int totelem;
44 619de35f 2022-04-22 thomas unsigned int flags;
45 619de35f 2022-04-22 thomas #define GOT_OBJECT_IDSET_F_TRAVERSAL 0x01
46 619de35f 2022-04-22 thomas #define GOT_OBJECT_IDSET_F_NOMEM 0x02
47 619de35f 2022-04-22 thomas SIPHASH_KEY key;
50 54be8251 2018-06-04 stsp struct got_object_idset *
51 60f2eee1 2018-07-08 stsp got_object_idset_alloc(void)
53 54be8251 2018-06-04 stsp struct got_object_idset *set;
56 984e8a45 2018-11-05 stsp set = malloc(sizeof(*set));
57 54be8251 2018-06-04 stsp if (set == NULL)
58 54be8251 2018-06-04 stsp return NULL;
60 619de35f 2022-04-22 thomas set->ids = calloc(sizeof(set->ids[0]), GOT_OBJECT_IDSET_MIN_BUCKETS);
61 619de35f 2022-04-22 thomas if (set->ids == NULL) {
62 619de35f 2022-04-22 thomas free(set);
63 619de35f 2022-04-22 thomas return NULL;
65 619de35f 2022-04-22 thomas for (i = 0; i < GOT_OBJECT_IDSET_MIN_BUCKETS; i++)
66 619de35f 2022-04-22 thomas STAILQ_INIT(&set->ids[i]);
68 619de35f 2022-04-22 thomas set->totelem = 0;
69 619de35f 2022-04-22 thomas set->nbuckets = GOT_OBJECT_IDSET_MIN_BUCKETS;
70 619de35f 2022-04-22 thomas set->flags = 0;
71 619de35f 2022-04-22 thomas arc4random_buf(&set->key, sizeof(set->key));
76 54be8251 2018-06-04 stsp got_object_idset_free(struct got_object_idset *set)
79 619de35f 2022-04-22 thomas struct got_object_qid *qid;
81 619de35f 2022-04-22 thomas for (i = 0; i < set->nbuckets; i++) {
82 619de35f 2022-04-22 thomas while (!STAILQ_EMPTY(&set->ids[i])) {
83 619de35f 2022-04-22 thomas qid = STAILQ_FIRST(&set->ids[i]);
84 619de35f 2022-04-22 thomas STAILQ_REMOVE(&set->ids[i], qid, got_object_qid, entry);
85 619de35f 2022-04-22 thomas got_object_qid_free(qid);
88 619de35f 2022-04-22 thomas /* User data should be freed by caller. */
89 619de35f 2022-04-22 thomas free(set->ids);
93 619de35f 2022-04-22 thomas static uint64_t
94 619de35f 2022-04-22 thomas idset_hash(struct got_object_idset *set, struct got_object_id *id)
96 619de35f 2022-04-22 thomas return SipHash24(&set->key, id->sha1, sizeof(id->sha1));
99 619de35f 2022-04-22 thomas static const struct got_error *
100 619de35f 2022-04-22 thomas idset_resize(struct got_object_idset *set, size_t nbuckets)
102 619de35f 2022-04-22 thomas struct got_object_id_queue *ids;
103 619de35f 2022-04-22 thomas size_t i;
105 619de35f 2022-04-22 thomas ids = calloc(nbuckets, sizeof(ids[0]));
106 619de35f 2022-04-22 thomas if (ids == NULL) {
107 619de35f 2022-04-22 thomas if (errno != ENOMEM)
108 619de35f 2022-04-22 thomas return got_error_from_errno("calloc");
109 619de35f 2022-04-22 thomas /* Proceed with our current amount of hash buckets. */
110 619de35f 2022-04-22 thomas set->flags |= GOT_OBJECT_IDSET_F_NOMEM;
111 619de35f 2022-04-22 thomas return NULL;
114 619de35f 2022-04-22 thomas for (i = 0; i < nbuckets; i++)
115 619de35f 2022-04-22 thomas STAILQ_INIT(&ids[i]);
117 619de35f 2022-04-22 thomas arc4random_buf(&set->key, sizeof(set->key));
119 619de35f 2022-04-22 thomas for (i = 0; i < set->nbuckets; i++) {
120 619de35f 2022-04-22 thomas while (!STAILQ_EMPTY(&set->ids[i])) {
121 619de35f 2022-04-22 thomas struct got_object_qid *qid;
122 619de35f 2022-04-22 thomas uint64_t idx;
123 619de35f 2022-04-22 thomas qid = STAILQ_FIRST(&set->ids[i]);
124 619de35f 2022-04-22 thomas STAILQ_REMOVE(&set->ids[i], qid, got_object_qid, entry);
125 ec242592 2022-04-22 thomas idx = idset_hash(set, &qid->id) % nbuckets;
126 619de35f 2022-04-22 thomas STAILQ_INSERT_HEAD(&ids[idx], qid, entry);
130 619de35f 2022-04-22 thomas free(set->ids);
131 619de35f 2022-04-22 thomas set->ids = ids;
132 619de35f 2022-04-22 thomas set->nbuckets = nbuckets;
133 b36429ab 2018-11-05 stsp return NULL;
136 619de35f 2022-04-22 thomas static const struct got_error *
137 619de35f 2022-04-22 thomas idset_grow(struct got_object_idset *set)
139 619de35f 2022-04-22 thomas size_t nbuckets;
141 619de35f 2022-04-22 thomas if (set->flags & GOT_OBJECT_IDSET_F_NOMEM)
142 619de35f 2022-04-22 thomas return NULL;
144 619de35f 2022-04-22 thomas if (set->nbuckets >= UINT_MAX / 2)
145 619de35f 2022-04-22 thomas nbuckets = UINT_MAX;
147 619de35f 2022-04-22 thomas nbuckets = set->nbuckets * 2;
149 619de35f 2022-04-22 thomas return idset_resize(set, nbuckets);
152 619de35f 2022-04-22 thomas const struct got_error *
153 619de35f 2022-04-22 thomas got_object_idset_add(struct got_object_idset *set, struct got_object_id *id,
154 619de35f 2022-04-22 thomas void *data)
156 619de35f 2022-04-22 thomas const struct got_error *err;
157 619de35f 2022-04-22 thomas struct got_object_qid *qid;
158 619de35f 2022-04-22 thomas uint64_t idx;
159 619de35f 2022-04-22 thomas struct got_object_id_queue *head;
161 619de35f 2022-04-22 thomas /* This function may resize the set. */
162 619de35f 2022-04-22 thomas if (set->flags & GOT_OBJECT_IDSET_F_TRAVERSAL)
163 619de35f 2022-04-22 thomas return got_error_msg(GOT_ERR_NOT_IMPL,
164 619de35f 2022-04-22 thomas "cannot add elements to idset during traversal");
166 619de35f 2022-04-22 thomas if (set->totelem == UINT_MAX)
167 619de35f 2022-04-22 thomas return got_error(GOT_ERR_NO_SPACE);
169 619de35f 2022-04-22 thomas err = got_object_qid_alloc_partial(&qid);
171 619de35f 2022-04-22 thomas return err;
172 ec242592 2022-04-22 thomas memcpy(&qid->id, id, sizeof(qid->id));
173 619de35f 2022-04-22 thomas qid->data = data;
175 619de35f 2022-04-22 thomas idx = idset_hash(set, id) % set->nbuckets;
176 619de35f 2022-04-22 thomas head = &set->ids[idx];
177 619de35f 2022-04-22 thomas STAILQ_INSERT_HEAD(head, qid, entry);
178 619de35f 2022-04-22 thomas set->totelem++;
180 619de35f 2022-04-22 thomas if (set->nbuckets < set->totelem)
181 619de35f 2022-04-22 thomas err = idset_grow(set);
183 619de35f 2022-04-22 thomas return err;
186 619de35f 2022-04-22 thomas static struct got_object_qid *
187 619de35f 2022-04-22 thomas find_element(struct got_object_idset *set, struct got_object_id *id)
189 619de35f 2022-04-22 thomas uint64_t idx = idset_hash(set, id) % set->nbuckets;
190 619de35f 2022-04-22 thomas struct got_object_id_queue *head = &set->ids[idx];
191 619de35f 2022-04-22 thomas struct got_object_qid *qid;
193 619de35f 2022-04-22 thomas STAILQ_FOREACH(qid, head, entry) {
194 ec242592 2022-04-22 thomas if (got_object_id_cmp(&qid->id, id) == 0)
195 619de35f 2022-04-22 thomas return qid;
198 619de35f 2022-04-22 thomas return NULL;
202 984e8a45 2018-11-05 stsp got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
204 619de35f 2022-04-22 thomas struct got_object_qid *qid = find_element(set, id);
205 619de35f 2022-04-22 thomas return qid ? qid->data : NULL;
208 54be8251 2018-06-04 stsp const struct got_error *
209 e7c810ea 2018-06-22 stsp got_object_idset_remove(void **data, struct got_object_idset *set,
210 54be8251 2018-06-04 stsp struct got_object_id *id)
212 619de35f 2022-04-22 thomas uint64_t idx;
213 619de35f 2022-04-22 thomas struct got_object_id_queue *head;
214 619de35f 2022-04-22 thomas struct got_object_qid *qid;
217 441e144c 2018-06-22 stsp *data = NULL;
219 984e8a45 2018-11-05 stsp if (set->totelem == 0)
220 c6f420bf 2018-06-04 stsp return got_error(GOT_ERR_NO_OBJ);
222 3a4790b6 2022-03-22 thomas if (id == NULL) {
223 619de35f 2022-04-22 thomas /* Remove a "random" element. */
224 619de35f 2022-04-22 thomas for (idx = 0; idx < set->nbuckets; idx++) {
225 619de35f 2022-04-22 thomas head = &set->ids[idx];
226 619de35f 2022-04-22 thomas qid = STAILQ_FIRST(head);
231 619de35f 2022-04-22 thomas idx = idset_hash(set, id) % set->nbuckets;
232 619de35f 2022-04-22 thomas head = &set->ids[idx];
233 619de35f 2022-04-22 thomas STAILQ_FOREACH(qid, head, entry) {
234 ec242592 2022-04-22 thomas if (got_object_id_cmp(&qid->id, id) == 0)
237 619de35f 2022-04-22 thomas if (qid == NULL)
238 3a4790b6 2022-03-22 thomas return got_error_no_obj(id);
242 619de35f 2022-04-22 thomas *data = qid->data;
243 619de35f 2022-04-22 thomas STAILQ_REMOVE(head, qid, got_object_qid, entry);
244 619de35f 2022-04-22 thomas got_object_qid_free(qid);
245 984e8a45 2018-11-05 stsp set->totelem--;
247 984e8a45 2018-11-05 stsp return NULL;
251 54be8251 2018-06-04 stsp got_object_idset_contains(struct got_object_idset *set,
252 54be8251 2018-06-04 stsp struct got_object_id *id)
254 619de35f 2022-04-22 thomas struct got_object_qid *qid = find_element(set, id);
255 619de35f 2022-04-22 thomas return qid ? 1 : 0;
258 cb103d04 2018-11-07 stsp const struct got_error *
259 cb103d04 2018-11-07 stsp got_object_idset_for_each(struct got_object_idset *set,
260 cb103d04 2018-11-07 stsp const struct got_error *(*cb)(struct got_object_id *, void *, void *),
263 619de35f 2022-04-22 thomas const struct got_error *err = NULL;
264 619de35f 2022-04-22 thomas struct got_object_id_queue *head;
265 619de35f 2022-04-22 thomas struct got_object_qid *qid, *tmp;
266 619de35f 2022-04-22 thomas size_t i;
268 619de35f 2022-04-22 thomas set->flags |= GOT_OBJECT_IDSET_F_TRAVERSAL;
269 619de35f 2022-04-22 thomas for (i = 0; i < set->nbuckets; i++) {
270 619de35f 2022-04-22 thomas head = &set->ids[i];
271 619de35f 2022-04-22 thomas STAILQ_FOREACH_SAFE(qid, head, entry, tmp) {
272 ec242592 2022-04-22 thomas err = (*cb)(&qid->id, qid->data, arg);
274 619de35f 2022-04-22 thomas goto done;
278 619de35f 2022-04-22 thomas set->flags &= ~GOT_OBJECT_IDSET_F_TRAVERSAL;
279 619de35f 2022-04-22 thomas return err;
283 c6f420bf 2018-06-04 stsp got_object_idset_num_elements(struct got_object_idset *set)
285 2bd394ff 2018-06-22 stsp return set->totelem;
