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