From patchwork Thu Jan 10 12:01:38 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Jiang Xin X-Patchwork-Id: 10755609 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 001EA13BF for ; Thu, 10 Jan 2019 12:05:15 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id E428520408 for ; Thu, 10 Jan 2019 12:05:14 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id D89F7292CB; Thu, 10 Jan 2019 12:05:14 +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 C2BF928BBF for ; Thu, 10 Jan 2019 12:05:13 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728178AbfAJMFM (ORCPT ); Thu, 10 Jan 2019 07:05:12 -0500 Received: from mail-pf1-f193.google.com ([209.85.210.193]:39186 "EHLO mail-pf1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728088AbfAJMFM (ORCPT ); Thu, 10 Jan 2019 07:05:12 -0500 Received: by mail-pf1-f193.google.com with SMTP id r136so5207606pfc.6 for ; Thu, 10 Jan 2019 04:05:11 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=t76JCUZ11pgI3UdkSSnuP+u5dpdputw/2vmRlfIoS7U=; b=V2t2a2S9ZzIteAQGa8Q90mYe9nDZWk4GFgwEy9f6fbhh0gANee7uAUvgqzwG0gw7RG TZdN63+4brYXmUma8NMuNWq9PAgOemzR313ucrCPbo8PEv4JM5CyPil5smfFZhel0WJ2 0GgSCKcuWNcRn0TzW1A/ryn7e4VGZMGhKdqQNrZoUKxAoCFwHSbZoLfocbZvaWPxJBig DStY5mH2bO/dDvgN0CCsC7giYT2LY2hvy94QCGuNiHjvetGqQmiUQbVN8IkwDy0JHUB3 GYz0bPU4rN7eSpleq6GWMebocBX7FxJNA84uGiQP5eDSrHOOlktgY7QiIHAAMwEFyZBC stYQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=t76JCUZ11pgI3UdkSSnuP+u5dpdputw/2vmRlfIoS7U=; b=BS79rGDSuQTVXIjKs4OSbM/T1MNrPITuFH2OfkNzB+Rxcmds2bz1/HBDrE/b9YJoTF ANLh5dMd7t76S4rEiBPRFf2A6A/GXF1LjjujfDVjuBH8RMgNL2ocuWPwEMgKJ+sJil/k s+xdmHtkhNcoZ+i9911kcsrTM/XvCkW/vDtKo46PucukNN642o/CwIMJj7rmWgGakIfH MBqXZmbf2cJgY7EwRdIXarC615T6gBLCfOHGXPnKYn1oSlL0l71yrsQFK0C/mbszWQxq OVEDpPmOGynl9ZmmRbNmvjmcNHu7qEK7X2M1onWAsvWWtFfAIGwWSDqbBgaH/gJ8hv/f nH2Q== X-Gm-Message-State: AJcUukdfpyClBfXYR/btzuC8R+6Eyh9bwVIGMH5LP0WwAVKIKEoSuLWw FHFgWnSb7ml/NBwQX25EpgU= X-Google-Smtp-Source: ALg8bN5wBZ8U5AhoOwX1FytF84dF6FN6g4Rf8Fyrd1BiyyxY5bBpq5GSGu2Px1LBM2O7cfpnBKignA== X-Received: by 2002:a63:4745:: with SMTP id w5mr9334928pgk.377.1547121910834; Thu, 10 Jan 2019 04:05:10 -0800 (PST) Received: from GotGit.hz.ali.com ([106.11.34.204]) by smtp.gmail.com with ESMTPSA id b2sm137189403pfm.3.2019.01.10.04.05.08 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 10 Jan 2019 04:05:10 -0800 (PST) From: Jiang Xin To: Junio C Hamano , Git List , =?utf-8?q?SZEDER_G=C3=A1bor?= , Sun Chao Cc: Jiang Xin , Johannes Sixt Subject: [PATCH v5 1/5] t5323: test cases for git-pack-redundant Date: Thu, 10 Jan 2019 20:01:38 +0800 Message-Id: <20190110120142.22271-2-worldhello.net@gmail.com> X-Mailer: git-send-email 2.20.1.101.gc01fadde4e In-Reply-To: <20190109164731.GJ4673@szeder.dev> References: <20190109164731.GJ4673@szeder.dev> MIME-Version: 1.0 Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Jiang Xin Add test cases for git pack-redundant to validate new algorithm for git pack-redundant. Signed-off-by: Jiang Xin Reviewed-by: SZEDER Gábor --- t/t5323-pack-redundant.sh | 157 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 157 insertions(+) create mode 100755 t/t5323-pack-redundant.sh diff --git a/t/t5323-pack-redundant.sh b/t/t5323-pack-redundant.sh new file mode 100755 index 0000000000..7410426dee --- /dev/null +++ b/t/t5323-pack-redundant.sh @@ -0,0 +1,157 @@ +#!/bin/sh +# +# Copyright (c) 2018 Jiang Xin +# + +test_description='git pack-redundant test' + +. ./test-lib.sh + +create_commits() +{ + parent= + for name in A B C D E F G H I J K L M N O P Q R + do + test_tick && + T=$(git write-tree) && + if test -z "$parent" + then + oid=$(echo $name | git commit-tree $T) + else + oid=$(echo $name | git commit-tree -p $parent $T) + fi && + eval $name=$oid && + parent=$oid || + return 1 + done + git update-ref refs/heads/master $M +} + +create_pack_1() +{ + P1=$(cd .git/objects/pack; printf "$T\n$A\n$B\n$C\n$D\n$E\n$F\n$R\n" | git pack-objects pack 2>/dev/null) && + eval P$P1=P1:$P1 +} + +create_pack_2() +{ + P2=$(cd .git/objects/pack; printf "$B\n$C\n$D\n$E\n$G\n$H\n$I\n" | git pack-objects pack 2>/dev/null) && + eval P$P2=P2:$P2 +} + +create_pack_3() +{ + P3=$(cd .git/objects/pack; printf "$F\n$I\n$J\n$K\n$L\n$M\n" | git pack-objects pack 2>/dev/null) && + eval P$P3=P3:$P3 +} + +create_pack_4() +{ + P4=$(cd .git/objects/pack; printf "$J\n$K\n$L\n$M\n$P\n" | git pack-objects pack 2>/dev/null) && + eval P$P4=P4:$P4 +} + +create_pack_5() +{ + P5=$(cd .git/objects/pack; printf "$G\n$H\n$N\n$O\n" | git pack-objects pack 2>/dev/null) && + eval P$P5=P5:$P5 +} + +create_pack_6() +{ + P6=$(cd .git/objects/pack; printf "$N\n$O\n$Q\n" | git pack-objects pack 2>/dev/null) && + eval P$P6=P6:$P6 +} + +create_pack_7() +{ + P7=$(cd .git/objects/pack; printf "$P\n$Q\n" | git pack-objects pack 2>/dev/null) && + eval P$P7=P7:$P7 +} + +create_pack_8() +{ + P8=$(cd .git/objects/pack; printf "$A\n" | git pack-objects pack 2>/dev/null) && + eval P$P8=P8:$P8 +} + +test_expect_success 'setup' ' + create_commits +' + +test_expect_success 'no redundant packs' ' + create_pack_1 && create_pack_2 && create_pack_3 && + git pack-redundant --all >out && + test_must_be_empty out +' + +test_expect_success 'create pack 4, 5' ' + create_pack_4 && create_pack_5 +' + +cat >expected <out && + sed -E -e "s#.*/pack-(.*)\.(idx|pack)#\1#" out | \ + sort -u | \ + while read p; do eval echo "\${P$p}"; done | \ + sort >actual && \ + test_cmp expected actual +' + +test_expect_success 'create pack 6, 7' ' + create_pack_6 && create_pack_7 +' + +cat >expected <out && + sed -E -e "s#.*/pack-(.*)\.(idx|pack)#\1#" out | \ + sort -u | \ + while read p; do eval echo "\${P$p}"; done | \ + sort >actual && \ + test_cmp expected actual +' + +test_expect_success 'create pack 8' ' + create_pack_8 +' + +cat >expected <out && + sed -E -e "s#.*/pack-(.*)\.(idx|pack)#\1#" out | \ + sort -u | \ + while read p; do eval echo "\${P$p}"; done | \ + sort >actual && \ + test_cmp expected actual +' + +test_expect_success 'clear loose objects' ' + git prune-packed && + find .git/objects -type f | sed -e "/objects\/pack\//d" >out && + test_must_be_empty out +' + +test_expect_success 'remove redundant packs' ' + git pack-redundant --all | xargs rm && + git fsck && + git pack-redundant --all >out && + test_must_be_empty out +' + +test_done From patchwork Thu Jan 10 12:01:39 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jiang Xin X-Patchwork-Id: 10755613 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 84E066C5 for ; Thu, 10 Jan 2019 12:05:19 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 7405220408 for ; Thu, 10 Jan 2019 12:05:19 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 6886A292CA; Thu, 10 Jan 2019 12:05:19 +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 95A9420408 for ; Thu, 10 Jan 2019 12:05:16 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728181AbfAJMFP (ORCPT ); Thu, 10 Jan 2019 07:05:15 -0500 Received: from mail-pl1-f194.google.com ([209.85.214.194]:45263 "EHLO mail-pl1-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728088AbfAJMFP (ORCPT ); Thu, 10 Jan 2019 07:05:15 -0500 Received: by mail-pl1-f194.google.com with SMTP id a14so5085577plm.12 for ; Thu, 10 Jan 2019 04:05:14 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=i8Fj7xfYWT+rZ0wVvqk62sVzjz4Lz7Q+q5ZQ7Q4He5U=; b=aotsu58sLiDB2rbOk4jH7thwCl34eCp0j3DT6CZLQE1FUB9wY4Cy9nhlYWjJSZhlTw K9LGxChFx5lTI3LlB1QWY+QmYAAVbOl78wKp7PFY+NGYIxds1P0BPgT1ZVlH0syqib5X hVsguLHEvCvhg12Y2zbEc65sfRBE6sagxuJA5LJgm4ogFQWeaNWKcMa7axWQdEjcM751 WTE7Z3q2RsPv+ASO/J4+cmtrwzjxBOMkkKytoqq8MkpVAtfeVxap4/jYzzrRubA5ov1N NI9PjRIHp3kUSbvpNOqiY3Szcq5PrBQJBe4WYD2aubVlylm74vjaIN9ZMkHqHD4752OK kkQw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=i8Fj7xfYWT+rZ0wVvqk62sVzjz4Lz7Q+q5ZQ7Q4He5U=; b=LpFcmlxaqmpczGEdrCvTDpF0SUVr5HROzO4k0ZmrzLcr3jmmWlMGf+LrVedl1KPp5q 16fLmj0KTWKL3Z9PIFDZkvYa4L9C866uGRm52bfn9elMVAJ5/jGeiy7yCqza4NYe9aL7 27+pwr4pCaCSrbmGluw9BQY3fRUG6gXKmUORnvZqcyGXkeGPyvyuSjLsNKeTk2TAnQMt AJs/zi9Y4dVvoyaAvwO0zYnsBUVNlvwLhdebHmzyVBY1OZpKulATP/E7eFFWTO78xi3k 8YkjsbahAQc3Urhbm0ncv5W6AB7tX4U0yIP8cNZ18gxs667XqviPKD6P7SFKGc6tYofN o5UA== X-Gm-Message-State: AJcUukdKCUZhZ0dVdIxqZW2QUguC3rzZ8BTGkVbQAyrd6DyXNPxTps3t pHBqTXjTSQ23zjyajpxYKZrqQpm1sJc= X-Google-Smtp-Source: ALg8bN4PRYqtisrDpcJeqo5uuThfndMWHeSisNrDC2XIRSbHydpROqMrePHSsHif+BQpsju9mhf5Wg== X-Received: by 2002:a17:902:50e:: with SMTP id 14mr9952021plf.141.1547121914047; Thu, 10 Jan 2019 04:05:14 -0800 (PST) Received: from GotGit.hz.ali.com ([106.11.34.204]) by smtp.gmail.com with ESMTPSA id b2sm137189403pfm.3.2019.01.10.04.05.11 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 10 Jan 2019 04:05:13 -0800 (PST) From: Jiang Xin To: Junio C Hamano , Git List , =?utf-8?q?SZEDER_G=C3=A1bor?= , Sun Chao Cc: Johannes Sixt , Jiang Xin Subject: [PATCH v5 2/5] pack-redundant: new algorithm to find min packs Date: Thu, 10 Jan 2019 20:01:39 +0800 Message-Id: <20190110120142.22271-3-worldhello.net@gmail.com> X-Mailer: git-send-email 2.20.1.101.gc01fadde4e In-Reply-To: <20190109164731.GJ4673@szeder.dev> References: <20190109164731.GJ4673@szeder.dev> MIME-Version: 1.0 Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Sun Chao When calling `git pack-redundant --all`, if there are too many local packs and too many redundant objects within them, the too deep iteration of `get_permutations` will exhaust all the resources, and the process of `git pack-redundant` will be killed. The following script could create a repository with too many redundant packs, and running `git pack-redundant --all` in the `test.git` repo will die soon. #!/bin/sh repo="$(pwd)/test.git" work="$(pwd)/test" i=1 max=199 if test -d "$repo" || test -d "$work"; then echo >&2 "ERROR: '$repo' or '$work' already exist" exit 1 fi git init -q --bare "$repo" git --git-dir="$repo" config gc.auto 0 git --git-dir="$repo" config transfer.unpackLimit 0 git clone -q "$repo" "$work" 2>/dev/null while :; do cd "$work" echo "loop $i: $(date +%s)" >$i git add $i git commit -q -sm "loop $i" git push -q origin HEAD:master printf "\rCreate pack %4d/%d\t" $i $max if test $i -ge $max; then break; fi cd "$repo" git repack -q if test $(($i % 2)) -eq 0; then git repack -aq pack=$(ls -t $repo/objects/pack/*.pack | head -1) touch "${pack%.pack}.keep" fi i=$((i+1)) done printf "\ndone\n" To get the `min` unique pack list, we can replace the iteration in `minimize` function with a new algorithm, and this could solve this issue: 1. Get the unique and non_uniqe packs, add the unique packs to the `min` list. 2. Remove the objects of unique packs from non_unique packs, then each object left in the non_unique packs will have at least two copies. 3. Sort the non_unique packs by the objects' size, more objects first, and add the first non_unique pack to `min` list. 4. Drop the duplicated objects from other packs in the ordered non_unique pack list, and repeat step 3. Original PR and discussions: https://github.com/jiangxin/git/pull/25 Signed-off-by: Sun Chao Signed-off-by: Jiang Xin Signed-off-by: Junio C Hamano --- builtin/pack-redundant.c | 109 ++++++++++++++++++++++++--------------- 1 file changed, 68 insertions(+), 41 deletions(-) diff --git a/builtin/pack-redundant.c b/builtin/pack-redundant.c index cf9a9aabd4..3655cc7dc6 100644 --- a/builtin/pack-redundant.c +++ b/builtin/pack-redundant.c @@ -421,14 +421,52 @@ static inline off_t pack_set_bytecount(struct pack_list *pl) return ret; } +static int cmp_pack_list_reverse(const void *a, const void *b) +{ + struct pack_list *pl_a = *((struct pack_list **)a); + struct pack_list *pl_b = *((struct pack_list **)b); + size_t sz_a = pl_a->all_objects->size; + size_t sz_b = pl_b->all_objects->size; + + if (sz_a == sz_b) + return 0; + else if (sz_a < sz_b) + return 1; + else + return -1; +} + +/* Sort pack_list, greater size of all_objects first */ +static void sort_pack_list(struct pack_list **pl) +{ + struct pack_list **ary, *p; + int i; + size_t n = pack_list_size(*pl); + + if (n < 2) + return; + + /* prepare an array of packed_list for easier sorting */ + ary = xcalloc(n, sizeof(struct pack_list *)); + for (n = 0, p = *pl; p; p = p->next) + ary[n++] = p; + + QSORT(ary, n, cmp_pack_list_reverse); + + /* link them back again */ + for (i = 0; i < n - 1; i++) + ary[i]->next = ary[i + 1]; + ary[n - 1]->next = NULL; + *pl = ary[0]; + + free(ary); +} + + static void minimize(struct pack_list **min) { - struct pack_list *pl, *unique = NULL, - *non_unique = NULL, *min_perm = NULL; - struct pll *perm, *perm_all, *perm_ok = NULL, *new_perm; - struct llist *missing; - off_t min_perm_size = 0, perm_size; - int n; + struct pack_list *pl, *unique = NULL, *non_unique = NULL; + struct llist *missing, *unique_pack_objects; pl = local_packs; while (pl) { @@ -446,49 +484,37 @@ static void minimize(struct pack_list **min) pl = pl->next; } + *min = unique; + /* return if there are no objects missing from the unique set */ if (missing->size == 0) { - *min = unique; free(missing); return; } - /* find the permutations which contain all missing objects */ - for (n = 1; n <= pack_list_size(non_unique) && !perm_ok; n++) { - perm_all = perm = get_permutations(non_unique, n); - while (perm) { - if (is_superset(perm->pl, missing)) { - new_perm = xmalloc(sizeof(struct pll)); - memcpy(new_perm, perm, sizeof(struct pll)); - new_perm->next = perm_ok; - perm_ok = new_perm; - } - perm = perm->next; - } - if (perm_ok) - break; - pll_free(perm_all); - } - if (perm_ok == NULL) - die("Internal error: No complete sets found!"); - - /* find the permutation with the smallest size */ - perm = perm_ok; - while (perm) { - perm_size = pack_set_bytecount(perm->pl); - if (!min_perm_size || min_perm_size > perm_size) { - min_perm_size = perm_size; - min_perm = perm->pl; - } - perm = perm->next; - } - *min = min_perm; - /* add the unique packs to the list */ - pl = unique; + unique_pack_objects = llist_copy(all_objects); + llist_sorted_difference_inplace(unique_pack_objects, missing); + + /* remove unique pack objects from the non_unique packs */ + pl = non_unique; while (pl) { - pack_list_insert(min, pl); + llist_sorted_difference_inplace(pl->all_objects, unique_pack_objects); pl = pl->next; } + + while (non_unique) { + /* sort the non_unique packs, greater size of all_objects first */ + sort_pack_list(&non_unique); + if (non_unique->all_objects->size == 0) + break; + + pack_list_insert(min, non_unique); + + for (pl = non_unique->next; pl && pl->all_objects->size > 0; pl = pl->next) + llist_sorted_difference_inplace(pl->all_objects, non_unique->all_objects); + + non_unique = non_unique->next; + } } static void load_all_objects(void) @@ -603,7 +629,7 @@ static void load_all(void) int cmd_pack_redundant(int argc, const char **argv, const char *prefix) { int i; - struct pack_list *min, *red, *pl; + struct pack_list *min = NULL, *red, *pl; struct llist *ignore; struct object_id *oid; char buf[GIT_MAX_HEXSZ + 2]; /* hex hash + \n + \0 */ @@ -664,6 +690,7 @@ int cmd_pack_redundant(int argc, const char **argv, const char *prefix) pl = local_packs; while (pl) { llist_sorted_difference_inplace(pl->unique_objects, ignore); + llist_sorted_difference_inplace(pl->all_objects, ignore); pl = pl->next; } From patchwork Thu Jan 10 12:01:40 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jiang Xin X-Patchwork-Id: 10755615 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 BD63417E1 for ; Thu, 10 Jan 2019 12:05:19 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id AC4C720408 for ; Thu, 10 Jan 2019 12:05:19 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id A0AAF292C2; Thu, 10 Jan 2019 12:05:19 +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 29F9728BBF for ; Thu, 10 Jan 2019 12:05:19 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728193AbfAJMFS (ORCPT ); Thu, 10 Jan 2019 07:05:18 -0500 Received: from mail-pf1-f195.google.com ([209.85.210.195]:38746 "EHLO mail-pf1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728088AbfAJMFR (ORCPT ); Thu, 10 Jan 2019 07:05:17 -0500 Received: by mail-pf1-f195.google.com with SMTP id q1so5219670pfi.5 for ; Thu, 10 Jan 2019 04:05:16 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=omq9iNaSuFesm3pOkIb34gc3XwOPHx6YaCh9mavardw=; b=hFJSaCb6INpsXWATbJW/NOFbRG6LmMIIr4Lgjbp8vVxBUlTrXDhVWbna3a1l+ryo3Y 56Zf0G0CgCV9cy0mKxxSSaUXtMtJstCpCY7TnfWBZ/kyK13/KMtP71Q7oDLgaRlxuZUC MM4s52Iw7hYQeXnuguzTNUSH70ATvWPvXVCWJiMN8Dn/C2BiLC/vvgpLrNY+a4tdNs/W YQEoE3wPBK2xeOE5J63Fyyk3HD1nefcIf0YfXGnroSIw3I9FawUPNcGOgwXQxYgxUYVi 09uUygXxRfY3GIHpNEyko9LuOaUGCGK4GWTO7abRO7oZmWNYxq6ZWRy+NQb61i5uqJGn XCQw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=omq9iNaSuFesm3pOkIb34gc3XwOPHx6YaCh9mavardw=; b=l05S6fU8RkEGVPd8NEe0UNRekNyqhBv6UhBYw37syQ6NHrUx4t8oEWO24Uhas/pLWR X0X7ACHTLDndAa5UQKUtcR5aiNP+1+u4RkOySo6GsnSGh7QaeC2XB+nXVkonH/TYby3O svmFfDRkfarXeIhh9JVPEmcuaqiOmZbzYBKnZtz54OuIqru7NJZgjSPA0XiSmDWZv4PF GEzg28xbhpfIVD8IRoUvSPhv3Iv+tiFaAKUcNfUSQJN1TvbR3oVS9d3XxbMXBaKLwk+g hRtpgNRWxzf2rIqagiEw5ZEW1Oxa7EZ5XwTWj5Ki5tNZlXGc6Ed1qiAGoc2etmufSNok 9R7w== X-Gm-Message-State: AJcUukegOVeSSVpg7+WjqVRfWEp4pPFvPrJvh3I917Y52K7m8HaOCn/H G7CWORSHGKvgZzNV7ZpH12c= X-Google-Smtp-Source: ALg8bN4ZiDQVJf46i9bC5V3vjBTDJ9Biqo860tuJP+35ceQeS/2cVtNkhEzPQHFYHgVrxwNmnEwWKA== X-Received: by 2002:a63:cd11:: with SMTP id i17mr9226761pgg.345.1547121916531; Thu, 10 Jan 2019 04:05:16 -0800 (PST) Received: from GotGit.hz.ali.com ([106.11.34.204]) by smtp.gmail.com with ESMTPSA id b2sm137189403pfm.3.2019.01.10.04.05.14 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 10 Jan 2019 04:05:16 -0800 (PST) From: Jiang Xin To: Junio C Hamano , Git List , =?utf-8?q?SZEDER_G=C3=A1bor?= , Sun Chao Cc: Jiang Xin , Johannes Sixt Subject: [PATCH v5 3/5] pack-redundant: rename pack_list.all_objects Date: Thu, 10 Jan 2019 20:01:40 +0800 Message-Id: <20190110120142.22271-4-worldhello.net@gmail.com> X-Mailer: git-send-email 2.20.1.101.gc01fadde4e In-Reply-To: <20190109164731.GJ4673@szeder.dev> References: <20190109164731.GJ4673@szeder.dev> MIME-Version: 1.0 Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Jiang Xin New algorithm uses `pack_list.all_objects` to track remaining objects, so rename it to `pack_list.remaining_objects`. Signed-off-by: Jiang Xin --- builtin/pack-redundant.c | 38 +++++++++++++++++++------------------- 1 file changed, 19 insertions(+), 19 deletions(-) diff --git a/builtin/pack-redundant.c b/builtin/pack-redundant.c index 3655cc7dc6..56591d283f 100644 --- a/builtin/pack-redundant.c +++ b/builtin/pack-redundant.c @@ -32,7 +32,7 @@ static struct pack_list { struct pack_list *next; struct packed_git *pack; struct llist *unique_objects; - struct llist *all_objects; + struct llist *remaining_objects; } *local_packs = NULL, *altodb_packs = NULL; struct pll { @@ -346,7 +346,7 @@ static int is_superset(struct pack_list *pl, struct llist *list) diff = llist_copy(list); while (pl) { - llist_sorted_difference_inplace(diff, pl->all_objects); + llist_sorted_difference_inplace(diff, pl->remaining_objects); if (diff->size == 0) { /* we're done */ llist_free(diff); return 1; @@ -425,8 +425,8 @@ static int cmp_pack_list_reverse(const void *a, const void *b) { struct pack_list *pl_a = *((struct pack_list **)a); struct pack_list *pl_b = *((struct pack_list **)b); - size_t sz_a = pl_a->all_objects->size; - size_t sz_b = pl_b->all_objects->size; + size_t sz_a = pl_a->remaining_objects->size; + size_t sz_b = pl_b->remaining_objects->size; if (sz_a == sz_b) return 0; @@ -436,7 +436,7 @@ static int cmp_pack_list_reverse(const void *a, const void *b) return -1; } -/* Sort pack_list, greater size of all_objects first */ +/* Sort pack_list, greater size of remaining_objects first */ static void sort_pack_list(struct pack_list **pl) { struct pack_list **ary, *p; @@ -480,7 +480,7 @@ static void minimize(struct pack_list **min) missing = llist_copy(all_objects); pl = unique; while (pl) { - llist_sorted_difference_inplace(missing, pl->all_objects); + llist_sorted_difference_inplace(missing, pl->remaining_objects); pl = pl->next; } @@ -498,20 +498,20 @@ static void minimize(struct pack_list **min) /* remove unique pack objects from the non_unique packs */ pl = non_unique; while (pl) { - llist_sorted_difference_inplace(pl->all_objects, unique_pack_objects); + llist_sorted_difference_inplace(pl->remaining_objects, unique_pack_objects); pl = pl->next; } while (non_unique) { - /* sort the non_unique packs, greater size of all_objects first */ + /* sort the non_unique packs, greater size of remaining_objects first */ sort_pack_list(&non_unique); - if (non_unique->all_objects->size == 0) + if (non_unique->remaining_objects->size == 0) break; pack_list_insert(min, non_unique); - for (pl = non_unique->next; pl && pl->all_objects->size > 0; pl = pl->next) - llist_sorted_difference_inplace(pl->all_objects, non_unique->all_objects); + for (pl = non_unique->next; pl && pl->remaining_objects->size > 0; pl = pl->next) + llist_sorted_difference_inplace(pl->remaining_objects, non_unique->remaining_objects); non_unique = non_unique->next; } @@ -526,7 +526,7 @@ static void load_all_objects(void) while (pl) { hint = NULL; - l = pl->all_objects->front; + l = pl->remaining_objects->front; while (l) { hint = llist_insert_sorted_unique(all_objects, l->oid, hint); @@ -537,7 +537,7 @@ static void load_all_objects(void) /* remove objects present in remote packs */ pl = altodb_packs; while (pl) { - llist_sorted_difference_inplace(all_objects, pl->all_objects); + llist_sorted_difference_inplace(all_objects, pl->remaining_objects); pl = pl->next; } } @@ -563,10 +563,10 @@ static void scan_alt_odb_packs(void) local = local_packs; while (local) { llist_sorted_difference_inplace(local->unique_objects, - alt->all_objects); + alt->remaining_objects); local = local->next; } - llist_sorted_difference_inplace(all_objects, alt->all_objects); + llist_sorted_difference_inplace(all_objects, alt->remaining_objects); alt = alt->next; } } @@ -581,7 +581,7 @@ static struct pack_list * add_pack(struct packed_git *p) return NULL; l.pack = p; - llist_init(&l.all_objects); + llist_init(&l.remaining_objects); if (open_pack_index(p)) return NULL; @@ -590,11 +590,11 @@ static struct pack_list * add_pack(struct packed_git *p) base += 256 * 4 + ((p->index_version < 2) ? 4 : 8); step = the_hash_algo->rawsz + ((p->index_version < 2) ? 4 : 0); while (off < p->num_objects * step) { - llist_insert_back(l.all_objects, (const struct object_id *)(base + off)); + llist_insert_back(l.remaining_objects, (const struct object_id *)(base + off)); off += step; } /* this list will be pruned in cmp_two_packs later */ - l.unique_objects = llist_copy(l.all_objects); + l.unique_objects = llist_copy(l.remaining_objects); if (p->pack_local) return pack_list_insert(&local_packs, &l); else @@ -690,7 +690,7 @@ int cmd_pack_redundant(int argc, const char **argv, const char *prefix) pl = local_packs; while (pl) { llist_sorted_difference_inplace(pl->unique_objects, ignore); - llist_sorted_difference_inplace(pl->all_objects, ignore); + llist_sorted_difference_inplace(pl->remaining_objects, ignore); pl = pl->next; } From patchwork Thu Jan 10 12:01:41 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Jiang Xin X-Patchwork-Id: 10755617 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 94BC56C5 for ; Thu, 10 Jan 2019 12:05:22 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 8360320408 for ; Thu, 10 Jan 2019 12:05:22 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 77EB1292C2; Thu, 10 Jan 2019 12:05:22 +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 124F920408 for ; Thu, 10 Jan 2019 12:05:22 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728206AbfAJMFV (ORCPT ); Thu, 10 Jan 2019 07:05:21 -0500 Received: from mail-pf1-f195.google.com ([209.85.210.195]:40188 "EHLO mail-pf1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727566AbfAJMFU (ORCPT ); Thu, 10 Jan 2019 07:05:20 -0500 Received: by mail-pf1-f195.google.com with SMTP id i12so5211979pfo.7 for ; Thu, 10 Jan 2019 04:05:19 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=jf8TnTfhSbw4KDZgdjQDqBI4e9cWjVlyf2vBihu61/Q=; b=Ky/AVE24mmK7U8EENoW4Fr1xBsyZtKjN5r71pZcg9bO/Nkaw/mv0EpW0DHtaQ/xFkw qgMgCuhEc2bo4qg52RXAQJpt1tc2UhD3joc3Evfnh36hcYKmZaYHI9UdbtXSsbXN2uN7 Vw/KlCycJK4F5OtHAsm7pDqOR9PKmWzutSplcWTb5j/SRM8V5D+QGkRZU5/0T6fgAxrG s/D4/RcTYhnvrolxVLgr600NrZCqS9grOyUj6nN8Tls9nDLeGSLE1RbeS3hf4SL5yBUh 5qdde93IIaBlM/s4a3PyeVwi9jvYxET3wpWqtBKB5jZkj3kCKZEEQMJjvKR70lHqjikd SEWA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=jf8TnTfhSbw4KDZgdjQDqBI4e9cWjVlyf2vBihu61/Q=; b=Wfeja4VrbqAwPcm4LBUtWIAqU8G5jyUoYopaCZGxKWOCYcy1FtgJIaTR3W8hu/29eK rx9P1ghwKomy2IciXcaEt1DFp/pph12226QeJXwaGERtVXQgXOjqmYLZddM5ptRXav70 f031oJYEjqsOhM0OXIBzTipGluOn8im/GcZ7ZXDN5lnt6ocHf4q58h4UCSl/ZgiKW1RD Her3614Ae8f1o6DtyZ4bZ9RBz5zWxJVs/ls3UFIc0mOUPfitCPGdn0mvXDUuJ0fhjNIV GyGhyiqc3BAfWbJjaHyXystILcA4uHKdrq7SDrSYFA++x43BJUmT/GwusPvsnDWH5vi4 BkPQ== X-Gm-Message-State: AJcUukd9tZs9Wy7H9mikJ2dLnqSdEAUgA9luddNVkxj63c/IBXhTOCF7 WL+dErRaK1esZr+mZxYOAvjX/zVfK0c= X-Google-Smtp-Source: ALg8bN4vWzdhMYacjt57SeAMFjei74Re0rboIXWc5jfPqIwR7o3aOWIM8kp8QEbIWfrpsIOJ/1eEkQ== X-Received: by 2002:a62:8e19:: with SMTP id k25mr9931222pfe.185.1547121918923; Thu, 10 Jan 2019 04:05:18 -0800 (PST) Received: from GotGit.hz.ali.com ([106.11.34.204]) by smtp.gmail.com with ESMTPSA id b2sm137189403pfm.3.2019.01.10.04.05.16 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 10 Jan 2019 04:05:18 -0800 (PST) From: Jiang Xin To: Junio C Hamano , Git List , =?utf-8?q?SZEDER_G=C3=A1bor?= , Sun Chao Cc: Jiang Xin , Johannes Sixt Subject: [PATCH v5 4/5] pack-redundant: consistent sort method Date: Thu, 10 Jan 2019 20:01:41 +0800 Message-Id: <20190110120142.22271-5-worldhello.net@gmail.com> X-Mailer: git-send-email 2.20.1.101.gc01fadde4e In-Reply-To: <20190109164731.GJ4673@szeder.dev> References: <20190109164731.GJ4673@szeder.dev> MIME-Version: 1.0 Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Jiang Xin SZEDER reported that test case t5323 has different test result on MacOS. This is because `cmp_pack_list_reverse` cannot give identical result when two pack being sorted has the same size of remaining_objects. Changes to the sorting function will make consistent test result for t5323. The new algorithm to find redundant packs is a trade-off to save memory resources, and the result of it may be different with old one, and may be not the best result sometimes. Update t5323 for the new algorithm. Reported-by: SZEDER Gábor Signed-off-by: Jiang Xin --- builtin/pack-redundant.c | 22 +++++++++++++++------- t/t5323-pack-redundant.sh | 2 +- 2 files changed, 16 insertions(+), 8 deletions(-) diff --git a/builtin/pack-redundant.c b/builtin/pack-redundant.c index 56591d283f..e9d2586e2e 100644 --- a/builtin/pack-redundant.c +++ b/builtin/pack-redundant.c @@ -33,6 +33,7 @@ static struct pack_list { struct packed_git *pack; struct llist *unique_objects; struct llist *remaining_objects; + size_t all_objects_size; } *local_packs = NULL, *altodb_packs = NULL; struct pll { @@ -421,16 +422,22 @@ static inline off_t pack_set_bytecount(struct pack_list *pl) return ret; } -static int cmp_pack_list_reverse(const void *a, const void *b) +static int cmp_remaining_objects(const void *a, const void *b) { struct pack_list *pl_a = *((struct pack_list **)a); struct pack_list *pl_b = *((struct pack_list **)b); - size_t sz_a = pl_a->remaining_objects->size; - size_t sz_b = pl_b->remaining_objects->size; - if (sz_a == sz_b) - return 0; - else if (sz_a < sz_b) + /* if have the same remaining_objects, big pack first */ + if (pl_a->remaining_objects->size == pl_b->remaining_objects->size) + if (pl_a->all_objects_size == pl_b->all_objects_size) + return 0; + else if (pl_a->all_objects_size < pl_b->all_objects_size) + return 1; + else + return -1; + + /* sort according to remaining objects, more remaining objects first */ + if (pl_a->remaining_objects->size < pl_b->remaining_objects->size) return 1; else return -1; @@ -451,7 +458,7 @@ static void sort_pack_list(struct pack_list **pl) for (n = 0, p = *pl; p; p = p->next) ary[n++] = p; - QSORT(ary, n, cmp_pack_list_reverse); + QSORT(ary, n, cmp_remaining_objects); /* link them back again */ for (i = 0; i < n - 1; i++) @@ -593,6 +600,7 @@ static struct pack_list * add_pack(struct packed_git *p) llist_insert_back(l.remaining_objects, (const struct object_id *)(base + off)); off += step; } + l.all_objects_size = l.remaining_objects->size; /* this list will be pruned in cmp_two_packs later */ l.unique_objects = llist_copy(l.remaining_objects); if (p->pack_local) diff --git a/t/t5323-pack-redundant.sh b/t/t5323-pack-redundant.sh index 7410426dee..2a09ff1bfb 100755 --- a/t/t5323-pack-redundant.sh +++ b/t/t5323-pack-redundant.sh @@ -90,7 +90,7 @@ test_expect_success 'create pack 4, 5' ' ' cat >expected < X-Patchwork-Id: 10755619 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 4B1F313BF for ; Thu, 10 Jan 2019 12:05:25 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 3A60320408 for ; Thu, 10 Jan 2019 12:05:25 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 2EBB8292C2; Thu, 10 Jan 2019 12:05:25 +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 C223420408 for ; Thu, 10 Jan 2019 12:05:24 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728215AbfAJMFX (ORCPT ); Thu, 10 Jan 2019 07:05:23 -0500 Received: from mail-pg1-f193.google.com ([209.85.215.193]:42553 "EHLO mail-pg1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728212AbfAJMFW (ORCPT ); Thu, 10 Jan 2019 07:05:22 -0500 Received: by mail-pg1-f193.google.com with SMTP id d72so4740655pga.9 for ; Thu, 10 Jan 2019 04:05:22 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=Ppb8OhGJpDYCo5Rzg+2JvZPBAKaZiAU2u5tjy5Rc/LE=; b=UZwzMlWpvKnGu3eafPRfkHPcKwCt5ZKNdAgrr+qLx//SWapvdsu2knsBVRoKwmcmeL A04j+VuqiuYlIH+bO2UcjCv5WwvXnrWLWJwqt/O6Su1tM834M1xscMTXopt6H+8abI5D D6iMAHc9rIsUtIgac35UmwjDdOczZo1FviedOJOPexJFT3As114T8xKcLFL97Nc9TO1d rgI9bIvHasQycdcizJ0DAJjM4+cTABd0H7Js1bjF3SdU6rkpNKoy3OHhGpnqsflx/AHo dC62fFwa9N5ViI9ujReM8ctww3a2Uv9G38evGZRB0CyaU7yu7hYtRJIdCDFdMsJLKNHj kH1g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=Ppb8OhGJpDYCo5Rzg+2JvZPBAKaZiAU2u5tjy5Rc/LE=; b=X79g07TJZtanxRD4RGaOmYKiWxXxNVa8XBgTRrgcFwma0htawK4Zuk1XWkMI6jD6x+ ZKwvW+/CcMOQy1heoyu7vOFx30c14zaKaYvgPLLzPChINZIT9BGSmLCogrgWNVfXav5p W4hAIierD9Zl07JvqeG0ILsaJlc51mOtdYNGEXyzdRjc9Dmgzkof2CfzYL5OwjtQOgUY IfRagX+Rix9KBq4D6vD2hNuAhP7po0v9avvfwFCEFGOgP7d8GipollKSKWdDzo0hHsbe Qx20WzDbhvu/gQ2Fr8MfZWtZiMwx2mzl8f+lRZBAy9293OZbEmxdiQRZ6CqP3F+ShA4c tFxA== X-Gm-Message-State: AJcUukdHYsnkivufp0Cb2ISicPjGhWI/W+9c5O5z84jcwa+eC6BdcHKm 4nkT6+fPeJr9oKoEbvK46V4= X-Google-Smtp-Source: ALg8bN7aMBIsr7SsiJPAk0OA8PfGDx4UlxHJzS6rIG6pO2y2HLwlvJqTQwMYKz7jBqZxIZEf6SHN6Q== X-Received: by 2002:a63:a84a:: with SMTP id i10mr9276227pgp.263.1547121921851; Thu, 10 Jan 2019 04:05:21 -0800 (PST) Received: from GotGit.hz.ali.com ([106.11.34.204]) by smtp.gmail.com with ESMTPSA id b2sm137189403pfm.3.2019.01.10.04.05.19 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 10 Jan 2019 04:05:20 -0800 (PST) From: Jiang Xin To: Junio C Hamano , Git List , =?utf-8?q?SZEDER_G=C3=A1bor?= , Sun Chao Cc: Johannes Sixt , Jiang Xin Subject: [PATCH v5 5/5] pack-redundant: remove unused functions Date: Thu, 10 Jan 2019 20:01:42 +0800 Message-Id: <20190110120142.22271-6-worldhello.net@gmail.com> X-Mailer: git-send-email 2.20.1.101.gc01fadde4e In-Reply-To: <20190109164731.GJ4673@szeder.dev> References: <20190109164731.GJ4673@szeder.dev> MIME-Version: 1.0 Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Sun Chao Remove unused functions to find `min` packs, such as `get_permutations`, `pll_free`, etc. Signed-off-by: Sun Chao Signed-off-by: Jiang Xin Signed-off-by: Junio C Hamano --- builtin/pack-redundant.c | 86 ---------------------------------------- 1 file changed, 86 deletions(-) diff --git a/builtin/pack-redundant.c b/builtin/pack-redundant.c index e9d2586e2e..dd71fdd435 100644 --- a/builtin/pack-redundant.c +++ b/builtin/pack-redundant.c @@ -36,11 +36,6 @@ static struct pack_list { size_t all_objects_size; } *local_packs = NULL, *altodb_packs = NULL; -struct pll { - struct pll *next; - struct pack_list *pl; -}; - static struct llist_item *free_nodes; static inline void llist_item_put(struct llist_item *item) @@ -64,15 +59,6 @@ static inline struct llist_item *llist_item_get(void) return new_item; } -static void llist_free(struct llist *list) -{ - while ((list->back = list->front)) { - list->front = list->front->next; - llist_item_put(list->back); - } - free(list); -} - static inline void llist_init(struct llist **list) { *list = xmalloc(sizeof(struct llist)); @@ -286,78 +272,6 @@ static void cmp_two_packs(struct pack_list *p1, struct pack_list *p2) } } -static void pll_free(struct pll *l) -{ - struct pll *old; - struct pack_list *opl; - - while (l) { - old = l; - while (l->pl) { - opl = l->pl; - l->pl = opl->next; - free(opl); - } - l = l->next; - free(old); - } -} - -/* all the permutations have to be free()d at the same time, - * since they refer to each other - */ -static struct pll * get_permutations(struct pack_list *list, int n) -{ - struct pll *subset, *ret = NULL, *new_pll = NULL; - - if (list == NULL || pack_list_size(list) < n || n == 0) - return NULL; - - if (n == 1) { - while (list) { - new_pll = xmalloc(sizeof(*new_pll)); - new_pll->pl = NULL; - pack_list_insert(&new_pll->pl, list); - new_pll->next = ret; - ret = new_pll; - list = list->next; - } - return ret; - } - - while (list->next) { - subset = get_permutations(list->next, n - 1); - while (subset) { - new_pll = xmalloc(sizeof(*new_pll)); - new_pll->pl = subset->pl; - pack_list_insert(&new_pll->pl, list); - new_pll->next = ret; - ret = new_pll; - subset = subset->next; - } - list = list->next; - } - return ret; -} - -static int is_superset(struct pack_list *pl, struct llist *list) -{ - struct llist *diff; - - diff = llist_copy(list); - - while (pl) { - llist_sorted_difference_inplace(diff, pl->remaining_objects); - if (diff->size == 0) { /* we're done */ - llist_free(diff); - return 1; - } - pl = pl->next; - } - llist_free(diff); - return 0; -} - static size_t sizeof_union(struct packed_git *p1, struct packed_git *p2) { size_t ret = 0;