Git Source Code Mirror - This is a publish-only repository and all pull requests are ignored. Please follow Documentation/SubmittingPatches procedure for any of your improvements. https://git-scm.com/
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
git/notes.c

1356 lines
38 KiB

#include "cache.h"
#include "config.h"
#include "notes.h"
#include "object-store.h"
Refactor notes concatenation into a flexible interface for combining notes When adding a note to an object that already has an existing note, the current solution is to concatenate the contents of the two notes. However, the caller may instead wish to _overwrite_ the existing note with the new note, or maybe even _ignore_ the new note, and keep the existing one. There might also be other ways of combining notes that are only known to the caller. Therefore, instead of unconditionally concatenating notes, we let the caller specify how to combine notes, by passing in a pointer to a function for combining notes. The caller may choose to implement its own function for notes combining, but normally one of the following three conveniently supplied notes combination functions will be sufficient: - combine_notes_concatenate() combines the two notes by appending the contents of the new note to the contents of the existing note. - combine_notes_overwrite() replaces the existing note with the new note. - combine_notes_ignore() keeps the existing note, and ignores the new note. A combine_notes function can be passed to init_notes() to choose a default combine_notes function for that notes tree. If NULL is given, the notes tree falls back to combine_notes_concatenate() as the ultimate default. A combine_notes function can also be passed directly to add_note(), to control the notes combining behaviour for a note addition in particular. If NULL is passed, the combine_notes function registered for the given notes tree is used. Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
#include "blob.h"
#include "tree.h"
#include "utf8.h"
#include "strbuf.h"
#include "tree-walk.h"
#include "string-list.h"
#include "refs.h"
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
/*
* 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];
};
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
/*
* 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
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
* 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
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
* the prefix. The value is the SHA1 of the tree object containing the notes
* subtree.
*/
struct leaf_node {
struct object_id key_oid;
struct object_id val_oid;
};
/*
* 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;
struct object_id oid;
};
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
#define PTR_TYPE_NULL 0
#define PTR_TYPE_INTERNAL 1
#define PTR_TYPE_NOTE 2
#define PTR_TYPE_SUBTREE 3
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
#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 KEY_INDEX (the_hash_algo->rawsz - 1)
#define FANOUT_PATH_SEPARATORS (the_hash_algo->rawsz - 1)
#define FANOUT_PATH_SEPARATORS_MAX ((GIT_MAX_HEXSZ / 2) - 1)
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
#define SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \
(memcmp(key_sha1, subtree_sha1, subtree_sha1[KEY_INDEX]))
struct notes_tree default_notes_tree;
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
static struct string_list display_notes_refs = STRING_LIST_INIT_NODUP;
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);
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
/*
* Search the tree until the appropriate location for the given key is found:
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
* 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
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
* - 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.
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
*/
static void **note_tree_search(struct notes_tree *t, struct int_node **tree,
unsigned char *n, const unsigned char *key_sha1)
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
{
struct leaf_node *l;
unsigned char i;
void *p = (*tree)->a[0];
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
if (GET_PTR_TYPE(p) == PTR_TYPE_SUBTREE) {
l = (struct leaf_node *) CLR_PTR_TYPE(p);
if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_oid.hash)) {
/* 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)) {
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
case PTR_TYPE_INTERNAL:
*tree = CLR_PTR_TYPE(p);
(*n)++;
return note_tree_search(t, tree, n, key_sha1);
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
case PTR_TYPE_SUBTREE:
l = (struct leaf_node *) CLR_PTR_TYPE(p);
if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_oid.hash)) {
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
/* unpack tree and resume search */
(*tree)->a[i] = NULL;
load_subtree(t, l, *tree, *n);
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
free(l);
return note_tree_search(t, tree, n, key_sha1);
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
}
/* fall through */
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
default:
return &((*tree)->a[i]);
}
}
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
/*
* To find a leaf_node:
* Search to the tree location appropriate for the given key:
* If a note entry with matching key, return the note entry, else return NULL.
*/
static struct leaf_node *note_tree_find(struct notes_tree *t,
struct int_node *tree, unsigned char n,
const unsigned char *key_sha1)
{
void **p = note_tree_search(t, &tree, &n, key_sha1);
if (GET_PTR_TYPE(*p) == PTR_TYPE_NOTE) {
struct leaf_node *l = (struct leaf_node *) CLR_PTR_TYPE(*p);
if (hasheq(key_sha1, l->key_oid.hash))
return l;
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
}
return NULL;
}
/*
* 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
notes: do not break note_tree structure in note_tree_consolidate() After a note is removed, note_tree_consolidate is called to eliminate some useless nodes. The typical case is that if you had an int_node with 2 PTR_TYPE_NOTEs in it, and remove one of them, then the PTR_TYPE_INTERNAL pointer in the parent tree can be replaced with the remaining PTR_TYPE_NOTE. This works fine when PTR_TYPE_NOTEs are involved, but falls flat when other types are involved. To put things in more practical terms, let's say we start from an empty notes tree, and add 3 notes: - one for a sha1 that starts with 424 - one for a sha1 that starts with 428 - one for a sha1 that starts with 4c To keep track of this, note_tree.root will have a PTR_TYPE_INTERNAL at a[4], pointing to an int_node*. In turn, that int_node* will have a PTR_TYPE_NOTE at a[0xc], pointing to the leaf_node* with the key and value, and a PTR_TYPE_INTERNAL at a[2], pointing to another int_node*. That other int_node* will have 2 PTR_TYPE_NOTE, one at a[4] and the other at a[8]. When looking for the note for the sha1 starting with 428, get_note() will recurse through (simplified) root.a[4].a[2].a[8]. Now, if we remove the note for the sha1 that starts with 4c, we're left with a int_node* with only one PTR_TYPE_INTERNAL entry in it. After note_tree_consolidate runs, root.a[4] now points to what used to be pointed at by root.a[4].a[2]. Which means looking up for the note for the sha1 starting with 428 now fails because there is nothing at root.a[4].a[2] anymore: there is only root.a[4].a[4] and root.a[4].a[8], which don't match the expected structure for the lookup. So if all there is left in an int_node* is a PTR_TYPE_INTERNAL pointer, we can't safely remove it. I think the same applies for PTR_TYPE_SUBTREE pointers. IOW, only PTR_TYPE_NOTEs are safe to be moved to the parent int_node*. This doesn't have a practical effect on git because all that happens after a remove_note is a write_notes_tree, which just iterates the entire note tree, but this affects anything using libgit.a that would try to do lookups after removing notes. Signed-off-by: Mike Hommey <mh@glandium.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
6 years ago
* with the only NOTE 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];
}
}
notes: do not break note_tree structure in note_tree_consolidate() After a note is removed, note_tree_consolidate is called to eliminate some useless nodes. The typical case is that if you had an int_node with 2 PTR_TYPE_NOTEs in it, and remove one of them, then the PTR_TYPE_INTERNAL pointer in the parent tree can be replaced with the remaining PTR_TYPE_NOTE. This works fine when PTR_TYPE_NOTEs are involved, but falls flat when other types are involved. To put things in more practical terms, let's say we start from an empty notes tree, and add 3 notes: - one for a sha1 that starts with 424 - one for a sha1 that starts with 428 - one for a sha1 that starts with 4c To keep track of this, note_tree.root will have a PTR_TYPE_INTERNAL at a[4], pointing to an int_node*. In turn, that int_node* will have a PTR_TYPE_NOTE at a[0xc], pointing to the leaf_node* with the key and value, and a PTR_TYPE_INTERNAL at a[2], pointing to another int_node*. That other int_node* will have 2 PTR_TYPE_NOTE, one at a[4] and the other at a[8]. When looking for the note for the sha1 starting with 428, get_note() will recurse through (simplified) root.a[4].a[2].a[8]. Now, if we remove the note for the sha1 that starts with 4c, we're left with a int_node* with only one PTR_TYPE_INTERNAL entry in it. After note_tree_consolidate runs, root.a[4] now points to what used to be pointed at by root.a[4].a[2]. Which means looking up for the note for the sha1 starting with 428 now fails because there is nothing at root.a[4].a[2] anymore: there is only root.a[4].a[4] and root.a[4].a[8], which don't match the expected structure for the lookup. So if all there is left in an int_node* is a PTR_TYPE_INTERNAL pointer, we can't safely remove it. I think the same applies for PTR_TYPE_SUBTREE pointers. IOW, only PTR_TYPE_NOTEs are safe to be moved to the parent int_node*. This doesn't have a practical effect on git because all that happens after a remove_note is a write_notes_tree, which just iterates the entire note tree, but this affects anything using libgit.a that would try to do lookups after removing notes. Signed-off-by: Mike Hommey <mh@glandium.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
6 years ago
if (p && (GET_PTR_TYPE(p) != PTR_TYPE_NOTE))
return -2;
/* 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.
* - Copy the matching entry's value into the given entry.
* - 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 notes_tree *t,
struct int_node *tree, unsigned char n,
struct leaf_node *entry)
{
struct leaf_node *l;
struct int_node *parent_stack[GIT_MAX_RAWSZ];
unsigned char i, j;
void **p = note_tree_search(t, &tree, &n, entry->key_oid.hash);
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 (!oideq(&l->key_oid, &entry->key_oid))
return; /* key mismatch, nothing to remove */
/* we have found a matching entry */
oidcpy(&entry->val_oid, &l->val_oid);
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] = t->root;
for (i = 0; i < n; i++) {
j = GET_NIBBLE(i, entry->key_oid.hash);
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_oid.hash)))
i--;
}
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
/*
* To insert a leaf_node:
* Search to the tree location appropriate for the given leaf_node's key:
* - If location is unused (NULL), store the tweaked pointer directly there
* - If location holds a note entry that matches the note-to-be-inserted, then
Refactor notes concatenation into a flexible interface for combining notes When adding a note to an object that already has an existing note, the current solution is to concatenate the contents of the two notes. However, the caller may instead wish to _overwrite_ the existing note with the new note, or maybe even _ignore_ the new note, and keep the existing one. There might also be other ways of combining notes that are only known to the caller. Therefore, instead of unconditionally concatenating notes, we let the caller specify how to combine notes, by passing in a pointer to a function for combining notes. The caller may choose to implement its own function for notes combining, but normally one of the following three conveniently supplied notes combination functions will be sufficient: - combine_notes_concatenate() combines the two notes by appending the contents of the new note to the contents of the existing note. - combine_notes_overwrite() replaces the existing note with the new note. - combine_notes_ignore() keeps the existing note, and ignores the new note. A combine_notes function can be passed to init_notes() to choose a default combine_notes function for that notes tree. If NULL is given, the notes tree falls back to combine_notes_concatenate() as the ultimate default. A combine_notes function can also be passed directly to add_note(), to control the notes combining behaviour for a note addition in particular. If NULL is passed, the combine_notes function registered for the given notes tree is used. Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
* combine the two notes (by calling the given combine_notes function).
* - If location holds a note entry that matches the subtree-to-be-inserted,
* then unpack the subtree-to-be-inserted into the location.
* - If location holds a matching subtree entry, unpack the subtree at that
* location, and restart the insert operation from that level.
* - Else, create a new int_node, holding both the node-at-location and the
* node-to-be-inserted, and store the new int_node into the location.
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
*/
static int note_tree_insert(struct notes_tree *t, struct int_node *tree,
unsigned char n, struct leaf_node *entry, unsigned char type,
Refactor notes concatenation into a flexible interface for combining notes When adding a note to an object that already has an existing note, the current solution is to concatenate the contents of the two notes. However, the caller may instead wish to _overwrite_ the existing note with the new note, or maybe even _ignore_ the new note, and keep the existing one. There might also be other ways of combining notes that are only known to the caller. Therefore, instead of unconditionally concatenating notes, we let the caller specify how to combine notes, by passing in a pointer to a function for combining notes. The caller may choose to implement its own function for notes combining, but normally one of the following three conveniently supplied notes combination functions will be sufficient: - combine_notes_concatenate() combines the two notes by appending the contents of the new note to the contents of the existing note. - combine_notes_overwrite() replaces the existing note with the new note. - combine_notes_ignore() keeps the existing note, and ignores the new note. A combine_notes function can be passed to init_notes() to choose a default combine_notes function for that notes tree. If NULL is given, the notes tree falls back to combine_notes_concatenate() as the ultimate default. A combine_notes function can also be passed directly to add_note(), to control the notes combining behaviour for a note addition in particular. If NULL is passed, the combine_notes function registered for the given notes tree is used. Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
combine_notes_fn combine_notes)
{
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
struct int_node *new_node;
struct leaf_node *l;
void **p = note_tree_search(t, &tree, &n, entry->key_oid.hash);
int ret = 0;
assert(GET_PTR_TYPE(entry) == 0); /* no type bits set */
l = (struct leaf_node *) CLR_PTR_TYPE(*p);
switch (GET_PTR_TYPE(*p)) {
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
case PTR_TYPE_NULL:
assert(!*p);
if (is_null_oid(&entry->val_oid))
free(entry);
else
*p = SET_PTR_TYPE(entry, type);
return 0;
case PTR_TYPE_NOTE:
switch (type) {
case PTR_TYPE_NOTE:
if (oideq(&l->key_oid, &entry->key_oid)) {
/* skip concatenation if l == entry */
if (oideq(&l->val_oid, &entry->val_oid)) {
free(entry);
return 0;
}
ret = combine_notes(&l->val_oid,
&entry->val_oid);
if (!ret && is_null_oid(&l->val_oid))
note_tree_remove(t, tree, n, entry);
free(entry);
return ret;
}
break;
case PTR_TYPE_SUBTREE:
if (!SUBTREE_SHA1_PREFIXCMP(l->key_oid.hash,
entry->key_oid.hash)) {
/* unpack 'entry' */
load_subtree(t, entry, tree, n);
free(entry);
return 0;
}
break;
}
break;
case PTR_TYPE_SUBTREE:
if (!SUBTREE_SHA1_PREFIXCMP(entry->key_oid.hash, l->key_oid.hash)) {
/* unpack 'l' and restart insert */
*p = NULL;
load_subtree(t, l, tree, n);
free(l);
return note_tree_insert(t, tree, n, entry, type,
combine_notes);
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
}
break;
}
/* non-matching leaf_node */
assert(GET_PTR_TYPE(*p) == PTR_TYPE_NOTE ||
GET_PTR_TYPE(*p) == PTR_TYPE_SUBTREE);
if (is_null_oid(&entry->val_oid)) { /* skip insertion of empty note */
free(entry);
return 0;
}
new_node = (struct int_node *) xcalloc(1, sizeof(struct int_node));
ret = note_tree_insert(t, new_node, n + 1, l, GET_PTR_TYPE(*p),
combine_notes);
if (ret)
return ret;
*p = SET_PTR_TYPE(new_node, PTR_TYPE_INTERNAL);
return note_tree_insert(t, new_node, n + 1, entry, type, combine_notes);
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
}
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up). In addition to this, comes the massive performance win associated with organizing the notes tree according to some fanout scheme. Even a simple 2/38 fanout scheme is dramatically quicker to traverse (going from tens of seconds to sub-second runtimes). As for memory usage, the new code is marginally better than the old code in the worst case, but in the case of looking up only some notes from a notes tree with proper fanout, the new code uses only a small fraction of the memory needed to hold the entire notes tree. However, there is one casualty of this patch. The old notes lookup code was able to parse notes that were associated with non-SHA1s (e.g. refs). The new code requires the referenced object to be named by a SHA1 sum. Still, this is not considered a major setback, since the notes infrastructure was not originally intended to annotate objects outside the Git object database. Cc: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
13 years ago
/* Free the entire notes data contained in the given tree */
static void note_tree_free(struct int_node *tree)
{
unsigned int i;
for (i = 0; i < 16; i++) {
void *p = tree->a[i];
switch (GET_PTR_TYPE(p)) {
Teach the notes lookup code to parse notes trees with various fanout schemes The semantics used when parsing notes trees (with regards to fanout subtrees) follow Dscho's proposal fairly closely: - No concatenation/merging of notes is performed. If there are several notes objects referencing a given commit, only one of those objects are used. - If a notes object for a given commit is present in the "root" notes tree, no subtrees are consulted; the object in the root tree is used directly. - If there are more than one subtree that prefix-matches the given commit, only the subtree with the longest matching prefix is consulted. This means that if the given commit is e.g. "deadbeef", and the notes tree have subtrees "de" and "dead", then the following paths in the notes tree are searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched. - Fanout directories (subtrees) must references a whole number of bytes from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are acceptable; "d" and "dea" are not. - Multiple levels of fanout are allowed. All the above rules apply recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc. This patch changes the in-memory datastructure for holding parsed notes: Instead of holding all note (and subtree) entries in a hash table, a simple 16-tree structure is used instead. The tree structure consists of 16-arrays as internal nodes, and note/subtree entries as leaf nodes. The tree is traversed by indexing subsequent nibbles of the search key until a leaf node is encountered. If a subtree entry is encountered while searching for a note, the subtree is unpacked into the 16-tree structure, and the search continues into that subtree. The new algorithm performs significantly better in the cases where only a fraction of the notes need to be looked up (this is assumed to be the common case for notes lookup). The new code even performs marginally better in the worst case (where _all_ the notes are looked up).