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