Merge branch 'maint' of git://repo.or.cz/git-gui into maint
[git/spearce.git] / tree-walk.c
blobcbb24eb3f663cd0370f528d983a2266a55b91c4f
1 #include "cache.h"
2 #include "tree-walk.h"
3 #include "tree.h"
5 static const char *get_mode(const char *str, unsigned int *modep)
7 unsigned char c;
8 unsigned int mode = 0;
10 while ((c = *str++) != ' ') {
11 if (c < '0' || c > '7')
12 return NULL;
13 mode = (mode << 3) + (c - '0');
15 *modep = mode;
16 return str;
19 static void decode_tree_entry(struct tree_desc *desc, const void *buf, unsigned long size)
21 const char *path;
22 unsigned int mode, len;
24 path = get_mode(buf, &mode);
25 if (!path)
26 die("corrupt tree file");
27 len = strlen(path) + 1;
29 /* Initialize the descriptor entry */
30 desc->entry.path = path;
31 desc->entry.mode = mode;
32 desc->entry.sha1 = (const unsigned char *)(path + len);
35 void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size)
37 desc->buffer = buffer;
38 desc->size = size;
39 if (size)
40 decode_tree_entry(desc, buffer, size);
43 void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
45 unsigned long size = 0;
46 void *buf = NULL;
48 if (sha1) {
49 buf = read_object_with_reference(sha1, tree_type, &size, NULL);
50 if (!buf)
51 die("unable to read tree %s", sha1_to_hex(sha1));
53 init_tree_desc(desc, buf, size);
54 return buf;
57 static int entry_compare(struct name_entry *a, struct name_entry *b)
59 return base_name_compare(
60 a->path, tree_entry_len(a->path, a->sha1), a->mode,
61 b->path, tree_entry_len(b->path, b->sha1), b->mode);
64 static void entry_clear(struct name_entry *a)
66 memset(a, 0, sizeof(*a));
69 static void entry_extract(struct tree_desc *t, struct name_entry *a)
71 *a = t->entry;
74 void update_tree_entry(struct tree_desc *desc)
76 const void *buf = desc->buffer;
77 const unsigned char *end = desc->entry.sha1 + 20;
78 unsigned long size = desc->size;
79 unsigned long len = end - (const unsigned char *)buf;
81 if (size < len)
82 die("corrupt tree file");
83 buf = end;
84 size -= len;
85 desc->buffer = buf;
86 desc->size = size;
87 if (size)
88 decode_tree_entry(desc, buf, size);
91 int tree_entry(struct tree_desc *desc, struct name_entry *entry)
93 if (!desc->size)
94 return 0;
96 *entry = desc->entry;
97 update_tree_entry(desc);
98 return 1;
101 void traverse_trees(int n, struct tree_desc *t, const char *base, traverse_callback_t callback)
103 struct name_entry *entry = xmalloc(n*sizeof(*entry));
105 for (;;) {
106 unsigned long mask = 0;
107 int i, last;
109 last = -1;
110 for (i = 0; i < n; i++) {
111 if (!t[i].size)
112 continue;
113 entry_extract(t+i, entry+i);
114 if (last >= 0) {
115 int cmp = entry_compare(entry+i, entry+last);
118 * Is the new name bigger than the old one?
119 * Ignore it
121 if (cmp > 0)
122 continue;
124 * Is the new name smaller than the old one?
125 * Ignore all old ones
127 if (cmp < 0)
128 mask = 0;
130 mask |= 1ul << i;
131 last = i;
133 if (!mask)
134 break;
137 * Update the tree entries we've walked, and clear
138 * all the unused name-entries.
140 for (i = 0; i < n; i++) {
141 if (mask & (1ul << i)) {
142 update_tree_entry(t+i);
143 continue;
145 entry_clear(entry + i);
147 callback(n, mask, entry, base);
149 free(entry);
152 static int find_tree_entry(struct tree_desc *t, const char *name, unsigned char *result, unsigned *mode)
154 int namelen = strlen(name);
155 while (t->size) {
156 const char *entry;
157 const unsigned char *sha1;
158 int entrylen, cmp;
160 sha1 = tree_entry_extract(t, &entry, mode);
161 update_tree_entry(t);
162 entrylen = tree_entry_len(entry, sha1);
163 if (entrylen > namelen)
164 continue;
165 cmp = memcmp(name, entry, entrylen);
166 if (cmp > 0)
167 continue;
168 if (cmp < 0)
169 break;
170 if (entrylen == namelen) {
171 hashcpy(result, sha1);
172 return 0;
174 if (name[entrylen] != '/')
175 continue;
176 if (!S_ISDIR(*mode))
177 break;
178 if (++entrylen == namelen) {
179 hashcpy(result, sha1);
180 return 0;
182 return get_tree_entry(sha1, name + entrylen, result, mode);
184 return -1;
187 int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned char *sha1, unsigned *mode)
189 int retval;
190 void *tree;
191 unsigned long size;
192 struct tree_desc t;
193 unsigned char root[20];
195 tree = read_object_with_reference(tree_sha1, tree_type, &size, root);
196 if (!tree)
197 return -1;
199 if (name[0] == '\0') {
200 hashcpy(sha1, root);
201 return 0;
204 init_tree_desc(&t, tree, size);
205 retval = find_tree_entry(&t, name, sha1, mode);
206 free(tree);
207 return retval;