]>
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 | { | |
17 | struct strbuf ak = STRBUF_INIT; | |
18 | struct strbuf bk = STRBUF_INIT; | |
19 | int cmp = 0; | |
20 | reftable_record_key(&a->rec, &ak); | |
21 | reftable_record_key(&b->rec, &bk); | |
22 | ||
23 | cmp = strbuf_cmp(&ak, &bk); | |
24 | ||
25 | strbuf_release(&ak); | |
26 | strbuf_release(&bk); | |
27 | ||
28 | if (cmp == 0) | |
29 | return a->index > b->index; | |
30 | ||
31 | return cmp < 0; | |
32 | } | |
33 | ||
34 | struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq) | |
35 | { | |
36 | return pq.heap[0]; | |
37 | } | |
38 | ||
39 | int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq) | |
40 | { | |
41 | return pq.len == 0; | |
42 | } | |
43 | ||
44 | struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq) | |
45 | { | |
46 | int i = 0; | |
47 | struct pq_entry e = pq->heap[0]; | |
48 | pq->heap[0] = pq->heap[pq->len - 1]; | |
49 | pq->len--; | |
50 | ||
51 | i = 0; | |
52 | while (i < pq->len) { | |
53 | int min = i; | |
54 | int j = 2 * i + 1; | |
55 | int k = 2 * i + 2; | |
56 | if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i])) { | |
57 | min = j; | |
58 | } | |
59 | if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min])) { | |
60 | min = k; | |
61 | } | |
62 | ||
63 | if (min == i) { | |
64 | break; | |
65 | } | |
66 | ||
67 | SWAP(pq->heap[i], pq->heap[min]); | |
68 | i = min; | |
69 | } | |
70 | ||
71 | return e; | |
72 | } | |
73 | ||
c18eecbe | 74 | void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e) |
3b34f636 HWN |
75 | { |
76 | int i = 0; | |
66c0daba | 77 | |
3b34f636 HWN |
78 | if (pq->len == pq->cap) { |
79 | pq->cap = 2 * pq->cap + 1; | |
80 | pq->heap = reftable_realloc(pq->heap, | |
81 | pq->cap * sizeof(struct pq_entry)); | |
82 | } | |
83 | ||
c18eecbe | 84 | pq->heap[pq->len++] = *e; |
3b34f636 HWN |
85 | i = pq->len - 1; |
86 | while (i > 0) { | |
87 | int j = (i - 1) / 2; | |
88 | if (pq_less(&pq->heap[j], &pq->heap[i])) { | |
89 | break; | |
90 | } | |
91 | ||
92 | SWAP(pq->heap[j], pq->heap[i]); | |
93 | ||
94 | i = j; | |
95 | } | |
96 | } | |
97 | ||
98 | void merged_iter_pqueue_release(struct merged_iter_pqueue *pq) | |
99 | { | |
100 | int i = 0; | |
101 | for (i = 0; i < pq->len; i++) { | |
66c0daba | 102 | reftable_record_release(&pq->heap[i].rec); |
3b34f636 HWN |
103 | } |
104 | FREE_AND_NULL(pq->heap); | |
105 | pq->len = pq->cap = 0; | |
106 | } |