]>
Commit | Line | Data |
---|---|---|
71db842f | 1 | /* |
5e0de328 | 2 | * Copyright (C) 2009-2012 the libgit2 contributors |
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 | ||
8 | #include "common.h" | |
9 | #include "pqueue.h" | |
10 | ||
87d9869f VM |
11 | #define left(i) ((i) << 1) |
12 | #define right(i) (((i) << 1) + 1) | |
71db842f VM |
13 | #define parent(i) ((i) >> 1) |
14 | ||
15 | int git_pqueue_init(git_pqueue *q, size_t n, git_pqueue_cmp cmppri) | |
16 | { | |
17 | assert(q); | |
18 | ||
87d9869f | 19 | /* Need to allocate n+1 elements since element 0 isn't used. */ |
3286c408 | 20 | if ((q->d = git__malloc((n + 1) * sizeof(void *))) == NULL) |
71db842f VM |
21 | return GIT_ENOMEM; |
22 | ||
87d9869f VM |
23 | q->size = 1; |
24 | q->avail = q->step = (n + 1); /* see comment above about n+1 */ | |
25 | q->cmppri = cmppri; | |
71db842f | 26 | |
87d9869f | 27 | return GIT_SUCCESS; |
71db842f VM |
28 | } |
29 | ||
30 | ||
31 | void git_pqueue_free(git_pqueue *q) | |
32 | { | |
3286c408 | 33 | git__free(q->d); |
71db842f VM |
34 | q->d = NULL; |
35 | } | |
36 | ||
36aaf1ff VM |
37 | void git_pqueue_clear(git_pqueue *q) |
38 | { | |
39 | q->size = 1; | |
40 | } | |
71db842f VM |
41 | |
42 | size_t git_pqueue_size(git_pqueue *q) | |
43 | { | |
87d9869f VM |
44 | /* queue element 0 exists but doesn't count since it isn't used. */ |
45 | return (q->size - 1); | |
71db842f VM |
46 | } |
47 | ||
48 | ||
49 | static void bubble_up(git_pqueue *q, size_t i) | |
50 | { | |
87d9869f VM |
51 | size_t parent_node; |
52 | void *moving_node = q->d[i]; | |
71db842f | 53 | |
87d9869f VM |
54 | for (parent_node = parent(i); |
55 | ((i > 1) && q->cmppri(q->d[parent_node], moving_node)); | |
56 | i = parent_node, parent_node = parent(i)) { | |
57 | q->d[i] = q->d[parent_node]; | |
58 | } | |
71db842f | 59 | |
87d9869f | 60 | q->d[i] = moving_node; |
71db842f VM |
61 | } |
62 | ||
63 | ||
64 | static size_t maxchild(git_pqueue *q, size_t i) | |
65 | { | |
87d9869f | 66 | size_t child_node = left(i); |
71db842f | 67 | |
87d9869f VM |
68 | if (child_node >= q->size) |
69 | return 0; | |
71db842f | 70 | |
87d9869f VM |
71 | if ((child_node + 1) < q->size && |
72 | q->cmppri(q->d[child_node], q->d[child_node + 1])) | |
73 | child_node++; /* use right child instead of left */ | |
71db842f | 74 | |
87d9869f | 75 | return child_node; |
71db842f VM |
76 | } |
77 | ||
78 | ||
79 | static void percolate_down(git_pqueue *q, size_t i) | |
80 | { | |
87d9869f VM |
81 | size_t child_node; |
82 | void *moving_node = q->d[i]; | |
71db842f | 83 | |
87d9869f VM |
84 | while ((child_node = maxchild(q, i)) != 0 && |
85 | q->cmppri(moving_node, q->d[child_node])) { | |
86 | q->d[i] = q->d[child_node]; | |
87 | i = child_node; | |
88 | } | |
71db842f | 89 | |
87d9869f | 90 | q->d[i] = moving_node; |
71db842f VM |
91 | } |
92 | ||
93 | ||
94 | int git_pqueue_insert(git_pqueue *q, void *d) | |
95 | { | |
87d9869f VM |
96 | void *tmp; |
97 | size_t i; | |
98 | size_t newsize; | |
71db842f | 99 | |
87d9869f | 100 | if (!q) return 1; |
71db842f | 101 | |
87d9869f VM |
102 | /* allocate more memory if necessary */ |
103 | if (q->size >= q->avail) { | |
104 | newsize = q->size + q->step; | |
3286c408 | 105 | if ((tmp = git__realloc(q->d, sizeof(void *) * newsize)) == NULL) |
87d9869f | 106 | return GIT_ENOMEM; |
71db842f | 107 | |
87d9869f VM |
108 | q->d = tmp; |
109 | q->avail = newsize; | |
110 | } | |
71db842f | 111 | |
87d9869f VM |
112 | /* insert item */ |
113 | i = q->size++; | |
114 | q->d[i] = d; | |
115 | bubble_up(q, i); | |
71db842f | 116 | |
87d9869f | 117 | return GIT_SUCCESS; |
71db842f VM |
118 | } |
119 | ||
120 | ||
121 | void *git_pqueue_pop(git_pqueue *q) | |
122 | { | |
87d9869f | 123 | void *head; |
71db842f | 124 | |
87d9869f VM |
125 | if (!q || q->size == 1) |
126 | return NULL; | |
71db842f | 127 | |
87d9869f VM |
128 | head = q->d[1]; |
129 | q->d[1] = q->d[--q->size]; | |
130 | percolate_down(q, 1); | |
71db842f | 131 | |
87d9869f | 132 | return head; |
71db842f VM |
133 | } |
134 | ||
135 | ||
136 | void *git_pqueue_peek(git_pqueue *q) | |
137 | { | |
87d9869f VM |
138 | if (!q || q->size == 1) |
139 | return NULL; | |
140 | return q->d[1]; | |
71db842f | 141 | } |