From patchwork Tue Oct 30 14:16:04 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Philippe Blain via GitGitGadget X-Patchwork-Id: 10660969 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 E295313B5 for ; Tue, 30 Oct 2018 14:16:08 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id CA67E28685 for ; Tue, 30 Oct 2018 14:16:08 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id BE853299D6; Tue, 30 Oct 2018 14:16:08 +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 4782629AF8 for ; Tue, 30 Oct 2018 14:16:08 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728252AbeJ3XJp (ORCPT ); Tue, 30 Oct 2018 19:09:45 -0400 Received: from mail-pg1-f193.google.com ([209.85.215.193]:35038 "EHLO mail-pg1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728033AbeJ3XJp (ORCPT ); Tue, 30 Oct 2018 19:09:45 -0400 Received: by mail-pg1-f193.google.com with SMTP id 32-v6so5729363pgu.2 for ; Tue, 30 Oct 2018 07:16:05 -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=Jj0SQsDFcUMKE5MPGJTxJ1/g7UyA4IupC/2yyqhmhJQ=; b=awRn8Ep3rI3E2K7twReZ8rkFqA3qwEiiecVUOvKM3xh9hNqLVuW8bhghw9KZ5Bm2Od iJPscPr/UKJ+93DDOOuTmSuRyJpoV4irFyMMSa+LnLSAvpEvKUJU7JM5EElC8PK12d02 Ad8P/hN6cfl5Clp/RMgX5hNOtJztZfMXGjmZu4FQjd07qy9Zf3Znch/j5huAQWPJsrTY HcCks/9fQjsbq+aUOdJte8R6G4LSs2eMXjS3lgvawB4TBg4VSFEk13Py0Kc5tlET+c9V wzJBiz00e3potWytwwJA7w5Y84UCHAqDbD9UFYu8ZTT3kta/mwZPkx7DecIuBnC7PeXV kd7g== 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=Jj0SQsDFcUMKE5MPGJTxJ1/g7UyA4IupC/2yyqhmhJQ=; b=Rq7/+4TFcIA8LfpUwz5XzSCEr/pR7NCqzmRAwg9O/9WtTp0H4SykAz046ITspB81hs inWISxWWc1q5gkXgzilNp3tCV5npk27YOOUcsc5ZVQDHNgmWMjBVUgYkdRvBPAeqcaNk xrfNAySeWzr5VFnygsbJ9SyfmdHKFiI+D4BGlDVlFHPBOl2f+9gHsqBdnTzSiGQcCkka 9c6Mv+rNQToKB4vzUeMFzkVEEf7UeYq4Nxx/m9Fk1aw4YI4jST4L3BgGXjtFCbnoHmPE NOIi8o4kBfdpfOUYdLcmBdp/mczuyRVJtuK9Vk6+f6/1fITgtv7XWBssyh2nk62y6WJs IjPg== X-Gm-Message-State: AGRZ1gJVJgh+qUsNd6kShgtcH/2MG6gq9BC5pwmCD6Q4XG6j4/P8dKKT EWSKKP7Nt6xjZiF/n/O0gd7xbixm X-Google-Smtp-Source: AJdET5ceV41Uj/C6nWestWAFWdkwPBwYRTw27FkfCv9QsnCsDTorwZZ71/xsERpebvFco01Ej4Vg8Q== X-Received: by 2002:a63:ba48:: with SMTP id l8mr17789320pgu.72.1540908965168; Tue, 30 Oct 2018 07:16:05 -0700 (PDT) Received: from [127.0.0.1] ([40.112.137.127]) by smtp.gmail.com with ESMTPSA id m16-v6sm22019628pff.173.2018.10.30.07.16.04 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 30 Oct 2018 07:16:04 -0700 (PDT) Date: Tue, 30 Oct 2018 07:16:04 -0700 (PDT) X-Google-Original-Date: Tue, 30 Oct 2018 14:15:58 GMT Message-Id: <4c0c5c9143a757ee5187ae6fca9a76f29b6c6ae2.1540908961.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH 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 | 10 ++++++++ 2 files changed, 80 insertions(+) diff --git a/commit-reach.c b/commit-reach.c index 9f79ce0a2..a98532ecc 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, + 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 7d313e297..43bd50a70 100644 --- a/commit-reach.h +++ b/commit-reach.h @@ -74,4 +74,14 @@ 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. + */ +struct commit_list *get_reachable_subset(struct commit **from, int nr_from, + struct commit **to, int nr_to, + int reachable_flag); + #endif From patchwork Tue Oct 30 14:16:05 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Philippe Blain via GitGitGadget X-Patchwork-Id: 10660971 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 2EC3C14E2 for ; Tue, 30 Oct 2018 14:16:10 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 16FB2299D6 for ; Tue, 30 Oct 2018 14:16:10 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 0B0CF29AF8; Tue, 30 Oct 2018 14:16:10 +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 8D1B3299D6 for ; Tue, 30 Oct 2018 14:16:09 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728267AbeJ3XJr (ORCPT ); Tue, 30 Oct 2018 19:09:47 -0400 Received: from mail-pf1-f194.google.com ([209.85.210.194]:36412 "EHLO mail-pf1-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728033AbeJ3XJq (ORCPT ); Tue, 30 Oct 2018 19:09:46 -0400 Received: by mail-pf1-f194.google.com with SMTP id j22-v6so2100170pfh.3 for ; Tue, 30 Oct 2018 07:16:07 -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=ZlRMzZ/RBQe6Pt54TTspNLG+YC8+I5sKPb3cl3F6FeM=; b=F1G2Ms8N+3aLGHF/pzn+E70wRAcr7RXdyPEzfkzeUSZ+FXB403ku9nteQLXkGBmVzV 1uBB7uY1ozFzz0J6x/R00F99M23kodjSykMLaScOp/GIF9q87Gp+Qnd17LZsErovN6/S Ri+gZhTvyPTmK7/v9Vpj1CTWg7bCxIIUzZWJKl5PlOmlPlUYQewBJjyno8z/u3ZEI/je v5yhIyZ1TfTG9Bymu44IKf9aB+smJGv1tlaEU76T46BCB7rPpzsNKmx4U3QM6OMg2oAH 9tdWndxQm6Ze764FX79vHFYK8aiOMgNS5v94glEpN0/3zBFyozD/ITrp3gnSJhdajc0k W7gQ== 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=ZlRMzZ/RBQe6Pt54TTspNLG+YC8+I5sKPb3cl3F6FeM=; b=TxdU7lZZqfZgeXK9AtSowo53WgNlRqegkMbEIIoHlToMMY0HNaHNOQKYdIaijbTk/n 0BVvE2MDrLUfaFiNTUblOBzpg4rCcwUKADHroQSlQeZ9FTKyLkUVuD7fnxZNH8x2yvii cbkK3nnmEhcmt5oOLGSb5YaFjxMU7UzVC48VG3774F6drTkxoxlHrmhvtUT51CV2inKp ei4fKyzHEB2bkVYIojJAOjn5IS7f/K+Iz5fHyVbl7V0bp3wLX9VNw9CaqGpSERGrRmZX jB+G6K/dUg+nWpRDLHVcdW60JpCVHUpEFQ7XYuE7vCweQQaK+bgwLQEqAgfeJIU1AMT8 F5XQ== X-Gm-Message-State: AGRZ1gI65fs95Wc9SrqH+rQCH2FO4S5E36s8d3fgRtikFTvAP1r2ASW7 KpkDs++bokZ3S5uWTqnyq4D9aHL9 X-Google-Smtp-Source: AJdET5fw+Df7QkMaXjMjjIyGqXPoEQzp/BOTUu3m827zTSr3kpMeEyEb/MlXGYr7Yw9GzOfMxlydLg== X-Received: by 2002:a63:d34f:: with SMTP id u15-v6mr18293133pgi.325.1540908966615; Tue, 30 Oct 2018 07:16:06 -0700 (PDT) Received: from [127.0.0.1] ([40.112.137.127]) by smtp.gmail.com with ESMTPSA id l26-v6sm43378210pfg.161.2018.10.30.07.16.05 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 30 Oct 2018 07:16:05 -0700 (PDT) Date: Tue, 30 Oct 2018 07:16:05 -0700 (PDT) X-Google-Original-Date: Tue, 30 Oct 2018 14:15:59 GMT Message-Id: <382f4f4a5b4671307530a34a60f9cc18c3b06443.1540908961.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH 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 08d2ea68e..a0272178b 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 ae94b27f7..a0c64e617 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 Tue Oct 30 14:16:07 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Philippe Blain via GitGitGadget X-Patchwork-Id: 10660973 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 41EC113B5 for ; Tue, 30 Oct 2018 14:16:11 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 2AEB428685 for ; Tue, 30 Oct 2018 14:16:11 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 1F19E29AF3; Tue, 30 Oct 2018 14:16:11 +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 B7C94299D6 for ; Tue, 30 Oct 2018 14:16:10 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728270AbeJ3XJs (ORCPT ); Tue, 30 Oct 2018 19:09:48 -0400 Received: from mail-pf1-f196.google.com ([209.85.210.196]:46889 "EHLO mail-pf1-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728033AbeJ3XJr (ORCPT ); Tue, 30 Oct 2018 19:09:47 -0400 Received: by mail-pf1-f196.google.com with SMTP id r64-v6so5898312pfb.13 for ; Tue, 30 Oct 2018 07:16:08 -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=q8+PCChIvI17zClm5NXMAMGHZU8A/a/avzv/EP3JNNA=; b=TF5D1ZZsGH5bWtw/RHjIuSAi65CK4ZbnFQtPkCaGFknqPk9/uuPrJAI2ClPMenCvD4 LJzBPamrQOUsJOCHrzZPVkO+0gfs/oUdMxJOuRKIgIvqCdYS0fBG8uFQMvAGQitE45wm G6Bmgv0C9KDT/CwsMAWwnfjPJmzfBEda7983h5pL2nvJ60u4PzFUYI4WCLkHeTlJDsFq pRzsJo7h+aNB0U3FcX+YvjPcHo9xUpLNH+V4eBouJ8NkiMFjGUFQ3PsdByPf8OHIMMGZ 55m+L9/nLa6ER71ETAsVTHON8SO7OVCUlNVdQRlyScZW6/dAEouvED/ICb9RF4VfojfE Snpg== 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=q8+PCChIvI17zClm5NXMAMGHZU8A/a/avzv/EP3JNNA=; b=eZ5pdmTUGJt+5fgcZY+TAz4RNWu4icQ/wzdQfI1XHqaO1vGWlwZtIMzydxpdHBEgau FOru0rXhuBLiAqyAG1rSBUS8/+i8feEQ+HivFER1zAdULAmQrBqBuCxwCt1XemEIalw/ eDHOgM6kBIiTfwRlxpEDfcohy7+pAas38zYRfDQSv2UiqCLJNyd1N+ifHlzQV5+Eparx nfmRjKwMomMxLMcuJ003pl3N5IoF7gVaTCQ+s1KSlQVuPxASZ+eKd+iXZR2KDTqKs/7u 6cExjCNvXHXI9OK7GUYClWZsyQMGGC85dE1HoyvM0QSEmoz/cCwBCMD1pzA5utw0ORDc pbvw== X-Gm-Message-State: AGRZ1gLsp2ow8eBjswF8+55TyApFFZpVVI2ujtJS1D+HCSVKUdWXbBrK zA1kKnOLlKQmAKfhUVv5kzV+Pnpc X-Google-Smtp-Source: AJdET5fLnCzR9SfqSuVUSnLGPoQ3VCsG/58kd2vMwTIlmqx7Lphq3LGoch3tmP7J9sydNu3QmC3vsA== X-Received: by 2002:a62:2606:: with SMTP id m6-v6mr3146189pfm.104.1540908968024; Tue, 30 Oct 2018 07:16:08 -0700 (PDT) Received: from [127.0.0.1] ([40.112.137.127]) by smtp.gmail.com with ESMTPSA id p64-v6sm22917036pfi.22.2018.10.30.07.16.06 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 30 Oct 2018 07:16:07 -0700 (PDT) Date: Tue, 30 Oct 2018 07:16:07 -0700 (PDT) X-Google-Original-Date: Tue, 30 Oct 2018 14:16:00 GMT Message-Id: In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Subject: [PATCH 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 81f4f01b0..b850f2feb 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); }