]> git.ipfire.org Git - thirdparty/git.git/blame - reftable/pq.c
Merge branch 'jk/clone-allow-bare-and-o-together'
[thirdparty/git.git] / reftable / pq.c
CommitLineData
3b34f636
HWN
1/*
2Copyright 2020 Google LLC
3
4Use of this source code is governed by a BSD-style
5license that can be found in the LICENSE file or at
6https://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
15int 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
34struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq)
35{
36 return pq.heap[0];
37}
38
39int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq)
40{
41 return pq.len == 0;
42}
43
44struct 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 74void 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
98void 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}