src/include/lib/binaryheap.h

   1 /*
   2  * binaryheap.h
   3  *
   4  * A simple binary heap implementation
   5  *
   6  * Portions Copyright (c) 2012-2024, PostgreSQL Global Development Group
   7  *
   8  * src/include/lib/binaryheap.h
   9  */
  10
  11 #ifndef BINARYHEAP_H
  12 #define BINARYHEAP_H
  13
  14 /*
  15  * We provide a Datum-based API for backend code and a void *-based API for
  16  * frontend code (since the Datum definitions are not available to frontend
  17  * code).  You should typically avoid using bh_node_type directly and instead
  18  * use Datum or void * as appropriate.
  19  */
  20 #ifdef FRONTEND
  21 typedef void *bh_node_type;
  22 #else
  23 typedef Datum bh_node_type;
  24 #endif
  25
  26 /*
  27  * For a max-heap, the comparator must return <0 iff a < b, 0 iff a == b,
  28  * and >0 iff a > b.  For a min-heap, the conditions are reversed.
  29  */
  30 typedef int (*binaryheap_comparator) (bh_node_type a, bh_node_type b, void *arg);
  31
  32 /*
  33  * binaryheap
  34  *
  35  *              bh_size                 how many nodes are currently in "nodes"
  36  *              bh_space                how many nodes can be stored in "nodes"
  37  *              bh_has_heap_property    no unordered operations since last heap build
  38  *              bh_compare              comparison function to define the heap property
  39  *              bh_arg                  user data for comparison function
  40  *              bh_nodes                variable-length array of "space" nodes
  41  */
  42 typedef struct binaryheap
  43 {
  44         int                     bh_size;
  45         int                     bh_space;
  46         bool            bh_has_heap_property;   /* debugging cross-check */
  47         binaryheap_comparator bh_compare;
  48         void       *bh_arg;
  49         bh_node_type bh_nodes[FLEXIBLE_ARRAY_MEMBER];
  50 } binaryheap;
  51
  52 extern binaryheap *binaryheap_allocate(int capacity,
  53                                                                            binaryheap_comparator compare,
  54                                                                            void *arg);
  55 extern void binaryheap_reset(binaryheap *heap);
  56 extern void binaryheap_free(binaryheap *heap);
  57 extern void binaryheap_add_unordered(binaryheap *heap, bh_node_type d);
  58 extern void binaryheap_build(binaryheap *heap);
  59 extern void binaryheap_add(binaryheap *heap, bh_node_type d);
  60 extern bh_node_type binaryheap_first(binaryheap *heap);
  61 extern bh_node_type binaryheap_remove_first(binaryheap *heap);
  62 extern void binaryheap_remove_node(binaryheap *heap, int n);
  63 extern void binaryheap_replace_first(binaryheap *heap, bh_node_type d);
  64
  65 #define binaryheap_empty(h)                     ((h)->bh_size == 0)
  66 #define binaryheap_size(h)                      ((h)->bh_size)
  67 #define binaryheap_get_node(h, n)       ((h)->bh_nodes[n])
  68
  69 #endif                                                  /* BINARYHEAP_H */