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