Header And Logo

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

Data Structures | Defines | Typedefs | Functions

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

Defines

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

Typedefs

typedef int(* binaryheap_comparator )(Datum a, Datum b, void *arg)
typedef struct binaryheap binaryheap

Functions

binaryheapbinaryheap_allocate (int capacity, binaryheap_comparator compare, void *arg)
void binaryheap_free (binaryheap *heap)
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)

Define Documentation

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

Typedef Documentation

typedef struct binaryheap binaryheap
typedef int(* binaryheap_comparator)(Datum a, Datum b, void *arg)

Definition at line 18 of file binaryheap.h.


Function Documentation

void binaryheap_add ( binaryheap heap,
Datum  d 
)

Definition at line 128 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 96 of file binaryheap.c.

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

Referenced by ExecMergeAppend().

{
    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 binaryheap::bh_arg, binaryheap::bh_compare, binaryheap::bh_has_heap_property, binaryheap::bh_size, binaryheap::bh_space, offsetof, and palloc().

Referenced by ExecInitMergeAppend().

{
    int         sz;
    binaryheap *heap;

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

    return heap;
}

void binaryheap_build ( binaryheap heap  ) 

Definition at line 112 of file binaryheap.c.

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

Referenced by ExecMergeAppend().

{
    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 145 of file binaryheap.c.

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

Referenced by ExecMergeAppend().

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

void binaryheap_free ( binaryheap heap  ) 

Definition at line 55 of file binaryheap.c.

References pfree().

{
    pfree(heap);
}

Datum binaryheap_remove_first ( binaryheap heap  ) 

Definition at line 160 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 ExecMergeAppend().

{
    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 190 of file binaryheap.c.

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

Referenced by ExecMergeAppend().

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

    heap->bh_nodes[0] = d;

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