Andrew's git - gitweb.git/blob

   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)
 101{
 102        struct parent *p = rev->parent;
 103
 104        /* If we've been here already, don't bother */
 105        if (rev->flags & REACHABLE)
 106                return;
 107        rev->flags |= REACHABLE | USED;
 108        while (p) {
 109                mark_reachable(p->parent);
 110                p = p->next;
 111        }
 112}
 113
 114#endif /* REVISION_H */