diff options
Diffstat (limited to 'tree-walk.c')
| -rw-r--r-- | tree-walk.c | 209 |
1 files changed, 209 insertions, 0 deletions
diff --git a/tree-walk.c b/tree-walk.c new file mode 100644 index 0000000000..cbb24eb3f6 --- /dev/null +++ b/tree-walk.c @@ -0,0 +1,209 @@ +#include "cache.h" +#include "tree-walk.h" +#include "tree.h" + +static const char *get_mode(const char *str, unsigned int *modep) +{ + unsigned char c; + unsigned int mode = 0; + + while ((c = *str++) != ' ') { + if (c < '0' || c > '7') + return NULL; + mode = (mode << 3) + (c - '0'); + } + *modep = mode; + return str; +} + +static void decode_tree_entry(struct tree_desc *desc, const void *buf, unsigned long size) +{ + const char *path; + unsigned int mode, len; + + path = get_mode(buf, &mode); + if (!path) + die("corrupt tree file"); + len = strlen(path) + 1; + + /* Initialize the descriptor entry */ + desc->entry.path = path; + desc->entry.mode = mode; + desc->entry.sha1 = (const unsigned char *)(path + len); +} + +void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size) +{ + desc->buffer = buffer; + desc->size = size; + if (size) + decode_tree_entry(desc, buffer, size); +} + +void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1) +{ + unsigned long size = 0; + void *buf = NULL; + + if (sha1) { + buf = read_object_with_reference(sha1, tree_type, &size, NULL); + if (!buf) + die("unable to read tree %s", sha1_to_hex(sha1)); + } + init_tree_desc(desc, buf, size); + return buf; +} + +static int entry_compare(struct name_entry *a, struct name_entry *b) +{ + return base_name_compare( + a->path, tree_entry_len(a->path, a->sha1), a->mode, + b->path, tree_entry_len(b->path, b->sha1), b->mode); +} + +static void entry_clear(struct name_entry *a) +{ + memset(a, 0, sizeof(*a)); +} + +static void entry_extract(struct tree_desc *t, struct name_entry *a) +{ + *a = t->entry; +} + +void update_tree_entry(struct tree_desc *desc) +{ + const void *buf = desc->buffer; + const unsigned char *end = desc->entry.sha1 + 20; + unsigned long size = desc->size; + unsigned long len = end - (const unsigned char *)buf; + + if (size < len) + die("corrupt tree file"); + buf = end; + size -= len; + desc->buffer = buf; + desc->size = size; + if (size) + decode_tree_entry(desc, buf, size); +} + +int tree_entry(struct tree_desc *desc, struct name_entry *entry) +{ + if (!desc->size) + return 0; + + *entry = desc->entry; + update_tree_entry(desc); + return 1; +} + +void traverse_trees(int n, struct tree_desc *t, const char *base, traverse_callback_t callback) +{ + struct name_entry *entry = xmalloc(n*sizeof(*entry)); + + for (;;) { + unsigned long mask = 0; + int i, last; + + last = -1; + for (i = 0; i < n; i++) { + if (!t[i].size) + continue; + entry_extract(t+i, entry+i); + if (last >= 0) { + int cmp = entry_compare(entry+i, entry+last); + + /* + * Is the new name bigger than the old one? + * Ignore it + */ + if (cmp > 0) + continue; + /* + * Is the new name smaller than the old one? + * Ignore all old ones + */ + if (cmp < 0) + mask = 0; + } + mask |= 1ul << i; + last = i; + } + if (!mask) + break; + + /* + * Update the tree entries we've walked, and clear + * all the unused name-entries. + */ + for (i = 0; i < n; i++) { + if (mask & (1ul << i)) { + update_tree_entry(t+i); + continue; + } + entry_clear(entry + i); + } + callback(n, mask, entry, base); + } + free(entry); +} + +static int find_tree_entry(struct tree_desc *t, const char *name, unsigned char *result, unsigned *mode) +{ + int namelen = strlen(name); + while (t->size) { + const char *entry; + const unsigned char *sha1; + int entrylen, cmp; + + sha1 = tree_entry_extract(t, &entry, mode); + update_tree_entry(t); + entrylen = tree_entry_len(entry, sha1); + if (entrylen > namelen) + continue; + cmp = memcmp(name, entry, entrylen); + if (cmp > 0) + continue; + if (cmp < 0) + break; + if (entrylen == namelen) { + hashcpy(result, sha1); + return 0; + } + if (name[entrylen] != '/') + continue; + if (!S_ISDIR(*mode)) + break; + if (++entrylen == namelen) { + hashcpy(result, sha1); + return 0; + } + return get_tree_entry(sha1, name + entrylen, result, mode); + } + return -1; +} + +int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned char *sha1, unsigned *mode) +{ + int retval; + void *tree; + unsigned long size; + struct tree_desc t; + unsigned char root[20]; + + tree = read_object_with_reference(tree_sha1, tree_type, &size, root); + if (!tree) + return -1; + + if (name[0] == '\0') { + hashcpy(sha1, root); + return 0; + } + + init_tree_desc(&t, tree, size); + retval = find_tree_entry(&t, name, sha1, mode); + free(tree); + return retval; +} + |