X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=cache-tree.c;h=a880c97b38e7d36f2a45a1743e9565cc1e58280d;hb=2b11e3170e919866c7f5554dd4089289a1bb6726;hp=b34b0bc3177de67d401f2a91d9355f6751e3d0d4;hpb=dd0c34c46bdda0c20fd92d00516e711a4c9f7837;p=git.git

diff --git a/cache-tree.c b/cache-tree.c
index b34b0bc3..a880c97b 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -11,16 +11,50 @@ struct cache_tree *cache_tree(void)
 	return it;
 }
 
-void cache_tree_free(struct cache_tree *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++)
-		cache_tree_free(it->down[i]->cache_tree);
+		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,
@@ -28,30 +62,41 @@ static struct cache_tree_sub *find_subtree(struct cache_tree *it,
 					   int pathlen,
 					   int create)
 {
-	int i;
 	struct cache_tree_sub *down;
-	for (i = 0; i < it->subtree_nr; i++) {
-		down = it->down[i];
-		if (down->namelen == pathlen &&
-		    !memcmp(down->name, path, pathlen))
-			return 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; /* cache_tree(); */
+	down->cache_tree = NULL;
 	down->namelen = pathlen;
 	memcpy(down->name, path, pathlen);
-	down->name[pathlen] = 0; /* not strictly needed */
-	it->down[it->subtree_nr++] = down;
+	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
@@ -65,30 +110,30 @@ void cache_tree_invalidate_path(struct cache_tree *it, const char *path)
 	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 i;
+		int pos;
 		namelen = strlen(path);
-		for (i = 0; i < it->subtree_nr; i++) {
-			if (it->down[i]->namelen == namelen &&
-			    !memcmp(it->down[i]->name, path, namelen))
-				break;
-		}
-		if (i < it->subtree_nr) {
-			cache_tree_free(it->down[i]->cache_tree);
-			free(it->down[i]);
+		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
-			 *       i
+			 *       pos
 			 * move 4 and 5 up one place (2 entries)
-			 * 2 = 6 - 3 - 1 = subtree_nr - i - 1
+			 * 2 = 6 - 3 - 1 = subtree_nr - pos - 1
 			 */
-			memmove(it->down+i, it->down+i+1,
+			memmove(it->down+pos, it->down+pos+1,
 				sizeof(struct cache_tree_sub *) *
-				(it->subtree_nr - i - 1));
+				(it->subtree_nr - pos - 1));
 			it->subtree_nr--;
 		}
 		return;
@@ -159,19 +204,34 @@ static void discard_unused_subtrees(struct cache_tree *it)
 		if (s->used)
 			down[dst++] = s;
 		else {
-			cache_tree_free(s->cache_tree);
+			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 missing_ok,
+		      int dryrun)
 {
 	unsigned long size, offset;
 	char *buffer;
@@ -218,7 +278,8 @@ static int update_one(struct cache_tree *it,
 				    cache + i, entries - i,
 				    path,
 				    baselen + sublen + 1,
-				    missing_ok);
+				    missing_ok,
+				    dryrun);
 		i += subcnt - 1;
 		sub->used = 1;
 	}
@@ -278,16 +339,23 @@ static int update_one(struct cache_tree *it,
 		offset += 20;
 
 #if DEBUG
-		fprintf(stderr, "cache-tree %o %.*s\n",
+		fprintf(stderr, "cache-tree update-one %o %.*s\n",
 			mode, entlen, path + baselen);
 #endif
 	}
 
-	write_sha1_file(buffer, offset, tree_type, it->sha1);
+	if (dryrun) {
+		unsigned char hdr[200];
+		int hdrlen;
+		write_sha1_file_prepare(buffer, offset, tree_type, it->sha1,
+					hdr, &hdrlen);
+	}
+	else
+		write_sha1_file(buffer, offset, tree_type, it->sha1);
 	free(buffer);
 	it->entry_count = i;
 #if DEBUG
-	fprintf(stderr, "cache-tree (%d ent, %d subtree) %s\n",
+	fprintf(stderr, "cache-tree update-one (%d ent, %d subtree) %s\n",
 		it->entry_count, it->subtree_nr,
 		sha1_to_hex(it->sha1));
 #endif
@@ -297,13 +365,14 @@ static int update_one(struct cache_tree *it,
 int cache_tree_update(struct cache_tree *it,
 		      struct cache_entry **cache,
 		      int entries,
-		      int missing_ok)
+		      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);
+	i = update_one(it, cache, entries, "", 0, missing_ok, dryrun);
 	if (i < 0)
 		return i;
 	return 0;
@@ -348,31 +417,35 @@ static void *write_one(struct cache_tree *it,
 	}
 	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");
+		}
 		buffer = write_one(down->cache_tree, down->name, down->namelen,
 				   buffer, size, offset);
 	}
 	return buffer;
 }
 
-static void *cache_tree_write(const unsigned char *cache_sha1,
-			      struct cache_tree *root,
-			      unsigned long *offset_p)
+void *cache_tree_write(struct cache_tree *root, unsigned long *size_p)
 {
 	char path[PATH_MAX];
 	unsigned long size = 8192;
 	char *buffer = xmalloc(size);
 
-	/* the cache checksum of the corresponding index file. */
-	memcpy(buffer, cache_sha1, 20);
-	*offset_p = 20;
+	*size_p = 0;
 	path[0] = 0;
-	return write_one(root, path, 0, buffer, &size, offset_p);
+	return write_one(root, path, 0, buffer, &size, size_p);
 }
 
 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;
 
@@ -386,7 +459,14 @@ static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)
 		goto free_return;
 	buf++; size--;
 	it = cache_tree();
-	if (sscanf(buf, "%d %d\n", &it->entry_count, &subtree_nr) != 2)
+
+	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--;
@@ -423,14 +503,14 @@ static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)
 	for (i = 0; i < subtree_nr; i++) {
 		/* read each subtree */
 		struct cache_tree *sub;
+		struct cache_tree_sub *subtree;
 		const char *name = buf;
-		int namelen;
+
 		sub = read_one(&buf, &size);
 		if (!sub)
 			goto free_return;
-		namelen = strlen(name);
-		it->down[i] = find_subtree(it, name, namelen, 1);
-		it->down[i]->cache_tree = sub;
+		subtree = cache_tree_sub(it, name);
+		subtree->cache_tree = sub;
 	}
 	if (subtree_nr != it->subtree_nr)
 		die("cache-tree: internal error");
@@ -439,81 +519,13 @@ static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)
 	return it;
 
  free_return:
-	cache_tree_free(it);
+	cache_tree_free(&it);
 	return NULL;
 }
 
-static struct cache_tree *cache_tree_read(unsigned char *sha1,
-					  const char *buffer,
-					  unsigned long size)
+struct cache_tree *cache_tree_read(const char *buffer, unsigned long size)
 {
-	/* check the cache-tree matches the index */
-	if (memcmp(buffer, sha1, 20))
-		return NULL; /* checksum mismatch */
-	if (buffer[20])
+	if (buffer[0])
 		return NULL; /* not the whole tree */
-	buffer += 20;
-	size -= 20;
 	return read_one(&buffer, &size);
 }
-
-struct cache_tree *read_cache_tree(unsigned char *sha1)
-{
-	int fd;
-	struct stat st;
-	char path[PATH_MAX];
-	unsigned long size = 0;
-	void *map;
-	struct cache_tree *it;
-
-	sprintf(path, "%s.aux", get_index_file());
-	fd = open(path, O_RDONLY);
-	if (fd < 0)
-		return cache_tree();
-
-	if (fstat(fd, &st))
-		return cache_tree();
-	size = st.st_size;
-	map = mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);
-	close(fd);
-	if (map == MAP_FAILED)
-		return cache_tree();
-	it = cache_tree_read(sha1, map, size);
-	munmap(map, size);
-	if (!it)
-		return cache_tree();
-	return it;
-}
-
-int write_cache_tree(const unsigned char *sha1, struct cache_tree *root)
-{
-	char path[PATH_MAX];
-	unsigned long size = 0;
-	void *buf, *buffer;
-	int fd, ret = -1;
-
-	sprintf(path, "%s.aux", get_index_file());
-	if (!root) {
-		unlink(path);
-		return -1;
-	}
-	fd = open(path, O_WRONLY|O_CREAT, 0666);
-	if (fd < 0)
-		return -1;
-	buffer = buf = cache_tree_write(sha1, root, &size);
-	while (size) {
-		int written = xwrite(fd, buf, size);
-		if (written <= 0)
-			goto fail;
-		buf += written;
-		size -= written;
-	}
-	ret = 0;
-
- fail:
-	close(fd);
-	free(buffer);
-	if (ret)
-		unlink(path);
-	return ret;
-}