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>
25 54be8251 2018-06-04 stsp #include "got_object.h"
26 54be8251 2018-06-04 stsp #include "got_error.h"
28 54be8251 2018-06-04 stsp #include "got_lib_delta.h"
29 54be8251 2018-06-04 stsp #include "got_lib_zbuf.h"
30 54be8251 2018-06-04 stsp #include "got_lib_object.h"
31 54be8251 2018-06-04 stsp #include "got_lib_object_idset.h"
33 54be8251 2018-06-04 stsp #ifndef nitems
34 54be8251 2018-06-04 stsp #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
37 54be8251 2018-06-04 stsp struct got_object_idset_element {
38 54be8251 2018-06-04 stsp TAILQ_ENTRY(got_object_idset_element) entry;
39 54be8251 2018-06-04 stsp struct got_object_id id;
40 54be8251 2018-06-04 stsp void *data; /* API user data */
43 54be8251 2018-06-04 stsp struct got_object_idset {
45 54be8251 2018-06-04 stsp * A set is implemented as a collection of 256 lists.
46 54be8251 2018-06-04 stsp * The value of the first byte of an object ID determines
47 54be8251 2018-06-04 stsp * which of these lists an object ID is stored in.
49 54be8251 2018-06-04 stsp TAILQ_HEAD(, got_object_idset_element) entries[0xff + 1];
52 54be8251 2018-06-04 stsp struct got_object_idset *
53 54be8251 2018-06-04 stsp got_object_idset_alloc(void)
55 54be8251 2018-06-04 stsp struct got_object_idset *set;
58 54be8251 2018-06-04 stsp set = calloc(1, sizeof(*set));
59 54be8251 2018-06-04 stsp if (set == NULL)
60 54be8251 2018-06-04 stsp return NULL;
62 54be8251 2018-06-04 stsp for (i = 0; i < nitems(set->entries); i++)
63 54be8251 2018-06-04 stsp TAILQ_INIT(&set->entries[i]);
69 54be8251 2018-06-04 stsp got_object_idset_free(struct got_object_idset *set)
71 54be8251 2018-06-04 stsp struct got_object_idset_element *entry;
74 54be8251 2018-06-04 stsp for (i = 0; i < nitems(set->entries); i++) {
75 54be8251 2018-06-04 stsp while (!TAILQ_EMPTY(&set->entries[i])) {
76 54be8251 2018-06-04 stsp entry = TAILQ_FIRST(&set->entries[i]);
77 54be8251 2018-06-04 stsp TAILQ_REMOVE(&set->entries[i], entry, entry);
78 54be8251 2018-06-04 stsp /* User data should be freed by caller. */
79 54be8251 2018-06-04 stsp free(entry);
85 54be8251 2018-06-04 stsp const struct got_error *
86 54be8251 2018-06-04 stsp got_object_idset_add(struct got_object_idset *set, struct got_object_id *id,
89 54be8251 2018-06-04 stsp struct got_object_idset_element *new, *entry;
90 54be8251 2018-06-04 stsp uint8_t i = id->sha1[0];
92 54be8251 2018-06-04 stsp new = calloc(1, sizeof(*new));
93 54be8251 2018-06-04 stsp if (new == NULL)
94 54be8251 2018-06-04 stsp return got_error_from_errno();
96 54be8251 2018-06-04 stsp memcpy(&new->id, id, sizeof(new->id));
97 54be8251 2018-06-04 stsp new->data = data;
99 54be8251 2018-06-04 stsp if (TAILQ_EMPTY(&set->entries[i])) {
100 54be8251 2018-06-04 stsp TAILQ_INSERT_HEAD(&set->entries[i], new, entry);
101 54be8251 2018-06-04 stsp return NULL;
105 54be8251 2018-06-04 stsp * Keep the list sorted by ID so that iterations of
106 54be8251 2018-06-04 stsp * the set occur in a predictable order.
108 54be8251 2018-06-04 stsp TAILQ_FOREACH(entry, &set->entries[i], entry) {
109 54be8251 2018-06-04 stsp int cmp = got_object_id_cmp(&new->id, &entry->id);
110 54be8251 2018-06-04 stsp struct got_object_idset_element *next;
112 54be8251 2018-06-04 stsp if (cmp == 0) {
114 54be8251 2018-06-04 stsp return got_error(GOT_ERR_OBJ_EXISTS);
115 54be8251 2018-06-04 stsp } else if (cmp < 0) {
116 54be8251 2018-06-04 stsp TAILQ_INSERT_BEFORE(entry, new, entry);
117 54be8251 2018-06-04 stsp return NULL;
120 54be8251 2018-06-04 stsp next = TAILQ_NEXT(entry, entry);
121 54be8251 2018-06-04 stsp if (next == NULL) {
122 54be8251 2018-06-04 stsp TAILQ_INSERT_AFTER(&set->entries[i], entry, new, entry);
123 54be8251 2018-06-04 stsp return NULL;
124 54be8251 2018-06-04 stsp } else if (got_object_id_cmp(&new->id, &next->id) > 0) {
125 54be8251 2018-06-04 stsp TAILQ_INSERT_BEFORE(next, new, entry);
126 54be8251 2018-06-04 stsp return NULL;
130 54be8251 2018-06-04 stsp return got_error(GOT_ERR_BAD_OBJ_ID); /* should not get here */
134 54be8251 2018-06-04 stsp got_object_idset_get_data(struct got_object_idset *set,
135 54be8251 2018-06-04 stsp struct got_object_id *id)
137 54be8251 2018-06-04 stsp struct got_object_idset_element *entry;
138 54be8251 2018-06-04 stsp uint8_t i = id->sha1[0];
140 54be8251 2018-06-04 stsp TAILQ_FOREACH(entry, &set->entries[i], entry) {
141 54be8251 2018-06-04 stsp if (got_object_id_cmp(&entry->id, id) == 0)
142 54be8251 2018-06-04 stsp return entry->data;
145 54be8251 2018-06-04 stsp return NULL;
148 54be8251 2018-06-04 stsp const struct got_error *
149 54be8251 2018-06-04 stsp got_object_idset_remove(struct got_object_idset *set,
150 54be8251 2018-06-04 stsp struct got_object_id *id)
152 54be8251 2018-06-04 stsp struct got_object_idset_element *entry, *tmp;
153 54be8251 2018-06-04 stsp uint8_t i = id->sha1[0];
155 54be8251 2018-06-04 stsp TAILQ_FOREACH_SAFE(entry, &set->entries[i], entry, tmp) {
156 54be8251 2018-06-04 stsp if (got_object_id_cmp(&entry->id, id) == 0) {
157 54be8251 2018-06-04 stsp TAILQ_REMOVE(&set->entries[i], entry, entry);
158 54be8251 2018-06-04 stsp return NULL;
162 54be8251 2018-06-04 stsp return got_error(GOT_ERR_NO_OBJ);
166 54be8251 2018-06-04 stsp got_object_idset_contains(struct got_object_idset *set,
167 54be8251 2018-06-04 stsp struct got_object_id *id)
169 54be8251 2018-06-04 stsp struct got_object_idset_element *entry;
170 54be8251 2018-06-04 stsp uint8_t i = id->sha1[0];
172 54be8251 2018-06-04 stsp TAILQ_FOREACH(entry, &set->entries[i], entry) {
173 54be8251 2018-06-04 stsp if (got_object_id_cmp(&entry->id, id) == 0)
180 54be8251 2018-06-04 stsp void got_object_idset_for_each(struct got_object_idset *set,
181 54be8251 2018-06-04 stsp void (*cb)(struct got_object_id *, void *))
183 54be8251 2018-06-04 stsp struct got_object_idset_element *entry, *tmp;
186 54be8251 2018-06-04 stsp for (i = 0; i < nitems(set->entries); i++) {
187 54be8251 2018-06-04 stsp TAILQ_FOREACH_SAFE(entry, &set->entries[i], entry, tmp) {
188 54be8251 2018-06-04 stsp cb(&entry->id, entry->data);