]>
Commit | Line | Data |
---|---|---|
3b34f636 HWN |
1 | /* |
2 | Copyright 2020 Google LLC | |
3 | ||
4 | Use of this source code is governed by a BSD-style | |
5 | license that can be found in the LICENSE file or at | |
6 | https://developers.google.com/open-source/licenses/bsd | |
7 | */ | |
8 | ||
9 | #include "pq.h" | |
10 | ||
11 | #include "reftable-record.h" | |
12 | #include "system.h" | |
13 | #include "basics.h" | |
14 | ||
15 | int pq_less(struct pq_entry *a, struct pq_entry *b) | |
16 | { | |
dbe4e8b3 | 17 | int cmp = reftable_record_cmp(&a->rec, &b->rec); |
3b34f636 HWN |
18 | if (cmp == 0) |
19 | return a->index > b->index; | |
3b34f636 HWN |
20 | return cmp < 0; |
21 | } | |
22 | ||
23 | struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq) | |
24 | { | |
25 | return pq.heap[0]; | |
26 | } | |
27 | ||
28 | int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq) | |
29 | { | |
30 | return pq.len == 0; | |
31 | } | |
32 | ||
33 | struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq) | |
34 | { | |
35 | int i = 0; | |
36 | struct pq_entry e = pq->heap[0]; | |
37 | pq->heap[0] = pq->heap[pq->len - 1]; | |
38 | pq->len--; | |
39 | ||
40 | i = 0; | |
41 | while (i < pq->len) { | |
42 | int min = i; | |
43 | int j = 2 * i + 1; | |
44 | int k = 2 * i + 2; | |
45 | if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i])) { | |
46 | min = j; | |
47 | } | |
48 | if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min])) { | |
49 | min = k; | |
50 | } | |
51 | ||
52 | if (min == i) { | |
53 | break; | |
54 | } | |
55 | ||
56 | SWAP(pq->heap[i], pq->heap[min]); | |
57 | i = min; | |
58 | } | |
59 | ||
60 | return e; | |
61 | } | |
62 | ||
c18eecbe | 63 | void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e) |
3b34f636 HWN |
64 | { |
65 | int i = 0; | |
66c0daba | 66 | |
f6b58c1b | 67 | REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap); |
c18eecbe | 68 | pq->heap[pq->len++] = *e; |
f6b58c1b | 69 | |
3b34f636 HWN |
70 | i = pq->len - 1; |
71 | while (i > 0) { | |
72 | int j = (i - 1) / 2; | |
73 | if (pq_less(&pq->heap[j], &pq->heap[i])) { | |
74 | break; | |
75 | } | |
76 | ||
77 | SWAP(pq->heap[j], pq->heap[i]); | |
78 | ||
79 | i = j; | |
80 | } | |
81 | } | |
82 | ||
83 | void merged_iter_pqueue_release(struct merged_iter_pqueue *pq) | |
84 | { | |
85 | int i = 0; | |
86 | for (i = 0; i < pq->len; i++) { | |
66c0daba | 87 | reftable_record_release(&pq->heap[i].rec); |
3b34f636 HWN |
88 | } |
89 | FREE_AND_NULL(pq->heap); | |
90 | pq->len = pq->cap = 0; | |
91 | } |