3 * Copyright 2005, Lukas Sandstrom <lukass@etek.chalmers.se>
5 * This file is licensed under the GPL v2.
11 static const char pack_redundant_usage[] =
12 "git-pack-redundant [ --verbose ] [ --alt-odb ] < --all | <.pack filename> ...>";
14 int load_all_packs = 0, verbose = 0, alt_odb = 0;
17 struct llist_item *next;
21 struct llist_item *front;
22 struct llist_item *back;
24 } *all_objects; /* all objects which must be present in local packfiles */
27 struct pack_list *next;
28 struct packed_git *pack;
29 struct llist *unique_objects;
30 struct llist *all_objects;
31 } *local_packs = NULL, *altodb_packs = NULL;
39 inline void llist_free(struct llist *list)
41 while((list->back = list->front)) {
42 list->front = list->front->next;
48 inline void llist_init(struct llist **list)
50 *list = xmalloc(sizeof(struct llist));
51 (*list)->front = (*list)->back = NULL;
55 struct llist * llist_copy(struct llist *list)
58 struct llist_item *new, *old, *prev;
62 if ((ret->size = list->size) == 0)
65 new = ret->front = xmalloc(sizeof(struct llist_item));
66 new->sha1 = list->front->sha1;
68 old = list->front->next;
71 new = xmalloc(sizeof(struct llist_item));
73 new->sha1 = old->sha1;
82 inline struct llist_item * llist_insert(struct llist *list,
83 struct llist_item *after, char *sha1)
85 struct llist_item *new = xmalloc(sizeof(struct llist_item));
90 new->next = after->next;
92 if (after == list->back)
94 } else {/* insert in front */
98 new->next = list->front;
105 inline struct llist_item * llist_insert_back(struct llist *list, char *sha1)
107 return llist_insert(list, list->back, sha1);
110 inline struct llist_item * llist_insert_sorted_unique(struct llist *list,
111 char *sha1, struct llist_item *hint)
113 struct llist_item *prev = NULL, *l;
115 l = (hint == NULL) ? list->front : hint;
117 int cmp = memcmp(l->sha1, sha1, 20);
118 if (cmp > 0) { /* we insert before this entry */
119 return llist_insert(list, prev, sha1);
121 if(!cmp) { /* already exists */
127 /* insert at the end */
128 return llist_insert_back(list, sha1);
131 /* returns a pointer to an item in front of sha1 */
132 inline struct llist_item * llist_sorted_remove(struct llist *list, char *sha1,
133 struct llist_item *hint)
135 struct llist_item *prev, *l;
138 l = (hint == NULL) ? list->front : hint;
141 int cmp = memcmp(l->sha1, sha1, 20);
142 if (cmp > 0) /* not in list, since sorted */
144 if(!cmp) { /* found */
146 if (hint != NULL && hint != list->front) {
147 /* we don't know the previous element */
149 goto redo_from_start;
151 list->front = l->next;
153 prev->next = l->next;
167 void llist_sorted_difference_inplace(struct llist *A,
170 struct llist_item *hint, *b;
176 hint = llist_sorted_remove(A, b->sha1, hint);
181 inline struct pack_list * pack_list_insert(struct pack_list **pl,
182 struct pack_list *entry)
184 struct pack_list *p = xmalloc(sizeof(struct pack_list));
185 memcpy(p, entry, sizeof(struct pack_list));
191 inline size_t pack_list_size(struct pack_list *pl)
201 struct pack_list * pack_list_difference(struct pack_list *A,
204 struct pack_list *ret, *pl;
211 if (A->pack == pl->pack)
212 return pack_list_difference(A->next, B);
215 ret = xmalloc(sizeof(struct pack_list));
216 memcpy(ret, A, sizeof(struct pack_list));
217 ret->next = pack_list_difference(A->next, B);
221 void cmp_two_packs(struct pack_list *p1, struct pack_list *p2)
224 void *p1_base, *p2_base;
225 struct llist_item *p1_hint = NULL, *p2_hint = NULL;
227 p1_off = p2_off = 256 * 4 + 4;
228 p1_base = (void *)p1->pack->index_base;
229 p2_base = (void *)p2->pack->index_base;
231 while (p1_off <= p1->pack->index_size - 3 * 20 &&
232 p2_off <= p2->pack->index_size - 3 * 20)
234 int cmp = memcmp(p1_base + p1_off, p2_base + p2_off, 20);
237 p1_hint = llist_sorted_remove(p1->unique_objects,
238 p1_base + p1_off, p1_hint);
239 p2_hint = llist_sorted_remove(p2->unique_objects,
240 p1_base + p1_off, p2_hint);
245 if (cmp < 0) { /* p1 has the object, p2 doesn't */
247 } else { /* p2 has the object, p1 doesn't */
253 void pll_insert(struct pll **pll, struct pll **hint_table)
256 int i = (*pll)->pl_size - 1;
258 if (hint_table[i] == NULL) {
259 hint_table[i--] = *pll;
260 for (; i >= 0; --i) {
261 if (hint_table[i] != NULL)
264 if (hint_table[i] == NULL) /* no elements in list */
265 die("Why did this happen?");
268 prev = hint_table[i];
269 while (prev->next && prev->next->pl_size < (*pll)->pl_size)
272 (*pll)->next = prev->next;
276 /* all the permutations have to be free()d at the same time,
277 * since they refer to each other
279 struct pll * get_all_permutations(struct pack_list *list)
281 struct pll *subset, *pll, *new_pll = NULL; /*silence warning*/
282 static struct pll **hint = NULL;
284 hint = xcalloc(pack_list_size(list), sizeof(struct pll *));
289 if (list->next == NULL) {
290 new_pll = xmalloc(sizeof(struct pll));
292 new_pll->next = NULL;
294 new_pll->pl_size = 1;
298 pll = subset = get_all_permutations(list->next);
300 if (pll->pl->pack == list->pack) {
304 new_pll = xmalloc(sizeof(struct pll));
306 new_pll->pl = xmalloc(sizeof(struct pack_list));
307 memcpy(new_pll->pl, list, sizeof(struct pack_list));
308 new_pll->pl->next = pll->pl;
309 new_pll->pl_size = pll->pl_size + 1;
311 pll_insert(&new_pll, hint);
316 new_pll = xmalloc(sizeof(struct pll));
317 new_pll->pl = xmalloc(sizeof(struct pack_list));
318 memcpy(new_pll->pl, list, sizeof(struct pack_list));
319 new_pll->pl->next = NULL;
320 new_pll->pl_size = 1;
321 pll_insert(&new_pll, hint);
326 int is_superset(struct pack_list *pl, struct llist *list)
330 diff = llist_copy(list);
333 llist_sorted_difference_inplace(diff,
335 if (diff->size == 0) { /* we're done */
345 size_t sizeof_union(struct packed_git *p1, struct packed_git *p2)
349 void *p1_base, *p2_base;
351 p1_off = p2_off = 256 * 4 + 4;
352 p1_base = (void *)p1->index_base;
353 p2_base = (void *)p2->index_base;
355 while (p1_off <= p1->index_size - 3 * 20 &&
356 p2_off <= p2->index_size - 3 * 20)
358 int cmp = memcmp(p1_base + p1_off, p2_base + p2_off, 20);
366 if (cmp < 0) { /* p1 has the object, p2 doesn't */
368 } else { /* p2 has the object, p1 doesn't */
375 /* another O(n^2) function ... */
376 size_t get_pack_redundancy(struct pack_list *pl)
378 struct pack_list *subset;
384 while ((subset = pl->next)) {
386 ret += sizeof_union(pl->pack, subset->pack);
387 subset = subset->next;
394 inline size_t pack_set_bytecount(struct pack_list *pl)
398 ret += pl->pack->pack_size;
399 ret += pl->pack->index_size;
405 void minimize(struct pack_list **min)
407 struct pack_list *pl, *unique = NULL,
408 *non_unique = NULL, *min_perm = NULL;
409 struct pll *perm, *perm_all, *perm_ok = NULL, *new_perm;
410 struct llist *missing;
411 size_t min_perm_size = (size_t)-1, perm_size;
415 if(pl->unique_objects->size)
416 pack_list_insert(&unique, pl);
418 pack_list_insert(&non_unique, pl);
421 /* find out which objects are missing from the set of unique packs */
422 missing = llist_copy(all_objects);
425 llist_sorted_difference_inplace(missing,
430 /* return if there are no objects missing from the unique set */
431 if (missing->size == 0) {
436 /* find the permutations which contain all missing objects */
437 perm_all = perm = get_all_permutations(non_unique);
439 if (perm_ok && perm->pl_size > perm_ok->pl_size)
440 break; /* ignore all larger permutations */
441 if (is_superset(perm->pl, missing)) {
442 new_perm = xmalloc(sizeof(struct pll));
443 memcpy(new_perm, perm, sizeof(struct pll));
444 new_perm->next = perm_ok;
451 die("Internal error: No complete sets found!\n");
453 /* find the permutation with the smallest size */
456 perm_size = pack_set_bytecount(perm->pl);
457 if (min_perm_size > perm_size) {
458 min_perm_size = perm_size;
464 /* add the unique packs to the list */
467 pack_list_insert(min, pl);
472 void load_all_objects()
474 struct pack_list *pl = local_packs;
475 struct llist_item *hint, *l;
478 llist_init(&all_objects);
483 l = pl->all_objects->front;
485 hint = llist_insert_sorted_unique(all_objects,
491 /* remove objects present in remote packs */
494 llist_sorted_difference_inplace(all_objects, pl->all_objects);
499 /* this scales like O(n^2) */
500 void cmp_local_packs()
502 struct pack_list *subset, *pl = local_packs;
504 while ((subset = pl)) {
505 while((subset = subset->next))
506 cmp_two_packs(pl, subset);
511 void scan_alt_odb_packs()
513 struct pack_list *local, *alt;
519 llist_sorted_difference_inplace(local->unique_objects,
527 struct pack_list * add_pack(struct packed_git *p)
533 if (!p->pack_local && !(alt_odb || verbose))
537 llist_init(&l.all_objects);
540 base = (void *)p->index_base;
541 while (off <= p->index_size - 3 * 20) {
542 llist_insert_back(l.all_objects, base + off);
545 /* this list will be pruned in cmp_two_packs later */
546 l.unique_objects = llist_copy(l.all_objects);
548 return pack_list_insert(&local_packs, &l);
550 return pack_list_insert(&altodb_packs, &l);
553 struct pack_list * add_pack_file(char *filename)
555 struct packed_git *p = packed_git;
557 if (strlen(filename) < 40)
558 die("Bad pack filename: %s\n", filename);
561 if (strstr(p->pack_name, filename))
565 die("Filename %s not found in packed_git\n", filename);
570 struct packed_git *p = packed_git;
578 int main(int argc, char **argv)
581 struct pack_list *min, *red, *pl;
583 for (i = 1; i < argc; i++) {
584 const char *arg = argv[i];
585 if(!strcmp(arg, "--")) {
589 if(!strcmp(arg, "--all")) {
593 if(!strcmp(arg, "--verbose")) {
597 if(!strcmp(arg, "--alt-odb")) {
602 usage(pack_redundant_usage);
607 prepare_packed_git();
612 while (*(argv + i) != NULL)
613 add_pack_file(*(argv + i++));
615 if (local_packs == NULL)
616 die("Zero packs found!\n");
622 scan_alt_odb_packs();
627 fprintf(stderr, "There are %lu packs available in alt-odbs.\n",
628 (unsigned long)pack_list_size(altodb_packs));
629 fprintf(stderr, "The smallest (bytewise) set of packs is:\n");
632 fprintf(stderr, "\t%s\n", pl->pack->pack_name);
635 fprintf(stderr, "containing %lu duplicate objects "
636 "with a total size of %lukb.\n",
637 (unsigned long)get_pack_redundancy(min),
638 (unsigned long)pack_set_bytecount(min)/1024);
639 fprintf(stderr, "A total of %lu unique objects were considered.\n",
640 (unsigned long)all_objects->size);
641 fprintf(stderr, "Redundant packs (with indexes):\n");
643 pl = red = pack_list_difference(local_packs, min);
646 sha1_pack_index_name(pl->pack->sha1),
647 pl->pack->pack_name);