3 #include "cache-tree.h"
9 struct cache_tree
*cache_tree(void)
11 struct cache_tree
*it
= xcalloc(1, sizeof(struct cache_tree
));
16 void cache_tree_free(struct cache_tree
**it_p
)
19 struct cache_tree
*it
= *it_p
;
23 for (i
= 0; i
< it
->subtree_nr
; i
++)
25 cache_tree_free(&it
->down
[i
]->cache_tree
);
31 static int subtree_name_cmp(const char *one
, int onelen
,
32 const char *two
, int twolen
)
38 return memcmp(one
, two
, onelen
);
41 static int subtree_pos(struct cache_tree
*it
, const char *path
, int pathlen
)
43 struct cache_tree_sub
**down
= it
->down
;
48 int mi
= (lo
+ hi
) / 2;
49 struct cache_tree_sub
*mdl
= down
[mi
];
50 int cmp
= subtree_name_cmp(path
, pathlen
,
51 mdl
->name
, mdl
->namelen
);
62 static struct cache_tree_sub
*find_subtree(struct cache_tree
*it
,
67 struct cache_tree_sub
*down
;
68 int pos
= subtree_pos(it
, path
, pathlen
);
75 if (it
->subtree_alloc
<= it
->subtree_nr
) {
76 it
->subtree_alloc
= alloc_nr(it
->subtree_alloc
);
77 it
->down
= xrealloc(it
->down
, it
->subtree_alloc
*
82 down
= xmalloc(sizeof(*down
) + pathlen
+ 1);
83 down
->cache_tree
= NULL
;
84 down
->namelen
= pathlen
;
85 memcpy(down
->name
, path
, pathlen
);
86 down
->name
[pathlen
] = 0;
88 if (pos
< it
->subtree_nr
)
89 memmove(it
->down
+ pos
+ 1,
91 sizeof(down
) * (it
->subtree_nr
- pos
- 1));
96 struct cache_tree_sub
*cache_tree_sub(struct cache_tree
*it
, const char *path
)
98 int pathlen
= strlen(path
);
99 return find_subtree(it
, path
, pathlen
, 1);
102 void cache_tree_invalidate_path(struct cache_tree
*it
, const char *path
)
105 * ==> invalidate self
106 * ==> find "a", have it invalidate "b/c"
108 * ==> invalidate self
109 * ==> if "a" exists as a subtree, remove it.
113 struct cache_tree_sub
*down
;
116 fprintf(stderr
, "cache-tree invalidate <%s>\n", path
);
121 slash
= strchr(path
, '/');
122 it
->entry_count
= -1;
125 namelen
= strlen(path
);
126 pos
= subtree_pos(it
, path
, namelen
);
128 cache_tree_free(&it
->down
[pos
]->cache_tree
);
133 * move 4 and 5 up one place (2 entries)
134 * 2 = 6 - 3 - 1 = subtree_nr - pos - 1
136 memmove(it
->down
+pos
, it
->down
+pos
+1,
137 sizeof(struct cache_tree_sub
*) *
138 (it
->subtree_nr
- pos
- 1));
143 namelen
= slash
- path
;
144 down
= find_subtree(it
, path
, namelen
, 0);
146 cache_tree_invalidate_path(down
->cache_tree
, slash
+ 1);
149 static int verify_cache(struct cache_entry
**cache
,
154 /* Verify that the tree is merged */
156 for (i
= 0; i
< entries
; i
++) {
157 struct cache_entry
*ce
= cache
[i
];
160 fprintf(stderr
, "...\n");
163 fprintf(stderr
, "%s: unmerged (%s)\n",
164 ce
->name
, sha1_to_hex(ce
->sha1
));
170 /* Also verify that the cache does not have path and path/file
171 * at the same time. At this point we know the cache has only
175 for (i
= 0; i
< entries
- 1; i
++) {
176 /* path/file always comes after path because of the way
177 * the cache is sorted. Also path can appear only once,
178 * which means conflicting one would immediately follow.
180 const char *this_name
= cache
[i
]->name
;
181 const char *next_name
= cache
[i
+1]->name
;
182 int this_len
= strlen(this_name
);
183 if (this_len
< strlen(next_name
) &&
184 strncmp(this_name
, next_name
, this_len
) == 0 &&
185 next_name
[this_len
] == '/') {
187 fprintf(stderr
, "...\n");
190 fprintf(stderr
, "You have both %s and %s\n",
191 this_name
, next_name
);
199 static void discard_unused_subtrees(struct cache_tree
*it
)
201 struct cache_tree_sub
**down
= it
->down
;
202 int nr
= it
->subtree_nr
;
204 for (dst
= src
= 0; src
< nr
; src
++) {
205 struct cache_tree_sub
*s
= down
[src
];
209 cache_tree_free(&s
->cache_tree
);
216 int cache_tree_fully_valid(struct cache_tree
*it
)
221 if (it
->entry_count
< 0 || !has_sha1_file(it
->sha1
))
223 for (i
= 0; i
< it
->subtree_nr
; i
++) {
224 if (!cache_tree_fully_valid(it
->down
[i
]->cache_tree
))
230 static int update_one(struct cache_tree
*it
,
231 struct cache_entry
**cache
,
238 unsigned long size
, offset
;
242 if (0 <= it
->entry_count
&& has_sha1_file(it
->sha1
))
243 return it
->entry_count
;
246 * We first scan for subtrees and update them; we start by
247 * marking existing subtrees -- the ones that are unmarked
248 * should not be in the result.
250 for (i
= 0; i
< it
->subtree_nr
; i
++)
251 it
->down
[i
]->used
= 0;
254 * Find the subtrees and update them.
256 for (i
= 0; i
< entries
; i
++) {
257 struct cache_entry
*ce
= cache
[i
];
258 struct cache_tree_sub
*sub
;
259 const char *path
, *slash
;
260 int pathlen
, sublen
, subcnt
;
263 pathlen
= ce_namelen(ce
);
264 if (pathlen
<= baselen
|| memcmp(base
, path
, baselen
))
265 break; /* at the end of this level */
267 slash
= strchr(path
+ baselen
, '/');
271 * a/bbb/c (base = a/, slash = /c)
273 * path+baselen = bbb/c, sublen = 3
275 sublen
= slash
- (path
+ baselen
);
276 sub
= find_subtree(it
, path
+ baselen
, sublen
, 1);
277 if (!sub
->cache_tree
)
278 sub
->cache_tree
= cache_tree();
279 subcnt
= update_one(sub
->cache_tree
,
280 cache
+ i
, entries
- i
,
282 baselen
+ sublen
+ 1,
291 discard_unused_subtrees(it
);
294 * Then write out the tree object for this level.
297 buffer
= xmalloc(size
);
300 for (i
= 0; i
< entries
; i
++) {
301 struct cache_entry
*ce
= cache
[i
];
302 struct cache_tree_sub
*sub
;
303 const char *path
, *slash
;
305 const unsigned char *sha1
;
309 pathlen
= ce_namelen(ce
);
310 if (pathlen
<= baselen
|| memcmp(base
, path
, baselen
))
311 break; /* at the end of this level */
313 slash
= strchr(path
+ baselen
, '/');
315 entlen
= slash
- (path
+ baselen
);
316 sub
= find_subtree(it
, path
+ baselen
, entlen
, 0);
318 die("cache-tree.c: '%.*s' in '%s' not found",
319 entlen
, path
+ baselen
, path
);
320 i
+= sub
->cache_tree
->entry_count
- 1;
321 sha1
= sub
->cache_tree
->sha1
;
326 mode
= ntohl(ce
->ce_mode
);
327 entlen
= pathlen
- baselen
;
329 if (!missing_ok
&& !has_sha1_file(sha1
))
330 return error("invalid object %s", sha1_to_hex(sha1
));
333 continue; /* entry being removed */
335 if (size
< offset
+ entlen
+ 100) {
336 size
= alloc_nr(offset
+ entlen
+ 100);
337 buffer
= xrealloc(buffer
, size
);
339 offset
+= sprintf(buffer
+ offset
,
340 "%o %.*s", mode
, entlen
, path
+ baselen
);
341 buffer
[offset
++] = 0;
342 hashcpy((unsigned char*)buffer
+ offset
, sha1
);
346 fprintf(stderr
, "cache-tree update-one %o %.*s\n",
347 mode
, entlen
, path
+ baselen
);
352 hash_sha1_file(buffer
, offset
, tree_type
, it
->sha1
);
354 write_sha1_file(buffer
, offset
, tree_type
, it
->sha1
);
358 fprintf(stderr
, "cache-tree update-one (%d ent, %d subtree) %s\n",
359 it
->entry_count
, it
->subtree_nr
,
360 sha1_to_hex(it
->sha1
));
365 int cache_tree_update(struct cache_tree
*it
,
366 struct cache_entry
**cache
,
372 i
= verify_cache(cache
, entries
);
375 i
= update_one(it
, cache
, entries
, "", 0, missing_ok
, dryrun
);
381 static void *write_one(struct cache_tree
*it
,
386 unsigned long *offset
)
390 /* One "cache-tree" entry consists of the following:
391 * path (NUL terminated)
392 * entry_count, subtree_nr ("%d %d\n")
393 * tree-sha1 (missing if invalid)
394 * subtree_nr "cache-tree" entries for subtrees.
396 if (*size
< *offset
+ pathlen
+ 100) {
397 *size
= alloc_nr(*offset
+ pathlen
+ 100);
398 buffer
= xrealloc(buffer
, *size
);
400 *offset
+= sprintf(buffer
+ *offset
, "%.*s%c%d %d\n",
402 it
->entry_count
, it
->subtree_nr
);
405 if (0 <= it
->entry_count
)
406 fprintf(stderr
, "cache-tree <%.*s> (%d ent, %d subtree) %s\n",
407 pathlen
, path
, it
->entry_count
, it
->subtree_nr
,
408 sha1_to_hex(it
->sha1
));
410 fprintf(stderr
, "cache-tree <%.*s> (%d subtree) invalid\n",
411 pathlen
, path
, it
->subtree_nr
);
414 if (0 <= it
->entry_count
) {
415 hashcpy((unsigned char*)buffer
+ *offset
, it
->sha1
);
418 for (i
= 0; i
< it
->subtree_nr
; i
++) {
419 struct cache_tree_sub
*down
= it
->down
[i
];
421 struct cache_tree_sub
*prev
= it
->down
[i
-1];
422 if (subtree_name_cmp(down
->name
, down
->namelen
,
423 prev
->name
, prev
->namelen
) <= 0)
424 die("fatal - unsorted cache subtree");
426 buffer
= write_one(down
->cache_tree
, down
->name
, down
->namelen
,
427 buffer
, size
, offset
);
432 void *cache_tree_write(struct cache_tree
*root
, unsigned long *size_p
)
435 unsigned long size
= 8192;
436 char *buffer
= xmalloc(size
);
440 return write_one(root
, path
, 0, buffer
, &size
, size_p
);
443 static struct cache_tree
*read_one(const char **buffer
, unsigned long *size_p
)
445 const char *buf
= *buffer
;
446 unsigned long size
= *size_p
;
449 struct cache_tree
*it
;
453 /* skip name, but make sure name exists */
454 while (size
&& *buf
) {
464 it
->entry_count
= strtol(cp
, &ep
, 10);
468 subtree_nr
= strtol(cp
, &ep
, 10);
471 while (size
&& *buf
&& *buf
!= '\n') {
478 if (0 <= it
->entry_count
) {
481 hashcpy(it
->sha1
, (unsigned char*)buf
);
487 if (0 <= it
->entry_count
)
488 fprintf(stderr
, "cache-tree <%s> (%d ent, %d subtree) %s\n",
489 *buffer
, it
->entry_count
, subtree_nr
,
490 sha1_to_hex(it
->sha1
));
492 fprintf(stderr
, "cache-tree <%s> (%d subtrees) invalid\n",
493 *buffer
, subtree_nr
);
497 * Just a heuristic -- we do not add directories that often but
498 * we do not want to have to extend it immediately when we do,
501 it
->subtree_alloc
= subtree_nr
+ 2;
502 it
->down
= xcalloc(it
->subtree_alloc
, sizeof(struct cache_tree_sub
*));
503 for (i
= 0; i
< subtree_nr
; i
++) {
504 /* read each subtree */
505 struct cache_tree
*sub
;
506 struct cache_tree_sub
*subtree
;
507 const char *name
= buf
;
509 sub
= read_one(&buf
, &size
);
512 subtree
= cache_tree_sub(it
, name
);
513 subtree
->cache_tree
= sub
;
515 if (subtree_nr
!= it
->subtree_nr
)
516 die("cache-tree: internal error");
522 cache_tree_free(&it
);
526 struct cache_tree
*cache_tree_read(const char *buffer
, unsigned long size
)
529 return NULL
; /* not the whole tree */
530 return read_one(&buffer
, &size
);
533 struct cache_tree
*cache_tree_find(struct cache_tree
*it
, const char *path
)
537 struct cache_tree_sub
*sub
;
539 slash
= strchr(path
, '/');
541 slash
= path
+ strlen(path
);
542 /* between path and slash is the name of the
543 * subtree to look for.
545 sub
= find_subtree(it
, path
, slash
- path
, 0);
548 it
= sub
->cache_tree
;
550 while (*slash
&& *slash
== '/')
552 if (!slash
|| !*slash
)
553 return it
; /* prefix ended with slashes */