2 * Copyright (c) 2018 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>
26 #include "got_object.h"
27 #include "got_error.h"
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"
35 #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
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 */
44 struct got_object_idset {
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.
50 TAILQ_HEAD(, got_object_idset_element) entries[0xff + 1];
52 #define GOT_OBJECT_IDSET_MAX_ELEM UINT_MAX
55 struct got_object_idset *
56 got_object_idset_alloc(void)
58 struct got_object_idset *set;
61 set = calloc(1, sizeof(*set));
65 for (i = 0; i < nitems(set->entries); i++)
66 TAILQ_INIT(&set->entries[i]);
72 got_object_idset_free(struct got_object_idset *set)
74 struct got_object_idset_element *entry;
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. */
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)
92 struct got_object_idset_element *new, *entry;
93 uint8_t i = id->sha1[0];
96 *existing_data = NULL;
98 if (set->nelem >= GOT_OBJECT_IDSET_MAX_ELEM)
99 return got_error(GOT_ERR_NO_SPACE);
101 new = calloc(1, sizeof(*new));
103 return got_error_from_errno();
105 memcpy(&new->id, id, sizeof(new->id));
108 if (TAILQ_EMPTY(&set->entries[i])) {
109 TAILQ_INSERT_HEAD(&set->entries[i], new, entry);
115 * Keep the list sorted by ID so that iterations of
116 * the set occur in a predictable order.
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;
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);
133 next = TAILQ_NEXT(entry, entry);
135 TAILQ_INSERT_AFTER(&set->entries[i], entry, new, entry);
138 } else if (got_object_id_cmp(&new->id, &next->id) > 0) {
139 TAILQ_INSERT_BEFORE(next, new, entry);
145 return got_error(GOT_ERR_BAD_OBJ_ID); /* should not get here */
149 got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
151 struct got_object_idset_element *entry;
152 uint8_t i = id->sha1[0];
154 TAILQ_FOREACH(entry, &set->entries[i], entry) {
155 if (got_object_id_cmp(&entry->id, id) == 0)
162 const struct got_error *
163 got_object_idset_remove(struct got_object_idset *set,
164 struct got_object_id *id)
166 struct got_object_idset_element *entry, *tmp;
167 uint8_t i = id->sha1[0];
170 return got_error(GOT_ERR_NO_OBJ);
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);
180 return got_error(GOT_ERR_NO_OBJ);
184 got_object_idset_contains(struct got_object_idset *set,
185 struct got_object_id *id)
187 struct got_object_idset_element *entry;
188 uint8_t i = id->sha1[0];
190 TAILQ_FOREACH(entry, &set->entries[i], entry) {
191 if (got_object_id_cmp(&entry->id, id) == 0)
198 void got_object_idset_for_each(struct got_object_idset *set,
199 void (*cb)(struct got_object_id *, void *, void *), void *arg)
201 struct got_object_idset_element *entry;
204 for (i = 0; i < nitems(set->entries); i++) {
205 TAILQ_FOREACH(entry, &set->entries[i], entry)
206 cb(&entry->id, entry->data, arg);
211 got_object_idset_num_elements(struct got_object_idset *set)