4 #include "cache-tree.h"
10 struct cache_tree
*cache_tree(void)
12 struct cache_tree
*it
= xcalloc(1, sizeof(struct cache_tree
));
17 void cache_tree_free(struct cache_tree
**it_p
)
20 struct cache_tree
*it
= *it_p
;
24 for (i
= 0; i
< it
->subtree_nr
; i
++)
26 cache_tree_free(&it
->down
[i
]->cache_tree
);
34 static int subtree_name_cmp(const char *one
, int onelen
,
35 const char *two
, int twolen
)
41 return memcmp(one
, two
, onelen
);
44 static int subtree_pos(struct cache_tree
*it
, const char *path
, int pathlen
)
46 struct cache_tree_sub
**down
= it
->down
;
51 int mi
= (lo
+ hi
) / 2;
52 struct cache_tree_sub
*mdl
= down
[mi
];
53 int cmp
= subtree_name_cmp(path
, pathlen
,
54 mdl
->name
, mdl
->namelen
);
65 static struct cache_tree_sub
*find_subtree(struct cache_tree
*it
,
70 struct cache_tree_sub
*down
;
71 int pos
= subtree_pos(it
, path
, pathlen
);
78 ALLOC_GROW(it
->down
, it
->subtree_nr
+ 1, it
->subtree_alloc
);
81 down
= xmalloc(sizeof(*down
) + pathlen
+ 1);
82 down
->cache_tree
= NULL
;
83 down
->namelen
= pathlen
;
84 memcpy(down
->name
, path
, pathlen
);
85 down
->name
[pathlen
] = 0;
87 if (pos
< it
->subtree_nr
)
88 memmove(it
->down
+ pos
+ 1,
90 sizeof(down
) * (it
->subtree_nr
- pos
- 1));
95 struct cache_tree_sub
*cache_tree_sub(struct cache_tree
*it
, const char *path
)
97 int pathlen
= strlen(path
);
98 return find_subtree(it
, path
, pathlen
, 1);
101 void cache_tree_invalidate_path(struct cache_tree
*it
, const char *path
)
104 * ==> invalidate self
105 * ==> find "a", have it invalidate "b/c"
107 * ==> invalidate self
108 * ==> if "a" exists as a subtree, remove it.
112 struct cache_tree_sub
*down
;
115 fprintf(stderr
, "cache-tree invalidate <%s>\n", path
);
120 slash
= strchrnul(path
, '/');
121 namelen
= slash
- path
;
122 it
->entry_count
= -1;
125 pos
= subtree_pos(it
, path
, namelen
);
127 cache_tree_free(&it
->down
[pos
]->cache_tree
);
132 * move 4 and 5 up one place (2 entries)
133 * 2 = 6 - 3 - 1 = subtree_nr - pos - 1
135 memmove(it
->down
+pos
, it
->down
+pos
+1,
136 sizeof(struct cache_tree_sub
*) *
137 (it
->subtree_nr
- pos
- 1));
142 down
= find_subtree(it
, path
, namelen
, 0);
144 cache_tree_invalidate_path(down
->cache_tree
, slash
+ 1);
147 static int verify_cache(const struct cache_entry
* const *cache
,
148 int entries
, int flags
)
151 int silent
= flags
& WRITE_TREE_SILENT
;
153 /* Verify that the tree is merged */
155 for (i
= 0; i
< entries
; i
++) {
156 const struct cache_entry
*ce
= cache
[i
];
161 fprintf(stderr
, "...\n");
164 fprintf(stderr
, "%s: unmerged (%s)\n",
165 ce
->name
, sha1_to_hex(ce
->sha1
));
171 /* Also verify that the cache does not have path and path/file
172 * at the same time. At this point we know the cache has only
176 for (i
= 0; i
< entries
- 1; i
++) {
177 /* path/file always comes after path because of the way
178 * the cache is sorted. Also path can appear only once,
179 * which means conflicting one would immediately follow.
181 const char *this_name
= cache
[i
]->name
;
182 const char *next_name
= cache
[i
+1]->name
;
183 int this_len
= strlen(this_name
);
184 if (this_len
< strlen(next_name
) &&
185 strncmp(this_name
, next_name
, this_len
) == 0 &&
186 next_name
[this_len
] == '/') {
188 fprintf(stderr
, "...\n");
191 fprintf(stderr
, "You have both %s and %s\n",
192 this_name
, next_name
);
200 static void discard_unused_subtrees(struct cache_tree
*it
)
202 struct cache_tree_sub
**down
= it
->down
;
203 int nr
= it
->subtree_nr
;
205 for (dst
= src
= 0; src
< nr
; src
++) {
206 struct cache_tree_sub
*s
= down
[src
];
210 cache_tree_free(&s
->cache_tree
);
217 int cache_tree_fully_valid(struct cache_tree
*it
)
222 if (it
->entry_count
< 0 || !has_sha1_file(it
->sha1
))
224 for (i
= 0; i
< it
->subtree_nr
; i
++) {
225 if (!cache_tree_fully_valid(it
->down
[i
]->cache_tree
))
231 static int update_one(struct cache_tree
*it
,
232 const struct cache_entry
* const *cache
,
239 struct strbuf buffer
;
240 int missing_ok
= flags
& WRITE_TREE_MISSING_OK
;
241 int dryrun
= flags
& WRITE_TREE_DRY_RUN
;
242 int repair
= flags
& WRITE_TREE_REPAIR
;
243 int to_invalidate
= 0;
246 assert(!(dryrun
&& repair
));
250 if (0 <= it
->entry_count
&& has_sha1_file(it
->sha1
))
251 return it
->entry_count
;
254 * We first scan for subtrees and update them; we start by
255 * marking existing subtrees -- the ones that are unmarked
256 * should not be in the result.
258 for (i
= 0; i
< it
->subtree_nr
; i
++)
259 it
->down
[i
]->used
= 0;
262 * Find the subtrees and update them.
265 while (i
< entries
) {
266 const struct cache_entry
*ce
= cache
[i
];
267 struct cache_tree_sub
*sub
;
268 const char *path
, *slash
;
269 int pathlen
, sublen
, subcnt
, subskip
;
272 pathlen
= ce_namelen(ce
);
273 if (pathlen
<= baselen
|| memcmp(base
, path
, baselen
))
274 break; /* at the end of this level */
276 slash
= strchr(path
+ baselen
, '/');
282 * a/bbb/c (base = a/, slash = /c)
284 * path+baselen = bbb/c, sublen = 3
286 sublen
= slash
- (path
+ baselen
);
287 sub
= find_subtree(it
, path
+ baselen
, sublen
, 1);
288 if (!sub
->cache_tree
)
289 sub
->cache_tree
= cache_tree();
290 subcnt
= update_one(sub
->cache_tree
,
291 cache
+ i
, entries
- i
,
293 baselen
+ sublen
+ 1,
299 sub
->count
= subcnt
; /* to be used in the next loop */
300 *skip_count
+= subskip
;
304 discard_unused_subtrees(it
);
307 * Then write out the tree object for this level.
309 strbuf_init(&buffer
, 8192);
312 while (i
< entries
) {
313 const struct cache_entry
*ce
= cache
[i
];
314 struct cache_tree_sub
*sub
;
315 const char *path
, *slash
;
317 const unsigned char *sha1
;
319 int expected_missing
= 0;
322 pathlen
= ce_namelen(ce
);
323 if (pathlen
<= baselen
|| memcmp(base
, path
, baselen
))
324 break; /* at the end of this level */
326 slash
= strchr(path
+ baselen
, '/');
328 entlen
= slash
- (path
+ baselen
);
329 sub
= find_subtree(it
, path
+ baselen
, entlen
, 0);
331 die("cache-tree.c: '%.*s' in '%s' not found",
332 entlen
, path
+ baselen
, path
);
334 sha1
= sub
->cache_tree
->sha1
;
336 if (sub
->cache_tree
->entry_count
< 0) {
338 expected_missing
= 1;
344 entlen
= pathlen
- baselen
;
347 if (mode
!= S_IFGITLINK
&& !missing_ok
&& !has_sha1_file(sha1
)) {
348 strbuf_release(&buffer
);
349 if (expected_missing
)
351 return error("invalid object %06o %s for '%.*s'",
352 mode
, sha1_to_hex(sha1
), entlen
+baselen
, path
);
356 * CE_REMOVE entries are removed before the index is
357 * written to disk. Skip them to remain consistent
358 * with the future on-disk index.
360 if (ce
->ce_flags
& CE_REMOVE
) {
361 *skip_count
= *skip_count
+ 1;
366 * CE_INTENT_TO_ADD entries exist on on-disk index but
367 * they are not part of generated trees. Invalidate up
368 * to root to force cache-tree users to read elsewhere.
370 if (ce
->ce_flags
& CE_INTENT_TO_ADD
) {
375 strbuf_grow(&buffer
, entlen
+ 100);
376 strbuf_addf(&buffer
, "%o %.*s%c", mode
, entlen
, path
+ baselen
, '\0');
377 strbuf_add(&buffer
, sha1
, 20);
380 fprintf(stderr
, "cache-tree update-one %o %.*s\n",
381 mode
, entlen
, path
+ baselen
);
386 unsigned char sha1
[20];
387 hash_sha1_file(buffer
.buf
, buffer
.len
, tree_type
, sha1
);
388 if (has_sha1_file(sha1
))
389 hashcpy(it
->sha1
, sha1
);
393 hash_sha1_file(buffer
.buf
, buffer
.len
, tree_type
, it
->sha1
);
394 else if (write_sha1_file(buffer
.buf
, buffer
.len
, tree_type
, it
->sha1
)) {
395 strbuf_release(&buffer
);
399 strbuf_release(&buffer
);
400 it
->entry_count
= to_invalidate
? -1 : i
- *skip_count
;
402 fprintf(stderr
, "cache-tree update-one (%d ent, %d subtree) %s\n",
403 it
->entry_count
, it
->subtree_nr
,
404 sha1_to_hex(it
->sha1
));
409 int cache_tree_update(struct cache_tree
*it
,
410 const struct cache_entry
* const *cache
,
415 i
= verify_cache(cache
, entries
, flags
);
418 i
= update_one(it
, cache
, entries
, "", 0, &skip
, flags
);
424 static void write_one(struct strbuf
*buffer
, struct cache_tree
*it
,
425 const char *path
, int pathlen
)
429 /* One "cache-tree" entry consists of the following:
430 * path (NUL terminated)
431 * entry_count, subtree_nr ("%d %d\n")
432 * tree-sha1 (missing if invalid)
433 * subtree_nr "cache-tree" entries for subtrees.
435 strbuf_grow(buffer
, pathlen
+ 100);
436 strbuf_add(buffer
, path
, pathlen
);
437 strbuf_addf(buffer
, "%c%d %d\n", 0, it
->entry_count
, it
->subtree_nr
);
440 if (0 <= it
->entry_count
)
441 fprintf(stderr
, "cache-tree <%.*s> (%d ent, %d subtree) %s\n",
442 pathlen
, path
, it
->entry_count
, it
->subtree_nr
,
443 sha1_to_hex(it
->sha1
));
445 fprintf(stderr
, "cache-tree <%.*s> (%d subtree) invalid\n",
446 pathlen
, path
, it
->subtree_nr
);
449 if (0 <= it
->entry_count
) {
450 strbuf_add(buffer
, it
->sha1
, 20);
452 for (i
= 0; i
< it
->subtree_nr
; i
++) {
453 struct cache_tree_sub
*down
= it
->down
[i
];
455 struct cache_tree_sub
*prev
= it
->down
[i
-1];
456 if (subtree_name_cmp(down
->name
, down
->namelen
,
457 prev
->name
, prev
->namelen
) <= 0)
458 die("fatal - unsorted cache subtree");
460 write_one(buffer
, down
->cache_tree
, down
->name
, down
->namelen
);
464 void cache_tree_write(struct strbuf
*sb
, struct cache_tree
*root
)
466 write_one(sb
, root
, "", 0);
469 static struct cache_tree
*read_one(const char **buffer
, unsigned long *size_p
)
471 const char *buf
= *buffer
;
472 unsigned long size
= *size_p
;
475 struct cache_tree
*it
;
479 /* skip name, but make sure name exists */
480 while (size
&& *buf
) {
490 it
->entry_count
= strtol(cp
, &ep
, 10);
494 subtree_nr
= strtol(cp
, &ep
, 10);
497 while (size
&& *buf
&& *buf
!= '\n') {
504 if (0 <= it
->entry_count
) {
507 hashcpy(it
->sha1
, (const unsigned char*)buf
);
513 if (0 <= it
->entry_count
)
514 fprintf(stderr
, "cache-tree <%s> (%d ent, %d subtree) %s\n",
515 *buffer
, it
->entry_count
, subtree_nr
,
516 sha1_to_hex(it
->sha1
));
518 fprintf(stderr
, "cache-tree <%s> (%d subtrees) invalid\n",
519 *buffer
, subtree_nr
);
523 * Just a heuristic -- we do not add directories that often but
524 * we do not want to have to extend it immediately when we do,
527 it
->subtree_alloc
= subtree_nr
+ 2;
528 it
->down
= xcalloc(it
->subtree_alloc
, sizeof(struct cache_tree_sub
*));
529 for (i
= 0; i
< subtree_nr
; i
++) {
530 /* read each subtree */
531 struct cache_tree
*sub
;
532 struct cache_tree_sub
*subtree
;
533 const char *name
= buf
;
535 sub
= read_one(&buf
, &size
);
538 subtree
= cache_tree_sub(it
, name
);
539 subtree
->cache_tree
= sub
;
541 if (subtree_nr
!= it
->subtree_nr
)
542 die("cache-tree: internal error");
548 cache_tree_free(&it
);
552 struct cache_tree
*cache_tree_read(const char *buffer
, unsigned long size
)
555 return NULL
; /* not the whole tree */
556 return read_one(&buffer
, &size
);
559 static struct cache_tree
*cache_tree_find(struct cache_tree
*it
, const char *path
)
565 struct cache_tree_sub
*sub
;
567 slash
= strchrnul(path
, '/');
569 * Between path and slash is the name of the subtree
572 sub
= find_subtree(it
, path
, slash
- path
, 0);
575 it
= sub
->cache_tree
;
584 int write_cache_as_tree(unsigned char *sha1
, int flags
, const char *prefix
)
586 int entries
, was_valid
, newfd
;
587 struct lock_file
*lock_file
;
590 * We can't free this memory, it becomes part of a linked list
593 lock_file
= xcalloc(1, sizeof(struct lock_file
));
595 newfd
= hold_locked_index(lock_file
, 1);
597 entries
= read_cache();
599 return WRITE_TREE_UNREADABLE_INDEX
;
600 if (flags
& WRITE_TREE_IGNORE_CACHE_TREE
)
601 cache_tree_free(&(active_cache_tree
));
603 if (!active_cache_tree
)
604 active_cache_tree
= cache_tree();
606 was_valid
= cache_tree_fully_valid(active_cache_tree
);
608 if (cache_tree_update(active_cache_tree
,
609 (const struct cache_entry
* const *)active_cache
,
610 active_nr
, flags
) < 0)
611 return WRITE_TREE_UNMERGED_INDEX
;
613 if (!write_cache(newfd
, active_cache
, active_nr
) &&
614 !commit_lock_file(lock_file
))
617 /* Not being able to write is fine -- we are only interested
618 * in updating the cache-tree part, and if the next caller
619 * ends up using the old index with unupdated cache-tree part
620 * it misses the work we did here, but that is just a
621 * performance penalty and not a big deal.
626 struct cache_tree
*subtree
=
627 cache_tree_find(active_cache_tree
, prefix
);
629 return WRITE_TREE_PREFIX_ERROR
;
630 hashcpy(sha1
, subtree
->sha1
);
633 hashcpy(sha1
, active_cache_tree
->sha1
);
636 rollback_lock_file(lock_file
);
641 static void prime_cache_tree_rec(struct cache_tree
*it
, struct tree
*tree
)
643 struct tree_desc desc
;
644 struct name_entry entry
;
647 hashcpy(it
->sha1
, tree
->object
.sha1
);
648 init_tree_desc(&desc
, tree
->buffer
, tree
->size
);
650 while (tree_entry(&desc
, &entry
)) {
651 if (!S_ISDIR(entry
.mode
))
654 struct cache_tree_sub
*sub
;
655 struct tree
*subtree
= lookup_tree(entry
.sha1
);
656 if (!subtree
->object
.parsed
)
658 sub
= cache_tree_sub(it
, entry
.path
);
659 sub
->cache_tree
= cache_tree();
660 prime_cache_tree_rec(sub
->cache_tree
, subtree
);
661 cnt
+= sub
->cache_tree
->entry_count
;
664 it
->entry_count
= cnt
;
667 void prime_cache_tree(struct cache_tree
**it
, struct tree
*tree
)
671 prime_cache_tree_rec(*it
, tree
);
675 * find the cache_tree that corresponds to the current level without
676 * exploding the full path into textual form. The root of the
677 * cache tree is given as "root", and our current level is "info".
678 * (1) When at root level, info->prev is NULL, so it is "root" itself.
679 * (2) Otherwise, find the cache_tree that corresponds to one level
680 * above us, and find ourselves in there.
682 static struct cache_tree
*find_cache_tree_from_traversal(struct cache_tree
*root
,
683 struct traverse_info
*info
)
685 struct cache_tree
*our_parent
;
689 our_parent
= find_cache_tree_from_traversal(root
, info
->prev
);
690 return cache_tree_find(our_parent
, info
->name
.path
);
693 int cache_tree_matches_traversal(struct cache_tree
*root
,
694 struct name_entry
*ent
,
695 struct traverse_info
*info
)
697 struct cache_tree
*it
;
699 it
= find_cache_tree_from_traversal(root
, info
);
700 it
= cache_tree_find(it
, ent
->path
);
701 if (it
&& it
->entry_count
> 0 && !hashcmp(ent
->sha1
, it
->sha1
))
702 return it
->entry_count
;
706 int update_main_cache_tree(int flags
)
708 if (!the_index
.cache_tree
)
709 the_index
.cache_tree
= cache_tree();
710 return cache_tree_update(the_index
.cache_tree
,
711 (const struct cache_entry
* const *)the_index
.cache
,
712 the_index
.cache_nr
, flags
);