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