src/include/lib/binaryheap.h

   1 /*
   2  * binaryheap.h
   3  *
   4  * A simple binary heap implementation
   5  *
   6  * Portions Copyright (c) 2012-2021, PostgreSQL Global Development Group
   7  *
   8  * src/include/lib/binaryheap.h
   9  */
  10
  11 #ifndef BINARYHEAP_H
  12 #define BINARYHEAP_H
  13
  14 /*
  15  * For a max-heap, the comparator must return <0 iff a < b, 0 iff a == b,
  16  * and >0 iff a > b.  For a min-heap, the conditions are reversed.
  17  */
  18 typedef int (*binaryheap_comparator) (Datum a, Datum b, void *arg);
  19
  20 /*
  21  * binaryheap
  22  *
  23  *              bh_size                 how many nodes are currently in "nodes"
  24  *              bh_space                how many nodes can be stored in "nodes"
  25  *              bh_has_heap_property    no unordered operations since last heap build
  26  *              bh_compare              comparison function to define the heap property
  27  *              bh_arg                  user data for comparison function
  28  *              bh_nodes                variable-length array of "space" nodes
  29  */
  30 typedef struct binaryheap
  31 {
  32         int                     bh_size;
  33         int                     bh_space;
  34         bool            bh_has_heap_property;   /* debugging cross-check */
  35         binaryheap_comparator bh_compare;
  36         void       *bh_arg;
  37         Datum           bh_nodes[FLEXIBLE_ARRAY_MEMBER];
  38 } binaryheap;
  39
  40 extern binaryheap *binaryheap_allocate(int capacity,
  41                                                                            binaryheap_comparator compare,
  42                                                                            void *arg);
  43 extern void binaryheap_reset(binaryheap *heap);
  44 extern void binaryheap_free(binaryheap *heap);
  45 extern void binaryheap_add_unordered(binaryheap *heap, Datum d);
  46 extern void binaryheap_build(binaryheap *heap);
  47 extern void binaryheap_add(binaryheap *heap, Datum d);
  48 extern Datum binaryheap_first(binaryheap *heap);
  49 extern Datum binaryheap_remove_first(binaryheap *heap);
  50 extern void binaryheap_replace_first(binaryheap *heap, Datum d);
  51
  52 #define binaryheap_empty(h)                     ((h)->bh_size == 0)
  53
  54 #endif                                                  /* BINARYHEAP_H */