pqueue.c 2.43 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
		/* skip this item if below min item in heap */
		if (pq->_cmp(item, git_vector_get(pq, 0)) <= 0)
91
			return 0;
92
		/* otherwise remove the min item before inserting new */
93
		(void)git_pqueue_pop(pq);
Vicent Marti committed
94
	}
95

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

99
	return error;
100 101
}

102
void *git_pqueue_pop(git_pqueue *pq)
103
{
104
	void *rval = git_pqueue_get(pq, 0);
105

106 107 108 109
	if (git_pqueue_size(pq) > 1) {
		/* move last item to top of heap, shrink, and push item down */
		pq->contents[0] = git_vector_last(pq);
		git_vector_pop(pq);
110 111
		pqueue_down(pq, 0);
	} else {
112 113
		/* all we need to do is shrink the heap in this case */
		git_vector_pop(pq);
114 115 116
	}

	return rval;
117
}