3 #include "refs-internal.h"
5 #include "../iterator.h"
7 void add_entry_to_dir(struct ref_dir *dir, struct ref_entry *entry)
9 ALLOC_GROW(dir->entries, dir->nr + 1, dir->alloc);
10 dir->entries[dir->nr++] = entry;
11 /* optimize for the case that entries are added in order */
13 (dir->nr == dir->sorted + 1 &&
14 strcmp(dir->entries[dir->nr - 2]->name,
15 dir->entries[dir->nr - 1]->name) < 0))
16 dir->sorted = dir->nr;
19 struct ref_dir *get_ref_dir(struct ref_entry *entry)
22 assert(entry->flag & REF_DIR);
23 dir = &entry->u.subdir;
24 if (entry->flag & REF_INCOMPLETE) {
25 if (!dir->cache->fill_ref_dir)
26 die("BUG: incomplete ref_store without fill_ref_dir function");
28 dir->cache->fill_ref_dir(dir->cache->ref_store, dir, entry->name);
29 entry->flag &= ~REF_INCOMPLETE;
34 struct ref_entry *create_ref_entry(const char *refname,
35 const unsigned char *sha1, int flag,
38 struct ref_entry *ref;
41 check_refname_format(refname, REFNAME_ALLOW_ONELEVEL))
42 die("Reference has invalid format: '%s'", refname);
43 FLEX_ALLOC_STR(ref, name, refname);
44 hashcpy(ref->u.value.oid.hash, sha1);
45 oidclr(&ref->u.value.peeled);
50 struct ref_cache *create_ref_cache(struct ref_store *refs,
51 fill_ref_dir_fn *fill_ref_dir)
53 struct ref_cache *ret = xcalloc(1, sizeof(*ret));
55 ret->ref_store = refs;
56 ret->fill_ref_dir = fill_ref_dir;
57 ret->root = create_dir_entry(ret, "", 0, 1);
61 static void clear_ref_dir(struct ref_dir *dir);
63 static void free_ref_entry(struct ref_entry *entry)
65 if (entry->flag & REF_DIR) {
67 * Do not use get_ref_dir() here, as that might
68 * trigger the reading of loose refs.
70 clear_ref_dir(&entry->u.subdir);
75 void free_ref_cache(struct ref_cache *cache)
77 free_ref_entry(cache->root);
82 * Clear and free all entries in dir, recursively.
84 static void clear_ref_dir(struct ref_dir *dir)
87 for (i = 0; i < dir->nr; i++)
88 free_ref_entry(dir->entries[i]);
90 dir->sorted = dir->nr = dir->alloc = 0;
94 struct ref_entry *create_dir_entry(struct ref_cache *cache,
95 const char *dirname, size_t len,
98 struct ref_entry *direntry;
100 FLEX_ALLOC_MEM(direntry, name, dirname, len);
101 direntry->u.subdir.cache = cache;
102 direntry->flag = REF_DIR | (incomplete ? REF_INCOMPLETE : 0);
106 static int ref_entry_cmp(const void *a, const void *b)
108 struct ref_entry *one = *(struct ref_entry **)a;
109 struct ref_entry *two = *(struct ref_entry **)b;
110 return strcmp(one->name, two->name);
113 static void sort_ref_dir(struct ref_dir *dir);
115 struct string_slice {
120 static int ref_entry_cmp_sslice(const void *key_, const void *ent_)
122 const struct string_slice *key = key_;
123 const struct ref_entry *ent = *(const struct ref_entry * const *)ent_;
124 int cmp = strncmp(key->str, ent->name, key->len);
127 return '\0' - (unsigned char)ent->name[key->len];
130 int search_ref_dir(struct ref_dir *dir, const char *refname, size_t len)
132 struct ref_entry **r;
133 struct string_slice key;
135 if (refname == NULL || !dir->nr)
141 r = bsearch(&key, dir->entries, dir->nr, sizeof(*dir->entries),
142 ref_entry_cmp_sslice);
147 return r - dir->entries;
151 * Search for a directory entry directly within dir (without
152 * recursing). Sort dir if necessary. subdirname must be a directory
153 * name (i.e., end in '/'). If mkdir is set, then create the
154 * directory if it is missing; otherwise, return NULL if the desired
155 * directory cannot be found. dir must already be complete.
157 static struct ref_dir *search_for_subdir(struct ref_dir *dir,
158 const char *subdirname, size_t len,
161 int entry_index = search_ref_dir(dir, subdirname, len);
162 struct ref_entry *entry;
163 if (entry_index == -1) {
167 * Since dir is complete, the absence of a subdir
168 * means that the subdir really doesn't exist;
169 * therefore, create an empty record for it but mark
170 * the record complete.
172 entry = create_dir_entry(dir->cache, subdirname, len, 0);
173 add_entry_to_dir(dir, entry);
175 entry = dir->entries[entry_index];
177 return get_ref_dir(entry);
180 struct ref_dir *find_containing_dir(struct ref_dir *dir,
181 const char *refname, int mkdir)
184 for (slash = strchr(refname, '/'); slash; slash = strchr(slash + 1, '/')) {
185 size_t dirnamelen = slash - refname + 1;
186 struct ref_dir *subdir;
187 subdir = search_for_subdir(dir, refname, dirnamelen, mkdir);
198 struct ref_entry *find_ref_entry(struct ref_dir *dir, const char *refname)
201 struct ref_entry *entry;
202 dir = find_containing_dir(dir, refname, 0);
205 entry_index = search_ref_dir(dir, refname, strlen(refname));
206 if (entry_index == -1)
208 entry = dir->entries[entry_index];
209 return (entry->flag & REF_DIR) ? NULL : entry;
212 int remove_entry_from_dir(struct ref_dir *dir, const char *refname)
214 int refname_len = strlen(refname);
216 struct ref_entry *entry;
217 int is_dir = refname[refname_len - 1] == '/';
220 * refname represents a reference directory. Remove
221 * the trailing slash; otherwise we will get the
222 * directory *representing* refname rather than the
223 * one *containing* it.
225 char *dirname = xmemdupz(refname, refname_len - 1);
226 dir = find_containing_dir(dir, dirname, 0);
229 dir = find_containing_dir(dir, refname, 0);
233 entry_index = search_ref_dir(dir, refname, refname_len);
234 if (entry_index == -1)
236 entry = dir->entries[entry_index];
238 memmove(&dir->entries[entry_index],
239 &dir->entries[entry_index + 1],
240 (dir->nr - entry_index - 1) * sizeof(*dir->entries)
243 if (dir->sorted > entry_index)
245 free_ref_entry(entry);
249 int add_ref_entry(struct ref_dir *dir, struct ref_entry *ref)
251 dir = find_containing_dir(dir, ref->name, 1);
254 add_entry_to_dir(dir, ref);
259 * Emit a warning and return true iff ref1 and ref2 have the same name
260 * and the same sha1. Die if they have the same name but different
263 static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2)
265 if (strcmp(ref1->name, ref2->name))
268 /* Duplicate name; make sure that they don't conflict: */
270 if ((ref1->flag & REF_DIR) || (ref2->flag & REF_DIR))
271 /* This is impossible by construction */
272 die("Reference directory conflict: %s", ref1->name);
274 if (oidcmp(&ref1->u.value.oid, &ref2->u.value.oid))
275 die("Duplicated ref, and SHA1s don't match: %s", ref1->name);
277 warning("Duplicated ref: %s", ref1->name);
282 * Sort the entries in dir non-recursively (if they are not already
283 * sorted) and remove any duplicate entries.
285 static void sort_ref_dir(struct ref_dir *dir)
288 struct ref_entry *last = NULL;
291 * This check also prevents passing a zero-length array to qsort(),
292 * which is a problem on some platforms.
294 if (dir->sorted == dir->nr)
297 QSORT(dir->entries, dir->nr, ref_entry_cmp);
299 /* Remove any duplicates: */
300 for (i = 0, j = 0; j < dir->nr; j++) {
301 struct ref_entry *entry = dir->entries[j];
302 if (last && is_dup_ref(last, entry))
303 free_ref_entry(entry);
305 last = dir->entries[i++] = entry;
307 dir->sorted = dir->nr = i;
310 int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
311 each_ref_entry_fn fn, void *cb_data)
314 assert(dir->sorted == dir->nr);
315 for (i = offset; i < dir->nr; i++) {
316 struct ref_entry *entry = dir->entries[i];
318 if (entry->flag & REF_DIR) {
319 struct ref_dir *subdir = get_ref_dir(entry);
320 sort_ref_dir(subdir);
321 retval = do_for_each_entry_in_dir(subdir, 0, fn, cb_data);
323 retval = fn(entry, cb_data);
331 void prime_ref_dir(struct ref_dir *dir)
334 * The hard work of loading loose refs is done by get_ref_dir(), so we
335 * just need to recurse through all of the sub-directories. We do not
336 * even need to care about sorting, as traversal order does not matter
340 for (i = 0; i < dir->nr; i++) {
341 struct ref_entry *entry = dir->entries[i];
342 if (entry->flag & REF_DIR)
343 prime_ref_dir(get_ref_dir(entry));
348 * A level in the reference hierarchy that is currently being iterated
351 struct cache_ref_iterator_level {
353 * The ref_dir being iterated over at this level. The ref_dir
354 * is sorted before being stored here.
359 * The index of the current entry within dir (which might
360 * itself be a directory). If index == -1, then the iteration
361 * hasn't yet begun. If index == dir->nr, then the iteration
362 * through this level is over.
368 * Represent an iteration through a ref_dir in the memory cache. The
369 * iteration recurses through subdirectories.
371 struct cache_ref_iterator {
372 struct ref_iterator base;
375 * The number of levels currently on the stack. This is always
376 * at least 1, because when it becomes zero the iteration is
377 * ended and this struct is freed.
381 /* The number of levels that have been allocated on the stack */
385 * A stack of levels. levels[0] is the uppermost level that is
386 * being iterated over in this iteration. (This is not
387 * necessary the top level in the references hierarchy. If we
388 * are iterating through a subtree, then levels[0] will hold
389 * the ref_dir for that subtree, and subsequent levels will go
392 struct cache_ref_iterator_level *levels;
395 static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)
397 struct cache_ref_iterator *iter =
398 (struct cache_ref_iterator *)ref_iterator;
401 struct cache_ref_iterator_level *level =
402 &iter->levels[iter->levels_nr - 1];
403 struct ref_dir *dir = level->dir;
404 struct ref_entry *entry;
406 if (level->index == -1)
409 if (++level->index == level->dir->nr) {
410 /* This level is exhausted; pop up a level */
411 if (--iter->levels_nr == 0)
412 return ref_iterator_abort(ref_iterator);
417 entry = dir->entries[level->index];
419 if (entry->flag & REF_DIR) {
420 /* push down a level */
421 ALLOC_GROW(iter->levels, iter->levels_nr + 1,
424 level = &iter->levels[iter->levels_nr++];
425 level->dir = get_ref_dir(entry);
428 iter->base.refname = entry->name;
429 iter->base.oid = &entry->u.value.oid;
430 iter->base.flags = entry->flag;
436 enum peel_status peel_entry(struct ref_entry *entry, int repeel)
438 enum peel_status status;
440 if (entry->flag & REF_KNOWS_PEELED) {
442 entry->flag &= ~REF_KNOWS_PEELED;
443 oidclr(&entry->u.value.peeled);
445 return is_null_oid(&entry->u.value.peeled) ?
446 PEEL_NON_TAG : PEEL_PEELED;
449 if (entry->flag & REF_ISBROKEN)
451 if (entry->flag & REF_ISSYMREF)
452 return PEEL_IS_SYMREF;
454 status = peel_object(entry->u.value.oid.hash, entry->u.value.peeled.hash);
455 if (status == PEEL_PEELED || status == PEEL_NON_TAG)
456 entry->flag |= REF_KNOWS_PEELED;
460 static int cache_ref_iterator_peel(struct ref_iterator *ref_iterator,
461 struct object_id *peeled)
463 struct cache_ref_iterator *iter =
464 (struct cache_ref_iterator *)ref_iterator;
465 struct cache_ref_iterator_level *level;
466 struct ref_entry *entry;
468 level = &iter->levels[iter->levels_nr - 1];
470 if (level->index == -1)
471 die("BUG: peel called before advance for cache iterator");
473 entry = level->dir->entries[level->index];
475 if (peel_entry(entry, 0))
477 oidcpy(peeled, &entry->u.value.peeled);
481 static int cache_ref_iterator_abort(struct ref_iterator *ref_iterator)
483 struct cache_ref_iterator *iter =
484 (struct cache_ref_iterator *)ref_iterator;
487 base_ref_iterator_free(ref_iterator);
491 static struct ref_iterator_vtable cache_ref_iterator_vtable = {
492 cache_ref_iterator_advance,
493 cache_ref_iterator_peel,
494 cache_ref_iterator_abort
497 struct ref_iterator *cache_ref_iterator_begin(struct ref_dir *dir)
499 struct cache_ref_iterator *iter;
500 struct ref_iterator *ref_iterator;
501 struct cache_ref_iterator_level *level;
503 iter = xcalloc(1, sizeof(*iter));
504 ref_iterator = &iter->base;
505 base_ref_iterator_init(ref_iterator, &cache_ref_iterator_vtable);
506 ALLOC_GROW(iter->levels, 10, iter->levels_alloc);
509 level = &iter->levels[0];