pairingheap.c File Reference

#include "postgres.h"
#include "lib/pairingheap.h"

Include dependency graph for pairingheap.c:

Go to the source code of this file.

Functions
static pairingheap_node *	merge (pairingheap *heap, pairingheap_node *a, pairingheap_node *b)
static pairingheap_node *	merge_children (pairingheap *heap, pairingheap_node *children)
pairingheap *	pairingheap_allocate (pairingheap_comparator compare, void *arg)
void	pairingheap_initialize (pairingheap *heap, pairingheap_comparator compare, void *arg)
void	pairingheap_free (pairingheap *heap)
void	pairingheap_add (pairingheap *heap, pairingheap_node *node)
pairingheap_node *	pairingheap_first (pairingheap *heap)
pairingheap_node *	pairingheap_remove_first (pairingheap *heap)
void	pairingheap_remove (pairingheap *heap, pairingheap_node *node)

Function Documentation

merge()

static pairingheap_node * merge ( pairingheap *  heap, pairingheap_node *  a, pairingheap_node *  b  )

static

Definition at line 93 of file pairingheap.c.

{
    if (a == NULL)
        return b;
    if (b == NULL)
        return a;
 
    /* swap 'a' and 'b' so that 'a' is the one with larger value */
    if (heap->ph_compare(a, b, heap->ph_arg) < 0)
    {
        pairingheap_node *tmp;
 
        tmp = a;
        a = b;
        b = tmp;
    }
 
    /* and put 'b' as a child of 'a' */
    if (a->first_child)
        a->first_child->prev_or_parent = b;
    b->prev_or_parent = a;
    b->next_sibling = a->first_child;
    a->first_child = b;
 
    return a;
}

References a, b, pairingheap::ph_arg, and pairingheap::ph_compare.

Referenced by _bt_load(), merge_children(), and pairingheap_add().

merge_children()

static pairingheap_node * merge_children ( pairingheap *  heap, pairingheap_node *  children  )

static

Definition at line 248 of file pairingheap.c.

{
    pairingheap_node *curr,
               *next;
    pairingheap_node *pairs;
    pairingheap_node *newroot;
 
    if (children == NULL || children->next_sibling == NULL)
        return children;
 
    /* Walk the subheaps from left to right, merging in pairs */
    next = children;
    pairs = NULL;
    for (;;)
    {
        curr = next;
 
        if (curr == NULL)
            break;
 
        if (curr->next_sibling == NULL)
        {
            /* last odd node at the end of list */
            curr->next_sibling = pairs;
            pairs = curr;
            break;
        }
 
        next = curr->next_sibling->next_sibling;
 
        /* merge this and the next subheap, and add to 'pairs' list. */
 
        curr = merge(heap, curr, curr->next_sibling);
        curr->next_sibling = pairs;
        pairs = curr;
    }
 
    /*
     * Merge all the pairs together to form a single heap.
     */
    newroot = pairs;
    next = pairs->next_sibling;
    while (next)
    {
        curr = next;
        next = curr->next_sibling;
 
        newroot = merge(heap, newroot, curr);
    }
 
    return newroot;
}

References merge(), next, and pairingheap_node::next_sibling.

Referenced by pairingheap_remove(), and pairingheap_remove_first().

pairingheap_add()

void pairingheap_add	(	pairingheap *	heap,
		pairingheap_node *	node
	)

Definition at line 126 of file pairingheap.c.

{
    node->first_child = NULL;
 
    /* Link the new node as a new tree */
    heap->ph_root = merge(heap, heap->ph_root, node);
    heap->ph_root->prev_or_parent = NULL;
    heap->ph_root->next_sibling = NULL;
}

References pairingheap_node::first_child, merge(), pairingheap_node::next_sibling, pairingheap::ph_root, and pairingheap_node::prev_or_parent.

Referenced by addLSNWaiter(), ExportSnapshot(), GetNonHistoricCatalogSnapshot(), GetTransactionSnapshot(), gistScanPage(), RegisterSnapshotOnOwner(), ReorderBufferChangeMemoryUpdate(), reorderqueue_push(), SetTransactionSnapshot(), and spgAddSearchItemToQueue().

pairingheap_allocate()

pairingheap* pairingheap_allocate	(	pairingheap_comparator	compare,
		void *	arg
	)

Definition at line 42 of file pairingheap.c.

{
    pairingheap *heap;
 
    heap = (pairingheap *) palloc(sizeof(pairingheap));
    pairingheap_initialize(heap, compare, arg);
 
    return heap;
}

References arg, compare(), pairingheap_initialize(), and palloc().

Referenced by ExecInitIndexScan(), gistrescan(), ReorderBufferAllocate(), and resetSpGistScanOpaque().

pairingheap_first()

pairingheap_node* pairingheap_first

(

pairingheap *

heap

)

Definition at line 144 of file pairingheap.c.

{
    Assert(!pairingheap_is_empty(heap));
 
    return heap->ph_root;
}

References Assert, pairingheap_is_empty, and pairingheap::ph_root.

Referenced by GetOldestSnapshot(), IndexNextWithReorder(), ReorderBufferLargestTXN(), SnapshotResetXmin(), updateMinWaitedLSN(), and WaitLSNSetLatches().

pairingheap_free()

void pairingheap_free

(

pairingheap *

heap

)

Definition at line 77 of file pairingheap.c.

{
    pfree(heap);
}

References pfree().

pairingheap_initialize()

void pairingheap_initialize	(	pairingheap *	heap,
		pairingheap_comparator	compare,
		void *	arg
	)

Definition at line 60 of file pairingheap.c.

{
    heap->ph_compare = compare;
    heap->ph_arg = arg;
 
    heap->ph_root = NULL;
}

References arg, compare(), pairingheap::ph_arg, pairingheap::ph_compare, and pairingheap::ph_root.

Referenced by pairingheap_allocate(), and WaitLSNShmemInit().

pairingheap_remove()

void pairingheap_remove	(	pairingheap *	heap,
		pairingheap_node *	node
	)

Definition at line 184 of file pairingheap.c.

{
    pairingheap_node *children;
    pairingheap_node *replacement;
    pairingheap_node *next_sibling;
    pairingheap_node **prev_ptr;
 
    /*
     * If the removed node happens to be the root node, do it with
     * pairingheap_remove_first().
     */
    if (node == heap->ph_root)
    {
        (void) pairingheap_remove_first(heap);
        return;
    }
 
    /*
     * Before we modify anything, remember the removed node's first_child and
     * next_sibling pointers.
     */
    children = node->first_child;
    next_sibling = node->next_sibling;
 
    /*
     * Also find the pointer to the removed node in its previous sibling, or
     * if this is the first child of its parent, in its parent.
     */
    if (node->prev_or_parent->first_child == node)
        prev_ptr = &node->prev_or_parent->first_child;
    else
        prev_ptr = &node->prev_or_parent->next_sibling;
    Assert(*prev_ptr == node);
 
    /*
     * If this node has children, make a new subheap of the children and link
     * the subheap in place of the removed node. Otherwise just unlink this
     * node.
     */
    if (children)
    {
        replacement = merge_children(heap, children);
 
        replacement->prev_or_parent = node->prev_or_parent;
        replacement->next_sibling = node->next_sibling;
        *prev_ptr = replacement;
        if (next_sibling)
            next_sibling->prev_or_parent = replacement;
    }
    else
    {
        *prev_ptr = next_sibling;
        if (next_sibling)
            next_sibling->prev_or_parent = node->prev_or_parent;
    }
}

References Assert, pairingheap_node::first_child, merge_children(), pairingheap_node::next_sibling, pairingheap_remove_first(), pairingheap::ph_root, and pairingheap_node::prev_or_parent.

Referenced by AtEOXact_Snapshot(), deleteLSNWaiter(), InvalidateCatalogSnapshot(), ReorderBufferChangeMemoryUpdate(), and UnregisterSnapshotNoOwner().

pairingheap_remove_first()

pairingheap_node* pairingheap_remove_first

(

pairingheap *

heap

)

Definition at line 159 of file pairingheap.c.

{
    pairingheap_node *result;
    pairingheap_node *children;
 
    Assert(!pairingheap_is_empty(heap));
 
    /* Remove the root, and form a new heap of its children. */
    result = heap->ph_root;
    children = result->first_child;
 
    heap->ph_root = merge_children(heap, children);
    if (heap->ph_root)
    {
        heap->ph_root->prev_or_parent = NULL;
        heap->ph_root->next_sibling = NULL;
    }
 
    return result;
}

References Assert, pairingheap_node::first_child, merge_children(), pairingheap_node::next_sibling, pairingheap_is_empty, pairingheap::ph_root, and pairingheap_node::prev_or_parent.

Referenced by getNextGISTSearchItem(), pairingheap_remove(), reorderqueue_pop(), spgGetNextQueueItem(), and WaitLSNSetLatches().