#include "cache.h"
#include "notes.h"
#include "blob.h"
#include "tree.h"
#include "utf8.h"
#include "strbuf.h"
#include "tree-walk.h"
#include "string-list.h"
#include "refs.h"
/*
* Use a non-balancing simple 16-tree structure with struct int_node as
* internal nodes, and struct leaf_node as leaf nodes. Each int_node has a
* 16-array of pointers to its children.
* The bottom 2 bits of each pointer is used to identify the pointer type
* - ptr & 3 == 0 - NULL pointer, assert(ptr == NULL)
* - ptr & 3 == 1 - pointer to next internal node - cast to struct int_node *
* - ptr & 3 == 2 - pointer to note entry - cast to struct leaf_node *
* - ptr & 3 == 3 - pointer to subtree entry - cast to struct leaf_node *
*
* The root node is a statically allocated struct int_node.
*/
struct int_node {
void *a[16];
};
/*
* Leaf nodes come in two variants, note entries and subtree entries,
* distinguished by the LSb of the leaf node pointer (see above).
* As a note entry, the key is the SHA1 of the referenced object, and the
* value is the SHA1 of the note object.
* As a subtree entry, the key is the prefix SHA1 (w/trailing NULs) of the
* referenced object, using the last byte of the key to store the length of
* the prefix. The value is the SHA1 of the tree object containing the notes
* subtree.
*/
struct leaf_node {
unsigned char key_sha1[20];
unsigned char val_sha1[20];
};
/*
* A notes tree may contain entries that are not notes, and that do not follow
* the naming conventions of notes. There are typically none/few of these, but
* we still need to keep track of them. Keep a simple linked list sorted alpha-
* betically on the non-note path. The list is populated when parsing tree
* objects in load_subtree(), and the non-notes are correctly written back into
* the tree objects produced by write_notes_tree().
*/
struct non_note {
struct non_note *next; /* grounded (last->next == NULL) */
char *path;
unsigned int mode;
unsigned char sha1[20];
};
#define PTR_TYPE_NULL 0
#define PTR_TYPE_INTERNAL 1
#define PTR_TYPE_NOTE 2
#define PTR_TYPE_SUBTREE 3
#define GET_PTR_TYPE(ptr) ((uintptr_t) (ptr) & 3)
#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 SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \
(memcmp(key_sha1, subtree_sha1, subtree_sha1[19]))
struct notes_tree default_notes_tree;
static struct string_list display_notes_refs;
static struct notes_tree **display_notes_trees;
static void load_subtree(struct notes_tree *t, struct leaf_node *subtree,
struct int_node *node, unsigned int n);
/*
* Search the tree until the appropriate location for the given key is found:
* 1. Start at the root node, with n = 0
* 2. If a[0] at the current level is a matching subtree entry, unpack that
* subtree entry and remove it; restart search at the current level.
* 3. Use the nth nibble of the key as an index into a:
* - If a[n] is an int_node, recurse from #2 into that node and increment n
* - If a matching subtree entry, unpack that subtree entry (and remove it);
* restart search at the current level.
* - Otherwise, we have found one of the following:
* - a subtree entry which does not match the key
* - a note entry which may or may not match the key
* - an unused leaf node (NULL)
* In any case, set *tree and *n, and return pointer to the tree location.
*/
static void **note_tree_search(struct notes_tree *t, struct int_node **tree,
unsigned char *n, const unsigned char *key_sha1)
{
struct leaf_node *l;
unsigned char i;
void *p = (*tree)->a[0];
if (GET_PTR_TYPE(p) == PTR_TYPE_SUBTREE) {
l = (struct leaf_node *) CLR_PTR_TYPE(p);
if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_sha1)) {
/* unpack tree and resume search */
(*tree)->a[0] = NULL;
load_subtree(t, l, *tree, *n);
free(l);
return note_tree_search(t, tree, n, key_sha1);
}
}
i = GET_NIBBLE(*n, key_sha1);
p = (*tree)->a[i];
switch (GET_PTR_TYPE(p)) {
case PTR_TYPE_INTERNAL:
*tree = CLR_PTR_TYPE(p);
(*n)++;
return note_tree_search(t, tree, n, key_sha1);
case PTR_TYPE_SUBTREE:
l = (struct leaf_node *) CLR_PTR_TYPE(p);
if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_sha1)) {
/* unpack tree and resume search */
(*tree)->a[i] = NULL;
|