pqueue.c 2.59 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

10
#include "util.h"
11

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

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

24 25 26 27 28 29 30 31 32 33
	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;
34
}
35

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

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

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

		pq->contents[el] = parent;
48

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

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

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

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

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

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

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

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

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

82
int git_pqueue_insert(git_pqueue *pq, void *item)
83
{
84 85 86 87
	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 &&
88
		pq->length >= pq->_alloc_size)
89
	{
90 91 92
		/* 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)
93
			return 0;
94
		/* otherwise remove the min item before inserting new */
95
		(void)git_pqueue_pop(pq);
Vicent Marti committed
96
	}
97

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

101
	return error;
102 103
}

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

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

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

	return rval;
125
}