summaryrefslogtreecommitdiffstats
path: root/refs/ref-cache.c
diff options
context:
space:
mode:
Diffstat (limited to 'refs/ref-cache.c')
-rw-r--r--refs/ref-cache.c508
1 files changed, 508 insertions, 0 deletions
diff --git a/refs/ref-cache.c b/refs/ref-cache.c
new file mode 100644
index 0000000..6e3b725
--- /dev/null
+++ b/refs/ref-cache.c
@@ -0,0 +1,508 @@
+#include "../git-compat-util.h"
+#include "../alloc.h"
+#include "../hash.h"
+#include "../refs.h"
+#include "../repository.h"
+#include "refs-internal.h"
+#include "ref-cache.h"
+#include "../iterator.h"
+
+void add_entry_to_dir(struct ref_dir *dir, struct ref_entry *entry)
+{
+ ALLOC_GROW(dir->entries, dir->nr + 1, dir->alloc);
+ dir->entries[dir->nr++] = entry;
+ /* optimize for the case that entries are added in order */
+ if (dir->nr == 1 ||
+ (dir->nr == dir->sorted + 1 &&
+ strcmp(dir->entries[dir->nr - 2]->name,
+ dir->entries[dir->nr - 1]->name) < 0))
+ dir->sorted = dir->nr;
+}
+
+struct ref_dir *get_ref_dir(struct ref_entry *entry)
+{
+ struct ref_dir *dir;
+ assert(entry->flag & REF_DIR);
+ dir = &entry->u.subdir;
+ if (entry->flag & REF_INCOMPLETE) {
+ if (!dir->cache->fill_ref_dir)
+ BUG("incomplete ref_store without fill_ref_dir function");
+
+ dir->cache->fill_ref_dir(dir->cache->ref_store, dir, entry->name);
+ entry->flag &= ~REF_INCOMPLETE;
+ }
+ return dir;
+}
+
+struct ref_entry *create_ref_entry(const char *refname,
+ const struct object_id *oid, int flag)
+{
+ struct ref_entry *ref;
+
+ FLEX_ALLOC_STR(ref, name, refname);
+ oidcpy(&ref->u.value.oid, oid);
+ ref->flag = flag;
+ return ref;
+}
+
+struct ref_cache *create_ref_cache(struct ref_store *refs,
+ fill_ref_dir_fn *fill_ref_dir)
+{
+ struct ref_cache *ret = xcalloc(1, sizeof(*ret));
+
+ ret->ref_store = refs;
+ ret->fill_ref_dir = fill_ref_dir;
+ ret->root = create_dir_entry(ret, "", 0);
+ return ret;
+}
+
+static void clear_ref_dir(struct ref_dir *dir);
+
+static void free_ref_entry(struct ref_entry *entry)
+{
+ if (entry->flag & REF_DIR) {
+ /*
+ * Do not use get_ref_dir() here, as that might
+ * trigger the reading of loose refs.
+ */
+ clear_ref_dir(&entry->u.subdir);
+ }
+ free(entry);
+}
+
+void free_ref_cache(struct ref_cache *cache)
+{
+ free_ref_entry(cache->root);
+ free(cache);
+}
+
+/*
+ * Clear and free all entries in dir, recursively.
+ */
+static void clear_ref_dir(struct ref_dir *dir)
+{
+ int i;
+ for (i = 0; i < dir->nr; i++)
+ free_ref_entry(dir->entries[i]);
+ FREE_AND_NULL(dir->entries);
+ dir->sorted = dir->nr = dir->alloc = 0;
+}
+
+struct ref_entry *create_dir_entry(struct ref_cache *cache,
+ const char *dirname, size_t len)
+{
+ struct ref_entry *direntry;
+
+ FLEX_ALLOC_MEM(direntry, name, dirname, len);
+ direntry->u.subdir.cache = cache;
+ direntry->flag = REF_DIR | REF_INCOMPLETE;
+ return direntry;
+}
+
+static int ref_entry_cmp(const void *a, const void *b)
+{
+ struct ref_entry *one = *(struct ref_entry **)a;
+ struct ref_entry *two = *(struct ref_entry **)b;
+ return strcmp(one->name, two->name);
+}
+
+static void sort_ref_dir(struct ref_dir *dir);
+
+struct string_slice {
+ size_t len;
+ const char *str;
+};
+
+static int ref_entry_cmp_sslice(const void *key_, const void *ent_)
+{
+ const struct string_slice *key = key_;
+ const struct ref_entry *ent = *(const struct ref_entry * const *)ent_;
+ int cmp = strncmp(key->str, ent->name, key->len);
+ if (cmp)
+ return cmp;
+ return '\0' - (unsigned char)ent->name[key->len];
+}
+
+int search_ref_dir(struct ref_dir *dir, const char *refname, size_t len)
+{
+ struct ref_entry **r;
+ struct string_slice key;
+
+ if (refname == NULL || !dir->nr)
+ return -1;
+
+ sort_ref_dir(dir);
+ key.len = len;
+ key.str = refname;
+ r = bsearch(&key, dir->entries, dir->nr, sizeof(*dir->entries),
+ ref_entry_cmp_sslice);
+
+ if (!r)
+ return -1;
+
+ return r - dir->entries;
+}
+
+/*
+ * Search for a directory entry directly within dir (without
+ * recursing). Sort dir if necessary. subdirname must be a directory
+ * name (i.e., end in '/'). Returns NULL if the desired
+ * directory cannot be found. dir must already be complete.
+ */
+static struct ref_dir *search_for_subdir(struct ref_dir *dir,
+ const char *subdirname, size_t len)
+{
+ int entry_index = search_ref_dir(dir, subdirname, len);
+ struct ref_entry *entry;
+
+ if (entry_index == -1)
+ return NULL;
+
+ entry = dir->entries[entry_index];
+ return get_ref_dir(entry);
+}
+
+/*
+ * If refname is a reference name, find the ref_dir within the dir
+ * tree that should hold refname. If refname is a directory name
+ * (i.e., it ends in '/'), then return that ref_dir itself. dir must
+ * represent the top-level directory and must already be complete.
+ * Sort ref_dirs and recurse into subdirectories as necessary. Will
+ * return NULL if the desired directory cannot be found.
+ */
+static struct ref_dir *find_containing_dir(struct ref_dir *dir,
+ const char *refname)
+{
+ const char *slash;
+ for (slash = strchr(refname, '/'); slash; slash = strchr(slash + 1, '/')) {
+ size_t dirnamelen = slash - refname + 1;
+ struct ref_dir *subdir;
+ subdir = search_for_subdir(dir, refname, dirnamelen);
+ if (!subdir) {
+ dir = NULL;
+ break;
+ }
+ dir = subdir;
+ }
+
+ return dir;
+}
+
+struct ref_entry *find_ref_entry(struct ref_dir *dir, const char *refname)
+{
+ int entry_index;
+ struct ref_entry *entry;
+ dir = find_containing_dir(dir, refname);
+ if (!dir)
+ return NULL;
+ entry_index = search_ref_dir(dir, refname, strlen(refname));
+ if (entry_index == -1)
+ return NULL;
+ entry = dir->entries[entry_index];
+ return (entry->flag & REF_DIR) ? NULL : entry;
+}
+
+/*
+ * Emit a warning and return true iff ref1 and ref2 have the same name
+ * and the same oid. Die if they have the same name but different
+ * oids.
+ */
+static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2)
+{
+ if (strcmp(ref1->name, ref2->name))
+ return 0;
+
+ /* Duplicate name; make sure that they don't conflict: */
+
+ if ((ref1->flag & REF_DIR) || (ref2->flag & REF_DIR))
+ /* This is impossible by construction */
+ die("Reference directory conflict: %s", ref1->name);
+
+ if (!oideq(&ref1->u.value.oid, &ref2->u.value.oid))
+ die("Duplicated ref, and SHA1s don't match: %s", ref1->name);
+
+ warning("Duplicated ref: %s", ref1->name);
+ return 1;
+}
+
+/*
+ * Sort the entries in dir non-recursively (if they are not already
+ * sorted) and remove any duplicate entries.
+ */
+static void sort_ref_dir(struct ref_dir *dir)
+{
+ int i, j;
+ struct ref_entry *last = NULL;
+
+ /*
+ * This check also prevents passing a zero-length array to qsort(),
+ * which is a problem on some platforms.
+ */
+ if (dir->sorted == dir->nr)
+ return;
+
+ QSORT(dir->entries, dir->nr, ref_entry_cmp);
+
+ /* Remove any duplicates: */
+ for (i = 0, j = 0; j < dir->nr; j++) {
+ struct ref_entry *entry = dir->entries[j];
+ if (last && is_dup_ref(last, entry))
+ free_ref_entry(entry);
+ else
+ last = dir->entries[i++] = entry;
+ }
+ dir->sorted = dir->nr = i;
+}
+
+enum prefix_state {
+ /* All refs within the directory would match prefix: */
+ PREFIX_CONTAINS_DIR,
+
+ /* Some, but not all, refs within the directory might match prefix: */
+ PREFIX_WITHIN_DIR,
+
+ /* No refs within the directory could possibly match prefix: */
+ PREFIX_EXCLUDES_DIR
+};
+
+/*
+ * Return a `prefix_state` constant describing the relationship
+ * between the directory with the specified `dirname` and `prefix`.
+ */
+static enum prefix_state overlaps_prefix(const char *dirname,
+ const char *prefix)
+{
+ while (*prefix && *dirname == *prefix) {
+ dirname++;
+ prefix++;
+ }
+ if (!*prefix)
+ return PREFIX_CONTAINS_DIR;
+ else if (!*dirname)
+ return PREFIX_WITHIN_DIR;
+ else
+ return PREFIX_EXCLUDES_DIR;
+}
+
+/*
+ * Load all of the refs from `dir` (recursively) that could possibly
+ * contain references matching `prefix` into our in-memory cache. If
+ * `prefix` is NULL, prime unconditionally.
+ */
+static void prime_ref_dir(struct ref_dir *dir, const char *prefix)
+{
+ /*
+ * The hard work of loading loose refs is done by get_ref_dir(), so we
+ * just need to recurse through all of the sub-directories. We do not
+ * even need to care about sorting, as traversal order does not matter
+ * to us.
+ */
+ int i;
+ for (i = 0; i < dir->nr; i++) {
+ struct ref_entry *entry = dir->entries[i];
+ if (!(entry->flag & REF_DIR)) {
+ /* Not a directory; no need to recurse. */
+ } else if (!prefix) {
+ /* Recurse in any case: */
+ prime_ref_dir(get_ref_dir(entry), NULL);
+ } else {
+ switch (overlaps_prefix(entry->name, prefix)) {
+ case PREFIX_CONTAINS_DIR:
+ /*
+ * Recurse, and from here down we
+ * don't have to check the prefix
+ * anymore:
+ */
+ prime_ref_dir(get_ref_dir(entry), NULL);
+ break;
+ case PREFIX_WITHIN_DIR:
+ prime_ref_dir(get_ref_dir(entry), prefix);
+ break;
+ case PREFIX_EXCLUDES_DIR:
+ /* No need to prime this directory. */
+ break;
+ }
+ }
+ }
+}
+
+/*
+ * A level in the reference hierarchy that is currently being iterated
+ * through.
+ */
+struct cache_ref_iterator_level {
+ /*
+ * The ref_dir being iterated over at this level. The ref_dir
+ * is sorted before being stored here.
+ */
+ struct ref_dir *dir;
+
+ enum prefix_state prefix_state;
+
+ /*
+ * The index of the current entry within dir (which might
+ * itself be a directory). If index == -1, then the iteration
+ * hasn't yet begun. If index == dir->nr, then the iteration
+ * through this level is over.
+ */
+ int index;
+};
+
+/*
+ * Represent an iteration through a ref_dir in the memory cache. The
+ * iteration recurses through subdirectories.
+ */
+struct cache_ref_iterator {
+ struct ref_iterator base;
+
+ /*
+ * The number of levels currently on the stack. This is always
+ * at least 1, because when it becomes zero the iteration is
+ * ended and this struct is freed.
+ */
+ size_t levels_nr;
+
+ /* The number of levels that have been allocated on the stack */
+ size_t levels_alloc;
+
+ /*
+ * Only include references with this prefix in the iteration.
+ * The prefix is matched textually, without regard for path
+ * component boundaries.
+ */
+ const char *prefix;
+
+ /*
+ * A stack of levels. levels[0] is the uppermost level that is
+ * being iterated over in this iteration. (This is not
+ * necessary the top level in the references hierarchy. If we
+ * are iterating through a subtree, then levels[0] will hold
+ * the ref_dir for that subtree, and subsequent levels will go
+ * on from there.)
+ */
+ struct cache_ref_iterator_level *levels;
+
+ struct repository *repo;
+};
+
+static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)
+{
+ struct cache_ref_iterator *iter =
+ (struct cache_ref_iterator *)ref_iterator;
+
+ while (1) {
+ struct cache_ref_iterator_level *level =
+ &iter->levels[iter->levels_nr - 1];
+ struct ref_dir *dir = level->dir;
+ struct ref_entry *entry;
+ enum prefix_state entry_prefix_state;
+
+ if (level->index == -1)
+ sort_ref_dir(dir);
+
+ if (++level->index == level->dir->nr) {
+ /* This level is exhausted; pop up a level */
+ if (--iter->levels_nr == 0)
+ return ref_iterator_abort(ref_iterator);
+
+ continue;
+ }
+
+ entry = dir->entries[level->index];
+
+ if (level->prefix_state == PREFIX_WITHIN_DIR) {
+ entry_prefix_state = overlaps_prefix(entry->name, iter->prefix);
+ if (entry_prefix_state == PREFIX_EXCLUDES_DIR ||
+ (entry_prefix_state == PREFIX_WITHIN_DIR && !(entry->flag & REF_DIR)))
+ continue;
+ } else {
+ entry_prefix_state = level->prefix_state;
+ }
+
+ if (entry->flag & REF_DIR) {
+ /* push down a level */
+ ALLOC_GROW(iter->levels, iter->levels_nr + 1,
+ iter->levels_alloc);
+
+ level = &iter->levels[iter->levels_nr++];
+ level->dir = get_ref_dir(entry);
+ level->prefix_state = entry_prefix_state;
+ level->index = -1;
+ } else {
+ iter->base.refname = entry->name;
+ iter->base.oid = &entry->u.value.oid;
+ iter->base.flags = entry->flag;
+ return ITER_OK;
+ }
+ }
+}
+
+static int cache_ref_iterator_peel(struct ref_iterator *ref_iterator,
+ struct object_id *peeled)
+{
+ struct cache_ref_iterator *iter =
+ (struct cache_ref_iterator *)ref_iterator;
+
+ if (iter->repo != the_repository)
+ BUG("peeling for non-the_repository is not supported");
+ return peel_object(ref_iterator->oid, peeled) ? -1 : 0;
+}
+
+static int cache_ref_iterator_abort(struct ref_iterator *ref_iterator)
+{
+ struct cache_ref_iterator *iter =
+ (struct cache_ref_iterator *)ref_iterator;
+
+ free((char *)iter->prefix);
+ free(iter->levels);
+ base_ref_iterator_free(ref_iterator);
+ return ITER_DONE;
+}
+
+static struct ref_iterator_vtable cache_ref_iterator_vtable = {
+ .advance = cache_ref_iterator_advance,
+ .peel = cache_ref_iterator_peel,
+ .abort = cache_ref_iterator_abort
+};
+
+struct ref_iterator *cache_ref_iterator_begin(struct ref_cache *cache,
+ const char *prefix,
+ struct repository *repo,
+ int prime_dir)
+{
+ struct ref_dir *dir;
+ struct cache_ref_iterator *iter;
+ struct ref_iterator *ref_iterator;
+ struct cache_ref_iterator_level *level;
+
+ dir = get_ref_dir(cache->root);
+ if (prefix && *prefix)
+ dir = find_containing_dir(dir, prefix);
+ if (!dir)
+ /* There's nothing to iterate over. */
+ return empty_ref_iterator_begin();
+
+ if (prime_dir)
+ prime_ref_dir(dir, prefix);
+
+ CALLOC_ARRAY(iter, 1);
+ ref_iterator = &iter->base;
+ base_ref_iterator_init(ref_iterator, &cache_ref_iterator_vtable, 1);
+ ALLOC_GROW(iter->levels, 10, iter->levels_alloc);
+
+ iter->levels_nr = 1;
+ level = &iter->levels[0];
+ level->index = -1;
+ level->dir = dir;
+
+ if (prefix && *prefix) {
+ iter->prefix = xstrdup(prefix);
+ level->prefix_state = PREFIX_WITHIN_DIR;
+ } else {
+ level->prefix_state = PREFIX_CONTAINS_DIR;
+ }
+
+ iter->repo = repo;
+
+ return ref_iterator;
+}