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