File Coverage

deps/libgit2/src/pqueue.c
Criterion Covered Total %
statement 48 55 87.2
branch 20 32 62.5
condition n/a
subroutine n/a
pod n/a
total 68 87 78.1


line stmt bran cond sub pod time code
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 113           int git_pqueue_init(
17             git_pqueue *pq,
18             uint32_t flags,
19             size_t init_size,
20             git_vector_cmp cmp)
21             {
22 113           int error = git_vector_init(pq, init_size, cmp);
23              
24 113 50         if (!error) {
25             /* mix in our flags */
26 113           pq->flags |= flags;
27              
28             /* if fixed size heap, pretend vector is exactly init_size elements */
29 113 50         if ((flags & GIT_PQUEUE_FIXED_SIZE) && init_size > 0)
    0          
30 0           pq->_alloc_size = init_size;
31             }
32              
33 113           return error;
34             }
35              
36 236           static void pqueue_up(git_pqueue *pq, size_t el)
37             {
38 236           size_t parent_el = PQUEUE_PARENT_OF(el);
39 236           void *kid = git_vector_get(pq, el);
40              
41 247 100         while (el > 0) {
42 168           void *parent = pq->contents[parent_el];
43              
44 168 100         if (pq->_cmp(parent, kid) <= 0)
45 157           break;
46              
47 11           pq->contents[el] = parent;
48              
49 11           el = parent_el;
50 11           parent_el = PQUEUE_PARENT_OF(el);
51             }
52              
53 236           pq->contents[el] = kid;
54 236           }
55              
56 164           static void pqueue_down(git_pqueue *pq, size_t el)
57             {
58 164           void *parent = git_vector_get(pq, el), *kid, *rkid;
59              
60             while (1) {
61 167           size_t kid_el = PQUEUE_LCHILD_OF(el);
62              
63 167 100         if ((kid = git_vector_get(pq, kid_el)) == NULL)
64 130           break;
65              
66 39           if ((rkid = git_vector_get(pq, kid_el + 1)) != NULL &&
67 2           pq->_cmp(kid, rkid) > 0) {
68 0           kid = rkid;
69 0           kid_el += 1;
70             }
71              
72 37 100         if (pq->_cmp(parent, kid) <= 0)
73 34           break;
74              
75 3           pq->contents[el] = kid;
76 3           el = kid_el;
77 3           }
78              
79 164           pq->contents[el] = parent;
80 164           }
81              
82 255           int git_pqueue_insert(git_pqueue *pq, void *item)
83             {
84 255           int error = 0;
85              
86             /* if heap is full, pop the top element if new one should replace it */
87 255 50         if ((pq->flags & GIT_PQUEUE_FIXED_SIZE) != 0 &&
    0          
88 0           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 0 0         if (!pq->_cmp || pq->_cmp(item, git_vector_get(pq, 0)) <= 0)
    0          
93 0           return 0;
94             /* otherwise remove the min item before inserting new */
95 0           (void)git_pqueue_pop(pq);
96             }
97              
98 255 50         if (!(error = git_vector_insert(pq, item)) && pq->_cmp)
    100          
99 236           pqueue_up(pq, pq->length - 1);
100              
101 255           return error;
102             }
103              
104 259           void *git_pqueue_pop(git_pqueue *pq)
105             {
106             void *rval;
107              
108 259 100         if (!pq->_cmp) {
109 24           rval = git_vector_last(pq);
110             } else {
111 235           rval = git_pqueue_get(pq, 0);
112             }
113              
114 259 100         if (git_pqueue_size(pq) > 1 && pq->_cmp) {
    100          
115             /* move last item to top of heap, shrink, and push item down */
116 164           pq->contents[0] = git_vector_last(pq);
117 164           git_vector_pop(pq);
118 164           pqueue_down(pq, 0);
119             } else {
120             /* all we need to do is shrink the heap in this case */
121 95           git_vector_pop(pq);
122             }
123              
124 259           return rval;
125             }