struct pll {
struct pll *next;
struct pack_list *pl;
+ size_t pl_size;
};
inline void llist_free(struct llist *list)
return llist_insert_back(list, sha1);
}
-/* computes A\B */
-void llist_sorted_difference_inplace(struct llist *A,
- struct llist *B)
-{
- struct llist_item *prev, *a, *b, *x;
-
- prev = a = A->front;
- b = B->front;
-
- while (a != NULL && b != NULL) {
- int cmp = memcmp(a->sha1, b->sha1, 20);
- if (!cmp) {
- x = a;
- if (a == A->front)
- A->front = a->next;
- a = prev->next = a->next;
-
- if (a == NULL) /* end of list */
- A->back = prev;
- A->size--;
- free(x);
- b = b->next;
- } else
- if (cmp > 0)
- b = b->next;
- else {
- prev = a;
- a = a->next;
- }
- }
-}
-
/* returns a pointer to an item in front of sha1 */
inline struct llist_item * llist_sorted_remove(struct llist *list, char *sha1,
struct llist_item *hint)
return prev;
}
+/* computes A\B */
+void llist_sorted_difference_inplace(struct llist *A,
+ struct llist *B)
+{
+ struct llist_item *hint, *b;
+
+ hint = NULL;
+ b = B->front;
+
+ while (b) {
+ hint = llist_sorted_remove(A, b->sha1, hint);
+ b = b->next;
+ }
+}
+
inline struct pack_list * pack_list_insert(struct pack_list **pl,
struct pack_list *entry)
{
}
}
+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;
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)
/* 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;
}