2 * Copyright (c) 2018, 2019 Stefan Sperling <stsp@openbsd.org>
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.
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.
25 #include "got_compat.h"
27 #include "got_object.h"
28 #include "got_error.h"
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"
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 */
41 RB_HEAD(got_object_idset_tree
, got_object_idset_element
);
44 cmp_elements(const struct got_object_idset_element
*e1
,
45 const struct got_object_idset_element
*e2
)
47 return got_object_id_cmp(&e1
->id
, &e2
->id
);
50 RB_PROTOTYPE(got_object_idset_tree
, got_object_idset_element
, entry
,
53 struct got_object_idset
{
54 struct got_object_idset_tree entries
;
56 #define GOT_OBJECT_IDSET_MAX_ELEM INT_MAX
59 struct got_object_idset
*
60 got_object_idset_alloc(void)
62 struct got_object_idset
*set
;
64 set
= malloc(sizeof(*set
));
68 RB_INIT(&set
->entries
);
75 got_object_idset_free(struct got_object_idset
*set
)
77 struct got_object_idset_element
*entry
;
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. */
88 const struct got_error
*
89 got_object_idset_add(struct got_object_idset
*set
, struct got_object_id
*id
,
92 struct got_object_idset_element
*new;
94 if (set
->totelem
>= GOT_OBJECT_IDSET_MAX_ELEM
)
95 return got_error(GOT_ERR_NO_SPACE
);
97 new = malloc(sizeof(*new));
99 return got_error_from_errno("malloc");
101 memcpy(&new->id
, id
, sizeof(new->id
));
104 RB_INSERT(got_object_idset_tree
, &set
->entries
, new);
109 static struct got_object_idset_element
*
110 find_element(struct got_object_idset
*set
, struct got_object_id
*id
)
112 struct got_object_idset_element
*entry
;
114 entry
= RB_ROOT(&set
->entries
);
116 int cmp
= got_object_id_cmp(id
, &entry
->id
);
118 entry
= RB_LEFT(entry
, entry
);
120 entry
= RB_RIGHT(entry
, entry
);
129 got_object_idset_get(struct got_object_idset
*set
, struct got_object_id
*id
)
131 struct got_object_idset_element
*entry
= find_element(set
, id
);
132 return entry
? entry
->data
: NULL
;
135 const struct got_error
*
136 got_object_idset_remove(void **data
, struct got_object_idset
*set
,
137 struct got_object_id
*id
)
139 struct got_object_idset_element
*entry
;
144 if (set
->totelem
== 0)
145 return got_error(GOT_ERR_NO_OBJ
);
148 entry
= RB_ROOT(&set
->entries
);
150 entry
= find_element(set
, id
);
152 return got_error_no_obj(id
);
154 RB_REMOVE(got_object_idset_tree
, &set
->entries
, entry
);
163 got_object_idset_contains(struct got_object_idset
*set
,
164 struct got_object_id
*id
)
166 struct got_object_idset_element
*entry
= find_element(set
, id
);
167 return entry
? 1 : 0;
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 *),
175 const struct got_error
*err
;
176 struct got_object_idset_element
*entry
, *tmp
;
178 RB_FOREACH_SAFE(entry
, got_object_idset_tree
, &set
->entries
, tmp
) {
179 err
= (*cb
)(&entry
->id
, entry
->data
, arg
);
187 got_object_idset_num_elements(struct got_object_idset
*set
)
192 RB_GENERATE(got_object_idset_tree
, got_object_idset_element
, entry
,