Andrew's git - gitweb.git/blob

f965f3fc5f66827759223dc9caf63d9abf40ae15
   1#ifndef REVISION_H
   2#define REVISION_H
   3
   4/*
   5 * The low 16 bits of the "flags" field shows whether
   6 * a commit is part of the path to the root for that
   7 * parent.
   8 *
   9 * Bit 16 is an internal flag that we've seen the
  10 * definition for this rev, and not just seen it as
  11 * a parent target.
  12 */
  13#define marked(rev)     ((rev)->flags & 0xffff)
  14#define SEEN 0x10000
  15#define USED 0x20000
  16#define REACHABLE 0x40000
  17
  18struct parent {
  19        struct revision *parent;
  20        struct parent *next;
  21};
  22
  23struct revision {
  24        unsigned int flags;
  25        unsigned char sha1[20];
  26        unsigned long date;
  27        struct parent *parent;
  28};
  29
  30static struct revision **revs;
  31static int nr_revs, rev_allocs;
  32
  33static int find_rev(unsigned char *sha1)
  34{
  35        int first = 0, last = nr_revs;
  36
  37        while (first < last) {
  38                int next = (first + last) / 2;
  39                struct revision *rev = revs[next];
  40                int cmp;
  41
  42                cmp = memcmp(sha1, rev->sha1, 20);
  43                if (!cmp)
  44                        return next;
  45                if (cmp < 0) {
  46                        last = next;
  47                        continue;
  48                }
  49                first = next+1;
  50        }
  51        return -first-1;
  52}
  53
  54static struct revision *lookup_rev(unsigned char *sha1)
  55{
  56        int pos = find_rev(sha1);
  57        struct revision *n;
  58
  59        if (pos >= 0)
  60                return revs[pos];
  61        
  62        pos = -pos-1;
  63
  64        if (rev_allocs == nr_revs) {
  65                rev_allocs = alloc_nr(rev_allocs);
  66                revs = realloc(revs, rev_allocs * sizeof(struct revision *));
  67        }
  68        n = malloc(sizeof(struct revision));
  69
  70        n->flags = 0;
  71        memcpy(n->sha1, sha1, 20);
  72        n->parent = NULL;
  73
  74        /* Insert it into the right place */
  75        memmove(revs + pos + 1, revs + pos, (nr_revs - pos) * sizeof(struct revision *));
  76        revs[pos] = n;
  77        nr_revs++;
  78
  79        return n;
  80}
  81
  82static struct revision *add_relationship(struct revision *rev, unsigned char *needs)
  83{
  84        struct revision *parent_rev = lookup_rev(needs);
  85        struct parent **pp = &rev->parent, *p;
  86
  87        while ((p = *pp) != NULL) {
  88                if (p->parent == parent_rev)
  89                        return parent_rev;
  90                pp = &p->next;
  91        }
  92
  93        p = malloc(sizeof(*p));
  94        p->parent = parent_rev;
  95        p->next = NULL;
  96        *pp = p;
  97        return parent_rev;
  98}
  99
 100static void mark_reachable(struct revision *rev, unsigned int mask)
 101{
 102        struct parent *p = rev->parent;
 103
 104        /* If we've been here already, don't bother */
 105        if (rev->flags & mask)
 106                return;
 107        rev->flags |= mask | USED;
 108        while (p) {
 109                mark_reachable(p->parent, mask);
 110                p = p->next;
 111        }
 112}
 113
 114static unsigned long parse_commit_date(const char *buf)
 115{
 116        unsigned long date;
 117
 118        if (memcmp(buf, "author", 6))
 119                return 0;
 120        while (*buf++ != '\n')
 121                /* nada */;
 122        if (memcmp(buf, "committer", 9))
 123                return 0;
 124        while (*buf++ != '>')
 125                /* nada */;
 126        date = strtoul(buf, NULL, 10);
 127        if (date == ULONG_MAX)
 128                date = 0;
 129        return date;
 130}
 131
 132static int parse_commit(unsigned char *sha1)
 133{
 134        struct revision *rev = lookup_rev(sha1);
 135
 136        if (!(rev->flags & SEEN)) {
 137                void *buffer, *bufptr;
 138                unsigned long size;
 139                char type[20];
 140                unsigned char parent[20];
 141
 142                rev->flags |= SEEN;
 143                buffer = bufptr = read_sha1_file(sha1, type, &size);
 144                if (!buffer || strcmp(type, "commit"))
 145                        return -1;
 146                bufptr += 46; /* "tree " + "hex sha1" + "\n" */
 147                while (!memcmp(bufptr, "parent ", 7) && !get_sha1_hex(bufptr+7, parent)) {
 148                        add_relationship(rev, parent);
 149                        parse_commit(parent);
 150                        bufptr += 48;   /* "parent " + "hex sha1" + "\n" */
 151                }
 152                rev->date = parse_commit_date(bufptr);
 153                free(buffer);
 154        }
 155        return 0;       
 156}
 157
 158#endif /* REVISION_H */