| 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-error.h" |
| 12 | #include "reftable-record.h" |
| 13 | #include "system.h" |
| 14 | #include "basics.h" |
| 15 | |
| 16 | int pq_less(struct pq_entry *a, struct pq_entry *b) |
| 17 | { |
| 18 | int cmp, err; |
| 19 | |
| 20 | err = reftable_record_cmp(a->rec, b->rec, &cmp); |
| 21 | if (err < 0) |
| 22 | return err; |
| 23 | |
| 24 | if (cmp == 0) |
| 25 | return a->index > b->index; |
| 26 | return cmp < 0; |
| 27 | } |
| 28 | |
| 29 | int merged_iter_pqueue_remove(struct merged_iter_pqueue *pq, struct pq_entry *out) |
| 30 | { |
| 31 | size_t i = 0; |
| 32 | struct pq_entry e = pq->heap[0]; |
| 33 | pq->heap[0] = pq->heap[pq->len - 1]; |
| 34 | pq->len--; |
| 35 | |
| 36 | while (i < pq->len) { |
| 37 | size_t min = i; |
| 38 | size_t j = 2 * i + 1; |
| 39 | size_t k = 2 * i + 2; |
| 40 | int cmp; |
| 41 | |
| 42 | if (j < pq->len) { |
| 43 | cmp = pq_less(&pq->heap[j], &pq->heap[i]); |
| 44 | if (cmp < 0) |
| 45 | return -1; |
| 46 | else if (cmp) |
| 47 | min = j; |
| 48 | } |
| 49 | |
| 50 | if (k < pq->len) { |
| 51 | cmp = pq_less(&pq->heap[k], &pq->heap[min]); |
| 52 | if (cmp < 0) |
| 53 | return -1; |
| 54 | else if (cmp) |
| 55 | min = k; |
| 56 | } |
| 57 | |
| 58 | if (min == i) |
| 59 | break; |
| 60 | REFTABLE_SWAP(pq->heap[i], pq->heap[min]); |
| 61 | i = min; |
| 62 | } |
| 63 | |
| 64 | if (out) |
| 65 | *out = e; |
| 66 | |
| 67 | return 0; |
| 68 | } |
| 69 | |
| 70 | int merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e) |
| 71 | { |
| 72 | size_t i = 0; |
| 73 | |
| 74 | REFTABLE_ALLOC_GROW_OR_NULL(pq->heap, pq->len + 1, pq->cap); |
| 75 | if (!pq->heap) |
| 76 | return REFTABLE_OUT_OF_MEMORY_ERROR; |
| 77 | pq->heap[pq->len++] = *e; |
| 78 | |
| 79 | i = pq->len - 1; |
| 80 | while (i > 0) { |
| 81 | size_t j = (i - 1) / 2; |
| 82 | if (pq_less(&pq->heap[j], &pq->heap[i])) |
| 83 | break; |
| 84 | REFTABLE_SWAP(pq->heap[j], pq->heap[i]); |
| 85 | i = j; |
| 86 | } |
| 87 | |
| 88 | return 0; |
| 89 | } |
| 90 | |
| 91 | void merged_iter_pqueue_release(struct merged_iter_pqueue *pq) |
| 92 | { |
| 93 | REFTABLE_FREE_AND_NULL(pq->heap); |
| 94 | memset(pq, 0, sizeof(*pq)); |
| 95 | } |