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