diff options
Diffstat (limited to 'third_party/git/refs/ref-cache.c')
| -rw-r--r-- | third_party/git/refs/ref-cache.c | 551 |
1 files changed, 0 insertions, 551 deletions
diff --git a/third_party/git/refs/ref-cache.c b/third_party/git/refs/ref-cache.c deleted file mode 100644 index b7052f72e2f4..000000000000 --- a/third_party/git/refs/ref-cache.c +++ /dev/null @@ -1,551 +0,0 @@ -#include "../cache.h" -#include "../refs.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, 1); - 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, - int incomplete) -{ - struct ref_entry *direntry; - - FLEX_ALLOC_MEM(direntry, name, dirname, len); - direntry->u.subdir.cache = cache; - direntry->flag = REF_DIR | (incomplete ? REF_INCOMPLETE : 0); - 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 == NULL) - 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 '/'). If mkdir is set, then create the - * directory if it is missing; otherwise, return 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 mkdir) -{ - int entry_index = search_ref_dir(dir, subdirname, len); - struct ref_entry *entry; - if (entry_index == -1) { - if (!mkdir) - return NULL; - /* - * Since dir is complete, the absence of a subdir - * means that the subdir really doesn't exist; - * therefore, create an empty record for it but mark - * the record complete. - */ - entry = create_dir_entry(dir->cache, subdirname, len, 0); - add_entry_to_dir(dir, entry); - } else { - 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. If - * mkdir is set, then create any missing directories; otherwise, - * return NULL if the desired directory cannot be found. - */ -static struct ref_dir *find_containing_dir(struct ref_dir *dir, - const char *refname, int mkdir) -{ - 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, mkdir); - 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, 0); - 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; -} - -int remove_entry_from_dir(struct ref_dir *dir, const char *refname) -{ - int refname_len = strlen(refname); - int entry_index; - struct ref_entry *entry; - int is_dir = refname[refname_len - 1] == '/'; - if (is_dir) { - /* - * refname represents a reference directory. Remove - * the trailing slash; otherwise we will get the - * directory *representing* refname rather than the - * one *containing* it. - */ - char *dirname = xmemdupz(refname, refname_len - 1); - dir = find_containing_dir(dir, dirname, 0); - free(dirname); - } else { - dir = find_containing_dir(dir, refname, 0); - } - if (!dir) - return -1; - entry_index = search_ref_dir(dir, refname, refname_len); - if (entry_index == -1) - return -1; - entry = dir->entries[entry_index]; - - MOVE_ARRAY(&dir->entries[entry_index], - &dir->entries[entry_index + 1], dir->nr - entry_index - 1); - dir->nr--; - if (dir->sorted > entry_index) - dir->sorted--; - free_ref_entry(entry); - return dir->nr; -} - -int add_ref_entry(struct ref_dir *dir, struct ref_entry *ref) -{ - dir = find_containing_dir(dir, ref->name, 1); - if (!dir) - return -1; - add_entry_to_dir(dir, ref); - return 0; -} - -/* - * 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; -}; - -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) - 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) -{ - return peel_object(ref_iterator->oid, peeled); -} - -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 = { - cache_ref_iterator_advance, - cache_ref_iterator_peel, - cache_ref_iterator_abort -}; - -struct ref_iterator *cache_ref_iterator_begin(struct ref_cache *cache, - const char *prefix, - 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, 0); - if (!dir) - /* There's nothing to iterate over. */ - return empty_ref_iterator_begin(); - - if (prime_dir) - prime_ref_dir(dir, prefix); - - iter = xcalloc(1, sizeof(*iter)); - 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; - } - - return ref_iterator; -} |