From patchwork Fri Nov 2 13:14:45 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bruce Perry via GitGitGadget X-Patchwork-Id: 10665527 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 9B66C13B5 for ; Fri, 2 Nov 2018 13:14:51 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 918072B598 for ; Fri, 2 Nov 2018 13:14:51 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 84B4E2B684; Fri, 2 Nov 2018 13:14:51 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 977FE2B598 for ; Fri, 2 Nov 2018 13:14:49 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727552AbeKBWVz (ORCPT ); Fri, 2 Nov 2018 18:21:55 -0400 Received: from mail-pg1-f193.google.com ([209.85.215.193]:34418 "EHLO mail-pg1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726094AbeKBWVz (ORCPT ); Fri, 2 Nov 2018 18:21:55 -0400 Received: by mail-pg1-f193.google.com with SMTP id k1-v6so996016pgq.1 for ; Fri, 02 Nov 2018 06:14:47 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=ITjmFg+PlIsAwHo1QEhE9E61cL2wnOaGWDvxGULWtNQ=; b=p268/RqrBL+qILfa0QfCtE6X85feFXOsJ4Jq+wOT+wVRUffH/REJN/koiCMn6vodQJ u0cHtg/DjlEutTa2u1/soYncSph//UmzpQK3GQPCkhFY++3fPmDz92UuUAlFEQyis2G1 eeBVyG7ebV7Sp/bzpB1QMcmcwcB8jEyezbQJoD874t/cMRDMrNKmWwjxP765KS+KLwaY CO0Zvz1P/wSpmviLG07UHeZgLrF3QgiQ+sqI6AlMEFkv9Cz2aB9lwiwp8orbdu5zDRyN FQOzBdScM/McP8HnhYPAC/1jHoqD/v4MnaYYTtca/nwlPKvL2YiBnhYIihR5fRnWi1D5 lM1Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=ITjmFg+PlIsAwHo1QEhE9E61cL2wnOaGWDvxGULWtNQ=; b=FJOXKBQorApo8Db77huq0oPLTYIC6ny1UDBdRd1K8IzhWQP6BAQ/jSLDwX7xI69iXK YbAYmnCNPyOsNlL+fxjNo7vFxclK2vt2bcRBsf+tRuE1XggSdXWl7b/NCdO51qEGpGZs uDmjz2MUdaQf6usQ8Swy1txUb8OiKjojxmlZ5AVEy17s5zFwNckS4jd+DJO6K8zxOKqq svGkaQJd5wS17CTIbpsEb47HUzPh3qQLzApajblepAloPVr0CfXgUEW33Q16u0v5V6BX qBGNimZz4Q3OXIv9XQ2TZQL/XzD+rDy4SXIk1SuETkfiyhGdCzfQud86Q9TXROmChxDf OLdA== X-Gm-Message-State: AGRZ1gIED3NW3LLCPBF0Ef6HhFuWvAhu6OMFX2O/cd1SB1K8G/6xb4yp 1W2k2ztkpIqxvjOqHHZYrjSTnt1j X-Google-Smtp-Source: AJdET5dGYq3lq2ShGjMjAzWzJpcej8mnlEJvhfEsMm2Vu+0k4bvvvTXYK8F4HcFPRTYgQtacPngqDw== X-Received: by 2002:a63:181:: with SMTP id 123-v6mr11045984pgb.149.1541164486571; Fri, 02 Nov 2018 06:14:46 -0700 (PDT) Received: from [127.0.0.1] ([40.112.137.127]) by smtp.gmail.com with ESMTPSA id p15-v6sm28963625pfj.72.2018.11.02.06.14.45 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 02 Nov 2018 06:14:45 -0700 (PDT) Date: Fri, 02 Nov 2018 06:14:45 -0700 (PDT) X-Google-Original-Date: Fri, 02 Nov 2018 13:14:40 GMT Message-Id: <9e570603bda528986f425cae8a9c32ba700bc29b.1541164482.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v2 1/3] commit-reach: implement get_reachable_subset Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: peff@peff.net, newren@gmail.com, Junio C Hamano , Derrick Stolee Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Derrick Stolee The existing reachability algorithms in commit-reach.c focus on finding merge-bases or determining if all commits in a set X can reach at least one commit in a set Y. However, for two commits sets X and Y, we may also care about which commits in Y are reachable from at least one commit in X. Implement get_reachable_subset() which answers this question. Given two arrays of commits, 'from' and 'to', return a commit_list with every commit from the 'to' array that is reachable from at least one commit in the 'from' array. The algorithm is a simple walk starting at the 'from' commits, using the PARENT2 flag to indicate "this commit has already been added to the walk queue". By marking the 'to' commits with the PARENT1 flag, we can determine when we see a commit from the 'to' array. We remove the PARENT1 flag as we add that commit to the result list to avoid duplicates. The order of the resulting list is a reverse of the order that the commits are discovered in the walk. There are a couple shortcuts to avoid walking more than we need: 1. We determine the minimum generation number of commits in the 'to' array. We do not walk commits with generation number below this minimum. 2. We count how many distinct commits are in the 'to' array, and decrement this count when we discover a 'to' commit during the walk. If this number reaches zero, then we can terminate the walk. Tests will be added using the 'test-tool reach' helper in a subsequent commit. Signed-off-by: Derrick Stolee --- commit-reach.c | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++ commit-reach.h | 13 ++++++++++ 2 files changed, 83 insertions(+) diff --git a/commit-reach.c b/commit-reach.c index 9f79ce0a22..8ad5352752 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -688,3 +688,73 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to, object_array_clear(&from_objs); return result; } + +struct commit_list *get_reachable_subset(struct commit **from, int nr_from, + struct commit **to, int nr_to, + unsigned int reachable_flag) +{ + struct commit **item; + struct commit *current; + struct commit_list *found_commits = NULL; + struct commit **to_last = to + nr_to; + struct commit **from_last = from + nr_from; + uint32_t min_generation = GENERATION_NUMBER_INFINITY; + int num_to_find = 0; + + struct prio_queue queue = { compare_commits_by_gen_then_commit_date }; + + for (item = to; item < to_last; item++) { + struct commit *c = *item; + + parse_commit(c); + if (c->generation < min_generation) + min_generation = c->generation; + + if (!(c->object.flags & PARENT1)) { + c->object.flags |= PARENT1; + num_to_find++; + } + } + + for (item = from; item < from_last; item++) { + struct commit *c = *item; + if (!(c->object.flags & PARENT2)) { + c->object.flags |= PARENT2; + parse_commit(c); + + prio_queue_put(&queue, *item); + } + } + + while (num_to_find && (current = prio_queue_get(&queue)) != NULL) { + struct commit_list *parents; + + if (current->object.flags & PARENT1) { + current->object.flags &= ~PARENT1; + current->object.flags |= reachable_flag; + commit_list_insert(current, &found_commits); + num_to_find--; + } + + for (parents = current->parents; parents; parents = parents->next) { + struct commit *p = parents->item; + + parse_commit(p); + + if (p->generation < min_generation) + continue; + + if (p->object.flags & PARENT2) + continue; + + p->object.flags |= PARENT2; + prio_queue_put(&queue, p); + } + } + + clear_commit_marks_many(nr_to, to, PARENT1); + clear_commit_marks_many(nr_from, from, PARENT2); + + return found_commits; +} + diff --git a/commit-reach.h b/commit-reach.h index 7d313e2975..bb34af0269 100644 --- a/commit-reach.h +++ b/commit-reach.h @@ -74,4 +74,17 @@ int can_all_from_reach_with_flag(struct object_array *from, int can_all_from_reach(struct commit_list *from, struct commit_list *to, int commit_date_cutoff); + +/* + * Return a list of commits containing the commits in the 'to' array + * that are reachable from at least one commit in the 'from' array. + * Also add the given 'flag' to each of the commits in the returned list. + * + * This method uses the PARENT1 and PARENT2 flags during its operation, + * so be sure these flags are not set before calling the method. + */ +struct commit_list *get_reachable_subset(struct commit **from, int nr_from, + struct commit **to, int nr_to, + unsigned int reachable_flag); + #endif From patchwork Fri Nov 2 13:14:47 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bruce Perry via GitGitGadget X-Patchwork-Id: 10665529 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 7211213B5 for ; Fri, 2 Nov 2018 13:14:52 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 6A6EA2B598 for ; Fri, 2 Nov 2018 13:14:52 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 5E9CC2B645; Fri, 2 Nov 2018 13:14:52 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id E72A12B639 for ; Fri, 2 Nov 2018 13:14:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727591AbeKBWV5 (ORCPT ); Fri, 2 Nov 2018 18:21:57 -0400 Received: from mail-pg1-f193.google.com ([209.85.215.193]:39736 "EHLO mail-pg1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726094AbeKBWV4 (ORCPT ); Fri, 2 Nov 2018 18:21:56 -0400 Received: by mail-pg1-f193.google.com with SMTP id r9-v6so984195pgv.6 for ; Fri, 02 Nov 2018 06:14:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=GPhYaq+heCDb7TbygE+8+SqfEFWI0gLbUbkBgEqQOpY=; b=HvM9OKlqZFX5kk3sKi3EhAecCnY/Tali4YW/jw7p9GWloV41hHdE8L1sonLvA+HvM0 sd6KlkZtpChkmhD4RNR7+febi2n1//Osw4j4kbsAaczf1Qcw8XcahJzbg/qLJS8ryqbb sUYACxTMoIT+uL2Kf7RsBpGDVYZyNoscjoL4bf++LdCv0sKxNDWFtudnr4AiOgzi3bo9 k8fOVBpBWbeSmhKYrZqmX/MxINPrRPHSWpktujNYWzn36GPky5Z1kB66I0aQ77Vi4etp Olwk53zEBxX39DYJMsHpubPeqdKoPaxyvOXXAKX71e3ouL04Ut1iGD6isarqDK0MgiBi F5IQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=GPhYaq+heCDb7TbygE+8+SqfEFWI0gLbUbkBgEqQOpY=; b=gRof8BOrg4T+BoDPm7Pv5N+aRwSs1yDZUgDydbaeLmMZaG/f7VglRyFFWOBt7chZC5 LfGmWVJGW8y1td1keJdnhPPTnkytToylNsYGKwoHRIbIeBn0iESoBt3YKGk0HiAbKDz1 p6/yVlhvlAnqkHOokwkSmMk0/jNECkZGXdSVM23xNo/GMylmWpgPjHDQPkDi3bhnDFpi AD7pI9ePNxcq7bZhmGW/M3T/UCWPVYfa2UZrzuJuQVC2OiPRs9W4gSFX0kEmzONsi6Zm cGIQmCmo/2fy46H/6Ihwf3OlyhL+KQ49KwAEt6VlMLQyLmmaFcF/Z0lGcnmWIa07BLb9 29yQ== X-Gm-Message-State: AGRZ1gIX1RUfKJJt2joc3Ojmjy/j66XzByzngp7hsKlyxl5UiNBmG8lt p03LiMnvq7BTSVpHv92byvJn1jQ5 X-Google-Smtp-Source: AJdET5fT6zxkj22OwzYP2hpS86r2DdmaHXUzgjFJi2BWzsavRWyLh5kpTfpVI5mqfaRJhSufa4x8qw== X-Received: by 2002:a62:9c8c:: with SMTP id u12-v6mr11692642pfk.162.1541164488030; Fri, 02 Nov 2018 06:14:48 -0700 (PDT) Received: from [127.0.0.1] ([40.112.137.127]) by smtp.gmail.com with ESMTPSA id s13-v6sm85674606pgs.76.2018.11.02.06.14.46 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 02 Nov 2018 06:14:47 -0700 (PDT) Date: Fri, 02 Nov 2018 06:14:47 -0700 (PDT) X-Google-Original-Date: Fri, 02 Nov 2018 13:14:41 GMT Message-Id: <52e847b9288439f25a7e06abfe0c68bc1e6dc915.1541164482.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v2 2/3] test-reach: test get_reachable_subset Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: peff@peff.net, newren@gmail.com, Junio C Hamano , Derrick Stolee Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Derrick Stolee The get_reachable_subset() method returns the list of commits in the 'to' array that are reachable from at least one commit in the 'from' array. Add tests that check this method works in a few cases: 1. All commits in the 'to' list are reachable. This exercises the early-termination condition. 2. Some commits in the 'to' list are reachable. This exercises the loop-termination condition. 3. No commits in the 'to' list are reachable. This exercises the NULL return condition. Signed-off-by: Derrick Stolee --- t/helper/test-reach.c | 34 ++++++++++++++++++++++++---- t/t6600-test-reach.sh | 52 +++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 82 insertions(+), 4 deletions(-) diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c index 08d2ea68e8..a0272178b7 100644 --- a/t/helper/test-reach.c +++ b/t/helper/test-reach.c @@ -32,8 +32,8 @@ int cmd__reach(int ac, const char **av) struct commit *A, *B; struct commit_list *X, *Y; struct object_array X_obj = OBJECT_ARRAY_INIT; - struct commit **X_array; - int X_nr, X_alloc; + struct commit **X_array, **Y_array; + int X_nr, X_alloc, Y_nr, Y_alloc; struct strbuf buf = STRBUF_INIT; struct repository *r = the_repository; @@ -44,9 +44,10 @@ int cmd__reach(int ac, const char **av) A = B = NULL; X = Y = NULL; - X_nr = 0; - X_alloc = 16; + X_nr = Y_nr = 0; + X_alloc = Y_alloc = 16; ALLOC_ARRAY(X_array, X_alloc); + ALLOC_ARRAY(Y_array, Y_alloc); while (strbuf_getline(&buf, stdin) != EOF) { struct object_id oid; @@ -92,6 +93,8 @@ int cmd__reach(int ac, const char **av) case 'Y': commit_list_insert(c, &Y); + ALLOC_GROW(Y_array, Y_nr + 1, Y_alloc); + Y_array[Y_nr++] = c; break; default: @@ -136,6 +139,29 @@ int cmd__reach(int ac, const char **av) filter.with_commit_tag_algo = 0; printf("%s(_,A,X,_):%d\n", av[1], commit_contains(&filter, A, X, &cache)); + } else if (!strcmp(av[1], "get_reachable_subset")) { + const int reachable_flag = 1; + int i, count = 0; + struct commit_list *current; + struct commit_list *list = get_reachable_subset(X_array, X_nr, + Y_array, Y_nr, + reachable_flag); + printf("get_reachable_subset(X,Y)\n"); + for (current = list; current; current = current->next) { + if (!(list->item->object.flags & reachable_flag)) + die(_("commit %s is not marked reachable"), + oid_to_hex(&list->item->object.oid)); + count++; + } + for (i = 0; i < Y_nr; i++) { + if (Y_array[i]->object.flags & reachable_flag) + count--; + } + + if (count < 0) + die(_("too many commits marked reachable")); + + print_sorted_commit_ids(list); } exit(0); diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh index ae94b27f70..a0c64e617a 100755 --- a/t/t6600-test-reach.sh +++ b/t/t6600-test-reach.sh @@ -265,4 +265,56 @@ test_expect_success 'commit_contains:miss' ' test_three_modes commit_contains --tag ' +test_expect_success 'get_reachable_subset:all' ' + cat >input <<-\EOF && + X:commit-9-1 + X:commit-8-3 + X:commit-7-5 + X:commit-6-6 + X:commit-1-7 + Y:commit-3-3 + Y:commit-1-7 + Y:commit-5-6 + EOF + ( + echo "get_reachable_subset(X,Y)" && + git rev-parse commit-3-3 \ + commit-1-7 \ + commit-5-6 | sort + ) >expect && + test_three_modes get_reachable_subset +' + +test_expect_success 'get_reachable_subset:some' ' + cat >input <<-\EOF && + X:commit-9-1 + X:commit-8-3 + X:commit-7-5 + X:commit-1-7 + Y:commit-3-3 + Y:commit-1-7 + Y:commit-5-6 + EOF + ( + echo "get_reachable_subset(X,Y)" && + git rev-parse commit-3-3 \ + commit-1-7 | sort + ) >expect && + test_three_modes get_reachable_subset +' + +test_expect_success 'get_reachable_subset:none' ' + cat >input <<-\EOF && + X:commit-9-1 + X:commit-8-3 + X:commit-7-5 + X:commit-1-7 + Y:commit-9-3 + Y:commit-7-6 + Y:commit-2-8 + EOF + echo "get_reachable_subset(X,Y)" >expect && + test_three_modes get_reachable_subset +' + test_done From patchwork Fri Nov 2 13:14:49 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bruce Perry via GitGitGadget X-Patchwork-Id: 10665531 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 14E4B157A for ; Fri, 2 Nov 2018 13:14:53 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 0D2C92B598 for ; Fri, 2 Nov 2018 13:14:53 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 014802B645; Fri, 2 Nov 2018 13:14:52 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 9505C2B598 for ; Fri, 2 Nov 2018 13:14:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727644AbeKBWV6 (ORCPT ); Fri, 2 Nov 2018 18:21:58 -0400 Received: from mail-pf1-f195.google.com ([209.85.210.195]:43596 "EHLO mail-pf1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726094AbeKBWV6 (ORCPT ); Fri, 2 Nov 2018 18:21:58 -0400 Received: by mail-pf1-f195.google.com with SMTP id h4-v6so1017328pfi.10 for ; Fri, 02 Nov 2018 06:14:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:message-id:in-reply-to:references:from:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=6r0EPGDqTvCRP9J6t3ef7WHyv6KSy4B5vamESNSP5Uc=; b=FfVp1Aa9oUkC4nIM7hsP4igTQgGfCiWbhjYIcmjPmHj/PJRIBsRO7pyYqyQmS26DVl bgo1Ph1E+IOmsfRe2V315kOOWXRQui5hLGcKbYMBvESYM6xTWL71TSNVSGsocuxh85HM REm290F96RbejOv+HffidiivOkjuIyCqnaXUVWhXOYBy8w02bi107xp3Ywm7JYQio7k+ PAAFjw4ZvL4vfV4SIVCbiMYWGL6//9x94gHtUruAuuPJqGFESRa8AundLEH7yC/azH3Q he0mQi3jeEfof5RMYHycywDi7C8ygGFNdhffMS4GSaVg199NdQdBHiFOqWQhJwDe4+Kb rkww== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:in-reply-to:references:from :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=6r0EPGDqTvCRP9J6t3ef7WHyv6KSy4B5vamESNSP5Uc=; b=Xs3FCY6YqjsEzyJpAF3vC70EQvgywpeQFXuqloWC8o4qwfPsMfdi55Osij+shFnMdZ MpXrY/KeNbFq40OexC+UVUIMAHNOdYEPz70f0LDgVFwBdejac5WOJCVFHRXgANrp62HU sYiF8LSi6JI6lCxzAOT4H7Nk3Qza30c303STbwK/RE2iu+epHtp2hYno6K1DLbUQKbLS ZnAUAwXjYoyfLTQyAalxOjupXJE3csbN0JmWLKaE0rZB8LuugOSW5TYlv2jvafP46YEf z1/LLzNFMIjg8QMA3sPTpbtb6HgPyousX4TmtgWNO4qqfVuxAFNovD2IKPRr/WDEr9F6 yOzw== X-Gm-Message-State: AGRZ1gL6Kugp295GTmjnkZpVg0/AEl7RAix6u/93HmzO47lakEwhNaRA MBSTtCaed8wZ3o9kDHorTRGpGxWY X-Google-Smtp-Source: AJdET5dYgeB7d6o28PNSoGkhSSXvFzD9BLoKgxJKUmYI1ZismIuJzMpc3inl+p/aplxQXf8TOhY0rw== X-Received: by 2002:a62:14d4:: with SMTP id 203-v6mr11682962pfu.221.1541164489801; Fri, 02 Nov 2018 06:14:49 -0700 (PDT) Received: from [127.0.0.1] ([40.112.137.127]) by smtp.gmail.com with ESMTPSA id 72-v6sm44544157pfl.126.2018.11.02.06.14.48 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 02 Nov 2018 06:14:49 -0700 (PDT) Date: Fri, 02 Nov 2018 06:14:49 -0700 (PDT) X-Google-Original-Date: Fri, 02 Nov 2018 13:14:42 GMT Message-Id: In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH v2 3/3] remote: make add_missing_tags() linear Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: peff@peff.net, newren@gmail.com, Junio C Hamano , Derrick Stolee Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Derrick Stolee The add_missing_tags() method currently has quadratic behavior. This is due to a linear number (based on number of tags T) of calls to in_merge_bases_many, which has linear performance (based on number of commits C in the repository). Replace this O(T * C) algorithm with an O(T + C) algorithm by using get_reachable_subset(). We ignore the return list and focus instead on the reachable_flag assigned to the commits we care about, because we need to interact with the tag ref and not just the commit object. Signed-off-by: Derrick Stolee --- remote.c | 34 +++++++++++++++++++++++++++++++++- 1 file changed, 33 insertions(+), 1 deletion(-) diff --git a/remote.c b/remote.c index 81f4f01b00..b850f2feb3 100644 --- a/remote.c +++ b/remote.c @@ -1205,9 +1205,36 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds * sent to the other side. */ if (sent_tips.nr) { + const int reachable_flag = 1; + struct commit_list *found_commits; + struct commit **src_commits; + int nr_src_commits = 0, alloc_src_commits = 16; + ALLOC_ARRAY(src_commits, alloc_src_commits); + for_each_string_list_item(item, &src_tag) { struct ref *ref = item->util; + struct commit *commit; + + if (is_null_oid(&ref->new_oid)) + continue; + commit = lookup_commit_reference_gently(the_repository, + &ref->new_oid, + 1); + if (!commit) + /* not pushing a commit, which is not an error */ + continue; + + ALLOC_GROW(src_commits, nr_src_commits + 1, alloc_src_commits); + src_commits[nr_src_commits++] = commit; + } + + found_commits = get_reachable_subset(sent_tips.tip, sent_tips.nr, + src_commits, nr_src_commits, + reachable_flag); + + for_each_string_list_item(item, &src_tag) { struct ref *dst_ref; + struct ref *ref = item->util; struct commit *commit; if (is_null_oid(&ref->new_oid)) @@ -1223,7 +1250,7 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds * Is this tag, which they do not have, reachable from * any of the commits we are sending? */ - if (!in_merge_bases_many(commit, sent_tips.nr, sent_tips.tip)) + if (!(commit->object.flags & reachable_flag)) continue; /* Add it in */ @@ -1231,7 +1258,12 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds oidcpy(&dst_ref->new_oid, &ref->new_oid); dst_ref->peer_ref = copy_ref(ref); } + + clear_commit_marks_many(nr_src_commits, src_commits, reachable_flag); + free(src_commits); + free_commit_list(found_commits); } + string_list_clear(&src_tag, 0); free(sent_tips.tip); }