2 54be8251 2018-06-04 stsp * Copyright (c) 2018 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 54be8251 2018-06-04 stsp #include <sys/queue.h>
19 54be8251 2018-06-04 stsp #include <stdlib.h>
20 54be8251 2018-06-04 stsp #include <string.h>
21 54be8251 2018-06-04 stsp #include <sha1.h>
22 54be8251 2018-06-04 stsp #include <stdio.h>
23 54be8251 2018-06-04 stsp #include <zlib.h>
24 c6f420bf 2018-06-04 stsp #include <limits.h>
25 788c352e 2018-06-16 stsp #include <time.h>
27 54be8251 2018-06-04 stsp #include "got_object.h"
28 54be8251 2018-06-04 stsp #include "got_error.h"
30 54be8251 2018-06-04 stsp #include "got_lib_delta.h"
31 54be8251 2018-06-04 stsp #include "got_lib_zbuf.h"
32 54be8251 2018-06-04 stsp #include "got_lib_object.h"
33 54be8251 2018-06-04 stsp #include "got_lib_object_idset.h"
35 54be8251 2018-06-04 stsp #ifndef nitems
36 54be8251 2018-06-04 stsp #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
39 54be8251 2018-06-04 stsp struct got_object_idset_element {
40 54be8251 2018-06-04 stsp TAILQ_ENTRY(got_object_idset_element) entry;
41 54be8251 2018-06-04 stsp struct got_object_id id;
42 54be8251 2018-06-04 stsp void *data; /* API user data */
45 54be8251 2018-06-04 stsp struct got_object_idset {
47 54be8251 2018-06-04 stsp * A set is implemented as a collection of 256 lists.
48 54be8251 2018-06-04 stsp * The value of the first byte of an object ID determines
49 54be8251 2018-06-04 stsp * which of these lists an object ID is stored in.
51 54be8251 2018-06-04 stsp TAILQ_HEAD(, got_object_idset_element) entries[0xff + 1];
52 2bd394ff 2018-06-22 stsp int nelem[0xff + 1];
53 2bd394ff 2018-06-22 stsp int totelem;
54 069f84d5 2018-06-11 stsp #define GOT_OBJECT_IDSET_MAX_ELEM INT_MAX
55 d54f52f4 2018-07-07 stsp enum got_object_idset_iteration_order order;
58 54be8251 2018-06-04 stsp struct got_object_idset *
59 d54f52f4 2018-07-07 stsp got_object_idset_alloc(enum got_object_idset_iteration_order order)
61 54be8251 2018-06-04 stsp struct got_object_idset *set;
64 54be8251 2018-06-04 stsp set = calloc(1, sizeof(*set));
65 54be8251 2018-06-04 stsp if (set == NULL)
66 54be8251 2018-06-04 stsp return NULL;
68 d54f52f4 2018-07-07 stsp set->order = order;
69 54be8251 2018-06-04 stsp for (i = 0; i < nitems(set->entries); i++)
70 54be8251 2018-06-04 stsp TAILQ_INIT(&set->entries[i]);
76 54be8251 2018-06-04 stsp got_object_idset_free(struct got_object_idset *set)
78 54be8251 2018-06-04 stsp struct got_object_idset_element *entry;
81 54be8251 2018-06-04 stsp for (i = 0; i < nitems(set->entries); i++) {
82 54be8251 2018-06-04 stsp while (!TAILQ_EMPTY(&set->entries[i])) {
83 54be8251 2018-06-04 stsp entry = TAILQ_FIRST(&set->entries[i]);
84 54be8251 2018-06-04 stsp TAILQ_REMOVE(&set->entries[i], entry, entry);
85 54be8251 2018-06-04 stsp /* User data should be freed by caller. */
86 54be8251 2018-06-04 stsp free(entry);
92 54be8251 2018-06-04 stsp const struct got_error *
93 d5a90aac 2018-06-04 stsp got_object_idset_add(void **existing_data,
94 d5a90aac 2018-06-04 stsp struct got_object_idset *set, struct got_object_id *id, void *data)
96 54be8251 2018-06-04 stsp struct got_object_idset_element *new, *entry;
97 54be8251 2018-06-04 stsp uint8_t i = id->sha1[0];
99 d5a90aac 2018-06-04 stsp if (existing_data)
100 d5a90aac 2018-06-04 stsp *existing_data = NULL;
102 2bd394ff 2018-06-22 stsp if (set->totelem >= GOT_OBJECT_IDSET_MAX_ELEM)
103 c6f420bf 2018-06-04 stsp return got_error(GOT_ERR_NO_SPACE);
105 54be8251 2018-06-04 stsp new = calloc(1, sizeof(*new));
106 54be8251 2018-06-04 stsp if (new == NULL)
107 54be8251 2018-06-04 stsp return got_error_from_errno();
109 54be8251 2018-06-04 stsp memcpy(&new->id, id, sizeof(new->id));
110 54be8251 2018-06-04 stsp new->data = data;
112 d54f52f4 2018-07-07 stsp if (TAILQ_EMPTY(&set->entries[i]) ||
113 d54f52f4 2018-07-07 stsp set->order == GOT_OBJECT_IDSET_ITERATE_RECENTLY_USED) {
114 54be8251 2018-06-04 stsp TAILQ_INSERT_HEAD(&set->entries[i], new, entry);
115 2bd394ff 2018-06-22 stsp set->nelem[i]++;
116 2bd394ff 2018-06-22 stsp set->totelem++;
117 54be8251 2018-06-04 stsp return NULL;
121 54be8251 2018-06-04 stsp * Keep the list sorted by ID so that iterations of
122 54be8251 2018-06-04 stsp * the set occur in a predictable order.
124 54be8251 2018-06-04 stsp TAILQ_FOREACH(entry, &set->entries[i], entry) {
125 54be8251 2018-06-04 stsp int cmp = got_object_id_cmp(&new->id, &entry->id);
126 54be8251 2018-06-04 stsp struct got_object_idset_element *next;
128 54be8251 2018-06-04 stsp if (cmp == 0) {
130 d5a90aac 2018-06-04 stsp if (existing_data)
131 d5a90aac 2018-06-04 stsp *existing_data = entry->data;
132 54be8251 2018-06-04 stsp return got_error(GOT_ERR_OBJ_EXISTS);
133 54be8251 2018-06-04 stsp } else if (cmp < 0) {
134 54be8251 2018-06-04 stsp TAILQ_INSERT_BEFORE(entry, new, entry);
135 2bd394ff 2018-06-22 stsp set->nelem[i]++;
136 2bd394ff 2018-06-22 stsp set->totelem++;
137 54be8251 2018-06-04 stsp return NULL;
140 54be8251 2018-06-04 stsp next = TAILQ_NEXT(entry, entry);
141 54be8251 2018-06-04 stsp if (next == NULL) {
142 54be8251 2018-06-04 stsp TAILQ_INSERT_AFTER(&set->entries[i], entry, new, entry);
143 2bd394ff 2018-06-22 stsp set->nelem[i]++;
144 2bd394ff 2018-06-22 stsp set->totelem++;
145 54be8251 2018-06-04 stsp return NULL;
146 54be8251 2018-06-04 stsp } else if (got_object_id_cmp(&new->id, &next->id) > 0) {
147 54be8251 2018-06-04 stsp TAILQ_INSERT_BEFORE(next, new, entry);
148 2bd394ff 2018-06-22 stsp set->nelem[i]++;
149 2bd394ff 2018-06-22 stsp set->totelem++;
150 54be8251 2018-06-04 stsp return NULL;
154 54be8251 2018-06-04 stsp return got_error(GOT_ERR_BAD_OBJ_ID); /* should not get here */
158 45b73774 2018-06-04 stsp got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
160 d54f52f4 2018-07-07 stsp struct got_object_idset_element *entry, *tmp;
161 54be8251 2018-06-04 stsp uint8_t i = id->sha1[0];
163 d54f52f4 2018-07-07 stsp TAILQ_FOREACH_SAFE(entry, &set->entries[i], entry, tmp) {
164 d54f52f4 2018-07-07 stsp if (got_object_id_cmp(&entry->id, id) != 0)
166 d54f52f4 2018-07-07 stsp if (set->order == GOT_OBJECT_IDSET_ITERATE_RECENTLY_USED &&
167 d54f52f4 2018-07-07 stsp entry != TAILQ_FIRST(&set->entries[i])) {
168 d54f52f4 2018-07-07 stsp TAILQ_REMOVE(&set->entries[i], entry, entry);
169 d54f52f4 2018-07-07 stsp TAILQ_INSERT_HEAD(&set->entries[i], entry, entry);
171 d54f52f4 2018-07-07 stsp return entry->data;
174 54be8251 2018-06-04 stsp return NULL;
177 54be8251 2018-06-04 stsp const struct got_error *
178 e7c810ea 2018-06-22 stsp got_object_idset_remove(void **data, struct got_object_idset *set,
179 54be8251 2018-06-04 stsp struct got_object_id *id)
181 54be8251 2018-06-04 stsp struct got_object_idset_element *entry, *tmp;
182 ac4e69fb 2018-06-22 stsp uint8_t i = id->sha1[0];
185 441e144c 2018-06-22 stsp *data = NULL;
187 2bd394ff 2018-06-22 stsp if (set->nelem[i] == 0)
188 c6f420bf 2018-06-04 stsp return got_error(GOT_ERR_NO_OBJ);
190 54be8251 2018-06-04 stsp TAILQ_FOREACH_SAFE(entry, &set->entries[i], entry, tmp) {
191 ac4e69fb 2018-06-22 stsp if (got_object_id_cmp(&entry->id, id) == 0) {
192 54be8251 2018-06-04 stsp TAILQ_REMOVE(&set->entries[i], entry, entry);
194 e7c810ea 2018-06-22 stsp *data = entry->data;
195 4a9bc5ca 2018-06-22 stsp free(entry);
196 2bd394ff 2018-06-22 stsp set->nelem[i]--;
197 2bd394ff 2018-06-22 stsp set->totelem--;
198 54be8251 2018-06-04 stsp return NULL;
202 54be8251 2018-06-04 stsp return got_error(GOT_ERR_NO_OBJ);
205 27c21a11 2018-06-22 stsp const struct got_error *
206 27c21a11 2018-06-22 stsp got_object_idset_remove_random(void **data, struct got_object_idset *set)
208 27c21a11 2018-06-22 stsp struct got_object_idset_element *entry, *tmp;
209 2bd394ff 2018-06-22 stsp int i, n, totelem;
212 433eb4d4 2018-06-22 stsp *data = NULL;
214 2bd394ff 2018-06-22 stsp if (set->totelem == 0)
215 27c21a11 2018-06-22 stsp return got_error(GOT_ERR_NO_OBJ);
217 2bd394ff 2018-06-22 stsp /* Pick a random element index across all lists. */
218 2bd394ff 2018-06-22 stsp if (set->totelem == 1)
221 2bd394ff 2018-06-22 stsp n = arc4random_uniform(set->totelem);
223 2bd394ff 2018-06-22 stsp totelem = 0;
224 27c21a11 2018-06-22 stsp for (i = 0; i < nitems(set->entries); i++) {
225 2bd394ff 2018-06-22 stsp /* Skip lists which don't contain the element we picked. */
226 2bd394ff 2018-06-22 stsp totelem += set->nelem[i];
227 2bd394ff 2018-06-22 stsp if (totelem == 0 || n > totelem - 1) {
228 2bd394ff 2018-06-22 stsp n -= set->nelem[i];
231 27c21a11 2018-06-22 stsp TAILQ_FOREACH_SAFE(entry, &set->entries[i], entry, tmp) {
232 a2965dbe 2018-06-22 stsp if (n == 0) {
233 27c21a11 2018-06-22 stsp TAILQ_REMOVE(&set->entries[i], entry, entry);
235 433eb4d4 2018-06-22 stsp *data = entry->data;
236 27c21a11 2018-06-22 stsp free(entry);
237 2bd394ff 2018-06-22 stsp set->nelem[i]--;
238 2bd394ff 2018-06-22 stsp set->totelem--;
239 27c21a11 2018-06-22 stsp return NULL;
245 27c21a11 2018-06-22 stsp return got_error(GOT_ERR_NO_OBJ);
249 54be8251 2018-06-04 stsp got_object_idset_contains(struct got_object_idset *set,
250 54be8251 2018-06-04 stsp struct got_object_id *id)
252 54be8251 2018-06-04 stsp struct got_object_idset_element *entry;
253 54be8251 2018-06-04 stsp uint8_t i = id->sha1[0];
255 54be8251 2018-06-04 stsp TAILQ_FOREACH(entry, &set->entries[i], entry) {
256 54be8251 2018-06-04 stsp if (got_object_id_cmp(&entry->id, id) == 0)
263 54be8251 2018-06-04 stsp void got_object_idset_for_each(struct got_object_idset *set,
264 917bfd05 2018-06-10 stsp void (*cb)(struct got_object_id *, void *, void *), void *arg)
266 956a5d5a 2018-06-04 stsp struct got_object_idset_element *entry;
269 54be8251 2018-06-04 stsp for (i = 0; i < nitems(set->entries); i++) {
270 956a5d5a 2018-06-04 stsp TAILQ_FOREACH(entry, &set->entries[i], entry)
271 917bfd05 2018-06-10 stsp cb(&entry->id, entry->data, arg);
276 c6f420bf 2018-06-04 stsp got_object_idset_num_elements(struct got_object_idset *set)
278 2bd394ff 2018-06-22 stsp return set->totelem;
