binaryheap.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	binaryheap

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)

Macro Definition Documentation

binaryheap_empty

#define binaryheap_empty

(

h

)

((h)->bh_size == 0)

Definition at line 65 of file binaryheap.h.

binaryheap_get_node

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

Definition at line 67 of file binaryheap.h.

binaryheap_size

#define binaryheap_size

(

h

)

((h)->bh_size)

Definition at line 66 of file binaryheap.h.

Typedef Documentation

bh_node_type

typedef Datum bh_node_type

Definition at line 23 of file binaryheap.h.

binaryheap

typedef struct binaryheap binaryheap

binaryheap_comparator

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

Definition at line 30 of file binaryheap.h.

Function Documentation

binaryheap_add()

void binaryheap_add	(	binaryheap *	heap,
		bh_node_type	d
	)

Definition at line 154 of file binaryheap.c.

{
    if (heap->bh_size >= heap->bh_space)
    {
#ifdef FRONTEND
        pg_fatal("out of binary heap slots");
#else
        elog(ERROR, "out of binary heap slots");
#endif
    }
    heap->bh_nodes[heap->bh_size] = d;
    heap->bh_size++;
    sift_up(heap, heap->bh_size - 1);
}

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(), test_basic(), test_duplicates(), test_remove_node(), test_replace_first(), test_reset(), and TopoSort().

binaryheap_add_unordered()

void binaryheap_add_unordered	(	binaryheap *	heap,
		bh_node_type	d
	)

Definition at line 116 of file binaryheap.c.

{
    if (heap->bh_size >= heap->bh_space)
    {
#ifdef FRONTEND
        pg_fatal("out of binary heap slots");
#else
        elog(ERROR, "out of binary heap slots");
#endif
    }
    heap->bh_has_heap_property = false;
    heap->bh_nodes[heap->bh_size] = d;
    heap->bh_size++;
}

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(), test_build(), and TopoSort().

binaryheap_allocate()

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

Definition at line 39 of file binaryheap.c.

{
    int         sz;
    binaryheap *heap;
 
    sz = offsetof(binaryheap, bh_nodes) + sizeof(bh_node_type) * capacity;
    heap = (binaryheap *) palloc(sz);
    heap->bh_space = capacity;
    heap->bh_compare = compare;
    heap->bh_arg = arg;
 
    heap->bh_size = 0;
    heap->bh_has_heap_property = true;
 
    return heap;
}

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(), test_basic(), test_build(), test_duplicates(), test_remove_node(), test_replace_first(), test_reset(), and TopoSort().

binaryheap_build()

void binaryheap_build

(

binaryheap *

heap

)

Definition at line 138 of file binaryheap.c.

{
    int         i;
 
    for (i = parent_offset(heap->bh_size - 1); i >= 0; i--)
        sift_down(heap, i);
    heap->bh_has_heap_property = true;
}

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(), test_build(), and TopoSort().

binaryheap_first()

bh_node_type binaryheap_first

(

binaryheap *

heap

)

Definition at line 177 of file binaryheap.c.

{
    Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
    return heap->bh_nodes[0];
}

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

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

binaryheap_free()

void binaryheap_free

(

binaryheap *

heap

)

Definition at line 75 of file binaryheap.c.

{
    pfree(heap);
}

References pfree().

Referenced by BufferSync(), ReorderBufferIterTXNFinish(), restore_toc_entries_parallel(), and TopoSort().

binaryheap_remove_first()

bh_node_type binaryheap_remove_first

(

binaryheap *

heap

)

Definition at line 192 of file binaryheap.c.

{
    bh_node_type result;
 
    Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
 
    /* extract the root node, which will be the result */
    result = heap->bh_nodes[0];
 
    /* easy if heap contains one element */
    if (heap->bh_size == 1)
    {
        heap->bh_size--;
        return result;
    }
 
    /*
     * Remove the last node, placing it in the vacated root entry, and sift
     * the new root node down to its correct position.
     */
    heap->bh_nodes[0] = heap->bh_nodes[--heap->bh_size];
    sift_down(heap, 0);
 
    return result;
}

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(), test_basic(), test_duplicates(), and TopoSort().

binaryheap_remove_node()

void binaryheap_remove_node	(	binaryheap *	heap,
		int	n
	)

Definition at line 225 of file binaryheap.c.

{
    int         cmp;
 
    Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
    Assert(n >= 0 && n < heap->bh_size);
 
    /* compare last node to the one that is being removed */
    cmp = heap->bh_compare(heap->bh_nodes[--heap->bh_size],
                           heap->bh_nodes[n],
                           heap->bh_arg);
 
    /* remove the last node, placing it in the vacated entry */
    heap->bh_nodes[n] = heap->bh_nodes[heap->bh_size];
 
    /* sift as needed to preserve the heap property */
    if (cmp > 0)
        sift_up(heap, n);
    else if (cmp < 0)
        sift_down(heap, n);
}

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(), and test_remove_node().

binaryheap_replace_first()

void binaryheap_replace_first	(	binaryheap *	heap,
		bh_node_type	d
	)

Definition at line 255 of file binaryheap.c.

{
    Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
 
    heap->bh_nodes[0] = d;
 
    if (heap->bh_size > 1)
        sift_down(heap, 0);
}

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(), ReorderBufferIterTXNNext(), and test_replace_first().

binaryheap_reset()

void binaryheap_reset

(

binaryheap *

heap

)

Definition at line 63 of file binaryheap.c.

{
    heap->bh_size = 0;
    heap->bh_has_heap_property = true;
}

References binaryheap::bh_has_heap_property, and binaryheap::bh_size.

Referenced by ExecReScanMergeAppend(), gather_merge_init(), pgarch_readyXlog(), and test_reset().