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
|
#include "cache.h"
#include "object.h"
int track_object_refs = 0;
static unsigned int refs_hash_size, nr_object_refs;
static struct object_refs **refs_hash;
static unsigned int hash_obj(struct object *obj, unsigned int n)
{
unsigned int hash = *(unsigned int *)obj->sha1;
return hash % n;
}
static void insert_ref_hash(struct object_refs *ref, struct object_refs **hash, unsigned int size)
{
int j = hash_obj(ref->base, size);
while (hash[j]) {
j++;
if (j >= size)
j = 0;
}
hash[j] = ref;
}
static void grow_refs_hash(void)
{
int i;
int new_hash_size = (refs_hash_size + 1000) * 3 / 2;
struct object_refs **new_hash;
new_hash = xcalloc(new_hash_size, sizeof(struct object_refs *));
for (i = 0; i < refs_hash_size; i++) {
struct object_refs *ref = refs_hash[i];
if (!ref)
continue;
insert_ref_hash(ref, new_hash, new_hash_size);
}
free(refs_hash);
refs_hash = new_hash;
refs_hash_size = new_hash_size;
}
static void add_object_refs(struct object *obj, struct object_refs *ref)
{
int nr = nr_object_refs + 1;
if (nr > refs_hash_size * 2 / 3)
grow_refs_hash();
ref->base = obj;
insert_ref_hash(ref, refs_hash, refs_hash_size);
nr_object_refs = nr;
}
struct object_refs *lookup_object_refs(struct object *obj)
{
int j = hash_obj(obj, refs_hash_size);
struct object_refs *ref;
while ((ref = refs_hash[j]) != NULL) {
if (ref->base == obj)
break;
j++;
if (j >= refs_hash_size)
j = 0;
}
return ref;
}
struct object_refs *alloc_object_refs(unsigned count)
{
struct object_refs *refs;
size_t size = sizeof(*refs) + count*sizeof(struct object *);
refs = xcalloc(1, size);
refs->count = count;
return refs;
}
static int compare_object_pointers(const void *a, const void *b)
{
const struct object * const *pa = a;
const struct object * const *pb = b;
if (*pa == *pb)
return 0;
else if (*pa < *pb)
return -1;
else
return 1;
}
void set_object_refs(struct object *obj, struct object_refs *refs)
{
unsigned int i, j;
/* Do not install empty list of references */
if (refs->count < 1) {
free(refs);
return;
}
/* Sort the list and filter out duplicates */
qsort(refs->ref, refs->count, sizeof(refs->ref[0]),
compare_object_pointers);
for (i = j = 1; i < refs->count; i++) {
if (refs->ref[i] != refs->ref[i - 1])
refs->ref[j++] = refs->ref[i];
}
if (j < refs->count) {
/* Duplicates were found - reallocate list */
size_t size = sizeof(*refs) + j*sizeof(struct object *);
refs->count = j;
refs = xrealloc(refs, size);
}
for (i = 0; i < refs->count; i++)
refs->ref[i]->used = 1;
add_object_refs(obj, refs);
}
void mark_reachable(struct object *obj, unsigned int mask)
{
const struct object_refs *refs;
if (!track_object_refs)
die("cannot do reachability with object refs turned off");
/* nothing to lookup */
if (!refs_hash_size)
return;
/* If we've been here already, don't bother */
if (obj->flags & mask)
return;
obj->flags |= mask;
refs = lookup_object_refs(obj);
if (refs) {
unsigned i;
for (i = 0; i < refs->count; i++)
mark_reachable(refs->ref[i], mask);
}
}
|
