Initialize tree descriptors with a helper function rather than by hand.
[git/git.git] / tree-walk.c
1 #include "cache.h"
2 #include "tree-walk.h"
3 #include "tree.h"
4
5 void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size)
6 {
7 desc->buffer = buffer;
8 desc->size = size;
9 }
10
11 void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
12 {
13 unsigned long size = 0;
14 void *buf = NULL;
15
16 if (sha1) {
17 buf = read_object_with_reference(sha1, tree_type, &size, NULL);
18 if (!buf)
19 die("unable to read tree %s", sha1_to_hex(sha1));
20 }
21 init_tree_desc(desc, buf, size);
22 return buf;
23 }
24
25 static int entry_compare(struct name_entry *a, struct name_entry *b)
26 {
27 return base_name_compare(
28 a->path, tree_entry_len(a->path, a->sha1), a->mode,
29 b->path, tree_entry_len(b->path, b->sha1), b->mode);
30 }
31
32 static void entry_clear(struct name_entry *a)
33 {
34 memset(a, 0, sizeof(*a));
35 }
36
37 static void entry_extract(struct tree_desc *t, struct name_entry *a)
38 {
39 a->sha1 = tree_entry_extract(t, &a->path, &a->mode);
40 }
41
42 void update_tree_entry(struct tree_desc *desc)
43 {
44 const void *buf = desc->buffer;
45 unsigned long size = desc->size;
46 int len = strlen(buf) + 1 + 20;
47
48 if (size < len)
49 die("corrupt tree file");
50 desc->buffer = (char *) buf + len;
51 desc->size = size - len;
52 }
53
54 static const char *get_mode(const char *str, unsigned int *modep)
55 {
56 unsigned char c;
57 unsigned int mode = 0;
58
59 while ((c = *str++) != ' ') {
60 if (c < '0' || c > '7')
61 return NULL;
62 mode = (mode << 3) + (c - '0');
63 }
64 *modep = mode;
65 return str;
66 }
67
68 const unsigned char *tree_entry_extract(struct tree_desc *desc, const char **pathp, unsigned int *modep)
69 {
70 const void *tree = desc->buffer;
71 unsigned long size = desc->size;
72 int len = strlen(tree)+1;
73 const unsigned char *sha1 = (unsigned char *) tree + len;
74 const char *path;
75 unsigned int mode;
76
77 path = get_mode(tree, &mode);
78 if (!path || size < len + 20)
79 die("corrupt tree file");
80 *pathp = path;
81 *modep = canon_mode(mode);
82 return sha1;
83 }
84
85 int tree_entry(struct tree_desc *desc, struct name_entry *entry)
86 {
87 const void *tree = desc->buffer;
88 const char *path;
89 unsigned long len, size = desc->size;
90
91 if (!size)
92 return 0;
93
94 path = get_mode(tree, &entry->mode);
95 if (!path)
96 die("corrupt tree file");
97
98 entry->path = path;
99 len = strlen(path);
100
101 path += len + 1;
102 entry->sha1 = (const unsigned char *) path;
103
104 path += 20;
105 len = path - (char *) tree;
106 if (len > size)
107 die("corrupt tree file");
108
109 desc->buffer = path;
110 desc->size = size - len;
111 return 1;
112 }
113
114 void traverse_trees(int n, struct tree_desc *t, const char *base, traverse_callback_t callback)
115 {
116 struct name_entry *entry = xmalloc(n*sizeof(*entry));
117
118 for (;;) {
119 unsigned long mask = 0;
120 int i, last;
121
122 last = -1;
123 for (i = 0; i < n; i++) {
124 if (!t[i].size)
125 continue;
126 entry_extract(t+i, entry+i);
127 if (last >= 0) {
128 int cmp = entry_compare(entry+i, entry+last);
129
130 /*
131 * Is the new name bigger than the old one?
132 * Ignore it
133 */
134 if (cmp > 0)
135 continue;
136 /*
137 * Is the new name smaller than the old one?
138 * Ignore all old ones
139 */
140 if (cmp < 0)
141 mask = 0;
142 }
143 mask |= 1ul << i;
144 last = i;
145 }
146 if (!mask)
147 break;
148
149 /*
150 * Update the tree entries we've walked, and clear
151 * all the unused name-entries.
152 */
153 for (i = 0; i < n; i++) {
154 if (mask & (1ul << i)) {
155 update_tree_entry(t+i);
156 continue;
157 }
158 entry_clear(entry + i);
159 }
160 callback(n, mask, entry, base);
161 }
162 free(entry);
163 }
164
165 static int find_tree_entry(struct tree_desc *t, const char *name, unsigned char *result, unsigned *mode)
166 {
167 int namelen = strlen(name);
168 while (t->size) {
169 const char *entry;
170 const unsigned char *sha1;
171 int entrylen, cmp;
172
173 sha1 = tree_entry_extract(t, &entry, mode);
174 update_tree_entry(t);
175 entrylen = tree_entry_len(entry, sha1);
176 if (entrylen > namelen)
177 continue;
178 cmp = memcmp(name, entry, entrylen);
179 if (cmp > 0)
180 continue;
181 if (cmp < 0)
182 break;
183 if (entrylen == namelen) {
184 hashcpy(result, sha1);
185 return 0;
186 }
187 if (name[entrylen] != '/')
188 continue;
189 if (!S_ISDIR(*mode))
190 break;
191 if (++entrylen == namelen) {
192 hashcpy(result, sha1);
193 return 0;
194 }
195 return get_tree_entry(sha1, name + entrylen, result, mode);
196 }
197 return -1;
198 }
199
200 int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned char *sha1, unsigned *mode)
201 {
202 int retval;
203 void *tree;
204 unsigned long size;
205 struct tree_desc t;
206 unsigned char root[20];
207
208 tree = read_object_with_reference(tree_sha1, tree_type, &size, root);
209 if (!tree)
210 return -1;
211
212 if (name[0] == '\0') {
213 hashcpy(sha1, root);
214 return 0;
215 }
216
217 init_tree_desc(&t, tree, size);
218 retval = find_tree_entry(&t, name, sha1, mode);
219 free(tree);
220 return retval;
221 }
222