LCOV - code coverage report
Current view: top level - src/backend/lib - pairingheap.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 78 82 95.1 %
Date: 2019-09-19 17:07:13 Functions: 7 8 87.5 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * pairingheap.c
       4             :  *    A Pairing Heap implementation
       5             :  *
       6             :  * A pairing heap is a data structure that's useful for implementing
       7             :  * priority queues. It is simple to implement, and provides amortized O(1)
       8             :  * insert and find-min operations, and amortized O(log n) delete-min.
       9             :  *
      10             :  * The pairing heap was first described in this paper:
      11             :  *
      12             :  *  Michael L. Fredman, Robert Sedgewick, Daniel D. Sleator, and Robert E.
      13             :  *   Tarjan. 1986.
      14             :  *  The pairing heap: a new form of self-adjusting heap.
      15             :  *  Algorithmica 1, 1 (January 1986), pages 111-129. DOI: 10.1007/BF01840439
      16             :  *
      17             :  * Portions Copyright (c) 2012-2019, PostgreSQL Global Development Group
      18             :  *
      19             :  * IDENTIFICATION
      20             :  *    src/backend/lib/pairingheap.c
      21             :  *
      22             :  *-------------------------------------------------------------------------
      23             :  */
      24             : 
      25             : #include "postgres.h"
      26             : 
      27             : #include "lib/pairingheap.h"
      28             : 
      29             : static pairingheap_node *merge(pairingheap *heap, pairingheap_node *a,
      30             :                                pairingheap_node *b);
      31             : static pairingheap_node *merge_children(pairingheap *heap,
      32             :                                         pairingheap_node *children);
      33             : 
      34             : /*
      35             :  * pairingheap_allocate
      36             :  *
      37             :  * Returns a pointer to a newly-allocated heap, with the heap property defined
      38             :  * by the given comparator function, which will be invoked with the additional
      39             :  * argument specified by 'arg'.
      40             :  */
      41             : pairingheap *
      42        1910 : pairingheap_allocate(pairingheap_comparator compare, void *arg)
      43             : {
      44             :     pairingheap *heap;
      45             : 
      46        1910 :     heap = (pairingheap *) palloc(sizeof(pairingheap));
      47        1910 :     heap->ph_compare = compare;
      48        1910 :     heap->ph_arg = arg;
      49             : 
      50        1910 :     heap->ph_root = NULL;
      51             : 
      52        1910 :     return heap;
      53             : }
      54             : 
      55             : /*
      56             :  * pairingheap_free
      57             :  *
      58             :  * Releases memory used by the given pairingheap.
      59             :  *
      60             :  * Note: The nodes in the heap are not freed!
      61             :  */
      62             : void
      63           0 : pairingheap_free(pairingheap *heap)
      64             : {
      65           0 :     pfree(heap);
      66           0 : }
      67             : 
      68             : /*
      69             :  * A helper function to merge two subheaps into one.
      70             :  *
      71             :  * The subheap with smaller value is put as a child of the other one (assuming
      72             :  * a max-heap).
      73             :  *
      74             :  * The next_sibling and prev_or_parent pointers of the input nodes are
      75             :  * ignored. On return, the returned node's next_sibling and prev_or_parent
      76             :  * pointers are garbage.
      77             :  */
      78             : static pairingheap_node *
      79    13264140 : merge(pairingheap *heap, pairingheap_node *a, pairingheap_node *b)
      80             : {
      81    13264140 :     if (a == NULL)
      82     1232474 :         return b;
      83    12031666 :     if (b == NULL)
      84           0 :         return a;
      85             : 
      86             :     /* swap 'a' and 'b' so that 'a' is the one with larger value */
      87    12031666 :     if (heap->ph_compare(a, b, heap->ph_arg) < 0)
      88             :     {
      89             :         pairingheap_node *tmp;
      90             : 
      91     1070922 :         tmp = a;
      92     1070922 :         a = b;
      93     1070922 :         b = tmp;
      94             :     }
      95             : 
      96             :     /* and put 'b' as a child of 'a' */
      97    12031666 :     if (a->first_child)
      98     3899998 :         a->first_child->prev_or_parent = b;
      99    12031666 :     b->prev_or_parent = a;
     100    12031666 :     b->next_sibling = a->first_child;
     101    12031666 :     a->first_child = b;
     102             : 
     103    12031666 :     return a;
     104             : }
     105             : 
     106             : /*
     107             :  * pairingheap_add
     108             :  *
     109             :  * Adds the given node to the heap in O(1) time.
     110             :  */
     111             : void
     112    10552506 : pairingheap_add(pairingheap *heap, pairingheap_node *node)
     113             : {
     114    10552506 :     node->first_child = NULL;
     115             : 
     116             :     /* Link the new node as a new tree */
     117    10552506 :     heap->ph_root = merge(heap, heap->ph_root, node);
     118    10552506 :     heap->ph_root->prev_or_parent = NULL;
     119    10552506 :     heap->ph_root->next_sibling = NULL;
     120    10552506 : }
     121             : 
     122             : /*
     123             :  * pairingheap_first
     124             :  *
     125             :  * Returns a pointer to the first (root, topmost) node in the heap without
     126             :  * modifying the heap. The caller must ensure that this routine is not used on
     127             :  * an empty heap. Always O(1).
     128             :  */
     129             : pairingheap_node *
     130     1572448 : pairingheap_first(pairingheap *heap)
     131             : {
     132             :     Assert(!pairingheap_is_empty(heap));
     133             : 
     134     1572448 :     return heap->ph_root;
     135             : }
     136             : 
     137             : /*
     138             :  * pairingheap_remove_first
     139             :  *
     140             :  * Removes the first (root, topmost) node in the heap and returns a pointer to
     141             :  * it after rebalancing the heap. The caller must ensure that this routine is
     142             :  * not used on an empty heap. O(log n) amortized.
     143             :  */
     144             : pairingheap_node *
     145     1600830 : pairingheap_remove_first(pairingheap *heap)
     146             : {
     147             :     pairingheap_node *result;
     148             :     pairingheap_node *children;
     149             : 
     150             :     Assert(!pairingheap_is_empty(heap));
     151             : 
     152             :     /* Remove the root, and form a new heap of its children. */
     153     1600830 :     result = heap->ph_root;
     154     1600830 :     children = result->first_child;
     155             : 
     156     1600830 :     heap->ph_root = merge_children(heap, children);
     157     1600830 :     if (heap->ph_root)
     158             :     {
     159      368448 :         heap->ph_root->prev_or_parent = NULL;
     160      368448 :         heap->ph_root->next_sibling = NULL;
     161             :     }
     162             : 
     163     1600830 :     return result;
     164             : }
     165             : 
     166             : /*
     167             :  * Remove 'node' from the heap. O(log n) amortized.
     168             :  */
     169             : void
     170    10209172 : pairingheap_remove(pairingheap *heap, pairingheap_node *node)
     171             : {
     172             :     pairingheap_node *children;
     173             :     pairingheap_node *replacement;
     174             :     pairingheap_node *next_sibling;
     175             :     pairingheap_node **prev_ptr;
     176             : 
     177             :     /*
     178             :      * If the removed node happens to be the root node, do it with
     179             :      * pairingheap_remove_first().
     180             :      */
     181    10209172 :     if (node == heap->ph_root)
     182             :     {
     183     1275894 :         (void) pairingheap_remove_first(heap);
     184     1275894 :         return;
     185             :     }
     186             : 
     187             :     /*
     188             :      * Before we modify anything, remember the removed node's first_child and
     189             :      * next_sibling pointers.
     190             :      */
     191     8933278 :     children = node->first_child;
     192     8933278 :     next_sibling = node->next_sibling;
     193             : 
     194             :     /*
     195             :      * Also find the pointer to the removed node in its previous sibling, or
     196             :      * if this is the first child of its parent, in its parent.
     197             :      */
     198     8933278 :     if (node->prev_or_parent->first_child == node)
     199     8921794 :         prev_ptr = &node->prev_or_parent->first_child;
     200             :     else
     201       11484 :         prev_ptr = &node->prev_or_parent->next_sibling;
     202             :     Assert(*prev_ptr == node);
     203             : 
     204             :     /*
     205             :      * If this node has children, make a new subheap of the children and link
     206             :      * the subheap in place of the removed node. Otherwise just unlink this
     207             :      * node.
     208             :      */
     209     8933278 :     if (children)
     210             :     {
     211        1240 :         replacement = merge_children(heap, children);
     212             : 
     213        1240 :         replacement->prev_or_parent = node->prev_or_parent;
     214        1240 :         replacement->next_sibling = node->next_sibling;
     215        1240 :         *prev_ptr = replacement;
     216        1240 :         if (next_sibling)
     217        1072 :             next_sibling->prev_or_parent = replacement;
     218             :     }
     219             :     else
     220             :     {
     221     8932038 :         *prev_ptr = next_sibling;
     222     8932038 :         if (next_sibling)
     223     1173202 :             next_sibling->prev_or_parent = node->prev_or_parent;
     224             :     }
     225             : }
     226             : 
     227             : /*
     228             :  * Merge a list of subheaps into a single heap.
     229             :  *
     230             :  * This implements the basic two-pass merging strategy, first forming pairs
     231             :  * from left to right, and then merging the pairs.
     232             :  */
     233             : static pairingheap_node *
     234     1602070 : merge_children(pairingheap *heap, pairingheap_node *children)
     235             : {
     236             :     pairingheap_node *curr,
     237             :                *next;
     238             :     pairingheap_node *pairs;
     239             :     pairingheap_node *newroot;
     240             : 
     241     1602070 :     if (children == NULL || children->next_sibling == NULL)
     242     1293732 :         return children;
     243             : 
     244             :     /* Walk the subheaps from left to right, merging in pairs */
     245      308338 :     next = children;
     246      308338 :     pairs = NULL;
     247             :     for (;;)
     248             :     {
     249     3179090 :         curr = next;
     250             : 
     251     1743714 :         if (curr == NULL)
     252      159118 :             break;
     253             : 
     254     1584596 :         if (curr->next_sibling == NULL)
     255             :         {
     256             :             /* last odd node at the end of list */
     257      149220 :             curr->next_sibling = pairs;
     258      149220 :             pairs = curr;
     259      149220 :             break;
     260             :         }
     261             : 
     262     1435376 :         next = curr->next_sibling->next_sibling;
     263             : 
     264             :         /* merge this and the next subheap, and add to 'pairs' list. */
     265             : 
     266     1435376 :         curr = merge(heap, curr, curr->next_sibling);
     267     1435376 :         curr->next_sibling = pairs;
     268     1435376 :         pairs = curr;
     269             :     }
     270             : 
     271             :     /*
     272             :      * Merge all the pairs together to form a single heap.
     273             :      */
     274      308338 :     newroot = pairs;
     275      308338 :     next = pairs->next_sibling;
     276     1892934 :     while (next)
     277             :     {
     278     1276258 :         curr = next;
     279     1276258 :         next = curr->next_sibling;
     280             : 
     281     1276258 :         newroot = merge(heap, newroot, curr);
     282             :     }
     283             : 
     284      308338 :     return newroot;
     285             : }
     286             : 
     287             : /*
     288             :  * A debug function to dump the contents of the heap as a string.
     289             :  *
     290             :  * The 'dumpfunc' callback appends a string representation of a single node
     291             :  * to the StringInfo. 'opaque' can be used to pass more information to the
     292             :  * callback.
     293             :  */
     294             : #ifdef PAIRINGHEAP_DEBUG
     295             : static void
     296             : pairingheap_dump_recurse(StringInfo buf,
     297             :                          pairingheap_node *node,
     298             :                          void (*dumpfunc) (pairingheap_node *node, StringInfo buf, void *opaque),
     299             :                          void *opaque,
     300             :                          int depth,
     301             :                          pairingheap_node *prev_or_parent)
     302             : {
     303             :     while (node)
     304             :     {
     305             :         Assert(node->prev_or_parent == prev_or_parent);
     306             : 
     307             :         appendStringInfoSpaces(buf, depth * 4);
     308             :         dumpfunc(node, buf, opaque);
     309             :         appendStringInfoChar(buf, '\n');
     310             :         if (node->first_child)
     311             :             pairingheap_dump_recurse(buf, node->first_child, dumpfunc, opaque, depth + 1, node);
     312             :         prev_or_parent = node;
     313             :         node = node->next_sibling;
     314             :     }
     315             : }
     316             : 
     317             : char *
     318             : pairingheap_dump(pairingheap *heap,
     319             :                  void (*dumpfunc) (pairingheap_node *node, StringInfo buf, void *opaque),
     320             :                  void *opaque)
     321             : {
     322             :     StringInfoData buf;
     323             : 
     324             :     if (!heap->ph_root)
     325             :         return pstrdup("(empty)");
     326             : 
     327             :     initStringInfo(&buf);
     328             : 
     329             :     pairingheap_dump_recurse(&buf, heap->ph_root, dumpfunc, opaque, 0, NULL);
     330             : 
     331             :     return buf.data;
     332             : }
     333             : #endif

Generated by: LCOV version 1.13