Header And Logo

PostgreSQL
| The world's most advanced open source database.

binaryheap.h

Go to the documentation of this file.
00001 /*
00002  * binaryheap.h
00003  *
00004  * A simple binary heap implementation
00005  *
00006  * Portions Copyright (c) 2012-2013, PostgreSQL Global Development Group
00007  *
00008  * src/include/lib/binaryheap.h
00009  */
00010 
00011 #ifndef BINARYHEAP_H
00012 #define BINARYHEAP_H
00013 
00014 /*
00015  * For a max-heap, the comparator must return <0 iff a < b, 0 iff a == b,
00016  * and >0 iff a > b.  For a min-heap, the conditions are reversed.
00017  */
00018 typedef int (*binaryheap_comparator) (Datum a, Datum b, void *arg);
00019 
00020 /*
00021  * binaryheap
00022  *
00023  *      bh_size         how many nodes are currently in "nodes"
00024  *      bh_space        how many nodes can be stored in "nodes"
00025  *      bh_has_heap_property    no unordered operations since last heap build
00026  *      bh_compare      comparison function to define the heap property
00027  *      bh_arg          user data for comparison function
00028  *      bh_nodes        variable-length array of "space" nodes
00029  */
00030 typedef struct binaryheap
00031 {
00032     int         bh_size;
00033     int         bh_space;
00034     bool        bh_has_heap_property;   /* debugging cross-check */
00035     binaryheap_comparator bh_compare;
00036     void       *bh_arg;
00037     Datum       bh_nodes[FLEXIBLE_ARRAY_MEMBER];
00038 }   binaryheap;
00039 
00040 extern binaryheap *binaryheap_allocate(int capacity,
00041                                 binaryheap_comparator compare,
00042                                 void *arg);
00043 extern void binaryheap_free(binaryheap *heap);
00044 extern void binaryheap_add_unordered(binaryheap *heap, Datum d);
00045 extern void binaryheap_build(binaryheap *heap);
00046 extern void binaryheap_add(binaryheap *heap, Datum d);
00047 extern Datum binaryheap_first(binaryheap *heap);
00048 extern Datum binaryheap_remove_first(binaryheap *heap);
00049 extern void binaryheap_replace_first(binaryheap *heap, Datum d);
00050 
00051 #define binaryheap_empty(h)         ((h)->bh_size == 0)
00052 
00053 #endif   /* BINARYHEAP_H */