binaryheap.c File Reference

#include "postgres.h"
#include <math.h>
#include "lib/binaryheap.h"

Include dependency graph for binaryheap.c:

Go to the source code of this file.

Functions
static void	sift_down (binaryheap *heap, int node_off)
static void	sift_up (binaryheap *heap, int node_off)
static void	swap_nodes (binaryheap *heap, int a, int b)
binaryheap *	binaryheap_allocate (int capacity, binaryheap_comparator compare, void *arg)
void	binaryheap_reset (binaryheap *heap)
void	binaryheap_free (binaryheap *heap)
static int	left_offset (int i)
static int	right_offset (int i)
static int	parent_offset (int i)
void	binaryheap_add_unordered (binaryheap *heap, Datum d)
void	binaryheap_build (binaryheap *heap)
void	binaryheap_add (binaryheap *heap, Datum d)
Datum	binaryheap_first (binaryheap *heap)
Datum	binaryheap_remove_first (binaryheap *heap)
void	binaryheap_replace_first (binaryheap *heap, Datum d)

Function Documentation

void binaryheap_add	(	binaryheap *	heap,
		Datum	d
	)

Definition at line 142 of file binaryheap.c.

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

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

void binaryheap_add_unordered	(	binaryheap *	heap,
		Datum	d
	)

Definition at line 110 of file binaryheap.c.

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

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

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

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

Definition at line 33 of file binaryheap.c.

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

Referenced by BufferSync(), ExecInitMergeAppend(), gather_merge_init(), and ReorderBufferIterTXNInit().

{
    int         sz;
    binaryheap *heap;

    sz = offsetof(binaryheap, bh_nodes) + sizeof(Datum) * 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;
}

void binaryheap_build

(

binaryheap *

heap

)

Definition at line 126 of file binaryheap.c.

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

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

{
    int         i;

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

Datum binaryheap_first

(

binaryheap *

heap

)

Definition at line 159 of file binaryheap.c.

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

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

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

void binaryheap_free

(

binaryheap *

heap

)

Definition at line 69 of file binaryheap.c.

References pfree().

Referenced by BufferSync(), gather_merge_clear_slots(), and ReorderBufferIterTXNFinish().

{
    pfree(heap);
}

Datum binaryheap_remove_first

(

binaryheap *

heap

)

Definition at line 174 of file binaryheap.c.

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

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

{
    Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);

    if (heap->bh_size == 1)
    {
        heap->bh_size--;
        return heap->bh_nodes[0];
    }

    /*
     * Swap the root and last nodes, decrease the size of the heap (i.e.
     * remove the former root node) and sift the new root node down to its
     * correct position.
     */
    swap_nodes(heap, 0, heap->bh_size - 1);
    heap->bh_size--;
    sift_down(heap, 0);

    return heap->bh_nodes[heap->bh_size];
}

void binaryheap_replace_first	(	binaryheap *	heap,
		Datum	d
	)

Definition at line 204 of file binaryheap.c.

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

{
    Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);

    heap->bh_nodes[0] = d;

    if (heap->bh_size > 1)
        sift_down(heap, 0);
}

void binaryheap_reset

(

binaryheap *

heap

)

Definition at line 57 of file binaryheap.c.

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

Referenced by ExecReScanMergeAppend().

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

static int left_offset ( int  i )

inlinestatic

Definition at line 84 of file binaryheap.c.

Referenced by sift_down().

{
    return 2 * i + 1;
}

static int parent_offset ( int  i )

inlinestatic

Definition at line 96 of file binaryheap.c.

Referenced by binaryheap_build(), and sift_up().

{
    return (i - 1) / 2;
}

static int right_offset ( int  i )

inlinestatic

Definition at line 90 of file binaryheap.c.

Referenced by sift_down().

{
    return 2 * i + 2;
}

static void sift_down ( binaryheap *  heap, int  node_off  )

static

Definition at line 264 of file binaryheap.c.

References binaryheap::bh_arg, binaryheap::bh_compare, binaryheap::bh_nodes, left_offset(), right_offset(), and swap_nodes().

Referenced by binaryheap_build(), binaryheap_remove_first(), and binaryheap_replace_first().

{
    while (true)
    {
        int         left_off = left_offset(node_off);
        int         right_off = right_offset(node_off);
        int         swap_off = 0;

        /* Is the left child larger than the parent? */
        if (left_off < heap->bh_size &&
            heap->bh_compare(heap->bh_nodes[node_off],
                             heap->bh_nodes[left_off],
                             heap->bh_arg) < 0)
            swap_off = left_off;

        /* Is the right child larger than the parent? */
        if (right_off < heap->bh_size &&
            heap->bh_compare(heap->bh_nodes[node_off],
                             heap->bh_nodes[right_off],
                             heap->bh_arg) < 0)
        {
            /* swap with the larger child */
            if (!swap_off ||
                heap->bh_compare(heap->bh_nodes[left_off],
                                 heap->bh_nodes[right_off],
                                 heap->bh_arg) < 0)
                swap_off = right_off;
        }

        /*
         * If we didn't find anything to swap, the heap condition is
         * satisfied, and we're done.
         */
        if (!swap_off)
            break;

        /*
         * Otherwise, swap the node with the child that violates the heap
         * property; then go on to check its children.
         */
        swap_nodes(heap, swap_off, node_off);
        node_off = swap_off;
    }
}

static void sift_up ( binaryheap *  heap, int  node_off  )

static

Definition at line 232 of file binaryheap.c.

References binaryheap::bh_arg, binaryheap::bh_compare, binaryheap::bh_nodes, cmp(), parent_offset(), and swap_nodes().

Referenced by binaryheap_add().

{
    while (node_off != 0)
    {
        int         cmp;
        int         parent_off;

        /*
         * If this node is smaller than its parent, the heap condition is
         * satisfied, and we're done.
         */
        parent_off = parent_offset(node_off);
        cmp = heap->bh_compare(heap->bh_nodes[node_off],
                               heap->bh_nodes[parent_off],
                               heap->bh_arg);
        if (cmp <= 0)
            break;

        /*
         * Otherwise, swap the node and its parent and go on to check the
         * node's new parent.
         */
        swap_nodes(heap, node_off, parent_off);
        node_off = parent_off;
    }
}

static void swap_nodes ( binaryheap *  heap, int  a, int  b  )

inlinestatic

Definition at line 218 of file binaryheap.c.

References binaryheap::bh_nodes, and swap.

Referenced by binaryheap_remove_first(), sift_down(), and sift_up().

{
    Datum       swap;

    swap = heap->bh_nodes[a];
    heap->bh_nodes[a] = heap->bh_nodes[b];
    heap->bh_nodes[b] = swap;
}