git-config-set: add more options

[git.git] / pack-redundant.c

diff --git a/pack-redundant.c b/pack-redundant.c
index fcb36ff..fb6cb48 100644 (file)
--- a/pack-redundant.c
+++ b/pack-redundant.c
@@ -33,6 +33,7 @@ struct pack_list {
 struct pll {
        struct pll *next;
        struct pack_list *pl;
+       size_t pl_size;
 };
 
 inline void llist_free(struct llist *list)
@@ -249,43 +250,77 @@ void cmp_two_packs(struct pack_list *p1, struct pack_list *p2)
        }
 }
 
+void pll_insert(struct pll **pll, struct pll **hint_table)
+{
+       struct pll *prev;
+       int i = (*pll)->pl_size - 1;
+
+       if (hint_table[i] == NULL) {
+               hint_table[i--] = *pll;
+               for (; i >= 0; --i) {
+                       if (hint_table[i] != NULL)
+                               break;
+               }
+               if (hint_table[i] == NULL) /* no elements in list */
+                       die("Why did this happen?");
+       }
+
+       prev = hint_table[i];
+       while (prev->next && prev->next->pl_size < (*pll)->pl_size)
+               prev = prev->next;
+
+       (*pll)->next = prev->next;
+       prev->next = *pll;
+}
+
 /* all the permutations have to be free()d at the same time,
  * since they refer to each other
  */
 struct pll * get_all_permutations(struct pack_list *list)
 {
        struct pll *subset, *pll, *new_pll = NULL; /*silence warning*/
-
+       static struct pll **hint = NULL;
+       if (hint == NULL)
+               hint = xcalloc(pack_list_size(list), sizeof(struct pll *));
+               
        if (list == NULL)
                return NULL;
 
        if (list->next == NULL) {
                new_pll = xmalloc(sizeof(struct pll));
+               hint[0] = new_pll;
                new_pll->next = NULL;
                new_pll->pl = list;
+               new_pll->pl_size = 1;
                return new_pll;
        }
 
        pll = subset = get_all_permutations(list->next);
        while (pll) {
+               if (pll->pl->pack == list->pack) {
+                       pll = pll->next;
+                       continue;
+               }
                new_pll = xmalloc(sizeof(struct pll));
-               new_pll->next = pll->next;
-               pll->next = new_pll;
 
                new_pll->pl = xmalloc(sizeof(struct pack_list));
                memcpy(new_pll->pl, list, sizeof(struct pack_list));
                new_pll->pl->next = pll->pl;
+               new_pll->pl_size = pll->pl_size + 1;
+               
+               pll_insert(&new_pll, hint);
 
-               pll = new_pll->next;
+               pll = pll->next;
        }
-       /* add ourself to the end */
-       new_pll->next = xmalloc(sizeof(struct pll));
-       new_pll->next->pl = xmalloc(sizeof(struct pack_list));
-       new_pll->next->next = NULL;
-       memcpy(new_pll->next->pl, list, sizeof(struct pack_list));
-       new_pll->next->pl->next = NULL;
-
-       return subset;
+       /* add ourself */
+       new_pll = xmalloc(sizeof(struct pll));
+       new_pll->pl = xmalloc(sizeof(struct pack_list));
+       memcpy(new_pll->pl, list, sizeof(struct pack_list));
+       new_pll->pl->next = NULL;
+       new_pll->pl_size = 1;
+       pll_insert(&new_pll, hint);
+
+       return hint[0];
 }
 
 int is_superset(struct pack_list *pl, struct llist *list)
@@ -401,9 +436,11 @@ void minimize(struct pack_list **min)
        /* find the permutations which contain all missing objects */
        perm_all = perm = get_all_permutations(non_unique);
        while (perm) {
+               if (perm_ok && perm->pl_size > perm_ok->pl_size)
+                       break; /* ignore all larger permutations */
                if (is_superset(perm->pl, missing)) {
                        new_perm = xmalloc(sizeof(struct pll));
-                       new_perm->pl = perm->pl;
+                       memcpy(new_perm, perm, sizeof(struct pll));
                        new_perm->next = perm_ok;
                        perm_ok = new_perm;
                }
@@ -460,7 +497,7 @@ void load_all_objects()
 }
 
 /* this scales like O(n^2) */
-void cmp_packs()
+void cmp_local_packs()
 {
        struct pack_list *subset, *pl = local_packs;
 
@@ -469,16 +506,21 @@ void cmp_packs()
                        cmp_two_packs(pl, subset);
                pl = pl->next;
        }
+}
 
-       pl = altodb_packs;
-       while (pl) {
-               subset = local_packs;
-               while (subset) {
-                       llist_sorted_difference_inplace(subset->unique_objects,
-                                                       pl->all_objects);
-                       subset = subset->next;
+void scan_alt_odb_packs()
+{
+       struct pack_list *local, *alt;
+
+       alt = altodb_packs;
+       while (alt) {
+               local = local_packs;
+               while (local) {
+                       llist_sorted_difference_inplace(local->unique_objects,
+                                                       alt->all_objects);
+                       local = local->next;
                }
-               pl = pl->next;
+               alt = alt->next;
        }
 }
 
@@ -488,6 +530,9 @@ struct pack_list * add_pack(struct packed_git *p)
        size_t off;
        void *base;
 
+       if (!p->pack_local && !(alt_odb || verbose))
+               return NULL;
+
        l.pack = p;
        llist_init(&l.all_objects);
 
@@ -495,14 +540,14 @@ struct pack_list * add_pack(struct packed_git *p)
        base = (void *)p->index_base;
        while (off <= p->index_size - 3 * 20) {
                llist_insert_back(l.all_objects, base + off);
-               off+=24;
+               off += 24;
        }
        /* this list will be pruned in cmp_two_packs later */
        l.unique_objects = llist_copy(l.all_objects);
        if (p->pack_local)
                return pack_list_insert(&local_packs, &l);
        else
-               return alt_odb ? pack_list_insert(&altodb_packs, &l) : NULL;
+               return pack_list_insert(&altodb_packs, &l);
 }
 
 struct pack_list * add_pack_file(char *filename)
@@ -570,11 +615,14 @@ int main(int argc, char **argv)
        if (local_packs == NULL)
                die("Zero packs found!\n");
 
-       cmp_packs();
-
        load_all_objects();
 
+       cmp_local_packs();
+       if (alt_odb)
+               scan_alt_odb_packs();
+
        minimize(&min);
+
        if (verbose) {
                fprintf(stderr, "There are %lu packs available in alt-odbs.\n",
                        (unsigned long)pack_list_size(altodb_packs));