#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 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().

Data Structures

Macros

Typedefs

Functions