[thirdparty/git.git] / cache-tree.c

#include "cache.h"
#include "tree.h"
#include "cache-tree.h"

#ifndef DEBUG
#define DEBUG 0
#endif

struct cache_tree *cache_tree(void)
{
	struct cache_tree *it = xcalloc(1, sizeof(struct cache_tree));
	it->entry_count = -1;
	return it;
}

void cache_tree_free(struct cache_tree **it_p)
{
	int i;
	struct cache_tree *it = *it_p;

	if (!it)
		return;
	for (i = 0; i < it->subtree_nr; i++)
		if (it->down[i])
			cache_tree_free(&it->down[i]->cache_tree);
	free(it->down);
	free(it);
	*it_p = NULL;
}

static int subtree_name_cmp(const char *one, int onelen,
			    const char *two, int twolen)
{
	if (onelen < twolen)
		return -1;
	if (twolen < onelen)
		return 1;
	return memcmp(one, two, onelen);
}

static int subtree_pos(struct cache_tree *it, const char *path, int pathlen)
{
	struct cache_tree_sub **down = it->down;
	int lo, hi;
	lo = 0;
	hi = it->subtree_nr;
	while (lo < hi) {
		int mi = (lo + hi) / 2;
		struct cache_tree_sub *mdl = down[mi];
		int cmp = subtree_name_cmp(path, pathlen,
					   mdl->name, mdl->namelen);
		if (!cmp)
			return mi;
		if (cmp < 0)
			hi = mi;
		else
			lo = mi + 1;
	}
	return -lo-1;
}

static struct cache_tree_sub *find_subtree(struct cache_tree *it,
					   const char *path,
					   int pathlen,
					   int create)
{
	struct cache_tree_sub *down;
	int pos = subtree_pos(it, path, pathlen);
	if (0 <= pos)
		return it->down[pos];
	if (!create)
		return NULL;

	pos = -pos-1;
	if (it->subtree_alloc <= it->subtree_nr) {
		it->subtree_alloc = alloc_nr(it->subtree_alloc);
		it->down = xrealloc(it->down, it->subtree_alloc *
				    sizeof(*it->down));
	}
	it->subtree_nr++;

	down = xmalloc(sizeof(*down) + pathlen + 1);
	down->cache_tree = NULL;
	down->namelen = pathlen;
	memcpy(down->name, path, pathlen);
	down->name[pathlen] = 0;

	if (pos < it->subtree_nr)
		memmove(it->down + pos + 1,
			it->down + pos,
			sizeof(down) * (it->subtree_nr - pos - 1));
	it->down[pos] = down;
	return down;
}

struct cache_tree_sub *cache_tree_sub(struct cache_tree *it, const char *path)
{
	int pathlen = strlen(path);
	return find_subtree(it, path, pathlen, 1);
}

void cache_tree_invalidate_path(struct cache_tree *it, const char *path)
{
	/* a/b/c
	 * ==> invalidate self
	 * ==> find "a", have it invalidate "b/c"
	 * a
	 * ==> invalidate self
	 * ==> if "a" exists as a subtree, remove it.
	 */
	const char *slash;
	int namelen;
	struct cache_tree_sub *down;

#if DEBUG
	fprintf(stderr, "cache-tree invalidate <%s>\n", path);
#endif

	if (!it)
		return;
	slash = strchr(path, '/');
	it->entry_count = -1;
	if (!slash) {
		int pos;
		namelen = strlen(path);
		pos = subtree_pos(it, path, namelen);
		if (0 <= pos) {
			cache_tree_free(&it->down[pos]->cache_tree);
			free(it->down[pos]);
			/* 0 1 2 3 4 5
			 *       ^     ^subtree_nr = 6
			 *       pos
			 * move 4 and 5 up one place (2 entries)
			 * 2 = 6 - 3 - 1 = subtree_nr - pos - 1
			 */
			memmove(it->down+pos, it->down+pos+1,
				sizeof(struct cache_tree_sub *) *
				(it->subtree_nr - pos - 1));
			it->subtree_nr--;
		}
		return;
	}
	namelen = slash - path;
	down = find_subtree(it, path, namelen, 0);
	if (down)
		cache_tree_invalidate_path(down->cache_tree, slash + 1);
}

static int verify_cache(struct cache_entry **cache,
			int entries)
{
	int i, funny;

	/* Verify that the tree is merged */
	funny = 0;
	for (i = 0; i < entries; i++) {
		struct cache_entry *ce = cache[i];
		if (ce_stage(ce)) {
			if (10 < ++funny) {
				fprintf(stderr, "...\n");
				break;
			}
			fprintf(stderr, "%s: unmerged (%s)\n",
				ce->name, sha1_to_hex(ce->sha1));
		}
	}
	if (funny)
		return -1;

	/* Also verify that the cache does not have path and path/file
	 * at the same time.  At this point we know the cache has only
	 * stage 0 entries.
	 */
	funny = 0;
	for (i = 0; i < entries - 1; i++) {
		/* path/file always comes after path because of the way
		 * the cache is sorted.  Also path can appear only once,
		 * which means conflicting one would immediately follow.
		 */
		const char *this_name = cache[i]->name;
		const char *next_name = cache[i+1]->name;
		int this_len = strlen(this_name);
		if (this_len < strlen(next_name) &&
		    strncmp(this_name, next_name, this_len) == 0 &&
		    next_name[this_len] == '/') {
			if (10 < ++funny) {
				fprintf(stderr, "...\n");
				break;
			}
			fprintf(stderr, "You have both %s and %s\n",
				this_name, next_name);
		}
	}
	if (funny)
		return -1;
	return 0;
}

static void discard_unused_subtrees(struct cache_tree *it)
{
	struct cache_tree_sub **down = it->down;
	int nr = it->subtree_nr;
	int dst, src;
	for (dst = src = 0; src < nr; src++) {
		struct cache_tree_sub *s = down[src];
		if (s->used)
			down[dst++] = s;
		else {
			cache_tree_free(&s->cache_tree);
			free(s);
			it->subtree_nr--;
		}
	}
}

int cache_tree_fully_valid(struct cache_tree *it)
{
	int i;
	if (!it)
		return 0;
	if (it->entry_count < 0 || !has_sha1_file(it->sha1))
		return 0;
	for (i = 0; i < it->subtree_nr; i++) {
		if (!cache_tree_fully_valid(it->down[i]->cache_tree))
			return 0;
	}
	return 1;
}

static int update_one(struct cache_tree *it,
		      struct cache_entry **cache,
		      int entries,
		      const char *base,
		      int baselen,
		      int missing_ok,
		      int dryrun)
{
	struct strbuf buffer;
	int i;

	if (0 <= it->entry_count && has_sha1_file(it->sha1))
		return it->entry_count;

	/*
	 * We first scan for subtrees and update them; we start by
	 * marking existing subtrees -- the ones that are unmarked
	 * should not be in the result.
	 */
	for (i = 0; i < it->subtree_nr; i++)
		it->down[i]->used = 0;

	/*
	 * Find the subtrees and update them.
	 */
	for (i = 0; i < entries; i++) {
		struct cache_entry *ce = cache[i];
		struct cache_tree_sub *sub;
		const char *path, *slash;
		int pathlen, sublen, subcnt;

		path = ce->name;
		pathlen = ce_namelen(ce);
		if (pathlen <= baselen || memcmp(base, path, baselen))
			break; /* at the end of this level */

		slash = strchr(path + baselen, '/');
		if (!slash)
			continue;
		/*
		 * a/bbb/c (base = a/, slash = /c)
		 * ==>
		 * path+baselen = bbb/c, sublen = 3
		 */
		sublen = slash - (path + baselen);
		sub = find_subtree(it, path + baselen, sublen, 1);
		if (!sub->cache_tree)
			sub->cache_tree = cache_tree();
		subcnt = update_one(sub->cache_tree,
				    cache + i, entries - i,
				    path,
				    baselen + sublen + 1,
				    missing_ok,
				    dryrun);
		if (subcnt < 0)
			return subcnt;
		i += subcnt - 1;
		sub->used = 1;
	}

	discard_unused_subtrees(it);

	/*
	 * Then write out the tree object for this level.
	 */
	strbuf_init(&buffer, 8192);

	for (i = 0; i < entries; i++) {
		struct cache_entry *ce = cache[i];
		struct cache_tree_sub *sub;
		const char *path, *slash;
		int pathlen, entlen;
		const unsigned char *sha1;
		unsigned mode;

		path = ce->name;
		pathlen = ce_namelen(ce);
		if (pathlen <= baselen || memcmp(base, path, baselen))
			break; /* at the end of this level */

		slash = strchr(path + baselen, '/');
		if (slash) {
			entlen = slash - (path + baselen);
			sub = find_subtree(it, path + baselen, entlen, 0);
			if (!sub)
				die("cache-tree.c: '%.*s' in '%s' not found",
				    entlen, path + baselen, path);
			i += sub->cache_tree->entry_count - 1;
			sha1 = sub->cache_tree->sha1;
			mode = S_IFDIR;
		}
		else {
			sha1 = ce->sha1;
			mode = ntohl(ce->ce_mode);
			entlen = pathlen - baselen;
		}
		if (mode != S_IFGITLINK && !missing_ok && !has_sha1_file(sha1))
			return error("invalid object %s", sha1_to_hex(sha1));

		if (!ce->ce_mode)
			continue; /* entry being removed */

		strbuf_grow(&buffer, entlen + 100);
		strbuf_addf(&buffer, "%o %.*s%c", mode, entlen, path + baselen, '\0');
		strbuf_add(&buffer, sha1, 20);

#if DEBUG
		fprintf(stderr, "cache-tree update-one %o %.*s\n",
			mode, entlen, path + baselen);
#endif
	}

	if (dryrun)
		hash_sha1_file(buffer.buf, buffer.len, tree_type, it->sha1);
	else
		write_sha1_file(buffer.buf, buffer.len, tree_type, it->sha1);
	strbuf_release(&buffer);
	it->entry_count = i;
#if DEBUG
	fprintf(stderr, "cache-tree update-one (%d ent, %d subtree) %s\n",
		it->entry_count, it->subtree_nr,
		sha1_to_hex(it->sha1));
#endif
	return i;
}

int cache_tree_update(struct cache_tree *it,
		      struct cache_entry **cache,
		      int entries,
		      int missing_ok,
		      int dryrun)
{
	int i;
	i = verify_cache(cache, entries);
	if (i)
		return i;
	i = update_one(it, cache, entries, "", 0, missing_ok, dryrun);
	if (i < 0)
		return i;
	return 0;
}

static void write_one(struct cache_tree *it,
		       char *path,
		       int pathlen,
			   struct strbuf *buffer)
{
	int i;

	/* One "cache-tree" entry consists of the following:
	 * path (NUL terminated)
	 * entry_count, subtree_nr ("%d %d\n")
	 * tree-sha1 (missing if invalid)
	 * subtree_nr "cache-tree" entries for subtrees.
	 */
	strbuf_grow(buffer, pathlen + 100);
	strbuf_add(buffer, path, pathlen);
	strbuf_addf(buffer, "%c%d %d\n", 0, it->entry_count, it->subtree_nr);

#if DEBUG
	if (0 <= it->entry_count)
		fprintf(stderr, "cache-tree <%.*s> (%d ent, %d subtree) %s\n",
			pathlen, path, it->entry_count, it->subtree_nr,
			sha1_to_hex(it->sha1));
	else
		fprintf(stderr, "cache-tree <%.*s> (%d subtree) invalid\n",
			pathlen, path, it->subtree_nr);
#endif

	if (0 <= it->entry_count) {
		strbuf_add(buffer, it->sha1, 20);
	}
	for (i = 0; i < it->subtree_nr; i++) {
		struct cache_tree_sub *down = it->down[i];
		if (i) {
			struct cache_tree_sub *prev = it->down[i-1];
			if (subtree_name_cmp(down->name, down->namelen,
					     prev->name, prev->namelen) <= 0)
				die("fatal - unsorted cache subtree");
		}
		write_one(down->cache_tree, down->name, down->namelen, buffer);
	}
}

void *cache_tree_write(struct cache_tree *root, unsigned long *size_p)
{
	char path[PATH_MAX];
	struct strbuf buffer;

	path[0] = 0;
	strbuf_init(&buffer, 0);
	write_one(root, path, 0, &buffer);
	*size_p = buffer.len;
	return strbuf_detach(&buffer);
}

static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)
{
	const char *buf = *buffer;
	unsigned long size = *size_p;
	const char *cp;
	char *ep;
	struct cache_tree *it;
	int i, subtree_nr;

	it = NULL;
	/* skip name, but make sure name exists */
	while (size && *buf) {
		size--;
		buf++;
	}
	if (!size)
		goto free_return;
	buf++; size--;
	it = cache_tree();

	cp = buf;
	it->entry_count = strtol(cp, &ep, 10);
	if (cp == ep)
		goto free_return;
	cp = ep;
	subtree_nr = strtol(cp, &ep, 10);
	if (cp == ep)
		goto free_return;
	while (size && *buf && *buf != '\n') {
		size--;
		buf++;
	}
	if (!size)
		goto free_return;
	buf++; size--;
	if (0 <= it->entry_count) {
		if (size < 20)
			goto free_return;
		hashcpy(it->sha1, (const unsigned char*)buf);
		buf += 20;
		size -= 20;
	}

#if DEBUG
	if (0 <= it->entry_count)
		fprintf(stderr, "cache-tree <%s> (%d ent, %d subtree) %s\n",
			*buffer, it->entry_count, subtree_nr,
			sha1_to_hex(it->sha1));
	else
		fprintf(stderr, "cache-tree <%s> (%d subtrees) invalid\n",
			*buffer, subtree_nr);
#endif

	/*
	 * Just a heuristic -- we do not add directories that often but
	 * we do not want to have to extend it immediately when we do,
	 * hence +2.
	 */
	it->subtree_alloc = subtree_nr + 2;
	it->down = xcalloc(it->subtree_alloc, sizeof(struct cache_tree_sub *));
	for (i = 0; i < subtree_nr; i++) {
		/* read each subtree */
		struct cache_tree *sub;
		struct cache_tree_sub *subtree;
		const char *name = buf;

		sub = read_one(&buf, &size);
		if (!sub)
			goto free_return;
		subtree = cache_tree_sub(it, name);
		subtree->cache_tree = sub;
	}
	if (subtree_nr != it->subtree_nr)
		die("cache-tree: internal error");
	*buffer = buf;
	*size_p = size;
	return it;

 free_return:
	cache_tree_free(&it);
	return NULL;
}

struct cache_tree *cache_tree_read(const char *buffer, unsigned long size)
{
	if (buffer[0])
		return NULL; /* not the whole tree */
	return read_one(&buffer, &size);
}

struct cache_tree *cache_tree_find(struct cache_tree *it, const char *path)
{
	while (*path) {
		const char *slash;
		struct cache_tree_sub *sub;

		slash = strchr(path, '/');
		if (!slash)
			slash = path + strlen(path);
		/* between path and slash is the name of the
		 * subtree to look for.
		 */
		sub = find_subtree(it, path, slash - path, 0);
		if (!sub)
			return NULL;
		it = sub->cache_tree;
		if (slash)
			while (*slash && *slash == '/')
				slash++;
		if (!slash || !*slash)
			return it; /* prefix ended with slashes */
		path = slash;
	}
	return it;
}
Commit	Line	Data
74986462 JH	1	#include "cache.h"
	2	#include "tree.h"
	3	#include "cache-tree.h"
	4
4903161f	5	#ifndef DEBUG
74986462	6	#define DEBUG 0
4903161f	7	#endif
74986462 JH	8
	9	struct cache_tree *cache_tree(void)
	10	{
	11	struct cache_tree *it = xcalloc(1, sizeof(struct cache_tree));
	12	it->entry_count = -1;
	13	return it;
	14	}
	15
bad68ec9	16	void cache_tree_free(struct cache_tree **it_p)
74986462 JH	17	{
74986462 JH	18	int i;
bad68ec9	19	struct cache_tree it = it_p;
74986462 JH	20
	21	if (!it)
	22	return;
	23	for (i = 0; i < it->subtree_nr; i++)
61fa3097 JH	24	if (it->down[i])
61fa3097 JH	25	cache_tree_free(&it->down[i]->cache_tree);
74986462 JH	26	free(it->down);
74986462 JH	27	free(it);
bad68ec9	28	*it_p = NULL;
74986462 JH	29	}
74986462 JH	30
61fa3097 JH	31	static int subtree_name_cmp(const char *one, int onelen,
	32	const char *two, int twolen)
	33	{
	34	if (onelen < twolen)
	35	return -1;
	36	if (twolen < onelen)
	37	return 1;
	38	return memcmp(one, two, onelen);
	39	}
	40
	41	static int subtree_pos(struct cache_tree it, const char path, int pathlen)
	42	{
	43	struct cache_tree_sub **down = it->down;
	44	int lo, hi;
	45	lo = 0;
	46	hi = it->subtree_nr;
	47	while (lo < hi) {
	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);
	52	if (!cmp)
	53	return mi;
	54	if (cmp < 0)
	55	hi = mi;
	56	else
	57	lo = mi + 1;
	58	}
	59	return -lo-1;
	60	}
	61
74986462 JH	62	static struct cache_tree_sub find_subtree(struct cache_tree it,
	63	const char *path,
	64	int pathlen,
	65	int create)
	66	{
74986462	67	struct cache_tree_sub *down;
61fa3097 JH	68	int pos = subtree_pos(it, path, pathlen);
	69	if (0 <= pos)
	70	return it->down[pos];
74986462 JH	71	if (!create)
74986462 JH	72	return NULL;
61fa3097 JH	73
61fa3097 JH	74	pos = -pos-1;
74986462 JH	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 *
	78	sizeof(*it->down));
	79	}
61fa3097 JH	80	it->subtree_nr++;
61fa3097 JH	81
74986462	82	down = xmalloc(sizeof(*down) + pathlen + 1);
61fa3097	83	down->cache_tree = NULL;
74986462 JH	84	down->namelen = pathlen;
74986462 JH	85	memcpy(down->name, path, pathlen);
61fa3097 JH	86	down->name[pathlen] = 0;
	87
	88	if (pos < it->subtree_nr)
	89	memmove(it->down + pos + 1,
	90	it->down + pos,
	91	sizeof(down) * (it->subtree_nr - pos - 1));
	92	it->down[pos] = down;
74986462 JH	93	return down;
	94	}
	95
7927a55d JH	96	struct cache_tree_sub cache_tree_sub(struct cache_tree it, const char *path)
	97	{
	98	int pathlen = strlen(path);
	99	return find_subtree(it, path, pathlen, 1);
	100	}
	101
74986462 JH	102	void cache_tree_invalidate_path(struct cache_tree it, const char path)
	103	{
	104	/* a/b/c
	105	* ==> invalidate self
	106	* ==> find "a", have it invalidate "b/c"
	107	* a
	108	* ==> invalidate self
	109	* ==> if "a" exists as a subtree, remove it.
	110	*/
	111	const char *slash;
	112	int namelen;
	113	struct cache_tree_sub *down;
	114
00703e6d JH	115	#if DEBUG
	116	fprintf(stderr, "cache-tree invalidate <%s>\n", path);
	117	#endif
	118
74986462 JH	119	if (!it)
	120	return;
	121	slash = strchr(path, '/');
	122	it->entry_count = -1;
	123	if (!slash) {
61fa3097	124	int pos;
74986462	125	namelen = strlen(path);
61fa3097 JH	126	pos = subtree_pos(it, path, namelen);
	127	if (0 <= pos) {
	128	cache_tree_free(&it->down[pos]->cache_tree);
	129	free(it->down[pos]);
74986462 JH	130	/* 0 1 2 3 4 5
74986462 JH	131	* ^ ^subtree_nr = 6
61fa3097	132	* pos
74986462	133	* move 4 and 5 up one place (2 entries)
61fa3097	134	* 2 = 6 - 3 - 1 = subtree_nr - pos - 1
74986462	135	*/
61fa3097	136	memmove(it->down+pos, it->down+pos+1,
74986462	137	sizeof(struct cache_tree_sub )
61fa3097	138	(it->subtree_nr - pos - 1));
74986462 JH	139	it->subtree_nr--;
	140	}
	141	return;
	142	}
	143	namelen = slash - path;
	144	down = find_subtree(it, path, namelen, 0);
	145	if (down)
	146	cache_tree_invalidate_path(down->cache_tree, slash + 1);
	147	}
	148
	149	static int verify_cache(struct cache_entry **cache,
	150	int entries)
	151	{
	152	int i, funny;
	153
	154	/* Verify that the tree is merged */
	155	funny = 0;
	156	for (i = 0; i < entries; i++) {
	157	struct cache_entry *ce = cache[i];
	158	if (ce_stage(ce)) {
	159	if (10 < ++funny) {
	160	fprintf(stderr, "...\n");
	161	break;
	162	}
	163	fprintf(stderr, "%s: unmerged (%s)\n",
	164	ce->name, sha1_to_hex(ce->sha1));
	165	}
	166	}
	167	if (funny)
	168	return -1;
	169
	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
	172	* stage 0 entries.
	173	*/
	174	funny = 0;
	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.
	179	*/
	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] == '/') {
	186	if (10 < ++funny) {
	187	fprintf(stderr, "...\n");
	188	break;
	189	}
	190	fprintf(stderr, "You have both %s and %s\n",
	191	this_name, next_name);
	192	}
	193	}
	194	if (funny)
	195	return -1;
	196	return 0;
	197	}
	198
	199	static void discard_unused_subtrees(struct cache_tree *it)
	200	{
	201	struct cache_tree_sub **down = it->down;
	202	int nr = it->subtree_nr;
203	int dst, src;
204	for (dst = src = 0; src < nr; src++) {
205	struct cache_tree_sub *s = down[src];
206	if (s->used)
207	down[dst++] = s;
208	else {
bad68ec9	209	cache_tree_free(&s->cache_tree);
74986462 JH	210	free(s);
	211	it->subtree_nr--;
	212	}
	213	}
	214	}
	215
bad68ec9 JH	216	int cache_tree_fully_valid(struct cache_tree *it)
	217	{
	218	int i;
	219	if (!it)
	220	return 0;
	221	if (it->entry_count < 0 \|\| !has_sha1_file(it->sha1))
	222	return 0;
	223	for (i = 0; i < it->subtree_nr; i++) {
	224	if (!cache_tree_fully_valid(it->down[i]->cache_tree))
	225	return 0;
	226	}
	227	return 1;
	228	}
	229
74986462 JH	230	static int update_one(struct cache_tree *it,
	231	struct cache_entry **cache,
	232	int entries,
	233	const char *base,
	234	int baselen,
2956dd3b JH	235	int missing_ok,
2956dd3b JH	236	int dryrun)
74986462	237	{
5242bcbb	238	struct strbuf buffer;
74986462 JH	239	int i;
74986462 JH	240
dd0c34c4	241	if (0 <= it->entry_count && has_sha1_file(it->sha1))
74986462 JH	242	return it->entry_count;
	243
	244	/*
	245	* We first scan for subtrees and update them; we start by
	246	* marking existing subtrees -- the ones that are unmarked
	247	* should not be in the result.
	248	*/
	249	for (i = 0; i < it->subtree_nr; i++)
	250	it->down[i]->used = 0;
	251
	252	/*
	253	* Find the subtrees and update them.
	254	*/
	255	for (i = 0; i < entries; i++) {
	256	struct cache_entry *ce = cache[i];
	257	struct cache_tree_sub *sub;
	258	const char path, slash;
	259	int pathlen, sublen, subcnt;
	260
	261	path = ce->name;
	262	pathlen = ce_namelen(ce);
	263	if (pathlen <= baselen \|\| memcmp(base, path, baselen))
	264	break; /* at the end of this level */
	265
	266	slash = strchr(path + baselen, '/');
	267	if (!slash)
	268	continue;
	269	/*
	270	* a/bbb/c (base = a/, slash = /c)
	271	* ==>
	272	* path+baselen = bbb/c, sublen = 3
	273	*/
	274	sublen = slash - (path + baselen);
	275	sub = find_subtree(it, path + baselen, sublen, 1);
	276	if (!sub->cache_tree)
	277	sub->cache_tree = cache_tree();
	278	subcnt = update_one(sub->cache_tree,
	279	cache + i, entries - i,
	280	path,
	281	baselen + sublen + 1,
2956dd3b JH	282	missing_ok,
2956dd3b JH	283	dryrun);
3d12d0cf JS	284	if (subcnt < 0)
3d12d0cf JS	285	return subcnt;
74986462 JH	286	i += subcnt - 1;
	287	sub->used = 1;
	288	}
	289
	290	discard_unused_subtrees(it);
	291
	292	/*
	293	* Then write out the tree object for this level.
	294	*/
f1696ee3	295	strbuf_init(&buffer, 8192);
74986462 JH	296
	297	for (i = 0; i < entries; i++) {
	298	struct cache_entry *ce = cache[i];
	299	struct cache_tree_sub *sub;
	300	const char path, slash;
	301	int pathlen, entlen;
	302	const unsigned char *sha1;
	303	unsigned mode;
	304
	305	path = ce->name;
	306	pathlen = ce_namelen(ce);
	307	if (pathlen <= baselen \|\| memcmp(base, path, baselen))
	308	break; /* at the end of this level */
	309
	310	slash = strchr(path + baselen, '/');
	311	if (slash) {
	312	entlen = slash - (path + baselen);
	313	sub = find_subtree(it, path + baselen, entlen, 0);
	314	if (!sub)
	315	die("cache-tree.c: '%.*s' in '%s' not found",
	316	entlen, path + baselen, path);
	317	i += sub->cache_tree->entry_count - 1;
	318	sha1 = sub->cache_tree->sha1;
	319	mode = S_IFDIR;
	320	}
	321	else {
	322	sha1 = ce->sha1;
	323	mode = ntohl(ce->ce_mode);
	324	entlen = pathlen - baselen;
	325	}
302b9282	326	if (mode != S_IFGITLINK && !missing_ok && !has_sha1_file(sha1))
74986462 JH	327	return error("invalid object %s", sha1_to_hex(sha1));
	328
	329	if (!ce->ce_mode)
	330	continue; /* entry being removed */
	331
5242bcbb PH	332	strbuf_grow(&buffer, entlen + 100);
	333	strbuf_addf(&buffer, "%o %.*s%c", mode, entlen, path + baselen, '\0');
	334	strbuf_add(&buffer, sha1, 20);
74986462 JH	335
74986462 JH	336	#if DEBUG
00703e6d	337	fprintf(stderr, "cache-tree update-one %o %.*s\n",
74986462 JH	338	mode, entlen, path + baselen);
	339	#endif
	340	}
	341
abdc3fc8	342	if (dryrun)
5242bcbb	343	hash_sha1_file(buffer.buf, buffer.len, tree_type, it->sha1);
2956dd3b	344	else
5242bcbb PH	345	write_sha1_file(buffer.buf, buffer.len, tree_type, it->sha1);
5242bcbb PH	346	strbuf_release(&buffer);
74986462 JH	347	it->entry_count = i;
74986462 JH	348	#if DEBUG
00703e6d	349	fprintf(stderr, "cache-tree update-one (%d ent, %d subtree) %s\n",
74986462 JH	350	it->entry_count, it->subtree_nr,
	351	sha1_to_hex(it->sha1));
	352	#endif
	353	return i;
	354	}
	355
	356	int cache_tree_update(struct cache_tree *it,
	357	struct cache_entry **cache,
	358	int entries,
2956dd3b JH	359	int missing_ok,
2956dd3b JH	360	int dryrun)
74986462 JH	361	{
	362	int i;
	363	i = verify_cache(cache, entries);
	364	if (i)
	365	return i;
2956dd3b	366	i = update_one(it, cache, entries, "", 0, missing_ok, dryrun);
74986462 JH	367	if (i < 0)
	368	return i;
	369	return 0;
	370	}
	371
5242bcbb	372	static void write_one(struct cache_tree *it,
74986462 JH	373	char *path,
74986462 JH	374	int pathlen,
5242bcbb	375	struct strbuf *buffer)
74986462 JH	376	{
	377	int i;
	378
	379	/* One "cache-tree" entry consists of the following:
	380	* path (NUL terminated)
	381	* entry_count, subtree_nr ("%d %d\n")
	382	* tree-sha1 (missing if invalid)
	383	* subtree_nr "cache-tree" entries for subtrees.
	384	*/
5242bcbb PH	385	strbuf_grow(buffer, pathlen + 100);
	386	strbuf_add(buffer, path, pathlen);
	387	strbuf_addf(buffer, "%c%d %d\n", 0, it->entry_count, it->subtree_nr);
74986462 JH	388
	389	#if DEBUG
	390	if (0 <= it->entry_count)
	391	fprintf(stderr, "cache-tree <%.*s> (%d ent, %d subtree) %s\n",
	392	pathlen, path, it->entry_count, it->subtree_nr,
	393	sha1_to_hex(it->sha1));
	394	else
	395	fprintf(stderr, "cache-tree <%.*s> (%d subtree) invalid\n",
	396	pathlen, path, it->subtree_nr);
	397	#endif
	398
	399	if (0 <= it->entry_count) {
5242bcbb	400	strbuf_add(buffer, it->sha1, 20);
74986462 JH	401	}
	402	for (i = 0; i < it->subtree_nr; i++) {
	403	struct cache_tree_sub *down = it->down[i];
61fa3097 JH	404	if (i) {
	405	struct cache_tree_sub *prev = it->down[i-1];
	406	if (subtree_name_cmp(down->name, down->namelen,
	407	prev->name, prev->namelen) <= 0)
	408	die("fatal - unsorted cache subtree");
	409	}
5242bcbb	410	write_one(down->cache_tree, down->name, down->namelen, buffer);
74986462	411	}
74986462 JH	412	}
74986462 JH	413
bad68ec9	414	void cache_tree_write(struct cache_tree root, unsigned long *size_p)
74986462 JH	415	{
74986462 JH	416	char path[PATH_MAX];
5242bcbb	417	struct strbuf buffer;
74986462	418
74986462	419	path[0] = 0;
f1696ee3	420	strbuf_init(&buffer, 0);
5242bcbb PH	421	write_one(root, path, 0, &buffer);
	422	*size_p = buffer.len;
	423	return strbuf_detach(&buffer);
74986462 JH	424	}
	425
	426	static struct cache_tree read_one(const char buffer, unsigned long size_p)
	427	{
	428	const char buf = buffer;
	429	unsigned long size = *size_p;
0111ea38 JS	430	const char *cp;
0111ea38 JS	431	char *ep;
74986462 JH	432	struct cache_tree *it;
	433	int i, subtree_nr;
	434
	435	it = NULL;
	436	/* skip name, but make sure name exists */
	437	while (size && *buf) {
	438	size--;
	439	buf++;
	440	}
	441	if (!size)
	442	goto free_return;
	443	buf++; size--;
	444	it = cache_tree();
0111ea38 JS	445
	446	cp = buf;
	447	it->entry_count = strtol(cp, &ep, 10);
	448	if (cp == ep)
	449	goto free_return;
	450	cp = ep;
	451	subtree_nr = strtol(cp, &ep, 10);
	452	if (cp == ep)
74986462 JH	453	goto free_return;
	454	while (size && buf && buf != '\n') {
	455	size--;
	456	buf++;
	457	}
	458	if (!size)
	459	goto free_return;
	460	buf++; size--;
	461	if (0 <= it->entry_count) {
	462	if (size < 20)
	463	goto free_return;
63daae47	464	hashcpy(it->sha1, (const unsigned char*)buf);
74986462 JH	465	buf += 20;
	466	size -= 20;
	467	}
	468
	469	#if DEBUG
	470	if (0 <= it->entry_count)
	471	fprintf(stderr, "cache-tree <%s> (%d ent, %d subtree) %s\n",
	472	*buffer, it->entry_count, subtree_nr,
	473	sha1_to_hex(it->sha1));
	474	else
	475	fprintf(stderr, "cache-tree <%s> (%d subtrees) invalid\n",
	476	*buffer, subtree_nr);
	477	#endif
	478
	479	/*
	480	* Just a heuristic -- we do not add directories that often but
	481	* we do not want to have to extend it immediately when we do,
	482	* hence +2.
	483	*/
	484	it->subtree_alloc = subtree_nr + 2;
	485	it->down = xcalloc(it->subtree_alloc, sizeof(struct cache_tree_sub *));
	486	for (i = 0; i < subtree_nr; i++) {
	487	/* read each subtree */
	488	struct cache_tree *sub;
61fa3097	489	struct cache_tree_sub *subtree;
74986462	490	const char *name = buf;
7927a55d	491
74986462 JH	492	sub = read_one(&buf, &size);
	493	if (!sub)
	494	goto free_return;
7927a55d	495	subtree = cache_tree_sub(it, name);
61fa3097	496	subtree->cache_tree = sub;
74986462 JH	497	}
	498	if (subtree_nr != it->subtree_nr)
	499	die("cache-tree: internal error");
	500	*buffer = buf;
	501	*size_p = size;
	502	return it;
	503
	504	free_return:
bad68ec9	505	cache_tree_free(&it);
74986462 JH	506	return NULL;
	507	}
	508
bad68ec9	509	struct cache_tree cache_tree_read(const char buffer, unsigned long size)
74986462	510	{
bad68ec9	511	if (buffer[0])
74986462	512	return NULL; /* not the whole tree */
74986462 JH	513	return read_one(&buffer, &size);
74986462 JH	514	}
6bd20358 JH	515
	516	struct cache_tree cache_tree_find(struct cache_tree it, const char *path)
	517	{
	518	while (*path) {
	519	const char *slash;
	520	struct cache_tree_sub *sub;
	521
	522	slash = strchr(path, '/');
	523	if (!slash)
	524	slash = path + strlen(path);
	525	/* between path and slash is the name of the
	526	* subtree to look for.
	527	*/
	528	sub = find_subtree(it, path, slash - path, 0);
	529	if (!sub)
	530	return NULL;
	531	it = sub->cache_tree;
	532	if (slash)
	533	while (slash && slash == '/')
	534	slash++;
	535	if (!slash \|\| !*slash)
	536	return it; /* prefix ended with slashes */
	537	path = slash;
	538	}
	539	return it;
	540	}