1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
#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, unsigned int mask)
{
struct parent *p = rev->parent;
/* If we've been here already, don't bother */
if (rev->flags & mask)
return;
rev->flags |= mask | USED;
while (p) {
mark_reachable(p->parent, mask);
p = p->next;
}
}
static unsigned long parse_commit_date(const char *buf)
{
unsigned long date;
if (memcmp(buf, "author", 6))
return 0;
while (*buf++ != '\n')
/* nada */;
if (memcmp(buf, "committer", 9))
return 0;
while (*buf++ != '>')
/* nada */;
date = strtoul(buf, NULL, 10);
if (date == ULONG_MAX)
date = 0;
return date;
}
static int parse_commit(unsigned char *sha1)
{
struct revision *rev = lookup_rev(sha1);
if (!(rev->flags & SEEN)) {
void *buffer, *bufptr;
unsigned long size;
char type[20];
unsigned char parent[20];
rev->flags |= SEEN;
buffer = bufptr = read_sha1_file(sha1, type, &size);
if (!buffer || strcmp(type, "commit"))
return -1;
bufptr += 46; /* "tree " + "hex sha1" + "\n" */
while (!memcmp(bufptr, "parent ", 7) && !get_sha1_hex(bufptr+7, parent)) {
add_relationship(rev, parent);
parse_commit(parent);
bufptr += 48; /* "parent " + "hex sha1" + "\n" */
}
rev->date = parse_commit_date(bufptr);
free(buffer);
}
return 0;
}
#endif /* REVISION_H */
|
