diff options
Diffstat (limited to 'notes.c')
| -rw-r--r-- | notes.c | 85 |
1 files changed, 84 insertions, 1 deletions
@@ -44,7 +44,7 @@ struct leaf_node { #define CLR_PTR_TYPE(ptr) ((void *) ((uintptr_t) (ptr) & ~3)) #define SET_PTR_TYPE(ptr, type) ((void *) ((uintptr_t) (ptr) | (type))) -#define GET_NIBBLE(n, sha1) (((sha1[n >> 1]) >> ((~n & 0x01) << 2)) & 0x0f) +#define GET_NIBBLE(n, sha1) (((sha1[(n) >> 1]) >> ((~(n) & 0x01) << 2)) & 0x0f) #define SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \ (memcmp(key_sha1, subtree_sha1, subtree_sha1[19])) @@ -249,6 +249,79 @@ static void note_tree_insert(struct int_node *tree, unsigned char n, note_tree_insert(new_node, n + 1, entry, type); } +/* + * How to consolidate an int_node: + * If there are > 1 non-NULL entries, give up and return non-zero. + * Otherwise replace the int_node at the given index in the given parent node + * with the only entry (or a NULL entry if no entries) from the given tree, + * and return 0. + */ +static int note_tree_consolidate(struct int_node *tree, + struct int_node *parent, unsigned char index) +{ + unsigned int i; + void *p = NULL; + + assert(tree && parent); + assert(CLR_PTR_TYPE(parent->a[index]) == tree); + + for (i = 0; i < 16; i++) { + if (GET_PTR_TYPE(tree->a[i]) != PTR_TYPE_NULL) { + if (p) /* more than one entry */ + return -2; + p = tree->a[i]; + } + } + + /* replace tree with p in parent[index] */ + parent->a[index] = p; + free(tree); + return 0; +} + +/* + * To remove a leaf_node: + * Search to the tree location appropriate for the given leaf_node's key: + * - If location does not hold a matching entry, abort and do nothing. + * - Replace the matching leaf_node with a NULL entry (and free the leaf_node). + * - Consolidate int_nodes repeatedly, while walking up the tree towards root. + */ +static void note_tree_remove(struct int_node *tree, unsigned char n, + struct leaf_node *entry) +{ + struct leaf_node *l; + struct int_node *parent_stack[20]; + unsigned char i, j; + void **p = note_tree_search(&tree, &n, entry->key_sha1); + + assert(GET_PTR_TYPE(entry) == 0); /* no type bits set */ + if (GET_PTR_TYPE(*p) != PTR_TYPE_NOTE) + return; /* type mismatch, nothing to remove */ + l = (struct leaf_node *) CLR_PTR_TYPE(*p); + if (hashcmp(l->key_sha1, entry->key_sha1)) + return; /* key mismatch, nothing to remove */ + + /* we have found a matching entry */ + free(l); + *p = SET_PTR_TYPE(NULL, PTR_TYPE_NULL); + + /* consolidate this tree level, and parent levels, if possible */ + if (!n) + return; /* cannot consolidate top level */ + /* first, build stack of ancestors between root and current node */ + parent_stack[0] = &root_node; + for (i = 0; i < n; i++) { + j = GET_NIBBLE(i, entry->key_sha1); + parent_stack[i + 1] = CLR_PTR_TYPE(parent_stack[i]->a[j]); + } + assert(i == n && parent_stack[i] == tree); + /* next, unwind stack until note_tree_consolidate() is done */ + while (i > 0 && + !note_tree_consolidate(parent_stack[i], parent_stack[i - 1], + GET_NIBBLE(i - 1, entry->key_sha1))) + i--; +} + /* Free the entire notes data contained in the given tree */ static void note_tree_free(struct int_node *tree) { @@ -379,6 +452,16 @@ void add_note(const unsigned char *object_sha1, const unsigned char *note_sha1) note_tree_insert(&root_node, 0, l, PTR_TYPE_NOTE); } +void remove_note(const unsigned char *object_sha1) +{ + struct leaf_node l; + + assert(initialized); + hashcpy(l.key_sha1, object_sha1); + hashclr(l.val_sha1); + return note_tree_remove(&root_node, 0, &l); +} + static unsigned char *lookup_notes(const unsigned char *object_sha1) { struct leaf_node *found = note_tree_find(&root_node, 0, object_sha1); |