lib/binheap.h

   1 /*
   2  *      Sherlock Library -- Binomial Heaps
   3  *
   4  *      (c) 2003 Martin Mares <mj@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 /*
  11  *  This is a generic implementation of Binomial Heaps. Each time you include
  12  *  this file with parameters set in the corresponding preprocessor macros
  13  *  as described below, it generates functions for manipulating the particular
  14  *  version of the binomial heap.
  15  *
  16  *  You need to specify:
  17  *
  18  *  BH_PREFIX(x)        macro to add a name prefix (used on all global names
  19  *                      defined by the hash table generator). All further
  20  *                      names mentioned here except for macro names will be
  21  *                      implicitly prefixed.
  22  *
  23  *  Then you continue by including "lib/binheap-node.h" which defines struct node
  24  *  (also prefixed) and struct root. The heap elements are always allocated by
  25  *  you and they must include struct node which serves as a handle used for all
  26  *  the heap functions and it contains all information needed for heap-keeping.
  27  *  The heap itself is also allocated by you and it's represented by struct root.
  28  *
  29  *  When you have the declaration of heap nodes, you continue with defining:
  30  *
  31  *  less(p,q)           returns 1 if the key corresponding to bh_node *p
  32  *                      is less than the one corresponding to *q.
  33  *
  34  *  Then specify what operations you request:
  35  *
  36  *  <always defined>    init(heap) -- initialize the heap.
  37  *  BH_WANT_INSERT      insert(heap, node*) -- insert the node to the heap.
  38  *  BH_WANT_FINDMIN     node *findmin(heap) -- find node with minimum key.
  39  *  BH_WANT_DELETEMIN   node *deletemin(heap) -- findmin and delete the node.
  40  *
  41  *  Then include "lib/binheap.h| and voila, you have a binomial heap
  42  *  suiting all your needs (at least those which you've revealed :) ).
  43  *
  44  *  After including this file, all parameter macros are automatically
  45  *  undef'd.
  46  */
  47
  48 static void
  49 BH_PREFIX(merge)(BH_NODE *a, BH_NODE *b)
  50 {
  51   BH_NODE **pp = &a->first_son;
  52   BH_NODE *q = b->first_son;
  53   BH_NODE *p, *r, *s;
  54
  55   while ((p = *pp) && q)
  56     {
  57       /* p,q are the next nodes of a,b; pp points to where p is linked */
  58       if (p->order < q->order)          /* p is smaller => skip it */
  59         pp = &p->next_sibling;
  60       else if (p->order > q->order)     /* q is smaller => insert it before p */
  61         {
  62           r = q;
  63           q = q->next_sibling;
  64           r->next_sibling = p;
  65           *pp = r;
  66           pp = &r->next_sibling;
  67         }
  68       else                              /* p and q are of the same order => need to merge them */
  69         {
  70           if (BH_PREFIX(less)(p, q))    /* we'll hang r below s */
  71             {
  72               r = q;
  73               s = p;
  74             }
  75           else
  76             {
  77               r = p;
  78               s = q;
  79             }
  80           *pp = p->next_sibling;        /* unlink p,q from their lists */
  81           q = q->next_sibling;
  82
  83           if (s->last_son)              /* merge r to s, increasing order */
  84             s->last_son->next_sibling = r;
  85           else
  86             s->first_son = r;
  87           s->last_son = r;
  88           s->order++;
  89           r->next_sibling = NULL;
  90
  91           if (!q || q->order > s->order) /* put the result into the b's list if possible */
  92             {
  93               s->next_sibling = q;
  94               q = s;
  95             }
  96           else                          /* otherwise put the result to the a's list */
  97             {
  98               p = s->next_sibling = *pp;
  99               *pp = s;
 100               if (p && p->order == s->order) /* 3-collision */
 101                 pp = &s->next_sibling;
 102             }
 103         }
 104     }
 105   if (!p)
 106     *pp = q;
 107 }
 108
 109 #ifdef BH_WANT_INSERT
 110 static void
 111 BH_PREFIX(insert)(BH_HEAP *heap, BH_NODE *a)
 112 {
 113   BH_NODE sh;
 114
 115   sh.first_son = a;
 116   a->first_son = a->last_son = a->next_sibling = NULL;
 117   BH_PREFIX(merge)(&heap->root, &sh);
 118 }
 119 #endif
 120
 121 #ifdef BH_WANT_FINDMIN
 122 static BH_NODE *
 123 BH_PREFIX(findmin)(BH_HEAP *heap)
 124 {
 125   BH_NODE *p, *best;
 126
 127   best = NULL;
 128   for (p=heap->root.first_son; p; p=p->next_sibling)
 129     if (!best || BH_PREFIX(less)(p, best))
 130       best = p;
 131   return best;
 132 }
 133 #endif
 134
 135 #ifdef BH_WANT_DELETEMIN
 136 static BH_NODE *
 137 BH_PREFIX(deletemin)(BH_HEAP *heap)
 138 {
 139   BH_NODE *p, **pp, **bestp;
 140
 141   bestp = NULL;
 142   for (pp=&heap->root.first_son; p=*pp; pp=&p->next_sibling)
 143     if (!bestp || BH_PREFIX(less)(p, *bestp))
 144       bestp = pp;
 145   if (!bestp)
 146     return NULL;
 147
 148   p = *bestp;
 149   *bestp = p->next_sibling;
 150   BH_PREFIX(merge)(&heap->root, p);
 151   return p;
 152 }
 153 #endif
 154
 155 static inline void
 156 BH_PREFIX(init)(BH_HEAP *heap)
 157 {
 158   bzero(heap, sizeof(*heap));
 159 }
 160
 161 #undef BH_PREFIX
 162 #undef BH_NODE
 163 #undef BH_HEAP
 164 #undef BH_WANT_INSERT
 165 #undef BH_WANT_FINDMIN
 166 #undef BH_WANT_DELETEMIN