3 #include "commit-graph.h"
5 #include "prio-queue.h"
7 #include "ref-filter.h"
10 #include "commit-reach.h"
12 /* Remember to update object flag allocation in object.h */
13 #define PARENT1 (1u<<16)
14 #define PARENT2 (1u<<17)
15 #define STALE (1u<<18)
16 #define RESULT (1u<<19)
18 static const unsigned all_flags
= (PARENT1
| PARENT2
| STALE
| RESULT
);
20 static int compare_commits_by_gen(const void *_a
, const void *_b
)
22 const struct commit
*a
= *(const struct commit
* const *)_a
;
23 const struct commit
*b
= *(const struct commit
* const *)_b
;
25 timestamp_t generation_a
= commit_graph_generation(a
);
26 timestamp_t generation_b
= commit_graph_generation(b
);
28 if (generation_a
< generation_b
)
30 if (generation_a
> generation_b
)
32 if (a
->date
< b
->date
)
34 if (a
->date
> b
->date
)
39 static int queue_has_nonstale(struct prio_queue
*queue
)
42 for (i
= 0; i
< queue
->nr
; i
++) {
43 struct commit
*commit
= queue
->array
[i
].data
;
44 if (!(commit
->object
.flags
& STALE
))
50 /* all input commits in one and twos[] must have been parsed! */
51 static struct commit_list
*paint_down_to_common(struct repository
*r
,
52 struct commit
*one
, int n
,
54 timestamp_t min_generation
)
56 struct prio_queue queue
= { compare_commits_by_gen_then_commit_date
};
57 struct commit_list
*result
= NULL
;
59 timestamp_t last_gen
= GENERATION_NUMBER_INFINITY
;
61 if (!min_generation
&& !corrected_commit_dates_enabled(r
))
62 queue
.compare
= compare_commits_by_commit_date
;
64 one
->object
.flags
|= PARENT1
;
66 commit_list_append(one
, &result
);
69 prio_queue_put(&queue
, one
);
71 for (i
= 0; i
< n
; i
++) {
72 twos
[i
]->object
.flags
|= PARENT2
;
73 prio_queue_put(&queue
, twos
[i
]);
76 while (queue_has_nonstale(&queue
)) {
77 struct commit
*commit
= prio_queue_get(&queue
);
78 struct commit_list
*parents
;
80 timestamp_t generation
= commit_graph_generation(commit
);
82 if (min_generation
&& generation
> last_gen
)
83 BUG("bad generation skip %"PRItime
" > %"PRItime
" at %s",
85 oid_to_hex(&commit
->object
.oid
));
86 last_gen
= generation
;
88 if (generation
< min_generation
)
91 flags
= commit
->object
.flags
& (PARENT1
| PARENT2
| STALE
);
92 if (flags
== (PARENT1
| PARENT2
)) {
93 if (!(commit
->object
.flags
& RESULT
)) {
94 commit
->object
.flags
|= RESULT
;
95 commit_list_insert_by_date(commit
, &result
);
97 /* Mark parents of a found merge stale */
100 parents
= commit
->parents
;
102 struct commit
*p
= parents
->item
;
103 parents
= parents
->next
;
104 if ((p
->object
.flags
& flags
) == flags
)
106 if (repo_parse_commit(r
, p
))
108 p
->object
.flags
|= flags
;
109 prio_queue_put(&queue
, p
);
113 clear_prio_queue(&queue
);
117 static struct commit_list
*merge_bases_many(struct repository
*r
,
118 struct commit
*one
, int n
,
119 struct commit
**twos
)
121 struct commit_list
*list
= NULL
;
122 struct commit_list
*result
= NULL
;
125 for (i
= 0; i
< n
; i
++) {
128 * We do not mark this even with RESULT so we do not
129 * have to clean it up.
131 return commit_list_insert(one
, &result
);
134 if (repo_parse_commit(r
, one
))
136 for (i
= 0; i
< n
; i
++) {
137 if (repo_parse_commit(r
, twos
[i
]))
141 list
= paint_down_to_common(r
, one
, n
, twos
, 0);
144 struct commit
*commit
= pop_commit(&list
);
145 if (!(commit
->object
.flags
& STALE
))
146 commit_list_insert_by_date(commit
, &result
);
151 struct commit_list
*get_octopus_merge_bases(struct commit_list
*in
)
153 struct commit_list
*i
, *j
, *k
, *ret
= NULL
;
158 commit_list_insert(in
->item
, &ret
);
160 for (i
= in
->next
; i
; i
= i
->next
) {
161 struct commit_list
*new_commits
= NULL
, *end
= NULL
;
163 for (j
= ret
; j
; j
= j
->next
) {
164 struct commit_list
*bases
;
165 bases
= get_merge_bases(i
->item
, j
->item
);
170 for (k
= bases
; k
; k
= k
->next
)
178 static int remove_redundant_no_gen(struct repository
*r
,
179 struct commit
**array
, int cnt
)
181 struct commit
**work
;
182 unsigned char *redundant
;
186 work
= xcalloc(cnt
, sizeof(*work
));
187 redundant
= xcalloc(cnt
, 1);
188 ALLOC_ARRAY(filled_index
, cnt
- 1);
190 for (i
= 0; i
< cnt
; i
++)
191 repo_parse_commit(r
, array
[i
]);
192 for (i
= 0; i
< cnt
; i
++) {
193 struct commit_list
*common
;
194 timestamp_t min_generation
= commit_graph_generation(array
[i
]);
198 for (j
= filled
= 0; j
< cnt
; j
++) {
199 timestamp_t curr_generation
;
200 if (i
== j
|| redundant
[j
])
202 filled_index
[filled
] = j
;
203 work
[filled
++] = array
[j
];
205 curr_generation
= commit_graph_generation(array
[j
]);
206 if (curr_generation
< min_generation
)
207 min_generation
= curr_generation
;
209 common
= paint_down_to_common(r
, array
[i
], filled
,
210 work
, min_generation
);
211 if (array
[i
]->object
.flags
& PARENT2
)
213 for (j
= 0; j
< filled
; j
++)
214 if (work
[j
]->object
.flags
& PARENT1
)
215 redundant
[filled_index
[j
]] = 1;
216 clear_commit_marks(array
[i
], all_flags
);
217 clear_commit_marks_many(filled
, work
, all_flags
);
218 free_commit_list(common
);
221 /* Now collect the result */
222 COPY_ARRAY(work
, array
, cnt
);
223 for (i
= filled
= 0; i
< cnt
; i
++)
225 array
[filled
++] = work
[i
];
232 static int remove_redundant_with_gen(struct repository
*r
,
233 struct commit
**array
, int cnt
)
235 int i
, count_non_stale
= 0, count_still_independent
= cnt
;
236 timestamp_t min_generation
= GENERATION_NUMBER_INFINITY
;
237 struct commit
**walk_start
;
238 size_t walk_start_nr
= 0, walk_start_alloc
= cnt
;
240 ALLOC_ARRAY(walk_start
, walk_start_alloc
);
242 /* Mark all parents of the input as STALE */
243 for (i
= 0; i
< cnt
; i
++) {
244 struct commit_list
*parents
;
245 timestamp_t generation
;
247 repo_parse_commit(r
, array
[i
]);
248 array
[i
]->object
.flags
|= RESULT
;
249 parents
= array
[i
]->parents
;
252 repo_parse_commit(r
, parents
->item
);
253 if (!(parents
->item
->object
.flags
& STALE
)) {
254 parents
->item
->object
.flags
|= STALE
;
255 ALLOC_GROW(walk_start
, walk_start_nr
+ 1, walk_start_alloc
);
256 walk_start
[walk_start_nr
++] = parents
->item
;
258 parents
= parents
->next
;
261 generation
= commit_graph_generation(array
[i
]);
263 if (generation
< min_generation
)
264 min_generation
= generation
;
267 QSORT(walk_start
, walk_start_nr
, compare_commits_by_gen
);
269 /* remove STALE bit for now to allow walking through parents */
270 for (i
= 0; i
< walk_start_nr
; i
++)
271 walk_start
[i
]->object
.flags
&= ~STALE
;
274 * Start walking from the highest generation. Hopefully, it will
275 * find all other items during the first-parent walk, and we can
276 * terminate early. Otherwise, we will do the same amount of work
279 for (i
= walk_start_nr
- 1; i
>= 0 && count_still_independent
> 1; i
--) {
280 /* push the STALE bits up to min generation */
281 struct commit_list
*stack
= NULL
;
283 commit_list_insert(walk_start
[i
], &stack
);
284 walk_start
[i
]->object
.flags
|= STALE
;
287 struct commit_list
*parents
;
288 struct commit
*c
= stack
->item
;
290 repo_parse_commit(r
, c
);
292 if (c
->object
.flags
& RESULT
) {
293 c
->object
.flags
&= ~RESULT
;
294 if (--count_still_independent
<= 1)
298 if (commit_graph_generation(c
) < min_generation
) {
303 parents
= c
->parents
;
305 if (!(parents
->item
->object
.flags
& STALE
)) {
306 parents
->item
->object
.flags
|= STALE
;
307 commit_list_insert(parents
->item
, &stack
);
310 parents
= parents
->next
;
313 /* pop if all parents have been visited already */
317 free_commit_list(stack
);
321 for (i
= 0; i
< cnt
; i
++)
322 array
[i
]->object
.flags
&= ~RESULT
;
324 /* rearrange array */
325 for (i
= count_non_stale
= 0; i
< cnt
; i
++) {
326 if (!(array
[i
]->object
.flags
& STALE
))
327 array
[count_non_stale
++] = array
[i
];
331 clear_commit_marks_many(walk_start_nr
, walk_start
, STALE
);
334 return count_non_stale
;
337 static int remove_redundant(struct repository
*r
, struct commit
**array
, int cnt
)
340 * Some commit in the array may be an ancestor of
341 * another commit. Move the independent commits to the
342 * beginning of 'array' and return their number. Callers
343 * should not rely upon the contents of 'array' after
346 if (generation_numbers_enabled(r
)) {
350 * If we have a single commit with finite generation
351 * number, then the _with_gen algorithm is preferred.
353 for (i
= 0; i
< cnt
; i
++) {
354 if (commit_graph_generation(array
[i
]) < GENERATION_NUMBER_INFINITY
)
355 return remove_redundant_with_gen(r
, array
, cnt
);
359 return remove_redundant_no_gen(r
, array
, cnt
);
362 static struct commit_list
*get_merge_bases_many_0(struct repository
*r
,
365 struct commit
**twos
,
368 struct commit_list
*list
;
369 struct commit
**rslt
;
370 struct commit_list
*result
;
373 result
= merge_bases_many(r
, one
, n
, twos
);
374 for (i
= 0; i
< n
; i
++) {
378 if (!result
|| !result
->next
) {
380 clear_commit_marks(one
, all_flags
);
381 clear_commit_marks_many(n
, twos
, all_flags
);
386 /* There are more than one */
387 cnt
= commit_list_count(result
);
388 rslt
= xcalloc(cnt
, sizeof(*rslt
));
389 for (list
= result
, i
= 0; list
; list
= list
->next
)
390 rslt
[i
++] = list
->item
;
391 free_commit_list(result
);
393 clear_commit_marks(one
, all_flags
);
394 clear_commit_marks_many(n
, twos
, all_flags
);
396 cnt
= remove_redundant(r
, rslt
, cnt
);
398 for (i
= 0; i
< cnt
; i
++)
399 commit_list_insert_by_date(rslt
[i
], &result
);
404 struct commit_list
*repo_get_merge_bases_many(struct repository
*r
,
407 struct commit
**twos
)
409 return get_merge_bases_many_0(r
, one
, n
, twos
, 1);
412 struct commit_list
*repo_get_merge_bases_many_dirty(struct repository
*r
,
415 struct commit
**twos
)
417 return get_merge_bases_many_0(r
, one
, n
, twos
, 0);
420 struct commit_list
*repo_get_merge_bases(struct repository
*r
,
424 return get_merge_bases_many_0(r
, one
, 1, &two
, 1);
428 * Is "commit" a descendant of one of the elements on the "with_commit" list?
430 int repo_is_descendant_of(struct repository
*r
,
431 struct commit
*commit
,
432 struct commit_list
*with_commit
)
437 if (generation_numbers_enabled(the_repository
)) {
438 struct commit_list
*from_list
= NULL
;
440 commit_list_insert(commit
, &from_list
);
441 result
= can_all_from_reach(from_list
, with_commit
, 0);
442 free_commit_list(from_list
);
445 while (with_commit
) {
446 struct commit
*other
;
448 other
= with_commit
->item
;
449 with_commit
= with_commit
->next
;
450 if (repo_in_merge_bases_many(r
, other
, 1, &commit
))
458 * Is "commit" an ancestor of one of the "references"?
460 int repo_in_merge_bases_many(struct repository
*r
, struct commit
*commit
,
461 int nr_reference
, struct commit
**reference
)
463 struct commit_list
*bases
;
465 timestamp_t generation
, max_generation
= GENERATION_NUMBER_ZERO
;
467 if (repo_parse_commit(r
, commit
))
469 for (i
= 0; i
< nr_reference
; i
++) {
470 if (repo_parse_commit(r
, reference
[i
]))
473 generation
= commit_graph_generation(reference
[i
]);
474 if (generation
> max_generation
)
475 max_generation
= generation
;
478 generation
= commit_graph_generation(commit
);
479 if (generation
> max_generation
)
482 bases
= paint_down_to_common(r
, commit
,
483 nr_reference
, reference
,
485 if (commit
->object
.flags
& PARENT2
)
487 clear_commit_marks(commit
, all_flags
);
488 clear_commit_marks_many(nr_reference
, reference
, all_flags
);
489 free_commit_list(bases
);
494 * Is "commit" an ancestor of (i.e. reachable from) the "reference"?
496 int repo_in_merge_bases(struct repository
*r
,
497 struct commit
*commit
,
498 struct commit
*reference
)
501 struct commit_list
*list
= NULL
;
502 struct commit_list
**next
= &list
;
504 next
= commit_list_append(commit
, next
);
505 res
= repo_is_descendant_of(r
, reference
, list
);
506 free_commit_list(list
);
511 struct commit_list
*reduce_heads(struct commit_list
*heads
)
513 struct commit_list
*p
;
514 struct commit_list
*result
= NULL
, **tail
= &result
;
515 struct commit
**array
;
522 for (p
= heads
; p
; p
= p
->next
)
523 p
->item
->object
.flags
&= ~STALE
;
524 for (p
= heads
, num_head
= 0; p
; p
= p
->next
) {
525 if (p
->item
->object
.flags
& STALE
)
527 p
->item
->object
.flags
|= STALE
;
530 array
= xcalloc(num_head
, sizeof(*array
));
531 for (p
= heads
, i
= 0; p
; p
= p
->next
) {
532 if (p
->item
->object
.flags
& STALE
) {
533 array
[i
++] = p
->item
;
534 p
->item
->object
.flags
&= ~STALE
;
537 num_head
= remove_redundant(the_repository
, array
, num_head
);
538 for (i
= 0; i
< num_head
; i
++)
539 tail
= &commit_list_insert(array
[i
], tail
)->next
;
544 void reduce_heads_replace(struct commit_list
**heads
)
546 struct commit_list
*result
= reduce_heads(*heads
);
547 free_commit_list(*heads
);
551 int ref_newer(const struct object_id
*new_oid
, const struct object_id
*old_oid
)
554 struct commit
*old_commit
, *new_commit
;
555 struct commit_list
*old_commit_list
= NULL
;
559 * Both new_commit and old_commit must be commit-ish and new_commit is descendant of
560 * old_commit. Otherwise we require --force.
562 o
= deref_tag(the_repository
, parse_object(the_repository
, old_oid
),
564 if (!o
|| o
->type
!= OBJ_COMMIT
)
566 old_commit
= (struct commit
*) o
;
568 o
= deref_tag(the_repository
, parse_object(the_repository
, new_oid
),
570 if (!o
|| o
->type
!= OBJ_COMMIT
)
572 new_commit
= (struct commit
*) o
;
574 if (parse_commit(new_commit
) < 0)
577 commit_list_insert(old_commit
, &old_commit_list
);
578 ret
= repo_is_descendant_of(the_repository
,
579 new_commit
, old_commit_list
);
580 free_commit_list(old_commit_list
);
585 * Mimicking the real stack, this stack lives on the heap, avoiding stack
588 * At each recursion step, the stack items points to the commits whose
589 * ancestors are to be inspected.
591 struct contains_stack
{
593 struct contains_stack_entry
{
594 struct commit
*commit
;
595 struct commit_list
*parents
;
599 static int in_commit_list(const struct commit_list
*want
, struct commit
*c
)
601 for (; want
; want
= want
->next
)
602 if (oideq(&want
->item
->object
.oid
, &c
->object
.oid
))
608 * Test whether the candidate is contained in the list.
609 * Do not recurse to find out, though, but return -1 if inconclusive.
611 static enum contains_result
contains_test(struct commit
*candidate
,
612 const struct commit_list
*want
,
613 struct contains_cache
*cache
,
616 enum contains_result
*cached
= contains_cache_at(cache
, candidate
);
618 /* If we already have the answer cached, return that. */
623 if (in_commit_list(want
, candidate
)) {
624 *cached
= CONTAINS_YES
;
628 /* Otherwise, we don't know; prepare to recurse */
629 parse_commit_or_die(candidate
);
631 if (commit_graph_generation(candidate
) < cutoff
)
634 return CONTAINS_UNKNOWN
;
637 static void push_to_contains_stack(struct commit
*candidate
, struct contains_stack
*contains_stack
)
639 ALLOC_GROW(contains_stack
->contains_stack
, contains_stack
->nr
+ 1, contains_stack
->alloc
);
640 contains_stack
->contains_stack
[contains_stack
->nr
].commit
= candidate
;
641 contains_stack
->contains_stack
[contains_stack
->nr
++].parents
= candidate
->parents
;
644 static enum contains_result
contains_tag_algo(struct commit
*candidate
,
645 const struct commit_list
*want
,
646 struct contains_cache
*cache
)
648 struct contains_stack contains_stack
= { 0, 0, NULL
};
649 enum contains_result result
;
650 timestamp_t cutoff
= GENERATION_NUMBER_INFINITY
;
651 const struct commit_list
*p
;
653 for (p
= want
; p
; p
= p
->next
) {
654 timestamp_t generation
;
655 struct commit
*c
= p
->item
;
656 load_commit_graph_info(the_repository
, c
);
657 generation
= commit_graph_generation(c
);
658 if (generation
< cutoff
)
662 result
= contains_test(candidate
, want
, cache
, cutoff
);
663 if (result
!= CONTAINS_UNKNOWN
)
666 push_to_contains_stack(candidate
, &contains_stack
);
667 while (contains_stack
.nr
) {
668 struct contains_stack_entry
*entry
= &contains_stack
.contains_stack
[contains_stack
.nr
- 1];
669 struct commit
*commit
= entry
->commit
;
670 struct commit_list
*parents
= entry
->parents
;
673 *contains_cache_at(cache
, commit
) = CONTAINS_NO
;
677 * If we just popped the stack, parents->item has been marked,
678 * therefore contains_test will return a meaningful yes/no.
680 else switch (contains_test(parents
->item
, want
, cache
, cutoff
)) {
682 *contains_cache_at(cache
, commit
) = CONTAINS_YES
;
686 entry
->parents
= parents
->next
;
688 case CONTAINS_UNKNOWN
:
689 push_to_contains_stack(parents
->item
, &contains_stack
);
693 free(contains_stack
.contains_stack
);
694 return contains_test(candidate
, want
, cache
, cutoff
);
697 int commit_contains(struct ref_filter
*filter
, struct commit
*commit
,
698 struct commit_list
*list
, struct contains_cache
*cache
)
700 if (filter
->with_commit_tag_algo
)
701 return contains_tag_algo(commit
, list
, cache
) == CONTAINS_YES
;
702 return repo_is_descendant_of(the_repository
, commit
, list
);
705 int can_all_from_reach_with_flag(struct object_array
*from
,
706 unsigned int with_flag
,
707 unsigned int assign_flag
,
708 time_t min_commit_date
,
709 timestamp_t min_generation
)
711 struct commit
**list
= NULL
;
716 ALLOC_ARRAY(list
, from
->nr
);
718 for (i
= 0; i
< from
->nr
; i
++) {
719 struct object
*from_one
= from
->objects
[i
].item
;
721 if (!from_one
|| from_one
->flags
& assign_flag
)
724 from_one
= deref_tag(the_repository
, from_one
,
726 if (!from_one
|| from_one
->type
!= OBJ_COMMIT
) {
728 * no way to tell if this is reachable by
729 * looking at the ancestry chain alone, so
730 * leave a note to ourselves not to worry about
731 * this object anymore.
733 from
->objects
[i
].item
->flags
|= assign_flag
;
737 list
[nr_commits
] = (struct commit
*)from_one
;
738 if (parse_commit(list
[nr_commits
]) ||
739 commit_graph_generation(list
[nr_commits
]) < min_generation
) {
747 QSORT(list
, nr_commits
, compare_commits_by_gen
);
749 for (i
= 0; i
< nr_commits
; i
++) {
750 /* DFS from list[i] */
751 struct commit_list
*stack
= NULL
;
753 list
[i
]->object
.flags
|= assign_flag
;
754 commit_list_insert(list
[i
], &stack
);
757 struct commit_list
*parent
;
759 if (stack
->item
->object
.flags
& (with_flag
| RESULT
)) {
762 stack
->item
->object
.flags
|= RESULT
;
766 for (parent
= stack
->item
->parents
; parent
; parent
= parent
->next
) {
767 if (parent
->item
->object
.flags
& (with_flag
| RESULT
))
768 stack
->item
->object
.flags
|= RESULT
;
770 if (!(parent
->item
->object
.flags
& assign_flag
)) {
771 parent
->item
->object
.flags
|= assign_flag
;
773 if (parse_commit(parent
->item
) ||
774 parent
->item
->date
< min_commit_date
||
775 commit_graph_generation(parent
->item
) < min_generation
)
778 commit_list_insert(parent
->item
, &stack
);
787 if (!(list
[i
]->object
.flags
& (with_flag
| RESULT
))) {
794 clear_commit_marks_many(nr_commits
, list
, RESULT
| assign_flag
);
797 for (i
= 0; i
< from
->nr
; i
++)
798 from
->objects
[i
].item
->flags
&= ~assign_flag
;
803 int can_all_from_reach(struct commit_list
*from
, struct commit_list
*to
,
804 int cutoff_by_min_date
)
806 struct object_array from_objs
= OBJECT_ARRAY_INIT
;
807 time_t min_commit_date
= cutoff_by_min_date
? from
->item
->date
: 0;
808 struct commit_list
*from_iter
= from
, *to_iter
= to
;
810 timestamp_t min_generation
= GENERATION_NUMBER_INFINITY
;
813 add_object_array(&from_iter
->item
->object
, NULL
, &from_objs
);
815 if (!parse_commit(from_iter
->item
)) {
816 timestamp_t generation
;
817 if (from_iter
->item
->date
< min_commit_date
)
818 min_commit_date
= from_iter
->item
->date
;
820 generation
= commit_graph_generation(from_iter
->item
);
821 if (generation
< min_generation
)
822 min_generation
= generation
;
825 from_iter
= from_iter
->next
;
829 if (!parse_commit(to_iter
->item
)) {
830 timestamp_t generation
;
831 if (to_iter
->item
->date
< min_commit_date
)
832 min_commit_date
= to_iter
->item
->date
;
834 generation
= commit_graph_generation(to_iter
->item
);
835 if (generation
< min_generation
)
836 min_generation
= generation
;
839 to_iter
->item
->object
.flags
|= PARENT2
;
841 to_iter
= to_iter
->next
;
844 result
= can_all_from_reach_with_flag(&from_objs
, PARENT2
, PARENT1
,
845 min_commit_date
, min_generation
);
848 clear_commit_marks(from
->item
, PARENT1
);
853 clear_commit_marks(to
->item
, PARENT2
);
857 object_array_clear(&from_objs
);
861 struct commit_list
*get_reachable_subset(struct commit
**from
, int nr_from
,
862 struct commit
**to
, int nr_to
,
863 unsigned int reachable_flag
)
865 struct commit
**item
;
866 struct commit
*current
;
867 struct commit_list
*found_commits
= NULL
;
868 struct commit
**to_last
= to
+ nr_to
;
869 struct commit
**from_last
= from
+ nr_from
;
870 timestamp_t min_generation
= GENERATION_NUMBER_INFINITY
;
873 struct prio_queue queue
= { compare_commits_by_gen_then_commit_date
};
875 for (item
= to
; item
< to_last
; item
++) {
876 timestamp_t generation
;
877 struct commit
*c
= *item
;
880 generation
= commit_graph_generation(c
);
881 if (generation
< min_generation
)
882 min_generation
= generation
;
884 if (!(c
->object
.flags
& PARENT1
)) {
885 c
->object
.flags
|= PARENT1
;
890 for (item
= from
; item
< from_last
; item
++) {
891 struct commit
*c
= *item
;
892 if (!(c
->object
.flags
& PARENT2
)) {
893 c
->object
.flags
|= PARENT2
;
896 prio_queue_put(&queue
, *item
);
900 while (num_to_find
&& (current
= prio_queue_get(&queue
)) != NULL
) {
901 struct commit_list
*parents
;
903 if (current
->object
.flags
& PARENT1
) {
904 current
->object
.flags
&= ~PARENT1
;
905 current
->object
.flags
|= reachable_flag
;
906 commit_list_insert(current
, &found_commits
);
910 for (parents
= current
->parents
; parents
; parents
= parents
->next
) {
911 struct commit
*p
= parents
->item
;
915 if (commit_graph_generation(p
) < min_generation
)
918 if (p
->object
.flags
& PARENT2
)
921 p
->object
.flags
|= PARENT2
;
922 prio_queue_put(&queue
, p
);
926 clear_commit_marks_many(nr_to
, to
, PARENT1
);
927 clear_commit_marks_many(nr_from
, from
, PARENT2
);
929 return found_commits
;