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 bh_node
  24  *  and struct bh_root (both without prefix). The heap elements are always allocated by
  25  *  you and they must include struct bh_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 bh_heap.
  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  *  You also get a iterator macro at no extra charge:
  45  *
  46  *  BH_FOR_ALL(bh_prefix, hash*, variable)
  47  *    {
  48  *      // node *variable gets declared automatically
  49  *      do_something_with_node(variable);
  50  *      // use BH_BREAK and BH_CONTINUE instead of break and continue
  51  *      // you must not alter contents of the hash table here
  52  *    }
  53  *  BH_END_FOR;
  54  *
  55  *  After including this file, all parameter macros are automatically
  56  *  undef'd.
  57  */
  58
  59 #define BH_NODE struct bh_node
  60 #define BH_HEAP struct bh_heap
  61
  62 static void
  63 BH_PREFIX(merge)(BH_NODE *a, BH_NODE *b)
  64 {
  65   BH_NODE **pp = &a->first_son;
  66   BH_NODE *q = b->first_son;
  67   BH_NODE *p, *r, *s;
  68
  69   while ((p = *pp) && q)
  70     {
  71       /* p,q are the next nodes of a,b; pp points to where p is linked */
  72       if (p->order < q->order)          /* p is smaller => skip it */
  73         pp = &p->next_sibling;
  74       else if (p->order > q->order)     /* q is smaller => insert it before p */
  75         {
  76           r = q;
  77           q = q->next_sibling;
  78           r->next_sibling = p;
  79           *pp = r;
  80           pp = &r->next_sibling;
  81         }
  82       else                              /* p and q are of the same order => need to merge them */
  83         {
  84           if (BH_PREFIX(less)(p, q))    /* we'll hang r below s */
  85             {
  86               r = q;
  87               s = p;
  88             }
  89           else
  90             {
  91               r = p;
  92               s = q;
  93             }
  94           *pp = p->next_sibling;        /* unlink p,q from their lists */
  95           q = q->next_sibling;
  96
  97           if (s->last_son)              /* merge r to s, increasing order */
  98             s->last_son->next_sibling = r;
  99           else
 100             s->first_son = r;
 101           s->last_son = r;
 102           s->order++;
 103           r->next_sibling = NULL;
 104
 105           if (!q || q->order > s->order) /* put the result into the b's list if possible */
 106             {
 107               s->next_sibling = q;
 108               q = s;
 109             }
 110           else                          /* otherwise put the result to the a's list */
 111             {
 112               p = s->next_sibling = *pp;
 113               *pp = s;
 114               if (p && p->order == s->order) /* 3-collision */
 115                 pp = &s->next_sibling;
 116             }
 117         }
 118     }
 119   if (!p)
 120     *pp = q;
 121 }
 122
 123 #ifdef BH_WANT_INSERT
 124 static void
 125 BH_PREFIX(insert)(BH_HEAP *heap, BH_NODE *a)
 126 {
 127   BH_NODE sh;
 128
 129   sh.first_son = a;
 130   a->first_son = a->last_son = a->next_sibling = NULL;
 131   BH_PREFIX(merge)(&heap->root, &sh);
 132 }
 133 #endif
 134
 135 #ifdef BH_WANT_FINDMIN
 136 static BH_NODE *
 137 BH_PREFIX(findmin)(BH_HEAP *heap)
 138 {
 139   BH_NODE *p, *best;
 140
 141   best = NULL;
 142   for (p=heap->root.first_son; p; p=p->next_sibling)
 143     if (!best || BH_PREFIX(less)(p, best))
 144       best = p;
 145   return best;
 146 }
 147 #endif
 148
 149 #ifdef BH_WANT_DELETEMIN
 150 static BH_NODE *
 151 BH_PREFIX(deletemin)(BH_HEAP *heap)
 152 {
 153   BH_NODE *p, **pp, **bestp;
 154
 155   bestp = NULL;
 156   for (pp=&heap->root.first_son; p=*pp; pp=&p->next_sibling)
 157     if (!bestp || BH_PREFIX(less)(p, *bestp))
 158       bestp = pp;
 159   if (!bestp)
 160     return NULL;
 161
 162   p = *bestp;
 163   *bestp = p->next_sibling;
 164   BH_PREFIX(merge)(&heap->root, p);
 165   return p;
 166 }
 167 #endif
 168
 169 static inline void
 170 BH_PREFIX(init)(BH_HEAP *heap)
 171 {
 172   bzero(heap, sizeof(*heap));
 173 }
 174
 175 #ifndef BH_FOR_ALL
 176
 177 #define BH_FOR_ALL(bh_px, bh_heap, bh_var)      \
 178 do {                                            \
 179   struct bh_node *bh_stack[32];                 \
 180   uns bh_sp = 0;                                \
 181   if (bh_stack[0] = (bh_heap)->root.first_son)  \
 182     bh_sp++;                                    \
 183   while (bh_sp) {                               \
 184     struct bh_node *bh_var = bh_stack[--bh_sp]; \
 185     if (bh_var->next_sibling)                   \
 186       bh_stack[bh_sp++] = bh_var->next_sibling; \
 187     if (bh_var->first_son)                      \
 188       bh_stack[bh_sp++] = bh_var->first_son;
 189 #define BH_END_FOR                              \
 190   }                                             \
 191 } while (0)
 192
 193 #define BH_BREAK { bh_sp=0; break; }
 194 #define BH_CONTINUE continue
 195
 196 #endif
 197
 198 #undef BH_PREFIX
 199 #undef BH_NODE
 200 #undef BH_HEAP
 201 #undef BH_WANT_INSERT
 202 #undef BH_WANT_FINDMIN
 203 #undef BH_WANT_DELETEMIN