1 #include "git-compat-util.h"
4 #include "../fetch-negotiator.h"
6 #include "../prio-queue.h"
10 /* Remember to update object flag allocation in object.h */
12 * Both us and the server know that both parties have this object.
14 #define COMMON (1U << 2)
16 * The server has told us that it has this object. We still need to tell the
17 * server that we have this object (or one of its descendants), but since we are
18 * going to do that, we do not need to tell the server about its ancestors.
20 #define ADVERTISED (1U << 3)
22 * This commit has entered the priority queue.
24 #define SEEN (1U << 4)
26 * This commit has left the priority queue.
28 #define POPPED (1U << 5)
33 * An entry in the priority queue.
36 struct commit
*commit
;
39 * Used only if commit is not COMMON.
41 uint16_t original_ttl
;
46 struct prio_queue rev_list
;
49 * The number of non-COMMON commits in rev_list.
54 static int compare(const void *a_
, const void *b_
, void *data UNUSED
)
56 const struct entry
*a
= a_
;
57 const struct entry
*b
= b_
;
58 return compare_commits_by_commit_date(a
->commit
, b
->commit
, NULL
);
61 static struct entry
*rev_list_push(struct data
*data
, struct commit
*commit
, int mark
)
64 commit
->object
.flags
|= mark
| SEEN
;
66 CALLOC_ARRAY(entry
, 1);
67 entry
->commit
= commit
;
68 prio_queue_put(&data
->rev_list
, entry
);
71 data
->non_common_revs
++;
75 static int clear_marks(const char *refname
, const struct object_id
*oid
,
79 struct object
*o
= deref_tag(the_repository
, parse_object(the_repository
, oid
), refname
, 0);
81 if (o
&& o
->type
== OBJ_COMMIT
)
82 clear_commit_marks((struct commit
*)o
,
83 COMMON
| ADVERTISED
| SEEN
| POPPED
);
88 * Mark this SEEN commit and all its SEEN ancestors as COMMON.
90 static void mark_common(struct data
*data
, struct commit
*seen_commit
)
92 struct prio_queue queue
= { NULL
};
95 prio_queue_put(&queue
, seen_commit
);
96 while ((c
= prio_queue_get(&queue
))) {
97 struct commit_list
*p
;
98 if (c
->object
.flags
& COMMON
)
100 c
->object
.flags
|= COMMON
;
101 if (!(c
->object
.flags
& POPPED
))
102 data
->non_common_revs
--;
104 if (!c
->object
.parsed
)
106 for (p
= c
->parents
; p
; p
= p
->next
) {
107 if (p
->item
->object
.flags
& SEEN
)
108 prio_queue_put(&queue
, p
->item
);
114 * Ensure that the priority queue has an entry for to_push, and ensure that the
115 * entry has the correct flags and ttl.
117 * This function returns 1 if an entry was found or created, and 0 otherwise
118 * (because the entry for this commit had already been popped).
120 static int push_parent(struct data
*data
, struct entry
*entry
,
121 struct commit
*to_push
)
123 struct entry
*parent_entry
;
125 if (to_push
->object
.flags
& SEEN
) {
127 if (to_push
->object
.flags
& POPPED
)
129 * The entry for this commit has already been popped,
130 * due to clock skew. Pretend that this parent does not
135 * Find the existing entry and use it.
137 for (i
= 0; i
< data
->rev_list
.nr
; i
++) {
138 parent_entry
= data
->rev_list
.array
[i
].data
;
139 if (parent_entry
->commit
== to_push
)
142 BUG("missing parent in priority queue");
146 parent_entry
= rev_list_push(data
, to_push
, 0);
149 if (entry
->commit
->object
.flags
& (COMMON
| ADVERTISED
)) {
150 mark_common(data
, to_push
);
152 uint16_t new_original_ttl
= entry
->ttl
153 ? entry
->original_ttl
: entry
->original_ttl
* 3 / 2 + 1;
154 uint16_t new_ttl
= entry
->ttl
155 ? entry
->ttl
- 1 : new_original_ttl
;
156 if (parent_entry
->original_ttl
< new_original_ttl
) {
157 parent_entry
->original_ttl
= new_original_ttl
;
158 parent_entry
->ttl
= new_ttl
;
165 static const struct object_id
*get_rev(struct data
*data
)
167 struct commit
*to_send
= NULL
;
169 while (to_send
== NULL
) {
171 struct commit
*commit
;
172 struct commit_list
*p
;
173 int parent_pushed
= 0;
175 if (data
->rev_list
.nr
== 0 || data
->non_common_revs
== 0)
178 entry
= prio_queue_get(&data
->rev_list
);
179 commit
= entry
->commit
;
180 commit
->object
.flags
|= POPPED
;
181 if (!(commit
->object
.flags
& COMMON
))
182 data
->non_common_revs
--;
184 if (!(commit
->object
.flags
& COMMON
) && !entry
->ttl
)
187 repo_parse_commit(the_repository
, commit
);
188 for (p
= commit
->parents
; p
; p
= p
->next
)
189 parent_pushed
|= push_parent(data
, entry
, p
->item
);
191 if (!(commit
->object
.flags
& COMMON
) && !parent_pushed
)
193 * This commit has no parents, or all of its parents
194 * have already been popped (due to clock skew), so send
202 return &to_send
->object
.oid
;
205 static void known_common(struct fetch_negotiator
*n
, struct commit
*c
)
207 if (c
->object
.flags
& SEEN
)
209 rev_list_push(n
->data
, c
, ADVERTISED
);
212 static void add_tip(struct fetch_negotiator
*n
, struct commit
*c
)
214 n
->known_common
= NULL
;
215 if (c
->object
.flags
& SEEN
)
217 rev_list_push(n
->data
, c
, 0);
220 static const struct object_id
*next(struct fetch_negotiator
*n
)
222 n
->known_common
= NULL
;
224 return get_rev(n
->data
);
227 static int ack(struct fetch_negotiator
*n
, struct commit
*c
)
229 int known_to_be_common
= !!(c
->object
.flags
& COMMON
);
230 if (!(c
->object
.flags
& SEEN
))
231 die("received ack for commit %s not sent as 'have'\n",
232 oid_to_hex(&c
->object
.oid
));
233 mark_common(n
->data
, c
);
234 return known_to_be_common
;
237 static void release(struct fetch_negotiator
*n
)
239 clear_prio_queue(&((struct data
*)n
->data
)->rev_list
);
240 FREE_AND_NULL(n
->data
);
243 void skipping_negotiator_init(struct fetch_negotiator
*negotiator
)
246 negotiator
->known_common
= known_common
;
247 negotiator
->add_tip
= add_tip
;
248 negotiator
->next
= next
;
249 negotiator
->ack
= ack
;
250 negotiator
->release
= release
;
251 negotiator
->data
= CALLOC_ARRAY(data
, 1);
252 data
->rev_list
.compare
= compare
;
255 for_each_ref(clear_marks
, NULL
);