ref-cache: use a callback function to fill the cache
[git/git.git] / refs / ref-cache.c
1 #include "../cache.h"
2 #include "../refs.h"
3 #include "refs-internal.h"
4 #include "ref-cache.h"
5 #include "../iterator.h"
6
7 void add_entry_to_dir(struct ref_dir *dir, struct ref_entry *entry)
8 {
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 */
12 if (dir->nr == 1 ||
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;
17 }
18
19 struct ref_dir *get_ref_dir(struct ref_entry *entry)
20 {
21 struct ref_dir *dir;
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");
27
28 dir->cache->fill_ref_dir(dir->cache->ref_store, dir, entry->name);
29
30 /*
31 * Manually add refs/bisect, which, being
32 * per-worktree, might not appear in the directory
33 * listing for refs/ in the main repo.
34 */
35 if (!strcmp(entry->name, "refs/")) {
36 int pos = search_ref_dir(dir, "refs/bisect/", 12);
37 if (pos < 0) {
38 struct ref_entry *child_entry;
39 child_entry = create_dir_entry(dir->cache,
40 "refs/bisect/",
41 12, 1);
42 add_entry_to_dir(dir, child_entry);
43 }
44 }
45 entry->flag &= ~REF_INCOMPLETE;
46 }
47 return dir;
48 }
49
50 struct ref_entry *create_ref_entry(const char *refname,
51 const unsigned char *sha1, int flag,
52 int check_name)
53 {
54 struct ref_entry *ref;
55
56 if (check_name &&
57 check_refname_format(refname, REFNAME_ALLOW_ONELEVEL))
58 die("Reference has invalid format: '%s'", refname);
59 FLEX_ALLOC_STR(ref, name, refname);
60 hashcpy(ref->u.value.oid.hash, sha1);
61 oidclr(&ref->u.value.peeled);
62 ref->flag = flag;
63 return ref;
64 }
65
66 struct ref_cache *create_ref_cache(struct ref_store *refs,
67 fill_ref_dir_fn *fill_ref_dir)
68 {
69 struct ref_cache *ret = xcalloc(1, sizeof(*ret));
70
71 ret->ref_store = refs;
72 ret->fill_ref_dir = fill_ref_dir;
73 ret->root = create_dir_entry(ret, "", 0, 1);
74 return ret;
75 }
76
77 static void clear_ref_dir(struct ref_dir *dir);
78
79 static void free_ref_entry(struct ref_entry *entry)
80 {
81 if (entry->flag & REF_DIR) {
82 /*
83 * Do not use get_ref_dir() here, as that might
84 * trigger the reading of loose refs.
85 */
86 clear_ref_dir(&entry->u.subdir);
87 }
88 free(entry);
89 }
90
91 void free_ref_cache(struct ref_cache *cache)
92 {
93 free_ref_entry(cache->root);
94 free(cache);
95 }
96
97 /*
98 * Clear and free all entries in dir, recursively.
99 */
100 static void clear_ref_dir(struct ref_dir *dir)
101 {
102 int i;
103 for (i = 0; i < dir->nr; i++)
104 free_ref_entry(dir->entries[i]);
105 free(dir->entries);
106 dir->sorted = dir->nr = dir->alloc = 0;
107 dir->entries = NULL;
108 }
109
110 struct ref_entry *create_dir_entry(struct ref_cache *cache,
111 const char *dirname, size_t len,
112 int incomplete)
113 {
114 struct ref_entry *direntry;
115
116 FLEX_ALLOC_MEM(direntry, name, dirname, len);
117 direntry->u.subdir.cache = cache;
118 direntry->flag = REF_DIR | (incomplete ? REF_INCOMPLETE : 0);
119 return direntry;
120 }
121
122 static int ref_entry_cmp(const void *a, const void *b)
123 {
124 struct ref_entry *one = *(struct ref_entry **)a;
125 struct ref_entry *two = *(struct ref_entry **)b;
126 return strcmp(one->name, two->name);
127 }
128
129 static void sort_ref_dir(struct ref_dir *dir);
130
131 struct string_slice {
132 size_t len;
133 const char *str;
134 };
135
136 static int ref_entry_cmp_sslice(const void *key_, const void *ent_)
137 {
138 const struct string_slice *key = key_;
139 const struct ref_entry *ent = *(const struct ref_entry * const *)ent_;
140 int cmp = strncmp(key->str, ent->name, key->len);
141 if (cmp)
142 return cmp;
143 return '\0' - (unsigned char)ent->name[key->len];
144 }
145
146 int search_ref_dir(struct ref_dir *dir, const char *refname, size_t len)
147 {
148 struct ref_entry **r;
149 struct string_slice key;
150
151 if (refname == NULL || !dir->nr)
152 return -1;
153
154 sort_ref_dir(dir);
155 key.len = len;
156 key.str = refname;
157 r = bsearch(&key, dir->entries, dir->nr, sizeof(*dir->entries),
158 ref_entry_cmp_sslice);
159
160 if (r == NULL)
161 return -1;
162
163 return r - dir->entries;
164 }
165
166 /*
167 * Search for a directory entry directly within dir (without
168 * recursing). Sort dir if necessary. subdirname must be a directory
169 * name (i.e., end in '/'). If mkdir is set, then create the
170 * directory if it is missing; otherwise, return NULL if the desired
171 * directory cannot be found. dir must already be complete.
172 */
173 static struct ref_dir *search_for_subdir(struct ref_dir *dir,
174 const char *subdirname, size_t len,
175 int mkdir)
176 {
177 int entry_index = search_ref_dir(dir, subdirname, len);
178 struct ref_entry *entry;
179 if (entry_index == -1) {
180 if (!mkdir)
181 return NULL;
182 /*
183 * Since dir is complete, the absence of a subdir
184 * means that the subdir really doesn't exist;
185 * therefore, create an empty record for it but mark
186 * the record complete.
187 */
188 entry = create_dir_entry(dir->cache, subdirname, len, 0);
189 add_entry_to_dir(dir, entry);
190 } else {
191 entry = dir->entries[entry_index];
192 }
193 return get_ref_dir(entry);
194 }
195
196 struct ref_dir *find_containing_dir(struct ref_dir *dir,
197 const char *refname, int mkdir)
198 {
199 const char *slash;
200 for (slash = strchr(refname, '/'); slash; slash = strchr(slash + 1, '/')) {
201 size_t dirnamelen = slash - refname + 1;
202 struct ref_dir *subdir;
203 subdir = search_for_subdir(dir, refname, dirnamelen, mkdir);
204 if (!subdir) {
205 dir = NULL;
206 break;
207 }
208 dir = subdir;
209 }
210
211 return dir;
212 }
213
214 struct ref_entry *find_ref_entry(struct ref_dir *dir, const char *refname)
215 {
216 int entry_index;
217 struct ref_entry *entry;
218 dir = find_containing_dir(dir, refname, 0);
219 if (!dir)
220 return NULL;
221 entry_index = search_ref_dir(dir, refname, strlen(refname));
222 if (entry_index == -1)
223 return NULL;
224 entry = dir->entries[entry_index];
225 return (entry->flag & REF_DIR) ? NULL : entry;
226 }
227
228 int remove_entry_from_dir(struct ref_dir *dir, const char *refname)
229 {
230 int refname_len = strlen(refname);
231 int entry_index;
232 struct ref_entry *entry;
233 int is_dir = refname[refname_len - 1] == '/';
234 if (is_dir) {
235 /*
236 * refname represents a reference directory. Remove
237 * the trailing slash; otherwise we will get the
238 * directory *representing* refname rather than the
239 * one *containing* it.
240 */
241 char *dirname = xmemdupz(refname, refname_len - 1);
242 dir = find_containing_dir(dir, dirname, 0);
243 free(dirname);
244 } else {
245 dir = find_containing_dir(dir, refname, 0);
246 }
247 if (!dir)
248 return -1;
249 entry_index = search_ref_dir(dir, refname, refname_len);
250 if (entry_index == -1)
251 return -1;
252 entry = dir->entries[entry_index];
253
254 memmove(&dir->entries[entry_index],
255 &dir->entries[entry_index + 1],
256 (dir->nr - entry_index - 1) * sizeof(*dir->entries)
257 );
258 dir->nr--;
259 if (dir->sorted > entry_index)
260 dir->sorted--;
261 free_ref_entry(entry);
262 return dir->nr;
263 }
264
265 int add_ref_entry(struct ref_dir *dir, struct ref_entry *ref)
266 {
267 dir = find_containing_dir(dir, ref->name, 1);
268 if (!dir)
269 return -1;
270 add_entry_to_dir(dir, ref);
271 return 0;
272 }
273
274 /*
275 * Emit a warning and return true iff ref1 and ref2 have the same name
276 * and the same sha1. Die if they have the same name but different
277 * sha1s.
278 */
279 static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2)
280 {
281 if (strcmp(ref1->name, ref2->name))
282 return 0;
283
284 /* Duplicate name; make sure that they don't conflict: */
285
286 if ((ref1->flag & REF_DIR) || (ref2->flag & REF_DIR))
287 /* This is impossible by construction */
288 die("Reference directory conflict: %s", ref1->name);
289
290 if (oidcmp(&ref1->u.value.oid, &ref2->u.value.oid))
291 die("Duplicated ref, and SHA1s don't match: %s", ref1->name);
292
293 warning("Duplicated ref: %s", ref1->name);
294 return 1;
295 }
296
297 /*
298 * Sort the entries in dir non-recursively (if they are not already
299 * sorted) and remove any duplicate entries.
300 */
301 static void sort_ref_dir(struct ref_dir *dir)
302 {
303 int i, j;
304 struct ref_entry *last = NULL;
305
306 /*
307 * This check also prevents passing a zero-length array to qsort(),
308 * which is a problem on some platforms.
309 */
310 if (dir->sorted == dir->nr)
311 return;
312
313 QSORT(dir->entries, dir->nr, ref_entry_cmp);
314
315 /* Remove any duplicates: */
316 for (i = 0, j = 0; j < dir->nr; j++) {
317 struct ref_entry *entry = dir->entries[j];
318 if (last && is_dup_ref(last, entry))
319 free_ref_entry(entry);
320 else
321 last = dir->entries[i++] = entry;
322 }
323 dir->sorted = dir->nr = i;
324 }
325
326 int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
327 each_ref_entry_fn fn, void *cb_data)
328 {
329 int i;
330 assert(dir->sorted == dir->nr);
331 for (i = offset; i < dir->nr; i++) {
332 struct ref_entry *entry = dir->entries[i];
333 int retval;
334 if (entry->flag & REF_DIR) {
335 struct ref_dir *subdir = get_ref_dir(entry);
336 sort_ref_dir(subdir);
337 retval = do_for_each_entry_in_dir(subdir, 0, fn, cb_data);
338 } else {
339 retval = fn(entry, cb_data);
340 }
341 if (retval)
342 return retval;
343 }
344 return 0;
345 }
346
347 void prime_ref_dir(struct ref_dir *dir)
348 {
349 /*
350 * The hard work of loading loose refs is done by get_ref_dir(), so we
351 * just need to recurse through all of the sub-directories. We do not
352 * even need to care about sorting, as traversal order does not matter
353 * to us.
354 */
355 int i;
356 for (i = 0; i < dir->nr; i++) {
357 struct ref_entry *entry = dir->entries[i];
358 if (entry->flag & REF_DIR)
359 prime_ref_dir(get_ref_dir(entry));
360 }
361 }
362
363 /*
364 * A level in the reference hierarchy that is currently being iterated
365 * through.
366 */
367 struct cache_ref_iterator_level {
368 /*
369 * The ref_dir being iterated over at this level. The ref_dir
370 * is sorted before being stored here.
371 */
372 struct ref_dir *dir;
373
374 /*
375 * The index of the current entry within dir (which might
376 * itself be a directory). If index == -1, then the iteration
377 * hasn't yet begun. If index == dir->nr, then the iteration
378 * through this level is over.
379 */
380 int index;
381 };
382
383 /*
384 * Represent an iteration through a ref_dir in the memory cache. The
385 * iteration recurses through subdirectories.
386 */
387 struct cache_ref_iterator {
388 struct ref_iterator base;
389
390 /*
391 * The number of levels currently on the stack. This is always
392 * at least 1, because when it becomes zero the iteration is
393 * ended and this struct is freed.
394 */
395 size_t levels_nr;
396
397 /* The number of levels that have been allocated on the stack */
398 size_t levels_alloc;
399
400 /*
401 * A stack of levels. levels[0] is the uppermost level that is
402 * being iterated over in this iteration. (This is not
403 * necessary the top level in the references hierarchy. If we
404 * are iterating through a subtree, then levels[0] will hold
405 * the ref_dir for that subtree, and subsequent levels will go
406 * on from there.)
407 */
408 struct cache_ref_iterator_level *levels;
409 };
410
411 static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)
412 {
413 struct cache_ref_iterator *iter =
414 (struct cache_ref_iterator *)ref_iterator;
415
416 while (1) {
417 struct cache_ref_iterator_level *level =
418 &iter->levels[iter->levels_nr - 1];
419 struct ref_dir *dir = level->dir;
420 struct ref_entry *entry;
421
422 if (level->index == -1)
423 sort_ref_dir(dir);
424
425 if (++level->index == level->dir->nr) {
426 /* This level is exhausted; pop up a level */
427 if (--iter->levels_nr == 0)
428 return ref_iterator_abort(ref_iterator);
429
430 continue;
431 }
432
433 entry = dir->entries[level->index];
434
435 if (entry->flag & REF_DIR) {
436 /* push down a level */
437 ALLOC_GROW(iter->levels, iter->levels_nr + 1,
438 iter->levels_alloc);
439
440 level = &iter->levels[iter->levels_nr++];
441 level->dir = get_ref_dir(entry);
442 level->index = -1;
443 } else {
444 iter->base.refname = entry->name;
445 iter->base.oid = &entry->u.value.oid;
446 iter->base.flags = entry->flag;
447 return ITER_OK;
448 }
449 }
450 }
451
452 enum peel_status peel_entry(struct ref_entry *entry, int repeel)
453 {
454 enum peel_status status;
455
456 if (entry->flag & REF_KNOWS_PEELED) {
457 if (repeel) {
458 entry->flag &= ~REF_KNOWS_PEELED;
459 oidclr(&entry->u.value.peeled);
460 } else {
461 return is_null_oid(&entry->u.value.peeled) ?
462 PEEL_NON_TAG : PEEL_PEELED;
463 }
464 }
465 if (entry->flag & REF_ISBROKEN)
466 return PEEL_BROKEN;
467 if (entry->flag & REF_ISSYMREF)
468 return PEEL_IS_SYMREF;
469
470 status = peel_object(entry->u.value.oid.hash, entry->u.value.peeled.hash);
471 if (status == PEEL_PEELED || status == PEEL_NON_TAG)
472 entry->flag |= REF_KNOWS_PEELED;
473 return status;
474 }
475
476 static int cache_ref_iterator_peel(struct ref_iterator *ref_iterator,
477 struct object_id *peeled)
478 {
479 struct cache_ref_iterator *iter =
480 (struct cache_ref_iterator *)ref_iterator;
481 struct cache_ref_iterator_level *level;
482 struct ref_entry *entry;
483
484 level = &iter->levels[iter->levels_nr - 1];
485
486 if (level->index == -1)
487 die("BUG: peel called before advance for cache iterator");
488
489 entry = level->dir->entries[level->index];
490
491 if (peel_entry(entry, 0))
492 return -1;
493 oidcpy(peeled, &entry->u.value.peeled);
494 return 0;
495 }
496
497 static int cache_ref_iterator_abort(struct ref_iterator *ref_iterator)
498 {
499 struct cache_ref_iterator *iter =
500 (struct cache_ref_iterator *)ref_iterator;
501
502 free(iter->levels);
503 base_ref_iterator_free(ref_iterator);
504 return ITER_DONE;
505 }
506
507 static struct ref_iterator_vtable cache_ref_iterator_vtable = {
508 cache_ref_iterator_advance,
509 cache_ref_iterator_peel,
510 cache_ref_iterator_abort
511 };
512
513 struct ref_iterator *cache_ref_iterator_begin(struct ref_dir *dir)
514 {
515 struct cache_ref_iterator *iter;
516 struct ref_iterator *ref_iterator;
517 struct cache_ref_iterator_level *level;
518
519 iter = xcalloc(1, sizeof(*iter));
520 ref_iterator = &iter->base;
521 base_ref_iterator_init(ref_iterator, &cache_ref_iterator_vtable);
522 ALLOC_GROW(iter->levels, 10, iter->levels_alloc);
523
524 iter->levels_nr = 1;
525 level = &iter->levels[0];
526 level->index = -1;
527 level->dir = dir;
528
529 return ref_iterator;
530 }