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         struct strbuf ak = STRBUF_INIT;
  18         struct strbuf bk = STRBUF_INIT;
  19         int cmp = 0;
  20         reftable_record_key(&a->rec, &ak);
  21         reftable_record_key(&b->rec, &bk);
  22
  23         cmp = strbuf_cmp(&ak, &bk);
  24
  25         strbuf_release(&ak);
  26         strbuf_release(&bk);
  27
  28         if (cmp == 0)
  29                 return a->index > b->index;
  30
  31         return cmp < 0;
  32 }
  33
  34 struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq)
  35 {
  36         return pq.heap[0];
  37 }
  38
  39 int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq)
  40 {
  41         return pq.len == 0;
  42 }
  43
  44 struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
  45 {
  46         int i = 0;
  47         struct pq_entry e = pq->heap[0];
  48         pq->heap[0] = pq->heap[pq->len - 1];
  49         pq->len--;
  50
  51         i = 0;
  52         while (i < pq->len) {
  53                 int min = i;
  54                 int j = 2 * i + 1;
  55                 int k = 2 * i + 2;
  56                 if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i])) {
  57                         min = j;
  58                 }
  59                 if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min])) {
  60                         min = k;
  61                 }
  62
  63                 if (min == i) {
  64                         break;
  65                 }
  66
  67                 SWAP(pq->heap[i], pq->heap[min]);
  68                 i = min;
  69         }
  70
  71         return e;
  72 }
  73
  74 void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)
  75 {
  76         int i = 0;
  77
  78         if (pq->len == pq->cap) {
  79                 pq->cap = 2 * pq->cap + 1;
  80                 pq->heap = reftable_realloc(pq->heap,
  81                                             pq->cap * sizeof(struct pq_entry));
  82         }
  83
  84         pq->heap[pq->len++] = *e;
  85         i = pq->len - 1;
  86         while (i > 0) {
  87                 int j = (i - 1) / 2;
  88                 if (pq_less(&pq->heap[j], &pq->heap[i])) {
  89                         break;
  90                 }
  91
  92                 SWAP(pq->heap[j], pq->heap[i]);
  93
  94                 i = j;
  95         }
  96 }
  97
  98 void merged_iter_pqueue_release(struct merged_iter_pqueue *pq)
  99 {
 100         int i = 0;
 101         for (i = 0; i < pq->len; i++) {
 102                 reftable_record_release(&pq->heap[i].rec);
 103         }
 104         FREE_AND_NULL(pq->heap);
 105         pq->len = pq->cap = 0;
 106 }