config: add git_config_get_expiry() from gc.c
[git] / prio-queue.c
1 #include "cache.h"
2 #include "prio-queue.h"
3
4 static inline int compare(struct prio_queue *queue, int i, int j)
5 {
6         int cmp = queue->compare(queue->array[i].data, queue->array[j].data,
7                                  queue->cb_data);
8         if (!cmp)
9                 cmp = queue->array[i].ctr - queue->array[j].ctr;
10         return cmp;
11 }
12
13 static inline void swap(struct prio_queue *queue, int i, int j)
14 {
15         struct prio_queue_entry tmp = queue->array[i];
16         queue->array[i] = queue->array[j];
17         queue->array[j] = tmp;
18 }
19
20 void prio_queue_reverse(struct prio_queue *queue)
21 {
22         int i, j;
23
24         if (queue->compare != NULL)
25                 die("BUG: prio_queue_reverse() on non-LIFO queue");
26         for (i = 0; i <= (j = (queue->nr - 1) - i); i++)
27                 swap(queue, i, j);
28 }
29
30 void clear_prio_queue(struct prio_queue *queue)
31 {
32         free(queue->array);
33         queue->nr = 0;
34         queue->alloc = 0;
35         queue->array = NULL;
36         queue->insertion_ctr = 0;
37 }
38
39 void prio_queue_put(struct prio_queue *queue, void *thing)
40 {
41         int ix, parent;
42
43         /* Append at the end */
44         ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);
45         queue->array[queue->nr].ctr = queue->insertion_ctr++;
46         queue->array[queue->nr].data = thing;
47         queue->nr++;
48         if (!queue->compare)
49                 return; /* LIFO */
50
51         /* Bubble up the new one */
52         for (ix = queue->nr - 1; ix; ix = parent) {
53                 parent = (ix - 1) / 2;
54                 if (compare(queue, parent, ix) <= 0)
55                         break;
56
57                 swap(queue, parent, ix);
58         }
59 }
60
61 void *prio_queue_get(struct prio_queue *queue)
62 {
63         void *result;
64         int ix, child;
65
66         if (!queue->nr)
67                 return NULL;
68         if (!queue->compare)
69                 return queue->array[--queue->nr].data; /* LIFO */
70
71         result = queue->array[0].data;
72         if (!--queue->nr)
73                 return result;
74
75         queue->array[0] = queue->array[queue->nr];
76
77         /* Push down the one at the root */
78         for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {
79                 child = ix * 2 + 1; /* left */
80                 if (child + 1 < queue->nr &&
81                     compare(queue, child, child + 1) >= 0)
82                         child++; /* use right child */
83
84                 if (compare(queue, ix, child) <= 0)
85                         break;
86
87                 swap(queue, child, ix);
88         }
89         return result;
90 }