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