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_top(struct merged_iter_pqueue pq)
  24 {
  25         return pq.heap[0];
  26 }
  27
  28 int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq)
  29 {
  30         return pq.len == 0;
  31 }
  32
  33 struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
  34 {
  35         int i = 0;
  36         struct pq_entry e = pq->heap[0];
  37         pq->heap[0] = pq->heap[pq->len - 1];
  38         pq->len--;
  39
  40         i = 0;
  41         while (i < pq->len) {
  42                 int min = i;
  43                 int j = 2 * i + 1;
  44                 int k = 2 * i + 2;
  45                 if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i])) {
  46                         min = j;
  47                 }
  48                 if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min])) {
  49                         min = k;
  50                 }
  51
  52                 if (min == i) {
  53                         break;
  54                 }
  55
  56                 SWAP(pq->heap[i], pq->heap[min]);
  57                 i = min;
  58         }
  59
  60         return e;
  61 }
  62
  63 void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)
  64 {
  65         int i = 0;
  66
  67         REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap);
  68         pq->heap[pq->len++] = *e;
  69
  70         i = pq->len - 1;
  71         while (i > 0) {
  72                 int j = (i - 1) / 2;
  73                 if (pq_less(&pq->heap[j], &pq->heap[i])) {
  74                         break;
  75                 }
  76
  77                 SWAP(pq->heap[j], pq->heap[i]);
  78
  79                 i = j;
  80         }
  81 }
  82
  83 void merged_iter_pqueue_release(struct merged_iter_pqueue *pq)
  84 {
  85         int i = 0;
  86         for (i = 0; i < pq->len; i++) {
  87                 reftable_record_release(&pq->heap[i].rec);
  88         }
  89         FREE_AND_NULL(pq->heap);
  90         pq->len = pq->cap = 0;
  91 }