src/variable_pairing_heap.h

   1 /**
   2  * @file variable_pairing_heap.h
   3  *
   4  * @author Jeremy Maitin-Shepard <jeremy@jeremyms.com>
   5  *
   6  * This file defines a type-generic pairing heap implementation as
   7  * several macros that generate the implementation code.
   8  */
   9
  10 #ifndef _VARIABLE_PAIRING_HEAP_H
  11 #define _VARIABLE_PAIRING_HEAP_H
  12
  13 #define PH_NEW_LINK(PH_ELEM_TYPE)               \
  14   struct                                        \
  15   {                                             \
  16     PH_ELEM_TYPE *child, *next, *prev;          \
  17   }
  18
  19 #define PH_DECLARE_TYPE(PH_PREFIX, PH_ELEM_TYPE)                        \
  20   typedef PH_ELEM_TYPE *PH_PREFIX ## _t;                                \
  21   void PH_PREFIX ## _init(PH_PREFIX ## _t *ph);                         \
  22   PH_ELEM_TYPE *PH_PREFIX ## _min(PH_PREFIX ## _t *ph);                 \
  23   void PH_PREFIX ## _insert(PH_PREFIX ## _t *ph, PH_ELEM_TYPE *elem);   \
  24   void PH_PREFIX ## _remove(PH_PREFIX ## _t *ph, PH_ELEM_TYPE *elem);   \
  25   void PH_PREFIX ## _remove_min(PH_PREFIX ## _t *ph);
  26
  27 #define PH_DEFINE_TYPE(PH_PREFIX, PH_ELEM_TYPE, PH_NODE_NAME, PH_KEY_NAME)     \
  28   void PH_PREFIX ## _init(PH_PREFIX ## _t *ph)                                 \
  29   {                                                                            \
  30     *ph = NULL;                                                                \
  31   }                                                                            \
  32   PH_ELEM_TYPE *PH_PREFIX ## _min(PH_PREFIX ## _t *ph)                         \
  33   {                                                                            \
  34     return *ph;                                                                \
  35   }                                                                            \
  36   static PH_ELEM_TYPE *PH_PREFIX ## _meld(PH_ELEM_TYPE *a,                     \
  37                                           PH_ELEM_TYPE *b)                     \
  38   {                                                                            \
  39     if (!b)                                                                    \
  40       return a;                                                                \
  41     if (a->PH_KEY_NAME > b->PH_KEY_NAME)                                       \
  42     {                                                                          \
  43       PH_ELEM_TYPE *temp = a;                                                  \
  44       a = b;                                                                   \
  45       b = temp;                                                                \
  46     }                                                                          \
  47     b->PH_NODE_NAME.next = a->PH_NODE_NAME.child;                              \
  48     b->PH_NODE_NAME.prev = a;                                                  \
  49     if (a->PH_NODE_NAME.child)                                                 \
  50       a->PH_NODE_NAME.child->PH_NODE_NAME.prev = b;                            \
  51     a->PH_NODE_NAME.child = b;                                                 \
  52     return a;                                                                  \
  53   }                                                                            \
  54   void PH_PREFIX ## _insert(PH_PREFIX ## _t *ph, PH_ELEM_TYPE *elem)           \
  55   {                                                                            \
  56     elem->PH_NODE_NAME.child = NULL;                                           \
  57     elem->PH_NODE_NAME.next = NULL;                                            \
  58     elem->PH_NODE_NAME.prev = NULL;                                            \
  59     *ph = PH_PREFIX ## _meld(elem, *ph);                                       \
  60   }                                                                            \
  61   static PH_ELEM_TYPE *PH_PREFIX ## _combine_children(PH_ELEM_TYPE *ph)        \
  62   {                                                                            \
  63     PH_ELEM_TYPE *head = NULL, *tail = NULL, *cur = ph->PH_NODE_NAME.child,    \
  64       *next, *nnext, *m = NULL;                                                \
  65     if (!cur)                                                                  \
  66       return NULL;                                                             \
  67     while (1)                                                                  \
  68     {                                                                          \
  69       if (!cur->PH_NODE_NAME.next)                                             \
  70         next = NULL;                                                           \
  71       else                                                                     \
  72         next = cur->PH_NODE_NAME.next->PH_NODE_NAME.next;                      \
  73       m = PH_PREFIX ## _meld(cur, cur->PH_NODE_NAME.next);                     \
  74       if (tail)                                                                \
  75         tail->PH_NODE_NAME.next = m;                                           \
  76       else                                                                     \
  77         head = m;                                                              \
  78       tail = m;                                                                \
  79       if (!next)                                                               \
  80         break;                                                                 \
  81       cur = next;                                                              \
  82     }                                                                          \
  83     while (head != tail)                                                       \
  84     {                                                                          \
  85       next = head->PH_NODE_NAME.next;                                          \
  86       nnext = next->PH_NODE_NAME.next;                                         \
  87       m = PH_PREFIX ## _meld(head, next);                                      \
  88       if (next == tail)                                                        \
  89         break;                                                                 \
  90       tail->PH_NODE_NAME.next = m;                                             \
  91       tail = m;                                                                \
  92       head = nnext;                                                            \
  93     }                                                                          \
  94     m->PH_NODE_NAME.prev = NULL;                                               \
  95     m->PH_NODE_NAME.next = NULL;                                               \
  96     return m;                                                                  \
  97   }                                                                            \
  98   void PH_PREFIX ## _remove_min(PH_PREFIX ## _t *ph)                           \
  99   {                                                                            \
 100     *ph = PH_PREFIX ## _combine_children(*ph);                                 \
 101   }                                                                            \
 102   void PH_PREFIX ## _remove(PH_PREFIX ## _t *ph, PH_ELEM_TYPE *elem)           \
 103   {                                                                            \
 104     if (elem == *ph)                                                           \
 105       PH_PREFIX ## _remove_min(ph);                                            \
 106     else                                                                       \
 107     {                                                                          \
 108       PH_ELEM_TYPE *prev = elem->PH_NODE_NAME.prev;                            \
 109       if (prev->PH_NODE_NAME.child == elem)                                    \
 110         prev->PH_NODE_NAME.child = elem->PH_NODE_NAME.next;                    \
 111       else                                                                     \
 112         prev->PH_NODE_NAME.next = elem->PH_NODE_NAME.next;                     \
 113       if (elem->PH_NODE_NAME.next)                                             \
 114         elem->PH_NODE_NAME.next->PH_NODE_NAME.prev = prev;                     \
 115       *ph = PH_PREFIX ## _meld                                                 \
 116         (*ph, PH_PREFIX ## _combine_children(elem));                           \
 117     }                                                                          \
 118   }
 119
 120 #endif /* _VARIABLE_PAIRING_HEAP_H */