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 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 struct object_id *oid, int flag)
37 struct ref_entry *ref;
39 FLEX_ALLOC_STR(ref, name, refname);
40 oidcpy(&ref->u.value.oid, oid);
45 struct ref_cache *create_ref_cache(struct ref_store *refs,
46 fill_ref_dir_fn *fill_ref_dir)
48 struct ref_cache *ret = xcalloc(1, sizeof(*ret));
50 ret->ref_store = refs;
51 ret->fill_ref_dir = fill_ref_dir;
52 ret->root = create_dir_entry(ret, "", 0, 1);
56 static void clear_ref_dir(struct ref_dir *dir);
58 static void free_ref_entry(struct ref_entry *entry)
60 if (entry->flag & REF_DIR) {
62 * Do not use get_ref_dir() here, as that might
63 * trigger the reading of loose refs.
65 clear_ref_dir(&entry->u.subdir);
70 void free_ref_cache(struct ref_cache *cache)
72 free_ref_entry(cache->root);
77 * Clear and free all entries in dir, recursively.
79 static void clear_ref_dir(struct ref_dir *dir)
82 for (i = 0; i < dir->nr; i++)
83 free_ref_entry(dir->entries[i]);
84 FREE_AND_NULL(dir->entries);
85 dir->sorted = dir->nr = dir->alloc = 0;
88 struct ref_entry *create_dir_entry(struct ref_cache *cache,
89 const char *dirname, size_t len,
92 struct ref_entry *direntry;
94 FLEX_ALLOC_MEM(direntry, name, dirname, len);
95 direntry->u.subdir.cache = cache;
96 direntry->flag = REF_DIR | (incomplete ? REF_INCOMPLETE : 0);
100 static int ref_entry_cmp(const void *a, const void *b)
102 struct ref_entry *one = *(struct ref_entry **)a;
103 struct ref_entry *two = *(struct ref_entry **)b;
104 return strcmp(one->name, two->name);
107 static void sort_ref_dir(struct ref_dir *dir);
109 struct string_slice {
114 static int ref_entry_cmp_sslice(const void *key_, const void *ent_)
116 const struct string_slice *key = key_;
117 const struct ref_entry *ent = *(const struct ref_entry * const *)ent_;
118 int cmp = strncmp(key->str, ent->name, key->len);
121 return '\0' - (unsigned char)ent->name[key->len];
124 int search_ref_dir(struct ref_dir *dir, const char *refname, size_t len)
126 struct ref_entry **r;
127 struct string_slice key;
129 if (refname == NULL || !dir->nr)
135 r = bsearch(&key, dir->entries, dir->nr, sizeof(*dir->entries),
136 ref_entry_cmp_sslice);
141 return r - dir->entries;
145 * Search for a directory entry directly within dir (without
146 * recursing). Sort dir if necessary. subdirname must be a directory
147 * name (i.e., end in '/'). If mkdir is set, then create the
148 * directory if it is missing; otherwise, return NULL if the desired
149 * directory cannot be found. dir must already be complete.
151 static struct ref_dir *search_for_subdir(struct ref_dir *dir,
152 const char *subdirname, size_t len,
155 int entry_index = search_ref_dir(dir, subdirname, len);
156 struct ref_entry *entry;
157 if (entry_index == -1) {
161 * Since dir is complete, the absence of a subdir
162 * means that the subdir really doesn't exist;
163 * therefore, create an empty record for it but mark
164 * the record complete.
166 entry = create_dir_entry(dir->cache, subdirname, len, 0);
167 add_entry_to_dir(dir, entry);
169 entry = dir->entries[entry_index];
171 return get_ref_dir(entry);
175 * If refname is a reference name, find the ref_dir within the dir
176 * tree that should hold refname. If refname is a directory name
177 * (i.e., it ends in '/'), then return that ref_dir itself. dir must
178 * represent the top-level directory and must already be complete.
179 * Sort ref_dirs and recurse into subdirectories as necessary. If
180 * mkdir is set, then create any missing directories; otherwise,
181 * return NULL if the desired directory cannot be found.
183 static struct ref_dir *find_containing_dir(struct ref_dir *dir,
184 const char *refname, int mkdir)
187 for (slash = strchr(refname, '/'); slash; slash = strchr(slash + 1, '/')) {
188 size_t dirnamelen = slash - refname + 1;
189 struct ref_dir *subdir;
190 subdir = search_for_subdir(dir, refname, dirnamelen, mkdir);
201 struct ref_entry *find_ref_entry(struct ref_dir *dir, const char *refname)
204 struct ref_entry *entry;
205 dir = find_containing_dir(dir, refname, 0);
208 entry_index = search_ref_dir(dir, refname, strlen(refname));
209 if (entry_index == -1)
211 entry = dir->entries[entry_index];
212 return (entry->flag & REF_DIR) ? NULL : entry;
215 int remove_entry_from_dir(struct ref_dir *dir, const char *refname)
217 int refname_len = strlen(refname);
219 struct ref_entry *entry;
220 int is_dir = refname[refname_len - 1] == '/';
223 * refname represents a reference directory. Remove
224 * the trailing slash; otherwise we will get the
225 * directory *representing* refname rather than the
226 * one *containing* it.
228 char *dirname = xmemdupz(refname, refname_len - 1);
229 dir = find_containing_dir(dir, dirname, 0);
232 dir = find_containing_dir(dir, refname, 0);
236 entry_index = search_ref_dir(dir, refname, refname_len);
237 if (entry_index == -1)
239 entry = dir->entries[entry_index];
241 MOVE_ARRAY(&dir->entries[entry_index],
242 &dir->entries[entry_index + 1], dir->nr - entry_index - 1);
244 if (dir->sorted > entry_index)
246 free_ref_entry(entry);
250 int add_ref_entry(struct ref_dir *dir, struct ref_entry *ref)
252 dir = find_containing_dir(dir, ref->name, 1);
255 add_entry_to_dir(dir, ref);
260 * Emit a warning and return true iff ref1 and ref2 have the same name
261 * and the same oid. Die if they have the same name but different
264 static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2)
266 if (strcmp(ref1->name, ref2->name))
269 /* Duplicate name; make sure that they don't conflict: */
271 if ((ref1->flag & REF_DIR) || (ref2->flag & REF_DIR))
272 /* This is impossible by construction */
273 die("Reference directory conflict: %s", ref1->name);
275 if (!oideq(&ref1->u.value.oid, &ref2->u.value.oid))
276 die("Duplicated ref, and SHA1s don't match: %s", ref1->name);
278 warning("Duplicated ref: %s", ref1->name);
283 * Sort the entries in dir non-recursively (if they are not already
284 * sorted) and remove any duplicate entries.
286 static void sort_ref_dir(struct ref_dir *dir)
289 struct ref_entry *last = NULL;
292 * This check also prevents passing a zero-length array to qsort(),
293 * which is a problem on some platforms.
295 if (dir->sorted == dir->nr)
298 QSORT(dir->entries, dir->nr, ref_entry_cmp);
300 /* Remove any duplicates: */
301 for (i = 0, j = 0; j < dir->nr; j++) {
302 struct ref_entry *entry = dir->entries[j];
303 if (last && is_dup_ref(last, entry))
304 free_ref_entry(entry);
306 last = dir->entries[i++] = entry;
308 dir->sorted = dir->nr = i;
312 /* All refs within the directory would match prefix: */
315 /* Some, but not all, refs within the directory might match prefix: */
318 /* No refs within the directory could possibly match prefix: */
323 * Return a `prefix_state` constant describing the relationship
324 * between the directory with the specified `dirname` and `prefix`.
326 static enum prefix_state overlaps_prefix(const char *dirname,
329 while (*prefix && *dirname == *prefix) {
334 return PREFIX_CONTAINS_DIR;
336 return PREFIX_WITHIN_DIR;
338 return PREFIX_EXCLUDES_DIR;
342 * Load all of the refs from `dir` (recursively) that could possibly
343 * contain references matching `prefix` into our in-memory cache. If
344 * `prefix` is NULL, prime unconditionally.
346 static void prime_ref_dir(struct ref_dir *dir, const char *prefix)
349 * The hard work of loading loose refs is done by get_ref_dir(), so we
350 * just need to recurse through all of the sub-directories. We do not
351 * even need to care about sorting, as traversal order does not matter
355 for (i = 0; i < dir->nr; i++) {
356 struct ref_entry *entry = dir->entries[i];
357 if (!(entry->flag & REF_DIR)) {
358 /* Not a directory; no need to recurse. */
359 } else if (!prefix) {
360 /* Recurse in any case: */
361 prime_ref_dir(get_ref_dir(entry), NULL);
363 switch (overlaps_prefix(entry->name, prefix)) {
364 case PREFIX_CONTAINS_DIR:
366 * Recurse, and from here down we
367 * don't have to check the prefix
370 prime_ref_dir(get_ref_dir(entry), NULL);
372 case PREFIX_WITHIN_DIR:
373 prime_ref_dir(get_ref_dir(entry), prefix);
375 case PREFIX_EXCLUDES_DIR:
376 /* No need to prime this directory. */
384 * A level in the reference hierarchy that is currently being iterated
387 struct cache_ref_iterator_level {
389 * The ref_dir being iterated over at this level. The ref_dir
390 * is sorted before being stored here.
394 enum prefix_state prefix_state;
397 * The index of the current entry within dir (which might
398 * itself be a directory). If index == -1, then the iteration
399 * hasn't yet begun. If index == dir->nr, then the iteration
400 * through this level is over.
406 * Represent an iteration through a ref_dir in the memory cache. The
407 * iteration recurses through subdirectories.
409 struct cache_ref_iterator {
410 struct ref_iterator base;
413 * The number of levels currently on the stack. This is always
414 * at least 1, because when it becomes zero the iteration is
415 * ended and this struct is freed.
419 /* The number of levels that have been allocated on the stack */
423 * Only include references with this prefix in the iteration.
424 * The prefix is matched textually, without regard for path
425 * component boundaries.
430 * A stack of levels. levels[0] is the uppermost level that is
431 * being iterated over in this iteration. (This is not
432 * necessary the top level in the references hierarchy. If we
433 * are iterating through a subtree, then levels[0] will hold
434 * the ref_dir for that subtree, and subsequent levels will go
437 struct cache_ref_iterator_level *levels;
440 static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)
442 struct cache_ref_iterator *iter =
443 (struct cache_ref_iterator *)ref_iterator;
446 struct cache_ref_iterator_level *level =
447 &iter->levels[iter->levels_nr - 1];
448 struct ref_dir *dir = level->dir;
449 struct ref_entry *entry;
450 enum prefix_state entry_prefix_state;
452 if (level->index == -1)
455 if (++level->index == level->dir->nr) {
456 /* This level is exhausted; pop up a level */
457 if (--iter->levels_nr == 0)
458 return ref_iterator_abort(ref_iterator);
463 entry = dir->entries[level->index];
465 if (level->prefix_state == PREFIX_WITHIN_DIR) {
466 entry_prefix_state = overlaps_prefix(entry->name, iter->prefix);
467 if (entry_prefix_state == PREFIX_EXCLUDES_DIR)
470 entry_prefix_state = level->prefix_state;
473 if (entry->flag & REF_DIR) {
474 /* push down a level */
475 ALLOC_GROW(iter->levels, iter->levels_nr + 1,
478 level = &iter->levels[iter->levels_nr++];
479 level->dir = get_ref_dir(entry);
480 level->prefix_state = entry_prefix_state;
483 iter->base.refname = entry->name;
484 iter->base.oid = &entry->u.value.oid;
485 iter->base.flags = entry->flag;
491 static int cache_ref_iterator_peel(struct ref_iterator *ref_iterator,
492 struct object_id *peeled)
494 return peel_object(ref_iterator->oid, peeled);
497 static int cache_ref_iterator_abort(struct ref_iterator *ref_iterator)
499 struct cache_ref_iterator *iter =
500 (struct cache_ref_iterator *)ref_iterator;
502 free((char *)iter->prefix);
504 base_ref_iterator_free(ref_iterator);
508 static struct ref_iterator_vtable cache_ref_iterator_vtable = {
509 cache_ref_iterator_advance,
510 cache_ref_iterator_peel,
511 cache_ref_iterator_abort
514 struct ref_iterator *cache_ref_iterator_begin(struct ref_cache *cache,
519 struct cache_ref_iterator *iter;
520 struct ref_iterator *ref_iterator;
521 struct cache_ref_iterator_level *level;
523 dir = get_ref_dir(cache->root);
524 if (prefix && *prefix)
525 dir = find_containing_dir(dir, prefix, 0);
527 /* There's nothing to iterate over. */
528 return empty_ref_iterator_begin();
531 prime_ref_dir(dir, prefix);
533 CALLOC_ARRAY(iter, 1);
534 ref_iterator = &iter->base;
535 base_ref_iterator_init(ref_iterator, &cache_ref_iterator_vtable, 1);
536 ALLOC_GROW(iter->levels, 10, iter->levels_alloc);
539 level = &iter->levels[0];
543 if (prefix && *prefix) {
544 iter->prefix = xstrdup(prefix);
545 level->prefix_state = PREFIX_WITHIN_DIR;
547 level->prefix_state = PREFIX_CONTAINS_DIR;