ucw/binheap.h

   1 /*
   2  *      UCW 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
  17 /***
  18  * [[generator]]
  19  * Interface to the generator
  20  * --------------------------
  21  *
  22  * To use the binomial heaps, you need to specify:
  23  *
  24  * - `BH_PREFIX(x)`  -- macro to add a name prefix (used on all global names
  25  *                      defined by the generator). All further names mentioned
  26  *                      here except for macro names will be implicitly prefixed.
  27  *
  28  * Then you continue by including `ucw/binheap-node.h` which defines <<struct_bh_node,struct bh_node>>
  29  * and <<struct_bh_heap,struct bh_heap>> (both without prefix). The heap elements are always allocated by
  30  * you and they must include `struct bh_node` which serves as a handle used for all
  31  * the heap functions and it contains all information needed for heap-keeping.
  32  * The heap itself is also allocated by you and it's represented by `struct bh_heap`.
  33  *
  34  * When you have the declaration of heap nodes, you continue with defining:
  35  *
  36  * - `less(p,q)`     -- returns `1` if the key corresponding to `bh_node *p`
  37  *                      is less than the one corresponding to `*q`.
  38  *
  39  * Then specify what operations you request:
  40  *
  41  * - `init(heap\*)` -- initialize the heap (always defined).
  42  * - `insert(heap\*, node\*)` -- insert the node to the heap (`BH_WANT_INSERT`).
  43  * - `node\* findmin(heap\*)` -- find node with minimum key (`BH_WANT_FINDMIN`).
  44  * - `node\* deletemin(heap\*)` -- findmin and delete the node (`BH_WANT_DELETEMIN`).
  45  *
  46  * Then include `ucw/binheap.h` and voila, you have a binomial heap
  47  * suiting all your needs (at least those which you've revealed :) ).
  48  *
  49  * You also get a iterator macro at no extra charge:
  50  *
  51  *   BH_FOR_ALL(bh_prefix, heap*, variable)
  52  *     {
  53  *       // node* variable gets declared automatically
  54  *       do_something_with_node(variable);
  55  *       // use BH_BREAK and BH_CONTINUE instead of break and continue
  56  *       // you must not alter contents of the binomial heap here
  57  *     }
  58  *   BH_END_FOR;
  59  *
  60  * After including this file, all parameter macros are automatically undef'd.
  61  ***/
  62
  63 #define BH_NODE struct bh_node
  64 #define BH_HEAP struct bh_heap
  65
  66 static void
  67 BH_PREFIX(merge)(BH_NODE *a, BH_NODE *b)
  68 {
  69   BH_NODE **pp = &a->first_son;
  70   BH_NODE *q = b->first_son;
  71   BH_NODE *p, *r, *s;
  72
  73   while ((p = *pp) && q)
  74     {
  75       /* p,q are the next nodes of a,b; pp points to where p is linked */
  76       if (p->order < q->order)          /* p is smaller => skip it */
  77         pp = &p->next_sibling;
  78       else if (p->order > q->order)     /* q is smaller => insert it before p */
  79         {
  80           r = q;
  81           q = q->next_sibling;
  82           r->next_sibling = p;
  83           *pp = r;
  84           pp = &r->next_sibling;
  85         }
  86       else                              /* p and q are of the same order => need to merge them */
  87         {
  88           if (BH_PREFIX(less)(p, q))    /* we'll hang r below s */
  89             {
  90               r = q;
  91               s = p;
  92             }
  93           else
  94             {
  95               r = p;
  96               s = q;
  97             }
  98           *pp = p->next_sibling;        /* unlink p,q from their lists */
  99           q = q->next_sibling;
 100
 101           if (s->last_son)              /* merge r to s, increasing order */
 102             s->last_son->next_sibling = r;
 103           else
 104             s->first_son = r;
 105           s->last_son = r;
 106           s->order++;
 107           r->next_sibling = NULL;
 108
 109           if (!q || q->order > s->order) /* put the result into the b's list if possible */
 110             {
 111               s->next_sibling = q;
 112               q = s;
 113             }
 114           else                          /* otherwise put the result to the a's list */
 115             {
 116               p = s->next_sibling = *pp;
 117               *pp = s;
 118               if (p && p->order == s->order) /* 3-collision */
 119                 pp = &s->next_sibling;
 120             }
 121         }
 122     }
 123   if (!p)
 124     *pp = q;
 125 }
 126
 127 #ifdef BH_WANT_INSERT
 128 static void
 129 BH_PREFIX(insert)(BH_HEAP *heap, BH_NODE *a)
 130 {
 131   BH_NODE sh;
 132
 133   sh.first_son = a;
 134   a->first_son = a->last_son = a->next_sibling = NULL;
 135   a->order = 0;
 136   BH_PREFIX(merge)(&heap->root, &sh);
 137 }
 138 #endif
 139
 140 #ifdef BH_WANT_FINDMIN
 141 static BH_NODE *
 142 BH_PREFIX(findmin)(BH_HEAP *heap)
 143 {
 144   BH_NODE *p, *best;
 145
 146   best = NULL;
 147   for (p=heap->root.first_son; p; p=p->next_sibling)
 148     if (!best || BH_PREFIX(less)(p, best))
 149       best = p;
 150   return best;
 151 }
 152 #endif
 153
 154 #ifdef BH_WANT_DELETEMIN
 155 static BH_NODE *
 156 BH_PREFIX(deletemin)(BH_HEAP *heap)
 157 {
 158   BH_NODE *p, **pp, **bestp;
 159
 160   bestp = NULL;
 161   for (pp=&heap->root.first_son; p=*pp; pp=&p->next_sibling)
 162     if (!bestp || BH_PREFIX(less)(p, *bestp))
 163       bestp = pp;
 164   if (!bestp)
 165     return NULL;
 166
 167   p = *bestp;
 168   *bestp = p->next_sibling;
 169   BH_PREFIX(merge)(&heap->root, p);
 170   return p;
 171 }
 172 #endif
 173
 174 static inline void
 175 BH_PREFIX(init)(BH_HEAP *heap)
 176 {
 177   bzero(heap, sizeof(*heap));
 178 }
 179
 180 #ifndef BH_FOR_ALL
 181
 182 #define BH_FOR_ALL(bh_px, bh_heap, bh_var)      \
 183 do {                                            \
 184   struct bh_node *bh_stack[32];                 \
 185   uint bh_sp = 0;                               \
 186   if (bh_stack[0] = (bh_heap)->root.first_son)  \
 187     bh_sp++;                                    \
 188   while (bh_sp) {                               \
 189     struct bh_node *bh_var = bh_stack[--bh_sp]; \
 190     if (bh_var->next_sibling)                   \
 191       bh_stack[bh_sp++] = bh_var->next_sibling; \
 192     if (bh_var->first_son)                      \
 193       bh_stack[bh_sp++] = bh_var->first_son;
 194 #define BH_END_FOR                              \
 195   }                                             \
 196 } while (0)
 197
 198 #define BH_BREAK { bh_sp=0; break; }
 199 #define BH_CONTINUE continue
 200
 201 #endif
 202
 203 #undef BH_PREFIX
 204 #undef BH_NODE
 205 #undef BH_HEAP
 206 #undef BH_WANT_INSERT
 207 #undef BH_WANT_FINDMIN
 208 #undef BH_WANT_DELETEMIN