git

1
#include "git-compat-util.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
	SWAP(queue->array[i], queue->array[j]);
16
}
17

18
void prio_queue_reverse(struct prio_queue *queue)
19
{
20
	int i, j;
21

22
	if (queue->compare)
23
		BUG("prio_queue_reverse() on non-LIFO queue");
24
	for (i = 0; i < (j = (queue->nr - 1) - i); i++)
25
		swap(queue, i, j);
26
}
27

28
void clear_prio_queue(struct prio_queue *queue)
29
{
30
	FREE_AND_NULL(queue->array);
31
	queue->nr = 0;
32
	queue->alloc = 0;
33
	queue->insertion_ctr = 0;
34
}
35

36
void prio_queue_put(struct prio_queue *queue, void *thing)
37
{
38
	int ix, parent;
39

40
	/* Append at the end */
41
	ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);
42
	queue->array[queue->nr].ctr = queue->insertion_ctr++;
43
	queue->array[queue->nr].data = thing;
44
	queue->nr++;
45
	if (!queue->compare)
46
		return; /* LIFO */
47

48
	/* Bubble up the new one */
49
	for (ix = queue->nr - 1; ix; ix = parent) {
50
		parent = (ix - 1) / 2;
51
		if (compare(queue, parent, ix) <= 0)
52
			break;
53

54
		swap(queue, parent, ix);
55
	}
56
}
57

58
void *prio_queue_get(struct prio_queue *queue)
59
{
60
	void *result;
61
	int ix, child;
62

63
	if (!queue->nr)
64
		return NULL;
65
	if (!queue->compare)
66
		return queue->array[--queue->nr].data; /* LIFO */
67

68
	result = queue->array[0].data;
69
	if (!--queue->nr)
70
		return result;
71

72
	queue->array[0] = queue->array[queue->nr];
73

74
	/* Push down the one at the root */
75
	for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {
76
		child = ix * 2 + 1; /* left */
77
		if (child + 1 < queue->nr &&
78
		    compare(queue, child, child + 1) >= 0)
79
			child++; /* use right child */
80

81
		if (compare(queue, ix, child) <= 0)
82
			break;
83

84
		swap(queue, child, ix);
85
	}
86
	return result;
87
}
88

89
void *prio_queue_peek(struct prio_queue *queue)
90
{
91
	if (!queue->nr)
92
		return NULL;
93
	if (!queue->compare)
94
		return queue->array[queue->nr - 1].data;
95
	return queue->array[0].data;
96
}
97