reftable/pq.c

   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         int cmp = reftable_record_cmp(a->rec, b->rec);
  18         if (cmp == 0)
  19                 return a->index > b->index;
  20         return cmp < 0;
  21 }
  22
  23 struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
  24 {
  25         int i = 0;
  26         struct pq_entry e = pq->heap[0];
  27         pq->heap[0] = pq->heap[pq->len - 1];
  28         pq->len--;
  29
  30         i = 0;
  31         while (i < pq->len) {
  32                 int min = i;
  33                 int j = 2 * i + 1;
  34                 int k = 2 * i + 2;
  35                 if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i])) {
  36                         min = j;
  37                 }
  38                 if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min])) {
  39                         min = k;
  40                 }
  41
  42                 if (min == i) {
  43                         break;
  44                 }
  45
  46                 SWAP(pq->heap[i], pq->heap[min]);
  47                 i = min;
  48         }
  49
  50         return e;
  51 }
  52
  53 void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)
  54 {
  55         int i = 0;
  56
  57         REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap);
  58         pq->heap[pq->len++] = *e;
  59
  60         i = pq->len - 1;
  61         while (i > 0) {
  62                 int j = (i - 1) / 2;
  63                 if (pq_less(&pq->heap[j], &pq->heap[i])) {
  64                         break;
  65                 }
  66
  67                 SWAP(pq->heap[j], pq->heap[i]);
  68
  69                 i = j;
  70         }
  71 }
  72
  73 void merged_iter_pqueue_release(struct merged_iter_pqueue *pq)
  74 {
  75         FREE_AND_NULL(pq->heap);
  76         memset(pq, 0, sizeof(*pq));
  77 }