Hi Yasushi, On Sat, Jan 6, 2018 at 3:27 PM, Yasushi SHOJI <yasushi.shoji@xxxxxxxxx> wrote: > best_bisection_sorted() seems to do > > - get the commit list along with the number of elements in the list > - walk the list one by one to check whether a element have TREESAME or not > - if TREESAME, skip > - if not, add it to array > - sort the array by distance > - put elements back to the list Yes. > so, if you find TREESAME, you get less elements than given, right? Yes. > Also, if you sort, the last commit, which has NULL in the ->next, > might get in the middle of the array?? Well, first the array is just necessary to sort the items pointed to by the list. It is freed at the end of the function. We are mostly interested in getting a sorted list from this function, not a sorted array. Also the array contains only items (commits) and distances, not list elements, so the elements in the array don't have a ->next pointer. About items in the list, when we put them back into the list we only change p->item, so p->next still points to the next one. Only for the last one we set p->next to NULL (if p is not NULL). So we don't actually sort the list elements, we sort the items pointed to by the list. > # BTW, is it really fast to use QSORT even if you have to convert to > # an array from list? It is easier and probably faster to just use qsort, which we get from #include <stdlib.h>, as it is hopefully optimized, rather than reimplementing our own list sorting. >>>> Since nobody noticed it since 7c117184d7, it must be a rare case, right? >> >> Right, you marked a commit both good and bad. That's probably not very >> common. But it obviously happens. :-) Yeah, mistakes unfortunately happens :-) >> Thank you for providing a script for reproducing this. It helped me come >> up with the attached patch. The patch is based on ma/bisect-leakfix, >> which includes Ævar's patch. >> >> I think this patch could be useful, either as a final "let's test >> something previously non-tested; this would have caught the segfault", >> or simply squashed into Ævar's patch as a "let's add a test that would >> have caught this, and which also tests a previously non-tested code >> path." > > Do we really need that? What is a practical use of a commit having > both good and bad? It is not practical, but it is a user mistake that happens. Thanks for your reports and test cases, Christian.
