2 5d56da81 2019-01-13 stsp * Copyright (c) 2018, 2019 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>
18 984e8a45 2018-11-05 stsp #include <sys/tree.h>
20 54be8251 2018-06-04 stsp #include <stdlib.h>
21 54be8251 2018-06-04 stsp #include <string.h>
22 54be8251 2018-06-04 stsp #include <sha1.h>
23 54be8251 2018-06-04 stsp #include <stdio.h>
24 54be8251 2018-06-04 stsp #include <zlib.h>
25 c6f420bf 2018-06-04 stsp #include <limits.h>
26 788c352e 2018-06-16 stsp #include <time.h>
28 54be8251 2018-06-04 stsp #include "got_object.h"
29 54be8251 2018-06-04 stsp #include "got_error.h"
31 54be8251 2018-06-04 stsp #include "got_lib_delta.h"
32 63581804 2018-07-09 stsp #include "got_lib_inflate.h"
33 54be8251 2018-06-04 stsp #include "got_lib_object.h"
34 54be8251 2018-06-04 stsp #include "got_lib_object_idset.h"
36 54be8251 2018-06-04 stsp struct got_object_idset_element {
37 e336e3d6 2018-11-05 stsp RB_ENTRY(got_object_idset_element) entry;
38 54be8251 2018-06-04 stsp struct got_object_id id;
39 54be8251 2018-06-04 stsp void *data; /* API user data */
42 e336e3d6 2018-11-05 stsp RB_HEAD(got_object_idset_tree, got_object_idset_element);
45 984e8a45 2018-11-05 stsp cmp_elements(const struct got_object_idset_element *e1,
46 984e8a45 2018-11-05 stsp const struct got_object_idset_element *e2)
48 984e8a45 2018-11-05 stsp return got_object_id_cmp(&e1->id, &e2->id);
51 e336e3d6 2018-11-05 stsp RB_PROTOTYPE(got_object_idset_tree, got_object_idset_element, entry,
52 984e8a45 2018-11-05 stsp cmp_elements);
54 54be8251 2018-06-04 stsp struct got_object_idset {
55 984e8a45 2018-11-05 stsp struct got_object_idset_tree entries;
56 2bd394ff 2018-06-22 stsp int totelem;
57 069f84d5 2018-06-11 stsp #define GOT_OBJECT_IDSET_MAX_ELEM INT_MAX
60 54be8251 2018-06-04 stsp struct got_object_idset *
61 60f2eee1 2018-07-08 stsp got_object_idset_alloc(void)
63 54be8251 2018-06-04 stsp struct got_object_idset *set;
65 984e8a45 2018-11-05 stsp set = malloc(sizeof(*set));
66 54be8251 2018-06-04 stsp if (set == NULL)
67 54be8251 2018-06-04 stsp return NULL;
69 e336e3d6 2018-11-05 stsp RB_INIT(&set->entries);
70 984e8a45 2018-11-05 stsp set->totelem = 0;
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;
80 e336e3d6 2018-11-05 stsp while ((entry = RB_MIN(got_object_idset_tree, &set->entries))) {
81 e336e3d6 2018-11-05 stsp RB_REMOVE(got_object_idset_tree, &set->entries, entry);
82 984e8a45 2018-11-05 stsp /* User data should be freed by caller. */
83 984e8a45 2018-11-05 stsp free(entry);
89 54be8251 2018-06-04 stsp const struct got_error *
90 b36429ab 2018-11-05 stsp got_object_idset_add(struct got_object_idset *set, struct got_object_id *id,
93 b36429ab 2018-11-05 stsp struct got_object_idset_element *new;
95 2bd394ff 2018-06-22 stsp if (set->totelem >= GOT_OBJECT_IDSET_MAX_ELEM)
96 c6f420bf 2018-06-04 stsp return got_error(GOT_ERR_NO_SPACE);
98 294f39b0 2018-11-05 stsp new = malloc(sizeof(*new));
99 54be8251 2018-06-04 stsp if (new == NULL)
100 638f9024 2019-05-13 stsp return got_error_from_errno("malloc");
102 54be8251 2018-06-04 stsp memcpy(&new->id, id, sizeof(new->id));
103 54be8251 2018-06-04 stsp new->data = data;
105 a7472cb3 2022-04-14 stsp if (RB_INSERT(got_object_idset_tree, &set->entries, new) != NULL) {
107 a7472cb3 2022-04-14 stsp return got_error(GOT_ERR_OBJ_EXISTS);
110 b36429ab 2018-11-05 stsp set->totelem++;
111 b36429ab 2018-11-05 stsp return NULL;
114 984e8a45 2018-11-05 stsp static struct got_object_idset_element *
115 984e8a45 2018-11-05 stsp find_element(struct got_object_idset *set, struct got_object_id *id)
117 60f2eee1 2018-07-08 stsp struct got_object_idset_element *entry;
119 e336e3d6 2018-11-05 stsp entry = RB_ROOT(&set->entries);
120 984e8a45 2018-11-05 stsp while (entry) {
121 984e8a45 2018-11-05 stsp int cmp = got_object_id_cmp(id, &entry->id);
122 984e8a45 2018-11-05 stsp if (cmp < 0)
123 e336e3d6 2018-11-05 stsp entry = RB_LEFT(entry, entry);
124 984e8a45 2018-11-05 stsp else if (cmp > 0)
125 e336e3d6 2018-11-05 stsp entry = RB_RIGHT(entry, entry);
130 984e8a45 2018-11-05 stsp return entry;
134 984e8a45 2018-11-05 stsp got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
136 984e8a45 2018-11-05 stsp struct got_object_idset_element *entry = find_element(set, id);
137 984e8a45 2018-11-05 stsp return entry ? entry->data : NULL;
140 54be8251 2018-06-04 stsp const struct got_error *
141 e7c810ea 2018-06-22 stsp got_object_idset_remove(void **data, struct got_object_idset *set,
142 54be8251 2018-06-04 stsp struct got_object_id *id)
144 984e8a45 2018-11-05 stsp struct got_object_idset_element *entry;
147 441e144c 2018-06-22 stsp *data = NULL;
149 984e8a45 2018-11-05 stsp if (set->totelem == 0)
150 c6f420bf 2018-06-04 stsp return got_error(GOT_ERR_NO_OBJ);
152 0ae61b79 2022-03-21 stsp if (id == NULL) {
153 e336e3d6 2018-11-05 stsp entry = RB_ROOT(&set->entries);
154 0ae61b79 2022-03-21 stsp if (entry == NULL)
155 0ae61b79 2022-03-21 stsp return got_error(GOT_ERR_NO_OBJ);
157 f054b67a 2018-11-05 stsp entry = find_element(set, id);
158 0ae61b79 2022-03-21 stsp if (entry == NULL)
159 0ae61b79 2022-03-21 stsp return got_error_no_obj(id);
162 e336e3d6 2018-11-05 stsp RB_REMOVE(got_object_idset_tree, &set->entries, entry);
164 984e8a45 2018-11-05 stsp *data = entry->data;
165 984e8a45 2018-11-05 stsp free(entry);
166 984e8a45 2018-11-05 stsp set->totelem--;
167 984e8a45 2018-11-05 stsp return NULL;
171 54be8251 2018-06-04 stsp got_object_idset_contains(struct got_object_idset *set,
172 54be8251 2018-06-04 stsp struct got_object_id *id)
174 984e8a45 2018-11-05 stsp struct got_object_idset_element *entry = find_element(set, id);
175 984e8a45 2018-11-05 stsp return entry ? 1 : 0;
178 cb103d04 2018-11-07 stsp const struct got_error *
179 cb103d04 2018-11-07 stsp got_object_idset_for_each(struct got_object_idset *set,
180 cb103d04 2018-11-07 stsp const struct got_error *(*cb)(struct got_object_id *, void *, void *),
183 cb103d04 2018-11-07 stsp const struct got_error *err;
184 9489f1f7 2018-11-11 stsp struct got_object_idset_element *entry, *tmp;
186 9489f1f7 2018-11-11 stsp RB_FOREACH_SAFE(entry, got_object_idset_tree, &set->entries, tmp) {
187 cb103d04 2018-11-07 stsp err = (*cb)(&entry->id, entry->data, arg);
189 cb103d04 2018-11-07 stsp return err;
191 cb103d04 2018-11-07 stsp return NULL;
195 c6f420bf 2018-06-04 stsp got_object_idset_num_elements(struct got_object_idset *set)
197 2bd394ff 2018-06-22 stsp return set->totelem;
200 67fd6849 2022-02-13 stsp struct got_object_idset_element *
201 67fd6849 2022-02-13 stsp got_object_idset_get_element(struct got_object_idset *set, struct got_object_id *id)
203 67fd6849 2022-02-13 stsp return find_element(set, id);
207 67fd6849 2022-02-13 stsp got_object_idset_get_element_data(struct got_object_idset_element *entry)
209 67fd6849 2022-02-13 stsp return entry->data;
212 67fd6849 2022-02-13 stsp const struct got_error *
213 67fd6849 2022-02-13 stsp got_object_idset_for_each_element(struct got_object_idset *set,
214 67fd6849 2022-02-13 stsp const struct got_error *(*cb)(struct got_object_idset_element *, void *),
217 67fd6849 2022-02-13 stsp const struct got_error *err;
218 67fd6849 2022-02-13 stsp struct got_object_idset_element *entry, *tmp;
220 67fd6849 2022-02-13 stsp RB_FOREACH_SAFE(entry, got_object_idset_tree, &set->entries, tmp) {
221 67fd6849 2022-02-13 stsp err = (*cb)(entry, arg);
223 67fd6849 2022-02-13 stsp return err;
225 67fd6849 2022-02-13 stsp return NULL;
229 67fd6849 2022-02-13 stsp got_object_idset_remove_element(struct got_object_idset *set,
230 67fd6849 2022-02-13 stsp struct got_object_idset_element *entry)
232 67fd6849 2022-02-13 stsp RB_REMOVE(got_object_idset_tree, &set->entries, entry);
233 67fd6849 2022-02-13 stsp free(entry);
234 67fd6849 2022-02-13 stsp set->totelem--;
237 e336e3d6 2018-11-05 stsp RB_GENERATE(got_object_idset_tree, got_object_idset_element, entry,
238 984e8a45 2018-11-05 stsp cmp_elements);