]> git.ipfire.org Git - thirdparty/git.git/blame - negotiator/skipping.c
Merge branch 'jk/clone-allow-bare-and-o-together'
[thirdparty/git.git] / negotiator / skipping.c
CommitLineData
42cc7485
JT
1#include "cache.h"
2#include "skipping.h"
3#include "../commit.h"
4#include "../fetch-negotiator.h"
5#include "../prio-queue.h"
6#include "../refs.h"
7#include "../tag.h"
8
9/* Remember to update object flag allocation in object.h */
10/*
11 * Both us and the server know that both parties have this object.
12 */
13#define COMMON (1U << 2)
14/*
15 * The server has told us that it has this object. We still need to tell the
16 * server that we have this object (or one of its descendants), but since we are
17 * going to do that, we do not need to tell the server about its ancestors.
18 */
19#define ADVERTISED (1U << 3)
20/*
21 * This commit has entered the priority queue.
22 */
23#define SEEN (1U << 4)
24/*
25 * This commit has left the priority queue.
26 */
27#define POPPED (1U << 5)
28
29static int marked;
30
31/*
32 * An entry in the priority queue.
33 */
34struct entry {
35 struct commit *commit;
36
37 /*
38 * Used only if commit is not COMMON.
39 */
40 uint16_t original_ttl;
41 uint16_t ttl;
42};
43
44struct data {
45 struct prio_queue rev_list;
46
47 /*
48 * The number of non-COMMON commits in rev_list.
49 */
50 int non_common_revs;
51};
52
53static int compare(const void *a_, const void *b_, void *unused)
54{
55 const struct entry *a = a_;
56 const struct entry *b = b_;
57 return compare_commits_by_commit_date(a->commit, b->commit, NULL);
58}
59
60static struct entry *rev_list_push(struct data *data, struct commit *commit, int mark)
61{
62 struct entry *entry;
63 commit->object.flags |= mark | SEEN;
64
ca56dadb 65 CALLOC_ARRAY(entry, 1);
42cc7485
JT
66 entry->commit = commit;
67 prio_queue_put(&data->rev_list, entry);
68
69 if (!(mark & COMMON))
70 data->non_common_revs++;
71 return entry;
72}
73
74static int clear_marks(const char *refname, const struct object_id *oid,
5cf88fd8
ÆAB
75 int flag UNUSED,
76 void *cb_data UNUSED)
42cc7485 77{
7c85ee6c 78 struct object *o = deref_tag(the_repository, parse_object(the_repository, oid), refname, 0);
42cc7485
JT
79
80 if (o && o->type == OBJ_COMMIT)
81 clear_commit_marks((struct commit *)o,
82 COMMON | ADVERTISED | SEEN | POPPED);
83 return 0;
84}
85
86/*
87 * Mark this SEEN commit and all its SEEN ancestors as COMMON.
88 */
89static void mark_common(struct data *data, struct commit *c)
90{
91 struct commit_list *p;
92
93 if (c->object.flags & COMMON)
94 return;
95 c->object.flags |= COMMON;
96 if (!(c->object.flags & POPPED))
97 data->non_common_revs--;
98
99 if (!c->object.parsed)
100 return;
101 for (p = c->parents; p; p = p->next) {
102 if (p->item->object.flags & SEEN)
103 mark_common(data, p->item);
104 }
105}
106
107/*
108 * Ensure that the priority queue has an entry for to_push, and ensure that the
109 * entry has the correct flags and ttl.
110 *
111 * This function returns 1 if an entry was found or created, and 0 otherwise
112 * (because the entry for this commit had already been popped).
113 */
114static int push_parent(struct data *data, struct entry *entry,
115 struct commit *to_push)
116{
117 struct entry *parent_entry;
118
119 if (to_push->object.flags & SEEN) {
120 int i;
121 if (to_push->object.flags & POPPED)
122 /*
123 * The entry for this commit has already been popped,
124 * due to clock skew. Pretend that this parent does not
125 * exist.
126 */
127 return 0;
128 /*
129 * Find the existing entry and use it.
130 */
131 for (i = 0; i < data->rev_list.nr; i++) {
132 parent_entry = data->rev_list.array[i].data;
133 if (parent_entry->commit == to_push)
134 goto parent_found;
135 }
136 BUG("missing parent in priority queue");
137parent_found:
138 ;
139 } else {
140 parent_entry = rev_list_push(data, to_push, 0);
141 }
142
143 if (entry->commit->object.flags & (COMMON | ADVERTISED)) {
144 mark_common(data, to_push);
145 } else {
146 uint16_t new_original_ttl = entry->ttl
147 ? entry->original_ttl : entry->original_ttl * 3 / 2 + 1;
148 uint16_t new_ttl = entry->ttl
149 ? entry->ttl - 1 : new_original_ttl;
150 if (parent_entry->original_ttl < new_original_ttl) {
151 parent_entry->original_ttl = new_original_ttl;
152 parent_entry->ttl = new_ttl;
153 }
154 }
155
156 return 1;
157}
158
159static const struct object_id *get_rev(struct data *data)
160{
161 struct commit *to_send = NULL;
162
163 while (to_send == NULL) {
164 struct entry *entry;
165 struct commit *commit;
166 struct commit_list *p;
167 int parent_pushed = 0;
168
169 if (data->rev_list.nr == 0 || data->non_common_revs == 0)
170 return NULL;
171
172 entry = prio_queue_get(&data->rev_list);
173 commit = entry->commit;
174 commit->object.flags |= POPPED;
175 if (!(commit->object.flags & COMMON))
176 data->non_common_revs--;
177
178 if (!(commit->object.flags & COMMON) && !entry->ttl)
179 to_send = commit;
180
181 parse_commit(commit);
182 for (p = commit->parents; p; p = p->next)
183 parent_pushed |= push_parent(data, entry, p->item);
184
185 if (!(commit->object.flags & COMMON) && !parent_pushed)
186 /*
187 * This commit has no parents, or all of its parents
188 * have already been popped (due to clock skew), so send
189 * it anyway.
190 */
191 to_send = commit;
192
193 free(entry);
194 }
195
196 return &to_send->object.oid;
197}
198
199static void known_common(struct fetch_negotiator *n, struct commit *c)
200{
201 if (c->object.flags & SEEN)
202 return;
203 rev_list_push(n->data, c, ADVERTISED);
204}
205
206static void add_tip(struct fetch_negotiator *n, struct commit *c)
207{
208 n->known_common = NULL;
209 if (c->object.flags & SEEN)
210 return;
211 rev_list_push(n->data, c, 0);
212}
213
214static const struct object_id *next(struct fetch_negotiator *n)
215{
216 n->known_common = NULL;
217 n->add_tip = NULL;
218 return get_rev(n->data);
219}
220
221static int ack(struct fetch_negotiator *n, struct commit *c)
222{
223 int known_to_be_common = !!(c->object.flags & COMMON);
224 if (!(c->object.flags & SEEN))
225 die("received ack for commit %s not sent as 'have'\n",
226 oid_to_hex(&c->object.oid));
227 mark_common(n->data, c);
228 return known_to_be_common;
229}
230
231static void release(struct fetch_negotiator *n)
232{
233 clear_prio_queue(&((struct data *)n->data)->rev_list);
234 FREE_AND_NULL(n->data);
235}
236
237void skipping_negotiator_init(struct fetch_negotiator *negotiator)
238{
239 struct data *data;
240 negotiator->known_common = known_common;
241 negotiator->add_tip = add_tip;
242 negotiator->next = next;
243 negotiator->ack = ack;
244 negotiator->release = release;
ca56dadb 245 negotiator->data = CALLOC_ARRAY(data, 1);
42cc7485
JT
246 data->rev_list.compare = compare;
247
248 if (marked)
249 for_each_ref(clear_marks, NULL);
250 marked = 1;
251}