create_ref_entry(): remove `check_name` option
[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 /*
316 * Load all of the refs from `dir` (recursively) into our in-memory
317 * cache.
318 */
319 static void prime_ref_dir(struct ref_dir *dir)
320 {
321 /*
322 * The hard work of loading loose refs is done by get_ref_dir(), so we
323 * just need to recurse through all of the sub-directories. We do not
324 * even need to care about sorting, as traversal order does not matter
325 * to us.
326 */
327 int i;
328 for (i = 0; i < dir->nr; i++) {
329 struct ref_entry *entry = dir->entries[i];
330 if (entry->flag & REF_DIR)
331 prime_ref_dir(get_ref_dir(entry));
332 }
333 }
334
335 /*
336 * A level in the reference hierarchy that is currently being iterated
337 * through.
338 */
339 struct cache_ref_iterator_level {
340 /*
341 * The ref_dir being iterated over at this level. The ref_dir
342 * is sorted before being stored here.
343 */
344 struct ref_dir *dir;
345
346 /*
347 * The index of the current entry within dir (which might
348 * itself be a directory). If index == -1, then the iteration
349 * hasn't yet begun. If index == dir->nr, then the iteration
350 * through this level is over.
351 */
352 int index;
353 };
354
355 /*
356 * Represent an iteration through a ref_dir in the memory cache. The
357 * iteration recurses through subdirectories.
358 */
359 struct cache_ref_iterator {
360 struct ref_iterator base;
361
362 /*
363 * The number of levels currently on the stack. This is always
364 * at least 1, because when it becomes zero the iteration is
365 * ended and this struct is freed.
366 */
367 size_t levels_nr;
368
369 /* The number of levels that have been allocated on the stack */
370 size_t levels_alloc;
371
372 /*
373 * A stack of levels. levels[0] is the uppermost level that is
374 * being iterated over in this iteration. (This is not
375 * necessary the top level in the references hierarchy. If we
376 * are iterating through a subtree, then levels[0] will hold
377 * the ref_dir for that subtree, and subsequent levels will go
378 * on from there.)
379 */
380 struct cache_ref_iterator_level *levels;
381 };
382
383 static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)
384 {
385 struct cache_ref_iterator *iter =
386 (struct cache_ref_iterator *)ref_iterator;
387
388 while (1) {
389 struct cache_ref_iterator_level *level =
390 &iter->levels[iter->levels_nr - 1];
391 struct ref_dir *dir = level->dir;
392 struct ref_entry *entry;
393
394 if (level->index == -1)
395 sort_ref_dir(dir);
396
397 if (++level->index == level->dir->nr) {
398 /* This level is exhausted; pop up a level */
399 if (--iter->levels_nr == 0)
400 return ref_iterator_abort(ref_iterator);
401
402 continue;
403 }
404
405 entry = dir->entries[level->index];
406
407 if (entry->flag & REF_DIR) {
408 /* push down a level */
409 ALLOC_GROW(iter->levels, iter->levels_nr + 1,
410 iter->levels_alloc);
411
412 level = &iter->levels[iter->levels_nr++];
413 level->dir = get_ref_dir(entry);
414 level->index = -1;
415 } else {
416 iter->base.refname = entry->name;
417 iter->base.oid = &entry->u.value.oid;
418 iter->base.flags = entry->flag;
419 return ITER_OK;
420 }
421 }
422 }
423
424 enum peel_status peel_entry(struct ref_entry *entry, int repeel)
425 {
426 enum peel_status status;
427
428 if (entry->flag & REF_KNOWS_PEELED) {
429 if (repeel) {
430 entry->flag &= ~REF_KNOWS_PEELED;
431 oidclr(&entry->u.value.peeled);
432 } else {
433 return is_null_oid(&entry->u.value.peeled) ?
434 PEEL_NON_TAG : PEEL_PEELED;
435 }
436 }
437 if (entry->flag & REF_ISBROKEN)
438 return PEEL_BROKEN;
439 if (entry->flag & REF_ISSYMREF)
440 return PEEL_IS_SYMREF;
441
442 status = peel_object(entry->u.value.oid.hash, entry->u.value.peeled.hash);
443 if (status == PEEL_PEELED || status == PEEL_NON_TAG)
444 entry->flag |= REF_KNOWS_PEELED;
445 return status;
446 }
447
448 static int cache_ref_iterator_peel(struct ref_iterator *ref_iterator,
449 struct object_id *peeled)
450 {
451 struct cache_ref_iterator *iter =
452 (struct cache_ref_iterator *)ref_iterator;
453 struct cache_ref_iterator_level *level;
454 struct ref_entry *entry;
455
456 level = &iter->levels[iter->levels_nr - 1];
457
458 if (level->index == -1)
459 die("BUG: peel called before advance for cache iterator");
460
461 entry = level->dir->entries[level->index];
462
463 if (peel_entry(entry, 0))
464 return -1;
465 oidcpy(peeled, &entry->u.value.peeled);
466 return 0;
467 }
468
469 static int cache_ref_iterator_abort(struct ref_iterator *ref_iterator)
470 {
471 struct cache_ref_iterator *iter =
472 (struct cache_ref_iterator *)ref_iterator;
473
474 free(iter->levels);
475 base_ref_iterator_free(ref_iterator);
476 return ITER_DONE;
477 }
478
479 static struct ref_iterator_vtable cache_ref_iterator_vtable = {
480 cache_ref_iterator_advance,
481 cache_ref_iterator_peel,
482 cache_ref_iterator_abort
483 };
484
485 struct ref_iterator *cache_ref_iterator_begin(struct ref_cache *cache,
486 const char *prefix,
487 int prime_dir)
488 {
489 struct ref_dir *dir;
490 struct cache_ref_iterator *iter;
491 struct ref_iterator *ref_iterator;
492 struct cache_ref_iterator_level *level;
493
494 dir = get_ref_dir(cache->root);
495 if (prefix && *prefix)
496 dir = find_containing_dir(dir, prefix, 0);
497 if (!dir)
498 /* There's nothing to iterate over. */
499 return empty_ref_iterator_begin();
500
501 if (prime_dir)
502 prime_ref_dir(dir);
503
504 iter = xcalloc(1, sizeof(*iter));
505 ref_iterator = &iter->base;
506 base_ref_iterator_init(ref_iterator, &cache_ref_iterator_vtable);
507 ALLOC_GROW(iter->levels, 10, iter->levels_alloc);
508
509 iter->levels_nr = 1;
510 level = &iter->levels[0];
511 level->index = -1;
512 level->dir = dir;
513
514 if (prefix && *prefix)
515 ref_iterator = prefix_ref_iterator_begin(ref_iterator,
516 prefix, 0);
517
518 return ref_iterator;
519 }