pqueue.c 2.58 KB
Newer Older
1
/*
Edward Thomson committed
2
 * Copyright (C) the libgit2 contributors. All rights reserved.
3
 *
Vicent Marti committed
4 5
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * a Linking Exception. For full terms see the included COPYING file.
6 7 8
 */

#include "pqueue.h"
9
#include "util.h"
10

11 12 13
#define PQUEUE_LCHILD_OF(I) (((I)<<1)+1)
#define PQUEUE_RCHILD_OF(I) (((I)<<1)+2)
#define PQUEUE_PARENT_OF(I) (((I)-1)>>1)
14

15 16 17
int git_pqueue_init(
	git_pqueue *pq,
	uint32_t flags,
18
	size_t init_size,
19
	git_vector_cmp cmp)
20
{
21
	int error = git_vector_init(pq, init_size, cmp);
22

23 24 25 26 27 28 29 30 31 32
	if (!error) {
		/* mix in our flags */
		pq->flags |= flags;

		/* if fixed size heap, pretend vector is exactly init_size elements */
		if ((flags & GIT_PQUEUE_FIXED_SIZE) && init_size > 0)
			pq->_alloc_size = init_size;
	}

	return error;
33
}
34

35
static void pqueue_up(git_pqueue *pq, size_t el)
36
{
37
	size_t parent_el = PQUEUE_PARENT_OF(el);
38
	void *kid = git_vector_get(pq, el);
39

40 41 42 43 44 45 46
	while (el > 0) {
		void *parent = pq->contents[parent_el];

		if (pq->_cmp(parent, kid) <= 0)
			break;

		pq->contents[el] = parent;
47

48 49
		el = parent_el;
		parent_el = PQUEUE_PARENT_OF(el);
Vicent Marti committed
50
	}
51 52

	pq->contents[el] = kid;
53 54
}

55
static void pqueue_down(git_pqueue *pq, size_t el)
56
{
57
	void *parent = git_vector_get(pq, el), *kid, *rkid;
58

59
	while (1) {
60 61 62
		size_t kid_el = PQUEUE_LCHILD_OF(el);

		if ((kid = git_vector_get(pq, kid_el)) == NULL)
63
			break;
64

65 66 67 68 69 70
		if ((rkid = git_vector_get(pq, kid_el + 1)) != NULL &&
			pq->_cmp(kid, rkid) > 0) {
			kid    = rkid;
			kid_el += 1;
		}

71
		if (pq->_cmp(parent, kid) <= 0)
72
			break;
73

74 75
		pq->contents[el] = kid;
		el = kid_el;
Vicent Marti committed
76
	}
77 78

	pq->contents[el] = parent;
79 80
}

81
int git_pqueue_insert(git_pqueue *pq, void *item)
82
{
83 84 85 86
	int error = 0;

	/* if heap is full, pop the top element if new one should replace it */
	if ((pq->flags & GIT_PQUEUE_FIXED_SIZE) != 0 &&
87
		pq->length >= pq->_alloc_size)
88
	{
89 90 91
		/* skip this item if below min item in heap or if
		 * we do not have a comparison function */
		if (!pq->_cmp || pq->_cmp(item, git_vector_get(pq, 0)) <= 0)
92
			return 0;
93
		/* otherwise remove the min item before inserting new */
94
		(void)git_pqueue_pop(pq);
Vicent Marti committed
95
	}
96

97
	if (!(error = git_vector_insert(pq, item)) && pq->_cmp)
98
		pqueue_up(pq, pq->length - 1);
99

100
	return error;
101 102
}

103
void *git_pqueue_pop(git_pqueue *pq)
104
{
105
	void *rval;
106

107 108 109 110 111 112 113
	if (!pq->_cmp) {
		rval = git_vector_last(pq);
	} else {
		rval = git_pqueue_get(pq, 0);
	}

	if (git_pqueue_size(pq) > 1 && pq->_cmp) {
114 115 116
		/* move last item to top of heap, shrink, and push item down */
		pq->contents[0] = git_vector_last(pq);
		git_vector_pop(pq);
117 118
		pqueue_down(pq, 0);
	} else {
119 120
		/* all we need to do is shrink the heap in this case */
		git_vector_pop(pq);
121 122 123
	}

	return rval;
124
}