#include "lib/stringinfo.h"

Include dependency graph for pairingheap.h:

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

Data Structures
struct	pairingheap_node

struct	pairingheap

Macros
#define	pairingheap_container(type, membername, ptr)

#define	pairingheap_const_container(type, membername, ptr)

#define	pairingheap_reset(h) ((h)->ph_root = NULL)

#define	pairingheap_is_empty(h) ((h)->ph_root == NULL)

#define	pairingheap_is_singular(h) ((h)->ph_root && (h)->ph_root->first_child == NULL)

Typedefs
typedef struct pairingheap_node	pairingheap_node

typedef int(*	pairingheap_comparator) (const pairingheap_node a, const pairingheap_node b, void *arg)

typedef struct pairingheap	pairingheap

Functions
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)

Macro Definition Documentation

◆ pairingheap_const_container

#define pairingheap_const_container	(	type,
		membername,
		ptr
	)

Value:

    (AssertVariableIsOfTypeMacro(ptr, const pairingheap_node *), \
     AssertVariableIsOfTypeMacro(((type *) NULL)->membername, pairingheap_node),  \
     ((const type *) ((const char *) (ptr) - offsetof(type, membername))))

Definition at line 51 of file pairingheap.h.

◆ pairingheap_container

#define pairingheap_container	(	type,
		membername,
		ptr
	)

Value:

    (AssertVariableIsOfTypeMacro(ptr, pairingheap_node *), \
     AssertVariableIsOfTypeMacro(((type *) NULL)->membername, pairingheap_node),  \
     ((type *) ((char *) (ptr) - offsetof(type, membername))))

Definition at line 43 of file pairingheap.h.

◆ pairingheap_is_empty

#define pairingheap_is_empty ( h ) ((h)->ph_root == NULL)

Definition at line 99 of file pairingheap.h.

◆ pairingheap_is_singular

#define pairingheap_is_singular ( h ) ((h)->ph_root && (h)->ph_root->first_child == NULL)

Definition at line 102 of file pairingheap.h.

◆ pairingheap_reset

#define pairingheap_reset ( h ) ((h)->ph_root = NULL)

Definition at line 96 of file pairingheap.h.

Typedef Documentation

◆ pairingheap

typedef struct pairingheap pairingheap

◆ pairingheap_comparator

typedef int(* pairingheap_comparator) (const pairingheap_node *a, const pairingheap_node *b, void *arg)

Definition at line 60 of file pairingheap.h.

◆ pairingheap_node

typedef struct pairingheap_node pairingheap_node

Function Documentation

◆ 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 IndexNextWithReorder(), ReorderBufferLargestTXN(), SnapshotResetXmin(), updateMinWaitedLSN(), and wakeupWaiters().

◆ 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 wakeupWaiters().

Data Structures

Macros

Typedefs

Functions