commit - 6dfaee0232282bb36fe0cd07674d8e6c1faa1ac9
commit + 984e8a45c4baf9764b411c634efe60ccb173097c
blob - 6a7f144c900f41a779d1c802f006ba97b8a14160
blob + 6ba2563737d96877e4e57392d5dd8bef4a272705
--- include/got_object.h
+++ include/got_object.h
/*
* Compare two object IDs. Return value behaves like memcmp(3).
*/
-int got_object_id_cmp(struct got_object_id *, struct got_object_id *);
+int got_object_id_cmp(const struct got_object_id *,
+ const struct got_object_id *);
/*
* Created a newly allocated copy of an object ID.
blob - 6c29e98e5a2c06798017cda85f03e0a402aa92d6
blob + fef5ccdb782e53e96ac507c88172e730cf6a7758
--- lib/object.c
+++ lib/object.c
#endif
int
-got_object_id_cmp(struct got_object_id *id1, struct got_object_id *id2)
+got_object_id_cmp(const struct got_object_id *id1,
+ const struct got_object_id *id2)
{
return memcmp(id1->sha1, id2->sha1, SHA1_DIGEST_LENGTH);
}
blob - bcfd309010b2fd55b09fb67b885691ae089e46a8
blob + 09fe0cf7c70523dc6ccd87e9f4beaa33af626a6d
--- lib/object_idset.c
+++ lib/object_idset.c
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
+#include <stddef.h>
#include <sys/queue.h>
+#include <sys/tree.h>
#include <stdlib.h>
#include <string.h>
#endif
struct got_object_idset_element {
- TAILQ_ENTRY(got_object_idset_element) entry;
+ RBT_ENTRY(got_object_idset_element) entry;
struct got_object_id id;
void *data; /* API user data */
};
+RBT_HEAD(got_object_idset_tree, got_object_idset_element);
+
+static int
+cmp_elements(const struct got_object_idset_element *e1,
+ const struct got_object_idset_element *e2)
+{
+ return got_object_id_cmp(&e1->id, &e2->id);
+}
+
+RBT_PROTOTYPE(got_object_idset_tree, got_object_idset_element, entry,
+ cmp_elements);
+
struct got_object_idset {
- /*
- * A set is implemented as a collection of 256 lists.
- * The value of the first byte of an object ID determines
- * which of these lists an object ID is stored in.
- */
- TAILQ_HEAD(, got_object_idset_element) entries[0xff + 1];
- int nelem[0xff + 1];
+ struct got_object_idset_tree entries;
int totelem;
#define GOT_OBJECT_IDSET_MAX_ELEM INT_MAX
};
got_object_idset_alloc(void)
{
struct got_object_idset *set;
- int i;
- set = calloc(1, sizeof(*set));
+ set = malloc(sizeof(*set));
if (set == NULL)
return NULL;
- for (i = 0; i < nitems(set->entries); i++)
- TAILQ_INIT(&set->entries[i]);
+ RBT_INIT(got_object_idset_tree, &set->entries);
+ set->totelem = 0;
return set;
}
got_object_idset_free(struct got_object_idset *set)
{
struct got_object_idset_element *entry;
- int i;
- for (i = 0; i < nitems(set->entries); i++) {
- while (!TAILQ_EMPTY(&set->entries[i])) {
- entry = TAILQ_FIRST(&set->entries[i]);
- TAILQ_REMOVE(&set->entries[i], entry, entry);
- /* User data should be freed by caller. */
- free(entry);
- }
+ while ((entry = RBT_MIN(got_object_idset_tree, &set->entries))) {
+ RBT_REMOVE(got_object_idset_tree, &set->entries, entry);
+ /* User data should be freed by caller. */
+ free(entry);
}
+
free(set);
}
void *data)
{
struct got_object_idset_element *new;
- uint8_t i = id->sha1[0];
if (set->totelem >= GOT_OBJECT_IDSET_MAX_ELEM)
return got_error(GOT_ERR_NO_SPACE);
memcpy(&new->id, id, sizeof(new->id));
new->data = data;
- TAILQ_INSERT_HEAD(&set->entries[i], new, entry);
- set->nelem[i]++;
+ RBT_INSERT(got_object_idset_tree, &set->entries, new);
set->totelem++;
return NULL;
}
-void *
-got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
+static struct got_object_idset_element *
+find_element(struct got_object_idset *set, struct got_object_id *id)
{
struct got_object_idset_element *entry;
- uint8_t i = id->sha1[0];
- TAILQ_FOREACH(entry, &set->entries[i], entry) {
- if (got_object_id_cmp(&entry->id, id) == 0)
- return entry->data;
+ entry = RBT_ROOT(got_object_idset_tree, &set->entries);
+ while (entry) {
+ int cmp = got_object_id_cmp(id, &entry->id);
+ if (cmp < 0)
+ entry = RBT_LEFT(got_object_idset_tree, entry);
+ else if (cmp > 0)
+ entry = RBT_RIGHT(got_object_idset_tree, entry);
+ else
+ break;
}
- return NULL;
+ return entry;
}
+void *
+got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
+{
+ struct got_object_idset_element *entry = find_element(set, id);
+ return entry ? entry->data : NULL;
+}
+
const struct got_error *
got_object_idset_remove(void **data, struct got_object_idset *set,
struct got_object_id *id)
{
- struct got_object_idset_element *entry, *tmp;
- uint8_t i = id->sha1[0];
+ struct got_object_idset_element *entry;
if (data)
*data = NULL;
- if (set->nelem[i] == 0)
+ if (set->totelem == 0)
return got_error(GOT_ERR_NO_OBJ);
- TAILQ_FOREACH_SAFE(entry, &set->entries[i], entry, tmp) {
- if (got_object_id_cmp(&entry->id, id) == 0) {
- TAILQ_REMOVE(&set->entries[i], entry, entry);
- if (data)
- *data = entry->data;
- free(entry);
- set->nelem[i]--;
- set->totelem--;
- return NULL;
- }
- }
+ entry = find_element(set, id);
+ if (entry == NULL)
+ return got_error(GOT_ERR_NO_OBJ);
- return got_error(GOT_ERR_NO_OBJ);
+ RBT_REMOVE(got_object_idset_tree, &set->entries, entry);
+ if (data)
+ *data = entry->data;
+ free(entry);
+ set->totelem--;
+ return NULL;
}
int
got_object_idset_contains(struct got_object_idset *set,
struct got_object_id *id)
{
- struct got_object_idset_element *entry;
- uint8_t i = id->sha1[0];
-
- TAILQ_FOREACH(entry, &set->entries[i], entry) {
- if (got_object_id_cmp(&entry->id, id) == 0)
- return 1;
- }
-
- return 0;
+ struct got_object_idset_element *entry = find_element(set, id);
+ return entry ? 1 : 0;
}
void got_object_idset_for_each(struct got_object_idset *set,
void (*cb)(struct got_object_id *, void *, void *), void *arg)
{
struct got_object_idset_element *entry;
- int i;
- for (i = 0; i < nitems(set->entries); i++) {
- TAILQ_FOREACH(entry, &set->entries[i], entry)
- cb(&entry->id, entry->data, arg);
- }
+ RBT_FOREACH(entry, got_object_idset_tree, &set->entries)
+ (*cb)(&entry->id, entry->data, arg);
}
int
{
return set->totelem;
}
+
+RBT_GENERATE(got_object_idset_tree, got_object_idset_element, entry,
+ cmp_elements);
