unpack-trees: batch fetching of missing blobs

diff --git a/prio-queue.c b/prio-queue.c
index 0f4fcf2755064e7299449f44d3687f2f6ca0d715..126d09672738533b6ecc6b94b7405dff888bbaf6 100644 (file)
--- a/prio-queue.c
+++ b/prio-queue.c
@@ -3,16 +3,16 @@
 
 static inline int compare(struct prio_queue *queue, int i, int j)
 {
-       int cmp = queue->compare(queue->array[i], queue->array[j],
+       int cmp = queue->compare(queue->array[i].data, queue->array[j].data,
                                 queue->cb_data);
+       if (!cmp)
+               cmp = queue->array[i].ctr - queue->array[j].ctr;
        return cmp;
 }
 
 static inline void swap(struct prio_queue *queue, int i, int j)
 {
-       void *tmp = queue->array[i];
-       queue->array[i] = queue->array[j];
-       queue->array[j] = tmp;
+       SWAP(queue->array[i], queue->array[j]);
 }
 
 void prio_queue_reverse(struct prio_queue *queue)
@@ -21,16 +21,16 @@ void prio_queue_reverse(struct prio_queue *queue)
 
        if (queue->compare != NULL)
                die("BUG: prio_queue_reverse() on non-LIFO queue");
-       for (i = 0; i <= (j = (queue->nr - 1) - i); i++)
+       for (i = 0; i < (j = (queue->nr - 1) - i); i++)
                swap(queue, i, j);
 }
 
 void clear_prio_queue(struct prio_queue *queue)
 {
-       free(queue->array);
+       FREE_AND_NULL(queue->array);
        queue->nr = 0;
        queue->alloc = 0;
-       queue->array = NULL;
+       queue->insertion_ctr = 0;
 }
 
 void prio_queue_put(struct prio_queue *queue, void *thing)
@@ -39,7 +39,9 @@ void prio_queue_put(struct prio_queue *queue, void *thing)
 
        /* Append at the end */
        ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);
-       queue->array[queue->nr++] = thing;
+       queue->array[queue->nr].ctr = queue->insertion_ctr++;
+       queue->array[queue->nr].data = thing;
+       queue->nr++;
        if (!queue->compare)
                return; /* LIFO */
 
@@ -61,9 +63,9 @@ void *prio_queue_get(struct prio_queue *queue)
        if (!queue->nr)
                return NULL;
        if (!queue->compare)
-               return queue->array[--queue->nr]; /* LIFO */
+               return queue->array[--queue->nr].data; /* LIFO */
 
-       result = queue->array[0];
+       result = queue->array[0].data;
        if (!--queue->nr)
                return result;