Line Flow Count Block(s) Source
1 - /*
2 - * Copyright (C) the libgit2 contributors. All rights reserved.
3 - *
4 - * This file is part of libgit2, distributed under the GNU GPL v2 with
5 - * a Linking Exception. For full terms see the included COPYING file.
6 - */
7 -
8 - #include "pqueue.h"
9 -
10 - #include "util.h"
11 -
12 - #define PQUEUE_LCHILD_OF(I) (((I)<<1)+1)
13 - #define PQUEUE_RCHILD_OF(I) (((I)<<1)+2)
14 - #define PQUEUE_PARENT_OF(I) (((I)-1)>>1)
15 -
16 876 2 int git_pqueue_init(
17 - git_pqueue *pq,
18 - uint32_t flags,
19 - size_t init_size,
20 - git_vector_cmp cmp)
21 - {
22 876 2 int error = git_vector_init(pq, init_size, cmp);
23 -
24 876 3 if (!error) {
25 - /* mix in our flags */
26 876 4 pq->flags |= flags;
27 -
28 - /* if fixed size heap, pretend vector is exactly init_size elements */
29 876 4,5 if ((flags & GIT_PQUEUE_FIXED_SIZE) && init_size > 0)
30 2 6 pq->_alloc_size = init_size;
31 - }
32 -
33 876 7 return error;
34 - }
35 -
36 4242 2 static void pqueue_up(git_pqueue *pq, size_t el)
37 - {
38 4242 2 size_t parent_el = PQUEUE_PARENT_OF(el);
39 4242 2 void *kid = git_vector_get(pq, el);
40 -
41 6644 3,8 while (el > 0) {
42 4821 4 void *parent = pq->contents[parent_el];
43 -
44 4821 4,5 if (pq->_cmp(parent, kid) <= 0)
45 2419 6 break;
46 -
47 2402 7 pq->contents[el] = parent;
48 -
49 2402 7 el = parent_el;
50 2402 7 parent_el = PQUEUE_PARENT_OF(el);
51 - }
52 -
53 4242 9 pq->contents[el] = kid;
54 4242 9 }
55 -
56 3608 2 static void pqueue_down(git_pqueue *pq, size_t el)
57 - {
58 3608 2 void *parent = git_vector_get(pq, el), *kid, *rkid;
59 -
60 - while (1) {
61 6668 3 size_t kid_el = PQUEUE_LCHILD_OF(el);
62 -
63 6668 3,4 if ((kid = git_vector_get(pq, kid_el)) == NULL)
64 2762 5 break;
65 -
66 3906 6,7,9 if ((rkid = git_vector_get(pq, kid_el + 1)) != NULL &&
67 2964 8 pq->_cmp(kid, rkid) > 0) {
68 1249 10 kid = rkid;
69 1249 10 kid_el += 1;
70 - }
71 -
72 3906 11,12 if (pq->_cmp(parent, kid) <= 0)
73 846 13 break;
74 -
75 3060 14 pq->contents[el] = kid;
76 3060 14 el = kid_el;
77 3060 14 }
78 -
79 3608 15 pq->contents[el] = parent;
80 3608 15 }
81 -
82 4383 2 int git_pqueue_insert(git_pqueue *pq, void *item)
83 - {
84 4383 2 int error = 0;
85 -
86 - /* if heap is full, pop the top element if new one should replace it */
87 4383 2,3 if ((pq->flags & GIT_PQUEUE_FIXED_SIZE) != 0 &&
88 200 3 pq->length >= pq->_alloc_size)
89 - {
90 - /* skip this item if below min item in heap or if
91 - * we do not have a comparison function */
92 100 4-7 if (!pq->_cmp || pq->_cmp(item, git_vector_get(pq, 0)) <= 0)
93 67 8 return 0;
94 - /* otherwise remove the min item before inserting new */
95 33 9 (void)git_pqueue_pop(pq);
96 - }
97 -
98 4316 10-12 if (!(error = git_vector_insert(pq, item)) && pq->_cmp)
99 4242 13 pqueue_up(pq, pq->length - 1);
100 -
101 4316 14 return error;
102 - }
103 -
104 4191 2 void *git_pqueue_pop(git_pqueue *pq)
105 - {
106 - void *rval;
107 -
108 4191 2 if (!pq->_cmp) {
109 80 3 rval = git_vector_last(pq);
110 - } else {
111 4111 4 rval = git_pqueue_get(pq, 0);
112 - }
113 -
114 4191 5-7 if (git_pqueue_size(pq) > 1 && pq->_cmp) {
115 - /* move last item to top of heap, shrink, and push item down */
116 3608 8 pq->contents[0] = git_vector_last(pq);
117 3608 9 git_vector_pop(pq);
118 3608 10 pqueue_down(pq, 0);
119 - } else {
120 - /* all we need to do is shrink the heap in this case */
121 583 11 git_vector_pop(pq);
122 - }
123 -
124 4191 12 return rval;
125 - }