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