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