Merge branch 'lt/fix-sol-pack'
[git] / tree-walk.c
1 #include "cache.h"
2 #include "tree-walk.h"
3
4 void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
5 {
6         unsigned long size = 0;
7         void *buf = NULL;
8
9         if (sha1) {
10                 buf = read_object_with_reference(sha1, "tree", &size, NULL);
11                 if (!buf)
12                         die("unable to read tree %s", sha1_to_hex(sha1));
13         }
14         desc->size = size;
15         desc->buf = buf;
16         return buf;
17 }
18
19 static int entry_compare(struct name_entry *a, struct name_entry *b)
20 {
21         return base_name_compare(
22                         a->path, a->pathlen, a->mode,
23                         b->path, b->pathlen, b->mode);
24 }
25
26 static void entry_clear(struct name_entry *a)
27 {
28         memset(a, 0, sizeof(*a));
29 }
30
31 static void entry_extract(struct tree_desc *t, struct name_entry *a)
32 {
33         a->sha1 = tree_entry_extract(t, &a->path, &a->mode);
34         a->pathlen = strlen(a->path);
35 }
36
37 void update_tree_entry(struct tree_desc *desc)
38 {
39         void *buf = desc->buf;
40         unsigned long size = desc->size;
41         int len = strlen(buf) + 1 + 20;
42
43         if (size < len)
44                 die("corrupt tree file");
45         desc->buf = buf + len;
46         desc->size = size - len;
47 }
48
49 const unsigned char *tree_entry_extract(struct tree_desc *desc, const char **pathp, unsigned int *modep)
50 {
51         void *tree = desc->buf;
52         unsigned long size = desc->size;
53         int len = strlen(tree)+1;
54         const unsigned char *sha1 = tree + len;
55         const char *path = strchr(tree, ' ');
56         unsigned int mode;
57
58         if (!path || size < len + 20 || sscanf(tree, "%o", &mode) != 1)
59                 die("corrupt tree file");
60         *pathp = path+1;
61         *modep = canon_mode(mode);
62         return sha1;
63 }
64
65 void traverse_trees(int n, struct tree_desc *t, const char *base, traverse_callback_t callback)
66 {
67         struct name_entry *entry = xmalloc(n*sizeof(*entry));
68
69         for (;;) {
70                 struct name_entry entry[3];
71                 unsigned long mask = 0;
72                 int i, last;
73
74                 last = -1;
75                 for (i = 0; i < n; i++) {
76                         if (!t[i].size)
77                                 continue;
78                         entry_extract(t+i, entry+i);
79                         if (last >= 0) {
80                                 int cmp = entry_compare(entry+i, entry+last);
81
82                                 /*
83                                  * Is the new name bigger than the old one?
84                                  * Ignore it
85                                  */
86                                 if (cmp > 0)
87                                         continue;
88                                 /*
89                                  * Is the new name smaller than the old one?
90                                  * Ignore all old ones
91                                  */
92                                 if (cmp < 0)
93                                         mask = 0;
94                         }
95                         mask |= 1ul << i;
96                         last = i;
97                 }
98                 if (!mask)
99                         break;
100
101                 /*
102                  * Update the tree entries we've walked, and clear
103                  * all the unused name-entries.
104                  */
105                 for (i = 0; i < n; i++) {
106                         if (mask & (1ul << i)) {
107                                 update_tree_entry(t+i);
108                                 continue;
109                         }
110                         entry_clear(entry + i);
111                 }
112                 callback(n, mask, entry, base);
113         }
114         free(entry);
115 }
116