1 /*
2  * Copyright (c) 2018 Stefan Sperling <stsp@openbsd.org>
3  *
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.
7  *
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.
15  */
16 
17 #include <sys/queue.h>
18 #include <sys/tree.h>
19 
20 #include <stdlib.h>
21 #include <string.h>
22 #include <sha1.h>
23 #include <stdio.h>
24 #include <zlib.h>
25 #include <limits.h>
26 #include <time.h>
27 
28 #include "got_object.h"
29 #include "got_error.h"
30 
31 #include "got_lib_delta.h"
32 #include "got_lib_inflate.h"
33 #include "got_lib_object.h"
34 #include "got_lib_object_idset.h"
35 
36 #ifndef nitems
37 #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
38 #endif
39 
40 struct got_object_idset_element {
41 	RB_ENTRY(got_object_idset_element)	entry;
42 	struct got_object_id id;
43 	void *data;	/* API user data */
44 };
45 
46 RB_HEAD(got_object_idset_tree, got_object_idset_element);
47 
48 static int
49 cmp_elements(const struct got_object_idset_element *e1,
50     const struct got_object_idset_element *e2)
51 {
52 	return got_object_id_cmp(&e1->id, &e2->id);
53 }
54 
55 RB_PROTOTYPE(got_object_idset_tree, got_object_idset_element, entry,
56     cmp_elements);
57 
58 struct got_object_idset {
59 	struct got_object_idset_tree entries;
60 	int totelem;
61 #define GOT_OBJECT_IDSET_MAX_ELEM INT_MAX
62 };
63 
64 struct got_object_idset *
65 got_object_idset_alloc(void)
66 {
67 	struct got_object_idset *set;
68 
69 	set = malloc(sizeof(*set));
70 	if (set == NULL)
71 		return NULL;
72 
73 	RB_INIT(&set->entries);
74 	set->totelem = 0;
75 
76 	return set;
77 }
78 
79 void
80 got_object_idset_free(struct got_object_idset *set)
81 {
82 	struct got_object_idset_element *entry;
83 
84 	while ((entry = RB_MIN(got_object_idset_tree, &set->entries))) {
85 		RB_REMOVE(got_object_idset_tree, &set->entries, entry);
86 		/* User data should be freed by caller. */
87 		free(entry);
88 	}
89 
90 	free(set);
91 }
92 
93 const struct got_error *
94 got_object_idset_add(struct got_object_idset *set, struct got_object_id *id,
95     void *data)
96 {
97 	struct got_object_idset_element *new;
98 
99 	if (set->totelem >= GOT_OBJECT_IDSET_MAX_ELEM)
100 		return got_error(GOT_ERR_NO_SPACE);
101 
102 	new = malloc(sizeof(*new));
103 	if (new == NULL)
104 		return got_error_from_errno();
105 
106 	memcpy(&new->id, id, sizeof(new->id));
107 	new->data = data;
108 
109 	RB_INSERT(got_object_idset_tree, &set->entries, new);
110 	set->totelem++;
111 	return NULL;
112 }
113 
114 static struct got_object_idset_element *
115 find_element(struct got_object_idset *set, struct got_object_id *id)
116 {
117 	struct got_object_idset_element *entry;
118 
119 	entry = RB_ROOT(&set->entries);
120 	while (entry) {
121 		int cmp = got_object_id_cmp(id, &entry->id);
122 		if (cmp < 0)
123 			entry = RB_LEFT(entry, entry);
124 		else if (cmp > 0)
125 			entry = RB_RIGHT(entry, entry);
126 		else
127 			break;
128 	}
129 
130 	return entry;
131 }
132 
133 void *
134 got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
135 {
136 	struct got_object_idset_element *entry = find_element(set, id);
137 	return entry ? entry->data : NULL;
138 }
139 
140 const struct got_error *
141 got_object_idset_remove(void **data, struct got_object_idset *set,
142     struct got_object_id *id)
143 {
144 	struct got_object_idset_element *entry;
145 
146 	if (data)
147 		*data = NULL;
148 
149 	if (set->totelem == 0)
150 		return got_error(GOT_ERR_NO_OBJ);
151 
152 	if (id == NULL)
153 		entry = RB_ROOT(&set->entries);
154 	else
155 		entry = find_element(set, id);
156 	if (entry == NULL)
157 		return got_error(GOT_ERR_NO_OBJ);
158 
159 	RB_REMOVE(got_object_idset_tree, &set->entries, entry);
160 	if (data)
161 		*data = entry->data;
162 	free(entry);
163 	set->totelem--;
164 	return NULL;
165 }
166 
167 int
168 got_object_idset_contains(struct got_object_idset *set,
169     struct got_object_id *id)
170 {
171 	struct got_object_idset_element *entry = find_element(set, id);
172 	return entry ? 1 : 0;
173 }
174 
175 const struct got_error *
176 got_object_idset_for_each(struct got_object_idset *set,
177     const struct got_error *(*cb)(struct got_object_id *, void *, void *),
178     void *arg)
179 {
180 	const struct got_error *err;
181 	struct got_object_idset_element *entry, *tmp;
182 
183 	RB_FOREACH_SAFE(entry, got_object_idset_tree, &set->entries, tmp) {
184 		err = (*cb)(&entry->id, entry->data, arg);
185 		if (err)
186 			return err;
187 	}
188 	return NULL;
189 }
190 
191 int
192 got_object_idset_num_elements(struct got_object_idset *set)
193 {
194 	return set->totelem;
195 }
196 
197 RB_GENERATE(got_object_idset_tree, got_object_idset_element, entry,
198     cmp_elements);