{"thread":{"id":"2440","subject":"[PATCH] Make git-pack-redundant consider alt-odbs","startedAt":"2005-11-11T00:25:04Z","lastAt":"2005-11-11T00:40:48Z","messageCount":2,"participants":["Lukas Sandström","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"11535","messageId":"4373E4E0.10903@etek.chalmers.se","threadId":"2440","inReplyTo":null,"subject":"[PATCH] Make git-pack-redundant consider alt-odbs","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-11T00:25:04Z","receivedAt":"2005-11-11T00:25:04Z","isPatch":true,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"[PATCH] Make git-pack-redundant consider alt-odbs\n\nThis patch changes git-pack-redundant so that packfiles\nin alternate object directories also are considered when\ndeciding which objects are redundant.\n\nThis functionality is controlled by the flag '--alt-odb'.\n\nAlso convert the other flags to the long form, and update\ndocs and git-repack accordingly.\n\nSigned-off-by: Lukas Sandström <lukass@etek.chalmers.se>\n\n---\n\nOn a related note; if you have unreachable objects in your\npackfiles, those objects might make otherwise redundant\npackfiles non-redundant. \n\nWould it be a useful feature to be able to give git-pack-redundant\na list of bad objects on stdin, which then will be ignored?\n\n(eg. git-fsck-objects --full --unreachable | cut -s -d ' ' -f 3 | git-pack-redundant)\n\n Documentation/git-pack-redundant.txt |   19 +++-\n git-repack.sh                        |    4 -\n pack-redundant.c                     |  147 ++++++++++++++++++++++------------\n 3 files changed, 107 insertions(+), 63 deletions(-)\n\napplies-to: 8f520c14677a07c01eb64f64bcd68cb174392ec9\nad7d016fcecacdfaf9cf0cc4b65fadf32e86899b\ndiff --git a/Documentation/git-pack-redundant.txt b/Documentation/git-pack-redundant.txt\nindex 3829616..2e23cbc 100644\n--- a/Documentation/git-pack-redundant.txt\n+++ b/Documentation/git-pack-redundant.txt\n@@ -8,7 +8,7 @@ git-pack-redundant - Program used to fin\n \n SYNOPSIS\n --------\n-'git-pack-redundant [ -v ] < -a | .pack filename ... >'\n+'git-pack-redundant [ --verbose ] [ --alt-odb ] < --all | .pack filename ... >'\n \n DESCRIPTION\n -----------\n@@ -19,13 +19,16 @@ are redundant. The output is suitable fo\n OPTIONS\n -------\n \n--v::\n-\tVerbose. Outputs some statistics to stderr.\n-\tHas a small performance penalty.\n-\n--a::\n-\tAll. Processes all the local packs. Any filenames on\n-\tthe commandline are ignored.\n+\n+--all::\n+\tProcesses all packs. Any filenames on the commandline are ignored.\n+\n+--alt-odb::\n+\tDon't require objects present in packs from alternate object\n+\tdirectories to be present in local packs.\n+\n+--verbose::\n+\tOutputs some statistics to stderr. Has a small performance penalty.\n \n Author\n ------\ndiff --git a/git-repack.sh b/git-repack.sh\nindex 4ce0022..f347207 100755\n--- a/git-repack.sh\n+++ b/git-repack.sh\n@@ -45,7 +45,7 @@ if [ -z \"$name\" ]; then\n \tif test \"$remove_redandant\" = t ; then\n \t\techo \"Removing redundant packs.\"\n \t\tsync\n-\t\tredundant=$(git-pack-redundant -a)\n+\t\tredundant=$(git-pack-redundant --all)\n \t\tif test \"$redundant\" != \"\" ; then\n \t\t\techo $redundant | xargs rm\n \t\tfi\n@@ -63,7 +63,7 @@ exit\n if test \"$remove_redandant\" = t\n then\n \tsync\n-\tredundant=$(git-pack-redundant -a)\n+\tredundant=$(git-pack-redundant --all)\n \tif test \"$redundant\" != \"\" ; then\n \t\techo $redundant | xargs rm\n \tfi\ndiff --git a/pack-redundant.c b/pack-redundant.c\nindex db3dcde..1f8c577 100644\n--- a/pack-redundant.c\n+++ b/pack-redundant.c\n@@ -9,9 +9,9 @@\n #include \"cache.h\"\n \n static const char pack_redundant_usage[] =\n-\"git-pack-redundant [ -v ]  < -a | <.pack filename> ...>\";\n+\"git-pack-redundant [ --verbose ] [ --alt-odb ] < --all | <.pack filename> ...>\";\n \n-int all = 0, verbose = 0;\n+int load_all_packs = 0, verbose = 0, alt_odb = 0;\n \n struct llist_item {\n \tstruct llist_item *next;\n@@ -21,14 +21,14 @@ struct llist {\n \tstruct llist_item *front;\n \tstruct llist_item *back;\n \tsize_t size;\n-} *all_objects;\n+} *all_objects; /* all objects which must be present in local packfiles */\n \n struct pack_list {\n \tstruct pack_list *next;\n \tstruct packed_git *pack;\n \tstruct llist *unique_objects;\n \tstruct llist *all_objects;\n-} *pack_list;\n+} *local_packs = NULL, *altodb_packs = NULL;\n \n struct pll {\n \tstruct pll *next;\n@@ -128,32 +128,35 @@ inline struct llist_item * llist_insert_\n }\n \n /* computes A\\B */\n-struct llist * llist_sorted_difference(struct llist_item *A,\n-\t\t\t\t       struct llist_item *B)\n+void llist_sorted_difference_inplace(struct llist *A,\n+\t\t\t\t     struct llist *B)\n {\n-\tstruct llist *ret;\n-\tllist_init(&ret);\n+\tstruct llist_item *prev, *a, *b, *x;\n \n-\twhile (A != NULL && B != NULL) {\n-\t\tint cmp = memcmp(A->sha1, B->sha1, 20);\n+\tprev = a = A->front;\n+\tb = B->front;\n+\n+\twhile (a != NULL && b != NULL) {\n+\t\tint cmp = memcmp(a->sha1, b->sha1, 20);\n \t\tif (!cmp) {\n-\t\t\tA = A->next;\n-\t\t\tB = B->next;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tif(cmp > 0) { /* we'll never find this B */\n-\t\t\tB = B->next;\n-\t\t\tcontinue;\n-\t\t}\n-\t\t/* A has the object, B doesn't */\n-\t\tllist_insert_back(ret, A->sha1);\n-\t\tA = A->next;\n-\t}\n-\twhile (A != NULL) {\n-\t\tllist_insert_back(ret, A->sha1);\n-\t\tA = A->next;\n+\t\t\tx = a;\n+\t\t\tif (a == A->front)\n+\t\t\t\tA->front = a->next;\n+\t\t\ta = prev->next = a->next;\n+\n+\t\t\tif (a == NULL) /* end of list */\n+\t\t\t\tA->back = prev;\n+\t\t\tA->size--;\n+\t\t\tfree(x);\n+\t\t\tb = b->next;\n+\t\t} else\n+\t\t\tif (cmp > 0)\n+\t\t\t\tb = b->next;\n+\t\t\telse {\n+\t\t\t\tprev = a;\n+\t\t\t\ta = a->next;\n+\t\t\t}\n \t}\n-\treturn ret;\n }\n \n /* returns a pointer to an item in front of sha1 */\n@@ -201,6 +204,16 @@ inline struct pack_list * pack_list_inse\n \treturn p;\n }\n \n+inline size_t pack_list_size(struct pack_list *pl)\n+{\n+\tsize_t ret = 0;\n+\twhile(pl) {\n+\t\tret++;\n+\t\tpl = pl->next;\n+\t}\n+\treturn ret;\n+}\n+\n struct pack_list * pack_list_difference(struct pack_list *A,\n \t\t\t\t\tstruct pack_list *B)\n {\n@@ -294,15 +307,13 @@ struct pll * get_all_permutations(struct\n \n int is_superset(struct pack_list *pl, struct llist *list)\n {\n-\tstruct llist *diff, *old;\n+\tstruct llist *diff;\n \n \tdiff = llist_copy(list);\n \n \twhile (pl) {\n-\t\told = diff;\n-\t\tdiff = llist_sorted_difference(diff->front,\n-\t\t\t\t\t       pl->all_objects->front);\n-\t\tllist_free(old);\n+\t\tllist_sorted_difference_inplace(diff,\n+\t\t\t\t\t\tpl->all_objects);\n \t\tif (diff->size == 0) { /* we're done */\n \t\t\tllist_free(diff);\n \t\t\treturn 1;\n@@ -347,6 +358,10 @@ size_t sizeof_union(struct packed_git *p\n size_t get_pack_redundancy(struct pack_list *pl)\n {\n \tstruct pack_list *subset;\n+\n+\tif (pl == NULL)\n+\t\treturn 0;\n+\n \tsize_t ret = 0;\n \twhile ((subset = pl->next)) {\n \t\twhile(subset) {\n@@ -374,10 +389,10 @@ void minimize(struct pack_list **min)\n \tstruct pack_list *pl, *unique = NULL,\n \t\t*non_unique = NULL, *min_perm = NULL;\n \tstruct pll *perm, *perm_all, *perm_ok = NULL, *new_perm;\n-\tstruct llist *missing, *old;\n+\tstruct llist *missing;\n \tsize_t min_perm_size = (size_t)-1, perm_size;\n \n-\tpl = pack_list;\n+\tpl = local_packs;\n \twhile (pl) {\n \t\tif(pl->unique_objects->size)\n \t\t\tpack_list_insert(&unique, pl);\n@@ -389,13 +404,12 @@ void minimize(struct pack_list **min)\n \tmissing = llist_copy(all_objects);\n \tpl = unique;\n \twhile (pl) {\n-\t\told = missing;\n-\t\tmissing = llist_sorted_difference(missing->front,\n-\t\t\t\t\t\t  pl->all_objects->front);\n-\t\tllist_free(old);\n+\t\tllist_sorted_difference_inplace(missing,\n+\t\t\t\t\t\tpl->all_objects);\n \t\tpl = pl->next;\n \t}\n \n+\t/* return if there are no objects missing from the unique set */\n \tif (missing->size == 0) {\n \t\t*min = unique;\n \t\treturn;\n@@ -437,7 +451,7 @@ void minimize(struct pack_list **min)\n \n void load_all_objects()\n {\n-\tstruct pack_list *pl = pack_list;\n+\tstruct pack_list *pl = local_packs;\n \tstruct llist_item *hint, *l;\n \tint i;\n \n@@ -454,17 +468,34 @@ void load_all_objects()\n \t\t}\n \t\tpl = pl->next;\n \t}\n+\t/* remove objects present in remote packs */\n+\tpl = altodb_packs;\n+\twhile (pl) {\n+\t\tllist_sorted_difference_inplace(all_objects, pl->all_objects);\n+\t\tpl = pl->next;\n+\t}\n }\n \n /* this scales like O(n^2) */\n void cmp_packs()\n {\n-\tstruct pack_list *subset, *curr = pack_list;\n+\tstruct pack_list *subset, *pl = local_packs;\n \n-\twhile ((subset = curr)) {\n+\twhile ((subset = pl)) {\n \t\twhile((subset = subset->next))\n-\t\t\tcmp_two_packs(curr, subset);\n-\t\tcurr = curr->next;\n+\t\t\tcmp_two_packs(pl, subset);\n+\t\tpl = pl->next;\n+\t}\n+\n+\tpl = altodb_packs;\n+\twhile (pl) {\n+\t\tsubset = local_packs;\n+\t\twhile (subset) {\n+\t\t\tllist_sorted_difference_inplace(subset->unique_objects,\n+\t\t\t\t\t\t\tpl->all_objects);\n+\t\t\tsubset = subset->next;\n+\t\t}\n+\t\tpl = pl->next;\n \t}\n }\n \n@@ -485,7 +516,10 @@ struct pack_list * add_pack(struct packe\n \t}\n \t/* this list will be pruned in cmp_two_packs later */\n \tl.unique_objects = llist_copy(l.all_objects);\n-\treturn pack_list_insert(&pack_list, &l);\n+\tif (p->pack_local)\n+\t\treturn pack_list_insert(&local_packs, &l);\n+\telse\n+\t\treturn alt_odb ? pack_list_insert(&altodb_packs, &l) : NULL;\n }\n \n struct pack_list * add_pack_file(char *filename)\n@@ -497,7 +531,6 @@ struct pack_list * add_pack_file(char *f\n \n \twhile (p) {\n \t\tif (strstr(p->pack_name, filename))\n-\t\t\t/* this will silently ignore packs in alt-odb */\n \t\t\treturn add_pack(p);\n \t\tp = p->next;\n \t}\n@@ -509,8 +542,7 @@ void load_all()\n \tstruct packed_git *p = packed_git;\n \n \twhile (p) {\n-\t\tif (p->pack_local) /* ignore alt-odb for now */\n-\t\t\tadd_pack(p);\n+\t\tadd_pack(p);\n \t\tp = p->next;\n \t}\n }\n@@ -526,14 +558,18 @@ int main(int argc, char **argv)\n \t\t\ti++;\n \t\t\tbreak;\n \t\t}\n-\t\tif(!strcmp(arg, \"-a\")) {\n-\t\t\tall = 1;\n+\t\tif(!strcmp(arg, \"--all\")) {\n+\t\t\tload_all_packs = 1;\n \t\t\tcontinue;\n \t\t}\n-\t\tif(!strcmp(arg, \"-v\")) {\n+\t\tif(!strcmp(arg, \"--verbose\")) {\n \t\t\tverbose = 1;\n \t\t\tcontinue;\n \t\t}\n+\t\tif(!strcmp(arg, \"--alt-odb\")) {\n+\t\t\talt_odb = 1;\n+\t\t\tcontinue;\n+\t\t}\n \t\tif(*arg == '-')\n \t\t\tusage(pack_redundant_usage);\n \t\telse\n@@ -542,13 +578,13 @@ int main(int argc, char **argv)\n \n \tprepare_packed_git();\n \n-\tif(all)\n+\tif (load_all_packs)\n \t\tload_all();\n \telse\n \t\twhile (*(argv + i) != NULL)\n \t\t\tadd_pack_file(*(argv + i++));\n \n-\tif (pack_list == NULL)\n+\tif (local_packs == NULL)\n \t\tdie(\"Zero packs found!\\n\");\n \n \tcmp_packs();\n@@ -557,6 +593,8 @@ int main(int argc, char **argv)\n \n \tminimize(&min);\n \tif (verbose) {\n+\t\tfprintf(stderr, \"There are %ld packs available in alt-odbs.\\n\",\n+\t\t\tpack_list_size(altodb_packs));\n \t\tfprintf(stderr, \"The smallest (bytewise) set of packs is:\\n\");\n \t\tpl = min;\n \t\twhile (pl) {\n@@ -566,12 +604,15 @@ int main(int argc, char **argv)\n \t\tfprintf(stderr, \"containing %ld duplicate objects \"\n \t\t\t\t\"with a total size of %ldkb.\\n\",\n \t\t\tget_pack_redundancy(min), pack_set_bytecount(min)/1024);\n+\t\tfprintf(stderr, \"A total of %ld unique objects were considered.\\n\",\n+\t\t\tall_objects->size);\n \t\tfprintf(stderr, \"Redundant packs (with indexes):\\n\");\n \t}\n-\tpl = red = pack_list_difference(pack_list, min);\n+\tpl = red = pack_list_difference(local_packs, min);\n \twhile (pl) {\n \t\tprintf(\"%s\\n%s\\n\",\n-\t\t       sha1_pack_index_name(pl->pack->sha1), pl->pack->pack_name);\n+\t\t       sha1_pack_index_name(pl->pack->sha1),\n+\t\t       pl->pack->pack_name);\n \t\tpl = pl->next;\n \t}\n \n---\n0.99.9.GIT\n"},{"id":"11536","messageId":"7vslu4vwxb.fsf@assigned-by-dhcp.cox.net","threadId":"2440","inReplyTo":"4373E4E0.10903@etek.chalmers.se","subject":"Re: [PATCH] Make git-pack-redundant consider alt-odbs","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-11-11T00:40:48Z","receivedAt":"2005-11-11T00:40:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Lukas Sandström <lukass@etek.chalmers.se> writes:\n\n> [PATCH] Make git-pack-redundant consider alt-odbs\n>\n> This patch changes git-pack-redundant so that packfiles\n> ...\n\nThis request is not just for Lukas, but people, please do not\nduplicate what is already on the Subject: line at the top of\nyour message body.\n"}]}