5 #include "cache-tree.h"
6 #include "object-store.h"
12 struct cache_tree
*cache_tree(void)
14 struct cache_tree
*it
= xcalloc(1, sizeof(struct cache_tree
));
19 void cache_tree_free(struct cache_tree
**it_p
)
22 struct cache_tree
*it
= *it_p
;
26 for (i
= 0; i
< it
->subtree_nr
; i
++)
28 cache_tree_free(&it
->down
[i
]->cache_tree
);
36 static int subtree_name_cmp(const char *one
, int onelen
,
37 const char *two
, int twolen
)
43 return memcmp(one
, two
, onelen
);
46 static int subtree_pos(struct cache_tree
*it
, const char *path
, int pathlen
)
48 struct cache_tree_sub
**down
= it
->down
;
53 int mi
= lo
+ (hi
- lo
) / 2;
54 struct cache_tree_sub
*mdl
= down
[mi
];
55 int cmp
= subtree_name_cmp(path
, pathlen
,
56 mdl
->name
, mdl
->namelen
);
67 static struct cache_tree_sub
*find_subtree(struct cache_tree
*it
,
72 struct cache_tree_sub
*down
;
73 int pos
= subtree_pos(it
, path
, pathlen
);
80 ALLOC_GROW(it
->down
, it
->subtree_nr
+ 1, it
->subtree_alloc
);
83 FLEX_ALLOC_MEM(down
, name
, path
, pathlen
);
84 down
->cache_tree
= NULL
;
85 down
->namelen
= pathlen
;
87 if (pos
< it
->subtree_nr
)
88 MOVE_ARRAY(it
->down
+ pos
+ 1, it
->down
+ pos
,
89 it
->subtree_nr
- pos
- 1);
94 struct cache_tree_sub
*cache_tree_sub(struct cache_tree
*it
, const char *path
)
96 int pathlen
= strlen(path
);
97 return find_subtree(it
, path
, pathlen
, 1);
100 static int do_invalidate_path(struct cache_tree
*it
, const char *path
)
103 * ==> invalidate self
104 * ==> find "a", have it invalidate "b/c"
106 * ==> invalidate self
107 * ==> if "a" exists as a subtree, remove it.
111 struct cache_tree_sub
*down
;
114 fprintf(stderr
, "cache-tree invalidate <%s>\n", path
);
119 slash
= strchrnul(path
, '/');
120 namelen
= slash
- path
;
121 it
->entry_count
= -1;
124 pos
= subtree_pos(it
, path
, namelen
);
126 cache_tree_free(&it
->down
[pos
]->cache_tree
);
131 * move 4 and 5 up one place (2 entries)
132 * 2 = 6 - 3 - 1 = subtree_nr - pos - 1
134 MOVE_ARRAY(it
->down
+ pos
, it
->down
+ pos
+ 1,
135 it
->subtree_nr
- pos
- 1);
140 down
= find_subtree(it
, path
, namelen
, 0);
142 do_invalidate_path(down
->cache_tree
, slash
+ 1);
146 void cache_tree_invalidate_path(struct index_state
*istate
, const char *path
)
148 if (do_invalidate_path(istate
->cache_tree
, path
))
149 istate
->cache_changed
|= CACHE_TREE_CHANGED
;
152 static int verify_cache(struct cache_entry
**cache
,
153 int entries
, int flags
)
156 int silent
= flags
& WRITE_TREE_SILENT
;
158 /* Verify that the tree is merged */
160 for (i
= 0; i
< entries
; i
++) {
161 const struct cache_entry
*ce
= cache
[i
];
166 fprintf(stderr
, "...\n");
169 fprintf(stderr
, "%s: unmerged (%s)\n",
170 ce
->name
, oid_to_hex(&ce
->oid
));
176 /* Also verify that the cache does not have path and path/file
177 * at the same time. At this point we know the cache has only
181 for (i
= 0; i
< entries
- 1; i
++) {
182 /* path/file always comes after path because of the way
183 * the cache is sorted. Also path can appear only once,
184 * which means conflicting one would immediately follow.
186 const char *this_name
= cache
[i
]->name
;
187 const char *next_name
= cache
[i
+1]->name
;
188 int this_len
= strlen(this_name
);
189 if (this_len
< strlen(next_name
) &&
190 strncmp(this_name
, next_name
, this_len
) == 0 &&
191 next_name
[this_len
] == '/') {
193 fprintf(stderr
, "...\n");
196 fprintf(stderr
, "You have both %s and %s\n",
197 this_name
, next_name
);
205 static void discard_unused_subtrees(struct cache_tree
*it
)
207 struct cache_tree_sub
**down
= it
->down
;
208 int nr
= it
->subtree_nr
;
210 for (dst
= src
= 0; src
< nr
; src
++) {
211 struct cache_tree_sub
*s
= down
[src
];
215 cache_tree_free(&s
->cache_tree
);
222 int cache_tree_fully_valid(struct cache_tree
*it
)
227 if (it
->entry_count
< 0 || !has_sha1_file(it
->oid
.hash
))
229 for (i
= 0; i
< it
->subtree_nr
; i
++) {
230 if (!cache_tree_fully_valid(it
->down
[i
]->cache_tree
))
236 static int update_one(struct cache_tree
*it
,
237 struct cache_entry
**cache
,
244 struct strbuf buffer
;
245 int missing_ok
= flags
& WRITE_TREE_MISSING_OK
;
246 int dryrun
= flags
& WRITE_TREE_DRY_RUN
;
247 int repair
= flags
& WRITE_TREE_REPAIR
;
248 int to_invalidate
= 0;
251 assert(!(dryrun
&& repair
));
255 if (0 <= it
->entry_count
&& has_sha1_file(it
->oid
.hash
))
256 return it
->entry_count
;
259 * We first scan for subtrees and update them; we start by
260 * marking existing subtrees -- the ones that are unmarked
261 * should not be in the result.
263 for (i
= 0; i
< it
->subtree_nr
; i
++)
264 it
->down
[i
]->used
= 0;
267 * Find the subtrees and update them.
270 while (i
< entries
) {
271 const struct cache_entry
*ce
= cache
[i
];
272 struct cache_tree_sub
*sub
;
273 const char *path
, *slash
;
274 int pathlen
, sublen
, subcnt
, subskip
;
277 pathlen
= ce_namelen(ce
);
278 if (pathlen
<= baselen
|| memcmp(base
, path
, baselen
))
279 break; /* at the end of this level */
281 slash
= strchr(path
+ baselen
, '/');
287 * a/bbb/c (base = a/, slash = /c)
289 * path+baselen = bbb/c, sublen = 3
291 sublen
= slash
- (path
+ baselen
);
292 sub
= find_subtree(it
, path
+ baselen
, sublen
, 1);
293 if (!sub
->cache_tree
)
294 sub
->cache_tree
= cache_tree();
295 subcnt
= update_one(sub
->cache_tree
,
296 cache
+ i
, entries
- i
,
298 baselen
+ sublen
+ 1,
304 die("index cache-tree records empty sub-tree");
306 sub
->count
= subcnt
; /* to be used in the next loop */
307 *skip_count
+= subskip
;
311 discard_unused_subtrees(it
);
314 * Then write out the tree object for this level.
316 strbuf_init(&buffer
, 8192);
319 while (i
< entries
) {
320 const struct cache_entry
*ce
= cache
[i
];
321 struct cache_tree_sub
*sub
= NULL
;
322 const char *path
, *slash
;
324 const struct object_id
*oid
;
326 int expected_missing
= 0;
327 int contains_ita
= 0;
330 pathlen
= ce_namelen(ce
);
331 if (pathlen
<= baselen
|| memcmp(base
, path
, baselen
))
332 break; /* at the end of this level */
334 slash
= strchr(path
+ baselen
, '/');
336 entlen
= slash
- (path
+ baselen
);
337 sub
= find_subtree(it
, path
+ baselen
, entlen
, 0);
339 die("cache-tree.c: '%.*s' in '%s' not found",
340 entlen
, path
+ baselen
, path
);
342 oid
= &sub
->cache_tree
->oid
;
344 contains_ita
= sub
->cache_tree
->entry_count
< 0;
347 expected_missing
= 1;
353 entlen
= pathlen
- baselen
;
357 if (is_null_oid(oid
) ||
358 (mode
!= S_IFGITLINK
&& !missing_ok
&& !has_object_file(oid
))) {
359 strbuf_release(&buffer
);
360 if (expected_missing
)
362 return error("invalid object %06o %s for '%.*s'",
363 mode
, oid_to_hex(oid
), entlen
+baselen
, path
);
367 * CE_REMOVE entries are removed before the index is
368 * written to disk. Skip them to remain consistent
369 * with the future on-disk index.
371 if (ce
->ce_flags
& CE_REMOVE
) {
372 *skip_count
= *skip_count
+ 1;
377 * CE_INTENT_TO_ADD entries exist on on-disk index but
378 * they are not part of generated trees. Invalidate up
379 * to root to force cache-tree users to read elsewhere.
381 if (!sub
&& ce_intent_to_add(ce
)) {
387 * "sub" can be an empty tree if all subentries are i-t-a.
389 if (contains_ita
&& is_empty_tree_oid(oid
))
392 strbuf_grow(&buffer
, entlen
+ 100);
393 strbuf_addf(&buffer
, "%o %.*s%c", mode
, entlen
, path
+ baselen
, '\0');
394 strbuf_add(&buffer
, oid
->hash
, the_hash_algo
->rawsz
);
397 fprintf(stderr
, "cache-tree update-one %o %.*s\n",
398 mode
, entlen
, path
+ baselen
);
403 struct object_id oid
;
404 hash_object_file(buffer
.buf
, buffer
.len
, tree_type
, &oid
);
405 if (has_object_file(&oid
))
406 oidcpy(&it
->oid
, &oid
);
410 hash_object_file(buffer
.buf
, buffer
.len
, tree_type
, &it
->oid
);
411 } else if (write_object_file(buffer
.buf
, buffer
.len
, tree_type
,
413 strbuf_release(&buffer
);
417 strbuf_release(&buffer
);
418 it
->entry_count
= to_invalidate
? -1 : i
- *skip_count
;
420 fprintf(stderr
, "cache-tree update-one (%d ent, %d subtree) %s\n",
421 it
->entry_count
, it
->subtree_nr
,
422 oid_to_hex(&it
->oid
));
427 int cache_tree_update(struct index_state
*istate
, int flags
)
429 struct cache_tree
*it
= istate
->cache_tree
;
430 struct cache_entry
**cache
= istate
->cache
;
431 int entries
= istate
->cache_nr
;
432 int skip
, i
= verify_cache(cache
, entries
, flags
);
436 i
= update_one(it
, cache
, entries
, "", 0, &skip
, flags
);
439 istate
->cache_changed
|= CACHE_TREE_CHANGED
;
443 static void write_one(struct strbuf
*buffer
, struct cache_tree
*it
,
444 const char *path
, int pathlen
)
448 /* One "cache-tree" entry consists of the following:
449 * path (NUL terminated)
450 * entry_count, subtree_nr ("%d %d\n")
451 * tree-sha1 (missing if invalid)
452 * subtree_nr "cache-tree" entries for subtrees.
454 strbuf_grow(buffer
, pathlen
+ 100);
455 strbuf_add(buffer
, path
, pathlen
);
456 strbuf_addf(buffer
, "%c%d %d\n", 0, it
->entry_count
, it
->subtree_nr
);
459 if (0 <= it
->entry_count
)
460 fprintf(stderr
, "cache-tree <%.*s> (%d ent, %d subtree) %s\n",
461 pathlen
, path
, it
->entry_count
, it
->subtree_nr
,
462 oid_to_hex(&it
->oid
));
464 fprintf(stderr
, "cache-tree <%.*s> (%d subtree) invalid\n",
465 pathlen
, path
, it
->subtree_nr
);
468 if (0 <= it
->entry_count
) {
469 strbuf_add(buffer
, it
->oid
.hash
, the_hash_algo
->rawsz
);
471 for (i
= 0; i
< it
->subtree_nr
; i
++) {
472 struct cache_tree_sub
*down
= it
->down
[i
];
474 struct cache_tree_sub
*prev
= it
->down
[i
-1];
475 if (subtree_name_cmp(down
->name
, down
->namelen
,
476 prev
->name
, prev
->namelen
) <= 0)
477 die("fatal - unsorted cache subtree");
479 write_one(buffer
, down
->cache_tree
, down
->name
, down
->namelen
);
483 void cache_tree_write(struct strbuf
*sb
, struct cache_tree
*root
)
485 write_one(sb
, root
, "", 0);
488 static struct cache_tree
*read_one(const char **buffer
, unsigned long *size_p
)
490 const char *buf
= *buffer
;
491 unsigned long size
= *size_p
;
494 struct cache_tree
*it
;
496 const unsigned rawsz
= the_hash_algo
->rawsz
;
499 /* skip name, but make sure name exists */
500 while (size
&& *buf
) {
510 it
->entry_count
= strtol(cp
, &ep
, 10);
514 subtree_nr
= strtol(cp
, &ep
, 10);
517 while (size
&& *buf
&& *buf
!= '\n') {
524 if (0 <= it
->entry_count
) {
527 oidread(&it
->oid
, (const unsigned char *)buf
);
533 if (0 <= it
->entry_count
)
534 fprintf(stderr
, "cache-tree <%s> (%d ent, %d subtree) %s\n",
535 *buffer
, it
->entry_count
, subtree_nr
,
536 oid_to_hex(&it
->oid
));
538 fprintf(stderr
, "cache-tree <%s> (%d subtrees) invalid\n",
539 *buffer
, subtree_nr
);
543 * Just a heuristic -- we do not add directories that often but
544 * we do not want to have to extend it immediately when we do,
547 it
->subtree_alloc
= subtree_nr
+ 2;
548 it
->down
= xcalloc(it
->subtree_alloc
, sizeof(struct cache_tree_sub
*));
549 for (i
= 0; i
< subtree_nr
; i
++) {
550 /* read each subtree */
551 struct cache_tree
*sub
;
552 struct cache_tree_sub
*subtree
;
553 const char *name
= buf
;
555 sub
= read_one(&buf
, &size
);
558 subtree
= cache_tree_sub(it
, name
);
559 subtree
->cache_tree
= sub
;
561 if (subtree_nr
!= it
->subtree_nr
)
562 die("cache-tree: internal error");
568 cache_tree_free(&it
);
572 struct cache_tree
*cache_tree_read(const char *buffer
, unsigned long size
)
575 return NULL
; /* not the whole tree */
576 return read_one(&buffer
, &size
);
579 static struct cache_tree
*cache_tree_find(struct cache_tree
*it
, const char *path
)
585 struct cache_tree_sub
*sub
;
587 slash
= strchrnul(path
, '/');
589 * Between path and slash is the name of the subtree
592 sub
= find_subtree(it
, path
, slash
- path
, 0);
595 it
= sub
->cache_tree
;
604 int write_index_as_tree(struct object_id
*oid
, struct index_state
*index_state
, const char *index_path
, int flags
, const char *prefix
)
606 int entries
, was_valid
;
607 struct lock_file lock_file
= LOCK_INIT
;
610 hold_lock_file_for_update(&lock_file
, index_path
, LOCK_DIE_ON_ERROR
);
612 entries
= read_index_from(index_state
, index_path
, get_git_dir());
614 ret
= WRITE_TREE_UNREADABLE_INDEX
;
617 if (flags
& WRITE_TREE_IGNORE_CACHE_TREE
)
618 cache_tree_free(&index_state
->cache_tree
);
620 if (!index_state
->cache_tree
)
621 index_state
->cache_tree
= cache_tree();
623 was_valid
= cache_tree_fully_valid(index_state
->cache_tree
);
625 if (cache_tree_update(index_state
, flags
) < 0) {
626 ret
= WRITE_TREE_UNMERGED_INDEX
;
629 write_locked_index(index_state
, &lock_file
, COMMIT_LOCK
);
630 /* Not being able to write is fine -- we are only interested
631 * in updating the cache-tree part, and if the next caller
632 * ends up using the old index with unupdated cache-tree part
633 * it misses the work we did here, but that is just a
634 * performance penalty and not a big deal.
639 struct cache_tree
*subtree
;
640 subtree
= cache_tree_find(index_state
->cache_tree
, prefix
);
642 ret
= WRITE_TREE_PREFIX_ERROR
;
645 oidcpy(oid
, &subtree
->oid
);
648 oidcpy(oid
, &index_state
->cache_tree
->oid
);
651 rollback_lock_file(&lock_file
);
655 static void prime_cache_tree_rec(struct cache_tree
*it
, struct tree
*tree
)
657 struct tree_desc desc
;
658 struct name_entry entry
;
661 oidcpy(&it
->oid
, &tree
->object
.oid
);
662 init_tree_desc(&desc
, tree
->buffer
, tree
->size
);
664 while (tree_entry(&desc
, &entry
)) {
665 if (!S_ISDIR(entry
.mode
))
668 struct cache_tree_sub
*sub
;
669 struct tree
*subtree
= lookup_tree(the_repository
,
671 if (!subtree
->object
.parsed
)
673 sub
= cache_tree_sub(it
, entry
.path
);
674 sub
->cache_tree
= cache_tree();
675 prime_cache_tree_rec(sub
->cache_tree
, subtree
);
676 cnt
+= sub
->cache_tree
->entry_count
;
679 it
->entry_count
= cnt
;
682 void prime_cache_tree(struct index_state
*istate
, struct tree
*tree
)
684 cache_tree_free(&istate
->cache_tree
);
685 istate
->cache_tree
= cache_tree();
686 prime_cache_tree_rec(istate
->cache_tree
, tree
);
687 istate
->cache_changed
|= CACHE_TREE_CHANGED
;
691 * find the cache_tree that corresponds to the current level without
692 * exploding the full path into textual form. The root of the
693 * cache tree is given as "root", and our current level is "info".
694 * (1) When at root level, info->prev is NULL, so it is "root" itself.
695 * (2) Otherwise, find the cache_tree that corresponds to one level
696 * above us, and find ourselves in there.
698 static struct cache_tree
*find_cache_tree_from_traversal(struct cache_tree
*root
,
699 struct traverse_info
*info
)
701 struct cache_tree
*our_parent
;
705 our_parent
= find_cache_tree_from_traversal(root
, info
->prev
);
706 return cache_tree_find(our_parent
, info
->name
.path
);
709 int cache_tree_matches_traversal(struct cache_tree
*root
,
710 struct name_entry
*ent
,
711 struct traverse_info
*info
)
713 struct cache_tree
*it
;
715 it
= find_cache_tree_from_traversal(root
, info
);
716 it
= cache_tree_find(it
, ent
->path
);
717 if (it
&& it
->entry_count
> 0 && !oidcmp(ent
->oid
, &it
->oid
))
718 return it
->entry_count
;