#include "tree.h"
#include "cache-tree.h"
+#ifndef DEBUG
#define DEBUG 0
+#endif
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,
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
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;
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;
int i;
- if (0 <= it->entry_count)
+ if (0 <= it->entry_count && has_sha1_file(it->sha1))
return it->entry_count;
/*
cache + i, entries - i,
path,
baselen + sublen + 1,
- missing_ok);
+ missing_ok,
+ dryrun);
+ if (subcnt < 0)
+ return subcnt;
i += subcnt - 1;
sub->used = 1;
}
offset += sprintf(buffer + offset,
"%o %.*s", mode, entlen, path + baselen);
buffer[offset++] = 0;
- memcpy(buffer + offset, sha1, 20);
+ hashcpy((unsigned char*)buffer + offset, sha1);
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)
+ hash_sha1_file(buffer, offset, tree_type, it->sha1);
+ 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
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;
#endif
if (0 <= it->entry_count) {
- memcpy(buffer + *offset, it->sha1, 20);
+ hashcpy((unsigned char*)buffer + *offset, it->sha1);
*offset += 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");
+ }
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;
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--;
if (0 <= it->entry_count) {
if (size < 20)
goto free_return;
- memcpy(it->sha1, buf, 20);
+ hashcpy(it->sha1, (unsigned char*)buf);
buf += 20;
size -= 20;
}
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");
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)
+struct cache_tree *cache_tree_find(struct cache_tree *it, const char *path)
{
- char path[PATH_MAX];
- unsigned long size = 0;
- void *buf, *buffer;
- int fd, ret = -1;
+ while (*path) {
+ const char *slash;
+ struct cache_tree_sub *sub;
- 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;
+ 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;
}
- ret = 0;
-
- fail:
- close(fd);
- free(buffer);
- if (ret)
- unlink(path);
- return ret;
+ return it;
}