diff options
| -rw-r--r-- | fsck-cache.c | 111 | ||||
| -rw-r--r-- | rev-tree.c | 98 | ||||
| -rw-r--r-- | revision.h | 114 |
3 files changed, 121 insertions, 202 deletions
diff --git a/fsck-cache.c b/fsck-cache.c index e7014a0..3fbcd2c 100644 --- a/fsck-cache.c +++ b/fsck-cache.c @@ -3,120 +3,11 @@ #include <sys/types.h> #include <dirent.h> -/* - * The low 16 bits of the "flags" field shows whether - * a commit is part of the path to the root for that - * parent. - * - * Bit 16 is an internal flag that we've seen the - * definition for this rev, and not just seen it as - * a parent target. - */ -#define MAX_COMMITS (16) -#define marked(rev) ((rev)->flags & 0xffff) -#define SEEN 0x10000 -#define USED 0x20000 -#define REACHABLE 0x40000 +#include "revision.h" static int show_unreachable = 0; static unsigned char head_sha1[20]; -struct parent { - struct revision *parent; - struct parent *next; -}; - -struct revision { - unsigned int flags; - unsigned char sha1[20]; - unsigned long date; - struct parent *parent; -}; - -static struct revision **revs; -static int nr_revs, rev_allocs; - -static int find_rev(unsigned char *sha1) -{ - int first = 0, last = nr_revs; - - while (first < last) { - int next = (first + last) / 2; - struct revision *rev = revs[next]; - int cmp; - - cmp = memcmp(sha1, rev->sha1, 20); - if (!cmp) - return next; - if (cmp < 0) { - last = next; - continue; - } - first = next+1; - } - return -first-1; -} - -static struct revision *lookup_rev(unsigned char *sha1) -{ - int pos = find_rev(sha1); - struct revision *n; - - if (pos >= 0) - return revs[pos]; - - pos = -pos-1; - - if (rev_allocs == nr_revs) { - rev_allocs = alloc_nr(rev_allocs); - revs = realloc(revs, rev_allocs * sizeof(struct revision *)); - } - n = malloc(sizeof(struct revision)); - - n->flags = 0; - memcpy(n->sha1, sha1, 20); - n->parent = NULL; - - /* Insert it into the right place */ - memmove(revs + pos + 1, revs + pos, (nr_revs - pos) * sizeof(struct revision *)); - revs[pos] = n; - nr_revs++; - - return n; -} - -static struct revision *add_relationship(struct revision *rev, unsigned char *needs) -{ - struct revision *parent_rev = lookup_rev(needs); - struct parent **pp = &rev->parent, *p; - - while ((p = *pp) != NULL) { - if (p->parent == parent_rev) - return parent_rev; - pp = &p->next; - } - - p = malloc(sizeof(*p)); - p->parent = parent_rev; - p->next = NULL; - *pp = p; - return parent_rev; -} - -static void mark_reachable(struct revision *rev) -{ - struct parent *p = rev->parent; - - /* If we've been here already, don't bother */ - if (rev->flags & REACHABLE) - return; - rev->flags |= REACHABLE | USED; - while (p) { - mark_reachable(p->parent); - p = p->next; - } -} - static void check_connectivity(void) { int i; @@ -1,106 +1,20 @@ #define _XOPEN_SOURCE /* glibc2 needs this */ #include <time.h> #include <ctype.h> + #include "cache.h" +#include "revision.h" /* - * The low 16 bits of the "flags" field shows whether - * a commit is part of the path to the root for that - * parent. - * - * Bit 16 is an internal flag that we've seen the - * definition for this rev, and not just seen it as - * a parent target. + * revision.h leaves the low 16 bits of the "flags" field of the + * revision data structure unused. We use it for a "reachable from + * this commit <N>" bitmask. */ -#define MAX_COMMITS (16) -#define marked(rev) ((rev)->flags & 0xffff) -#define SEEN 0x10000 +#define MAX_COMMITS 16 static int show_edges = 0; static int basemask = 0; -struct parent { - struct revision *parent; - struct parent *next; -}; - -struct revision { - unsigned int flags; - unsigned char sha1[20]; - unsigned long date; - struct parent *parent; -}; - -static struct revision **revs; -static int nr_revs, rev_allocs; - -static int find_rev(unsigned char *sha1) -{ - int first = 0, last = nr_revs; - - while (first < last) { - int next = (first + last) / 2; - struct revision *rev = revs[next]; - int cmp; - - cmp = memcmp(sha1, rev->sha1, 20); - if (!cmp) - return next; - if (cmp < 0) { - last = next; - continue; - } - first = next+1; - } - return -first-1; -} - -static struct revision *lookup_rev(unsigned char *sha1) -{ - int pos = find_rev(sha1); - struct revision *n; - - if (pos >= 0) - return revs[pos]; - - pos = -pos-1; - - if (rev_allocs == nr_revs) { - rev_allocs = alloc_nr(rev_allocs); - revs = realloc(revs, rev_allocs * sizeof(struct revision *)); - } - n = malloc(sizeof(struct revision)); - - n->flags = 0; - memcpy(n->sha1, sha1, 20); - n->parent = NULL; - - /* Insert it into the right place */ - memmove(revs + pos + 1, revs + pos, (nr_revs - pos) * sizeof(struct revision *)); - revs[pos] = n; - nr_revs++; - - return n; -} - -static int add_relationship(struct revision *rev, unsigned char *parent_sha) -{ - struct revision *parent_rev = lookup_rev(parent_sha); - struct parent **pp = &rev->parent, *p; - - while ((p = *pp) != NULL) { - if (p->parent == parent_rev) - return 0; - pp = &p->next; - } - - p = malloc(sizeof(*p)); - p->parent = parent_rev; - p->next = NULL; - *pp = p; - return 1; -} - static unsigned long parse_time(const char *buf) { char c, *p; diff --git a/revision.h b/revision.h new file mode 100644 index 0000000..4f140ca --- /dev/null +++ b/revision.h @@ -0,0 +1,114 @@ +#ifndef REVISION_H +#define REVISION_H + +/* + * The low 16 bits of the "flags" field shows whether + * a commit is part of the path to the root for that + * parent. + * + * Bit 16 is an internal flag that we've seen the + * definition for this rev, and not just seen it as + * a parent target. + */ +#define marked(rev) ((rev)->flags & 0xffff) +#define SEEN 0x10000 +#define USED 0x20000 +#define REACHABLE 0x40000 + +struct parent { + struct revision *parent; + struct parent *next; +}; + +struct revision { + unsigned int flags; + unsigned char sha1[20]; + unsigned long date; + struct parent *parent; +}; + +static struct revision **revs; +static int nr_revs, rev_allocs; + +static int find_rev(unsigned char *sha1) +{ + int first = 0, last = nr_revs; + + while (first < last) { + int next = (first + last) / 2; + struct revision *rev = revs[next]; + int cmp; + + cmp = memcmp(sha1, rev->sha1, 20); + if (!cmp) + return next; + if (cmp < 0) { + last = next; + continue; + } + first = next+1; + } + return -first-1; +} + +static struct revision *lookup_rev(unsigned char *sha1) +{ + int pos = find_rev(sha1); + struct revision *n; + + if (pos >= 0) + return revs[pos]; + + pos = -pos-1; + + if (rev_allocs == nr_revs) { + rev_allocs = alloc_nr(rev_allocs); + revs = realloc(revs, rev_allocs * sizeof(struct revision *)); + } + n = malloc(sizeof(struct revision)); + + n->flags = 0; + memcpy(n->sha1, sha1, 20); + n->parent = NULL; + + /* Insert it into the right place */ + memmove(revs + pos + 1, revs + pos, (nr_revs - pos) * sizeof(struct revision *)); + revs[pos] = n; + nr_revs++; + + return n; +} + +static struct revision *add_relationship(struct revision *rev, unsigned char *needs) +{ + struct revision *parent_rev = lookup_rev(needs); + struct parent **pp = &rev->parent, *p; + + while ((p = *pp) != NULL) { + if (p->parent == parent_rev) + return parent_rev; + pp = &p->next; + } + + p = malloc(sizeof(*p)); + p->parent = parent_rev; + p->next = NULL; + *pp = p; + return parent_rev; +} + +static void mark_reachable(struct revision *rev) +{ + struct parent *p = rev->parent; + + /* If we've been here already, don't bother */ + if (rev->flags & REACHABLE) + return; + rev->flags |= REACHABLE | USED; + while (p) { + mark_reachable(p->parent); + p = p->next; + } +} + +#endif /* REVISION_H */ |