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 984e8a45 2018-11-05 stsp #include <stddef.h>
18 54be8251 2018-06-04 stsp #include <sys/queue.h>
19 984e8a45 2018-11-05 stsp #include <sys/tree.h>
21 54be8251 2018-06-04 stsp #include <stdlib.h>
22 54be8251 2018-06-04 stsp #include <string.h>
23 54be8251 2018-06-04 stsp #include <sha1.h>
24 54be8251 2018-06-04 stsp #include <stdio.h>
25 54be8251 2018-06-04 stsp #include <zlib.h>
26 c6f420bf 2018-06-04 stsp #include <limits.h>
27 788c352e 2018-06-16 stsp #include <time.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"
37 54be8251 2018-06-04 stsp #ifndef nitems
38 54be8251 2018-06-04 stsp #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
41 54be8251 2018-06-04 stsp struct got_object_idset_element {
42 984e8a45 2018-11-05 stsp RBT_ENTRY(got_object_idset_element) entry;
43 54be8251 2018-06-04 stsp struct got_object_id id;
44 54be8251 2018-06-04 stsp void *data; /* API user data */
47 984e8a45 2018-11-05 stsp RBT_HEAD(got_object_idset_tree, got_object_idset_element);
50 984e8a45 2018-11-05 stsp cmp_elements(const struct got_object_idset_element *e1,
51 984e8a45 2018-11-05 stsp const struct got_object_idset_element *e2)
53 984e8a45 2018-11-05 stsp return got_object_id_cmp(&e1->id, &e2->id);
56 984e8a45 2018-11-05 stsp RBT_PROTOTYPE(got_object_idset_tree, got_object_idset_element, entry,
57 984e8a45 2018-11-05 stsp cmp_elements);
59 54be8251 2018-06-04 stsp struct got_object_idset {
60 984e8a45 2018-11-05 stsp struct got_object_idset_tree entries;
61 2bd394ff 2018-06-22 stsp int totelem;
62 069f84d5 2018-06-11 stsp #define GOT_OBJECT_IDSET_MAX_ELEM INT_MAX
65 54be8251 2018-06-04 stsp struct got_object_idset *
66 60f2eee1 2018-07-08 stsp got_object_idset_alloc(void)
68 54be8251 2018-06-04 stsp struct got_object_idset *set;
70 984e8a45 2018-11-05 stsp set = malloc(sizeof(*set));
71 54be8251 2018-06-04 stsp if (set == NULL)
72 54be8251 2018-06-04 stsp return NULL;
74 984e8a45 2018-11-05 stsp RBT_INIT(got_object_idset_tree, &set->entries);
75 984e8a45 2018-11-05 stsp set->totelem = 0;
81 54be8251 2018-06-04 stsp got_object_idset_free(struct got_object_idset *set)
83 54be8251 2018-06-04 stsp struct got_object_idset_element *entry;
85 984e8a45 2018-11-05 stsp while ((entry = RBT_MIN(got_object_idset_tree, &set->entries))) {
86 984e8a45 2018-11-05 stsp RBT_REMOVE(got_object_idset_tree, &set->entries, entry);
87 984e8a45 2018-11-05 stsp /* User data should be freed by caller. */
88 984e8a45 2018-11-05 stsp free(entry);
94 54be8251 2018-06-04 stsp const struct got_error *
95 b36429ab 2018-11-05 stsp got_object_idset_add(struct got_object_idset *set, struct got_object_id *id,
98 b36429ab 2018-11-05 stsp struct got_object_idset_element *new;
100 2bd394ff 2018-06-22 stsp if (set->totelem >= GOT_OBJECT_IDSET_MAX_ELEM)
101 c6f420bf 2018-06-04 stsp return got_error(GOT_ERR_NO_SPACE);
103 294f39b0 2018-11-05 stsp new = malloc(sizeof(*new));
104 54be8251 2018-06-04 stsp if (new == NULL)
105 54be8251 2018-06-04 stsp return got_error_from_errno();
107 54be8251 2018-06-04 stsp memcpy(&new->id, id, sizeof(new->id));
108 54be8251 2018-06-04 stsp new->data = data;
110 984e8a45 2018-11-05 stsp RBT_INSERT(got_object_idset_tree, &set->entries, new);
111 b36429ab 2018-11-05 stsp set->totelem++;
112 b36429ab 2018-11-05 stsp return NULL;
115 984e8a45 2018-11-05 stsp static struct got_object_idset_element *
116 984e8a45 2018-11-05 stsp find_element(struct got_object_idset *set, struct got_object_id *id)
118 60f2eee1 2018-07-08 stsp struct got_object_idset_element *entry;
120 984e8a45 2018-11-05 stsp entry = RBT_ROOT(got_object_idset_tree, &set->entries);
121 984e8a45 2018-11-05 stsp while (entry) {
122 984e8a45 2018-11-05 stsp int cmp = got_object_id_cmp(id, &entry->id);
123 984e8a45 2018-11-05 stsp if (cmp < 0)
124 984e8a45 2018-11-05 stsp entry = RBT_LEFT(got_object_idset_tree, entry);
125 984e8a45 2018-11-05 stsp else if (cmp > 0)
126 984e8a45 2018-11-05 stsp entry = RBT_RIGHT(got_object_idset_tree, entry);
131 984e8a45 2018-11-05 stsp return entry;
135 984e8a45 2018-11-05 stsp got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
137 984e8a45 2018-11-05 stsp struct got_object_idset_element *entry = find_element(set, id);
138 984e8a45 2018-11-05 stsp return entry ? entry->data : NULL;
141 54be8251 2018-06-04 stsp const struct got_error *
142 e7c810ea 2018-06-22 stsp got_object_idset_remove(void **data, struct got_object_idset *set,
143 54be8251 2018-06-04 stsp struct got_object_id *id)
145 984e8a45 2018-11-05 stsp struct got_object_idset_element *entry;
148 441e144c 2018-06-22 stsp *data = NULL;
150 984e8a45 2018-11-05 stsp if (set->totelem == 0)
151 c6f420bf 2018-06-04 stsp return got_error(GOT_ERR_NO_OBJ);
153 f054b67a 2018-11-05 stsp if (id == NULL)
154 f054b67a 2018-11-05 stsp entry = RBT_ROOT(got_object_idset_tree, &set->entries);
156 f054b67a 2018-11-05 stsp entry = find_element(set, id);
157 984e8a45 2018-11-05 stsp if (entry == NULL)
158 984e8a45 2018-11-05 stsp return got_error(GOT_ERR_NO_OBJ);
160 984e8a45 2018-11-05 stsp RBT_REMOVE(got_object_idset_tree, &set->entries, entry);
162 984e8a45 2018-11-05 stsp *data = entry->data;
163 984e8a45 2018-11-05 stsp free(entry);
164 984e8a45 2018-11-05 stsp set->totelem--;
165 984e8a45 2018-11-05 stsp return NULL;
169 54be8251 2018-06-04 stsp got_object_idset_contains(struct got_object_idset *set,
170 54be8251 2018-06-04 stsp struct got_object_id *id)
172 984e8a45 2018-11-05 stsp struct got_object_idset_element *entry = find_element(set, id);
173 984e8a45 2018-11-05 stsp return entry ? 1 : 0;
176 54be8251 2018-06-04 stsp void got_object_idset_for_each(struct got_object_idset *set,
177 917bfd05 2018-06-10 stsp void (*cb)(struct got_object_id *, void *, void *), void *arg)
179 956a5d5a 2018-06-04 stsp struct got_object_idset_element *entry;
181 984e8a45 2018-11-05 stsp RBT_FOREACH(entry, got_object_idset_tree, &set->entries)
182 984e8a45 2018-11-05 stsp (*cb)(&entry->id, entry->data, arg);
186 c6f420bf 2018-06-04 stsp got_object_idset_num_elements(struct got_object_idset *set)
188 2bd394ff 2018-06-22 stsp return set->totelem;
191 984e8a45 2018-11-05 stsp RBT_GENERATE(got_object_idset_tree, got_object_idset_element, entry,
192 984e8a45 2018-11-05 stsp cmp_elements);
