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         size_t i = 0;
  26         struct pq_entry e = pq->heap[0];
  27         pq->heap[0] = pq->heap[pq->len - 1];
  28         pq->len--;
  29
  30         while (i < pq->len) {
  31                 size_t min = i;
  32                 size_t j = 2 * i + 1;
  33                 size_t k = 2 * i + 2;
  34                 if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i]))
  35                         min = j;
  36                 if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min]))
  37                         min = k;
  38                 if (min == i)
  39                         break;
  40                 SWAP(pq->heap[i], pq->heap[min]);
  41                 i = min;
  42         }
  43
  44         return e;
  45 }
  46
  47 void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)
  48 {
  49         size_t i = 0;
  50
  51         REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap);
  52         pq->heap[pq->len++] = *e;
  53
  54         i = pq->len - 1;
  55         while (i > 0) {
  56                 size_t j = (i - 1) / 2;
  57                 if (pq_less(&pq->heap[j], &pq->heap[i]))
  58                         break;
  59                 SWAP(pq->heap[j], pq->heap[i]);
  60                 i = j;
  61         }
  62 }
  63
  64 void merged_iter_pqueue_release(struct merged_iter_pqueue *pq)
  65 {
  66         FREE_AND_NULL(pq->heap);
  67         memset(pq, 0, sizeof(*pq));
  68 }