binaryheap.h File Reference (original) (raw)

Go to the source code of this file.

Macros
#define	binaryheap_empty(h) ((h)->bh_size == 0)

#define	binaryheap_size(h) ((h)->bh_size)

#define	binaryheap_get_node(h, n) ((h)->bh_nodes[n])

Typedefs
typedef Datum	bh_node_type

typedef int(*	binaryheap_comparator) (bh_node_type a, bh_node_type b, void *arg)

typedef struct binaryheap	binaryheap

Functions
binaryheap *	binaryheap_allocate (int capacity, binaryheap_comparator compare, void *arg)

void	binaryheap_reset (binaryheap *heap)

void	binaryheap_free (binaryheap *heap)

void	binaryheap_add_unordered (binaryheap *heap, bh_node_type d)

void	binaryheap_build (binaryheap *heap)

void	binaryheap_add (binaryheap *heap, bh_node_type d)

bh_node_type	binaryheap_first (binaryheap *heap)

bh_node_type	binaryheap_remove_first (binaryheap *heap)

void	binaryheap_remove_node (binaryheap *heap, int n)

void	binaryheap_replace_first (binaryheap *heap, bh_node_type d)

◆ binaryheap_empty

| #define binaryheap_empty | ( | | h | ) | ((h)->bh_size == 0) | | ------------------------- | - | | - | - | -------------------- |

◆ binaryheap_get_node

| #define binaryheap_get_node | ( | | h, | | ----------------------------- | --------------------- | | -- | | | n | | | | | ) | ((h)->bh_nodes[n]) | | |

◆ binaryheap_size

| #define binaryheap_size | ( | | h | ) | ((h)->bh_size) | | ------------------------ | - | | - | - | --------------- |

◆ bh_node_type

◆ binaryheap_comparator

◆ binaryheap_add()

Definition at line 154 of file binaryheap.c.

155{

157 {

158#ifdef FRONTEND

159 pg_fatal("out of binary heap slots");

160#else

161 elog(ERROR, "out of binary heap slots");

162#endif

163 }

167}

static void sift_up(binaryheap *heap, int node_off)

bh_node_type bh_nodes[FLEXIBLE_ARRAY_MEMBER]

References binaryheap::bh_nodes, binaryheap::bh_size, binaryheap::bh_space, elog, ERROR, pg_fatal, and sift_up().

Referenced by move_to_ready_heap(), pgarch_readyXlog(), reduce_dependencies(), and TopoSort().

◆ binaryheap_add_unordered()

Definition at line 116 of file binaryheap.c.

117{

119 {

120#ifdef FRONTEND

121 pg_fatal("out of binary heap slots");

122#else

123 elog(ERROR, "out of binary heap slots");

124#endif

125 }

129}

bool bh_has_heap_property

References binaryheap::bh_has_heap_property, binaryheap::bh_nodes, binaryheap::bh_size, binaryheap::bh_space, elog, ERROR, and pg_fatal.

Referenced by BufferSync(), ExecMergeAppend(), gather_merge_init(), pgarch_readyXlog(), ReorderBufferIterTXNInit(), and TopoSort().

◆ binaryheap_allocate()

Definition at line 39 of file binaryheap.c.

40{

41 int sz;

53 return heap;

54}

static int compare(const void *arg1, const void *arg2)

binaryheap_comparator bh_compare

References arg, binaryheap::bh_arg, binaryheap::bh_compare, binaryheap::bh_has_heap_property, binaryheap::bh_size, binaryheap::bh_space, compare(), and palloc().

Referenced by BufferSync(), ExecInitMergeAppend(), gather_merge_setup(), PgArchiverMain(), ReorderBufferIterTXNInit(), restore_toc_entries_parallel(), and TopoSort().

◆ binaryheap_build()

Definition at line 138 of file binaryheap.c.

139{

140 int i;

141

145}

static void sift_down(binaryheap *heap, int node_off)

static int parent_offset(int i)

References binaryheap::bh_has_heap_property, binaryheap::bh_size, i, parent_offset(), and sift_down().

Referenced by BufferSync(), ExecMergeAppend(), gather_merge_init(), pgarch_readyXlog(), ReorderBufferIterTXNInit(), and TopoSort().

◆ binaryheap_first()

◆ binaryheap_free()

◆ binaryheap_remove_first()

Definition at line 192 of file binaryheap.c.

193{

195

197

198

200

201

203 {

205 return result;

206 }

207

208

209

210

211

214

215 return result;

216}

References Assert(), binaryheap::bh_has_heap_property, binaryheap::bh_nodes, binaryheap::bh_size, binaryheap_empty, and sift_down().

Referenced by BufferSync(), ExecMergeAppend(), gather_merge_getnext(), pgarch_readyXlog(), ReorderBufferIterTXNNext(), and TopoSort().

◆ binaryheap_remove_node()

void binaryheap_remove_node	(	binaryheap *	heap,
int	n
)

Definition at line 225 of file binaryheap.c.

226{

228

230 Assert(n >= 0 && n < heap->bh_size);

231

232

236

237

239

240

241 if (cmp > 0)

243 else if (cmp < 0)

245}

static int cmp(const chr *x, const chr *y, size_t len)

References Assert(), binaryheap::bh_arg, binaryheap::bh_compare, binaryheap::bh_has_heap_property, binaryheap::bh_nodes, binaryheap::bh_size, binaryheap_empty, cmp(), sift_down(), and sift_up().

Referenced by pop_next_work_item().