]>
Commit | Line | Data |
---|---|---|
3e4339e6 LT |
1 | #include "cache.h" |
2 | #include "object.h" | |
3 | ||
4 | int track_object_refs = 0; | |
5 | ||
6 | static unsigned int refs_hash_size, nr_object_refs; | |
7 | static struct object_refs **refs_hash; | |
8 | ||
9 | static unsigned int hash_obj(struct object *obj, unsigned int n) | |
10 | { | |
11 | unsigned int hash = *(unsigned int *)obj->sha1; | |
12 | return hash % n; | |
13 | } | |
14 | ||
5fdc8499 LT |
15 | static void insert_ref_hash(struct object_refs *ref, struct object_refs **hash, unsigned int size) |
16 | { | |
17 | int j = hash_obj(ref->base, size); | |
18 | ||
19 | while (hash[j]) { | |
20 | j++; | |
21 | if (j >= size) | |
22 | j = 0; | |
23 | } | |
24 | hash[j] = ref; | |
25 | } | |
26 | ||
3e4339e6 LT |
27 | static void grow_refs_hash(void) |
28 | { | |
29 | int i; | |
30 | int new_hash_size = (refs_hash_size + 1000) * 3 / 2; | |
31 | struct object_refs **new_hash; | |
32 | ||
b3c952f8 | 33 | new_hash = xcalloc(new_hash_size, sizeof(struct object_refs *)); |
3e4339e6 | 34 | for (i = 0; i < refs_hash_size; i++) { |
3e4339e6 LT |
35 | struct object_refs *ref = refs_hash[i]; |
36 | if (!ref) | |
37 | continue; | |
5fdc8499 | 38 | insert_ref_hash(ref, new_hash, new_hash_size); |
3e4339e6 LT |
39 | } |
40 | free(refs_hash); | |
41 | refs_hash = new_hash; | |
42 | refs_hash_size = new_hash_size; | |
43 | } | |
44 | ||
3e4339e6 LT |
45 | static void add_object_refs(struct object *obj, struct object_refs *ref) |
46 | { | |
47 | int nr = nr_object_refs + 1; | |
48 | ||
49 | if (nr > refs_hash_size * 2 / 3) | |
50 | grow_refs_hash(); | |
51 | ref->base = obj; | |
5fdc8499 | 52 | insert_ref_hash(ref, refs_hash, refs_hash_size); |
3e4339e6 LT |
53 | nr_object_refs = nr; |
54 | } | |
55 | ||
56 | struct object_refs *lookup_object_refs(struct object *obj) | |
57 | { | |
58 | int j = hash_obj(obj, refs_hash_size); | |
59 | struct object_refs *ref; | |
60 | ||
61 | while ((ref = refs_hash[j]) != NULL) { | |
62 | if (ref->base == obj) | |
63 | break; | |
64 | j++; | |
65 | if (j >= refs_hash_size) | |
66 | j = 0; | |
67 | } | |
68 | return ref; | |
69 | } | |
70 | ||
71 | struct object_refs *alloc_object_refs(unsigned count) | |
72 | { | |
73 | struct object_refs *refs; | |
74 | size_t size = sizeof(*refs) + count*sizeof(struct object *); | |
75 | ||
76 | refs = xcalloc(1, size); | |
77 | refs->count = count; | |
78 | return refs; | |
79 | } | |
80 | ||
81 | static int compare_object_pointers(const void *a, const void *b) | |
82 | { | |
83 | const struct object * const *pa = a; | |
84 | const struct object * const *pb = b; | |
85 | if (*pa == *pb) | |
86 | return 0; | |
87 | else if (*pa < *pb) | |
88 | return -1; | |
89 | else | |
90 | return 1; | |
91 | } | |
92 | ||
93 | void set_object_refs(struct object *obj, struct object_refs *refs) | |
94 | { | |
95 | unsigned int i, j; | |
96 | ||
97 | /* Do not install empty list of references */ | |
98 | if (refs->count < 1) { | |
99 | free(refs); | |
100 | return; | |
101 | } | |
102 | ||
103 | /* Sort the list and filter out duplicates */ | |
104 | qsort(refs->ref, refs->count, sizeof(refs->ref[0]), | |
105 | compare_object_pointers); | |
106 | for (i = j = 1; i < refs->count; i++) { | |
107 | if (refs->ref[i] != refs->ref[i - 1]) | |
108 | refs->ref[j++] = refs->ref[i]; | |
109 | } | |
110 | if (j < refs->count) { | |
111 | /* Duplicates were found - reallocate list */ | |
112 | size_t size = sizeof(*refs) + j*sizeof(struct object *); | |
113 | refs->count = j; | |
114 | refs = xrealloc(refs, size); | |
115 | } | |
116 | ||
117 | for (i = 0; i < refs->count; i++) | |
118 | refs->ref[i]->used = 1; | |
119 | add_object_refs(obj, refs); | |
120 | } | |
121 | ||
122 | void mark_reachable(struct object *obj, unsigned int mask) | |
123 | { | |
124 | const struct object_refs *refs; | |
125 | ||
126 | if (!track_object_refs) | |
127 | die("cannot do reachability with object refs turned off"); | |
86f660b1 AN |
128 | /* nothing to lookup */ |
129 | if (!refs_hash_size) | |
130 | return; | |
3e4339e6 LT |
131 | /* If we've been here already, don't bother */ |
132 | if (obj->flags & mask) | |
133 | return; | |
134 | obj->flags |= mask; | |
135 | refs = lookup_object_refs(obj); | |
136 | if (refs) { | |
137 | unsigned i; | |
138 | for (i = 0; i < refs->count; i++) | |
139 | mark_reachable(refs->ref[i], mask); | |
140 | } | |
141 | } | |
142 | ||
143 |