Document the color.interactive semantics
[git/git.git] / tree-walk.c
1 #include "cache.h"
2 #include "tree-walk.h"
3 #include "tree.h"
4
5 static const char *get_mode(const char *str, unsigned int *modep)
6 {
7 unsigned char c;
8 unsigned int mode = 0;
9
10 while ((c = *str++) != ' ') {
11 if (c < '0' || c > '7')
12 return NULL;
13 mode = (mode << 3) + (c - '0');
14 }
15 *modep = mode;
16 return str;
17 }
18
19 static void decode_tree_entry(struct tree_desc *desc, const void *buf, unsigned long size)
20 {
21 const char *path;
22 unsigned int mode, len;
23
24 path = get_mode(buf, &mode);
25 if (!path)
26 die("corrupt tree file");
27 len = strlen(path) + 1;
28
29 /* Initialize the descriptor entry */
30 desc->entry.path = path;
31 desc->entry.mode = mode;
32 desc->entry.sha1 = (const unsigned char *)(path + len);
33 }
34
35 void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size)
36 {
37 desc->buffer = buffer;
38 desc->size = size;
39 if (size)
40 decode_tree_entry(desc, buffer, size);
41 }
42
43 void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
44 {
45 unsigned long size = 0;
46 void *buf = NULL;
47
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));
52 }
53 init_tree_desc(desc, buf, size);
54 return buf;
55 }
56
57 static int entry_compare(struct name_entry *a, struct name_entry *b)
58 {
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);
62 }
63
64 static void entry_clear(struct name_entry *a)
65 {
66 memset(a, 0, sizeof(*a));
67 }
68
69 static void entry_extract(struct tree_desc *t, struct name_entry *a)
70 {
71 *a = t->entry;
72 }
73
74 void update_tree_entry(struct tree_desc *desc)
75 {
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;
80
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);
89 }
90
91 int tree_entry(struct tree_desc *desc, struct name_entry *entry)
92 {
93 if (!desc->size)
94 return 0;
95
96 *entry = desc->entry;
97 update_tree_entry(desc);
98 return 1;
99 }
100
101 void traverse_trees(int n, struct tree_desc *t, const char *base, traverse_callback_t callback)
102 {
103 struct name_entry *entry = xmalloc(n*sizeof(*entry));
104
105 for (;;) {
106 unsigned long mask = 0;
107 int i, last;
108
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);
116
117 /*
118 * Is the new name bigger than the old one?
119 * Ignore it
120 */
121 if (cmp > 0)
122 continue;
123 /*
124 * Is the new name smaller than the old one?
125 * Ignore all old ones
126 */
127 if (cmp < 0)
128 mask = 0;
129 }
130 mask |= 1ul << i;
131 last = i;
132 }
133 if (!mask)
134 break;
135
136 /*
137 * Update the tree entries we've walked, and clear
138 * all the unused name-entries.
139 */
140 for (i = 0; i < n; i++) {
141 if (mask & (1ul << i)) {
142 update_tree_entry(t+i);
143 continue;
144 }
145 entry_clear(entry + i);
146 }
147 callback(n, mask, entry, base);
148 }
149 free(entry);
150 }
151
152 static int find_tree_entry(struct tree_desc *t, const char *name, unsigned char *result, unsigned *mode)
153 {
154 int namelen = strlen(name);
155 while (t->size) {
156 const char *entry;
157 const unsigned char *sha1;
158 int entrylen, cmp;
159
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;
173 }
174 if (name[entrylen] != '/')
175 continue;
176 if (!S_ISDIR(*mode))
177 break;
178 if (++entrylen == namelen) {
179 hashcpy(result, sha1);
180 return 0;
181 }
182 return get_tree_entry(sha1, name + entrylen, result, mode);
183 }
184 return -1;
185 }
186
187 int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned char *sha1, unsigned *mode)
188 {
189 int retval;
190 void *tree;
191 unsigned long size;
192 struct tree_desc t;
193 unsigned char root[20];
194
195 tree = read_object_with_reference(tree_sha1, tree_type, &size, root);
196 if (!tree)
197 return -1;
198
199 if (name[0] == '\0') {
200 hashcpy(sha1, root);
201 return 0;
202 }
203
204 init_tree_desc(&t, tree, size);
205 retval = find_tree_entry(&t, name, sha1, mode);
206 free(tree);
207 return retval;
208 }