commit 54be8251170ea16b244d270abfc498e266117d84 from: Stefan Sperling date: Mon Jun 04 18:23:59 2018 UTC add an object id set data structure commit - c82623105fb79ac87c0fdc09d0d3820452201a7c commit + 54be8251170ea16b244d270abfc498e266117d84 blob - 2ee49f4dea4dc0411630a0f1a58de71caf718ba2 blob + ccb4b12a334d7abc51fe78fad336beb6ce83f395 --- include/got_error.h +++ include/got_error.h @@ -56,6 +56,8 @@ #define GOT_ERR_PRIVSEP_DIED 40 #define GOT_ERR_PRIVSEP_EXIT 41 #define GOT_ERR_PACK_OFFSET 42 +#define GOT_ERR_OBJ_EXISTS 43 +#define GOT_ERR_BAD_OBJ_ID 44 static const struct got_error { int code; @@ -97,10 +99,12 @@ static const struct got_error { "from unprivileged process" }, { GOT_ERR_PRIVSEP_PIPE, "unprivileged process closed pipe" }, { GOT_ERR_PRIVSEP_NO_FD,"out of file descriptors for privsep" }, - { GOT_ERR_PRIVSEP_MSG,"unexpected message from unprivileged process" }, - { GOT_ERR_PRIVSEP_DIED,"unprivileged process died unexpectedly" }, - { GOT_ERR_PRIVSEP_EXIT,"bad exit code from unprivileged process" }, - { GOT_ERR_PACK_OFFSET,"bad offset in pack file" }, + { GOT_ERR_PRIVSEP_MSG, "unexpected message from unprivileged process" }, + { GOT_ERR_PRIVSEP_DIED, "unprivileged process died unexpectedly" }, + { GOT_ERR_PRIVSEP_EXIT, "bad exit code from unprivileged process" }, + { GOT_ERR_PACK_OFFSET, "bad offset in pack file" }, + { GOT_ERR_OBJ_EXISTS, "object already exists" }, + { GOT_ERR_BAD_OBJ_ID, "bad object id" }, }; /* blob - /dev/null blob + a20b75466181dee94c186da82535ac7e202885d8 (mode 644) --- /dev/null +++ lib/got_lib_object_idset.h @@ -0,0 +1,31 @@ +/* + * Copyright (c) 2018 Stefan Sperling + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +struct got_object_idset; + +struct got_object_idset *got_object_idset_alloc(void); +void got_object_idset_free(struct got_object_idset *); + +const struct got_error *got_object_idset_add(struct got_object_idset *, + struct got_object_id *, void *); +void *got_object_idset_get_data(struct got_object_idset *, + struct got_object_id *); +const struct got_error *got_object_idset_remove(struct got_object_idset *, + struct got_object_id *); +int got_object_idset_contains(struct got_object_idset *, + struct got_object_id *); +void got_object_idset_for_each(struct got_object_idset *, + void (*cb)(struct got_object_id *, void *)); blob - /dev/null blob + 58f89bfb1e95a823d47d2738635c5c20d1584f37 (mode 644) --- /dev/null +++ lib/object_idset.c @@ -0,0 +1,191 @@ +/* + * Copyright (c) 2018 Stefan Sperling + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include + +#include +#include +#include +#include +#include + +#include "got_object.h" +#include "got_error.h" + +#include "got_lib_delta.h" +#include "got_lib_zbuf.h" +#include "got_lib_object.h" +#include "got_lib_object_idset.h" + +#ifndef nitems +#define nitems(_a) (sizeof(_a) / sizeof((_a)[0])) +#endif + +struct got_object_idset_element { + TAILQ_ENTRY(got_object_idset_element) entry; + struct got_object_id id; + void *data; /* API user data */ +}; + +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]; +}; + +struct got_object_idset * +got_object_idset_alloc(void) +{ + struct got_object_idset *set; + int i; + + set = calloc(1, sizeof(*set)); + if (set == NULL) + return NULL; + + for (i = 0; i < nitems(set->entries); i++) + TAILQ_INIT(&set->entries[i]); + + return set; +} + +void +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); + } + } + free(set); +} + +const struct got_error * +got_object_idset_add(struct got_object_idset *set, struct got_object_id *id, + void *data) +{ + struct got_object_idset_element *new, *entry; + uint8_t i = id->sha1[0]; + + new = calloc(1, sizeof(*new)); + if (new == NULL) + return got_error_from_errno(); + + memcpy(&new->id, id, sizeof(new->id)); + new->data = data; + + if (TAILQ_EMPTY(&set->entries[i])) { + TAILQ_INSERT_HEAD(&set->entries[i], new, entry); + return NULL; + } + + /* + * Keep the list sorted by ID so that iterations of + * the set occur in a predictable order. + */ + TAILQ_FOREACH(entry, &set->entries[i], entry) { + int cmp = got_object_id_cmp(&new->id, &entry->id); + struct got_object_idset_element *next; + + if (cmp == 0) { + free(new); + return got_error(GOT_ERR_OBJ_EXISTS); + } else if (cmp < 0) { + TAILQ_INSERT_BEFORE(entry, new, entry); + return NULL; + } + + next = TAILQ_NEXT(entry, entry); + if (next == NULL) { + TAILQ_INSERT_AFTER(&set->entries[i], entry, new, entry); + return NULL; + } else if (got_object_id_cmp(&new->id, &next->id) > 0) { + TAILQ_INSERT_BEFORE(next, new, entry); + return NULL; + } + } + + return got_error(GOT_ERR_BAD_OBJ_ID); /* should not get here */ +} + +void * +got_object_idset_get_data(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; + } + + return NULL; +} + +const struct got_error * +got_object_idset_remove(struct got_object_idset *set, + struct got_object_id *id) +{ + struct got_object_idset_element *entry, *tmp; + uint8_t i = id->sha1[0]; + + 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); + return NULL; + } + } + + return got_error(GOT_ERR_NO_OBJ); +} + +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; +} + +void got_object_idset_for_each(struct got_object_idset *set, + void (*cb)(struct got_object_id *, void *)) +{ + struct got_object_idset_element *entry, *tmp; + int i; + + for (i = 0; i < nitems(set->entries); i++) { + TAILQ_FOREACH_SAFE(entry, &set->entries[i], entry, tmp) { + cb(&entry->id, entry->data); + } + } +}