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