contrib/jemalloc/include/jemalloc/internal/ph.h

   1 /*
   2  * A Pairing Heap implementation.
   3  *
   4  * "The Pairing Heap: A New Form of Self-Adjusting Heap"
   5  * https://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf
   6  *
   7  * With auxiliary twopass list, described in a follow on paper.
   8  *
   9  * "Pairing Heaps: Experiments and Analysis"
  10  * http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.2988&rep=rep1&type=pdf
  11  *
  12  *******************************************************************************
  13  */
  14
  15 #ifndef PH_H_
  16 #define PH_H_
  17
  18 /* Node structure. */
  19 #define phn(a_type)                                                     \
  20 struct {                                                                \
  21         a_type  *phn_prev;                                              \
  22         a_type  *phn_next;                                              \
  23         a_type  *phn_lchild;                                            \
  24 }
  25
  26 /* Root structure. */
  27 #define ph(a_type)                                                      \
  28 struct {                                                                \
  29         a_type  *ph_root;                                               \
  30 }
  31
  32 /* Internal utility macros. */
  33 #define phn_lchild_get(a_type, a_field, a_phn)                          \
  34         (a_phn->a_field.phn_lchild)
  35 #define phn_lchild_set(a_type, a_field, a_phn, a_lchild) do {           \
  36         a_phn->a_field.phn_lchild = a_lchild;                           \
  37 } while (0)
  38
  39 #define phn_next_get(a_type, a_field, a_phn)                            \
  40         (a_phn->a_field.phn_next)
  41 #define phn_prev_set(a_type, a_field, a_phn, a_prev) do {               \
  42         a_phn->a_field.phn_prev = a_prev;                               \
  43 } while (0)
  44
  45 #define phn_prev_get(a_type, a_field, a_phn)                            \
  46         (a_phn->a_field.phn_prev)
  47 #define phn_next_set(a_type, a_field, a_phn, a_next) do {               \
  48         a_phn->a_field.phn_next = a_next;                               \
  49 } while (0)
  50
  51 #define phn_merge_ordered(a_type, a_field, a_phn0, a_phn1, a_cmp) do {  \
  52         a_type *phn0child;                                              \
  53                                                                         \
  54         assert(a_phn0 != NULL);                                         \
  55         assert(a_phn1 != NULL);                                         \
  56         assert(a_cmp(a_phn0, a_phn1) <= 0);                             \
  57                                                                         \
  58         phn_prev_set(a_type, a_field, a_phn1, a_phn0);                  \
  59         phn0child = phn_lchild_get(a_type, a_field, a_phn0);            \
  60         phn_next_set(a_type, a_field, a_phn1, phn0child);               \
  61         if (phn0child != NULL) {                                        \
  62                 phn_prev_set(a_type, a_field, phn0child, a_phn1);       \
  63         }                                                               \
  64         phn_lchild_set(a_type, a_field, a_phn0, a_phn1);                \
  65 } while (0)
  66
  67 #define phn_merge(a_type, a_field, a_phn0, a_phn1, a_cmp, r_phn) do {   \
  68         if (a_phn0 == NULL) {                                           \
  69                 r_phn = a_phn1;                                         \
  70         } else if (a_phn1 == NULL) {                                    \
  71                 r_phn = a_phn0;                                         \
  72         } else if (a_cmp(a_phn0, a_phn1) < 0) {                         \
  73                 phn_merge_ordered(a_type, a_field, a_phn0, a_phn1,      \
  74                     a_cmp);                                             \
  75                 r_phn = a_phn0;                                         \
  76         } else {                                                        \
  77                 phn_merge_ordered(a_type, a_field, a_phn1, a_phn0,      \
  78                     a_cmp);                                             \
  79                 r_phn = a_phn1;                                         \
  80         }                                                               \
  81 } while (0)
  82
  83 #define ph_merge_siblings(a_type, a_field, a_phn, a_cmp, r_phn) do {    \
  84         a_type *head = NULL;                                            \
  85         a_type *tail = NULL;                                            \
  86         a_type *phn0 = a_phn;                                           \
  87         a_type *phn1 = phn_next_get(a_type, a_field, phn0);             \
  88                                                                         \
  89         /*                                                              \
  90          * Multipass merge, wherein the first two elements of a FIFO    \
  91          * are repeatedly merged, and each result is appended to the    \
  92          * singly linked FIFO, until the FIFO contains only a single    \
  93          * element.  We start with a sibling list but no reference to   \
  94          * its tail, so we do a single pass over the sibling list to    \
  95          * populate the FIFO.                                           \
  96          */                                                             \
  97         if (phn1 != NULL) {                                             \
  98                 a_type *phnrest = phn_next_get(a_type, a_field, phn1);  \
  99                 if (phnrest != NULL) {                                  \
 100                         phn_prev_set(a_type, a_field, phnrest, NULL);   \
 101                 }                                                       \
 102                 phn_prev_set(a_type, a_field, phn0, NULL);              \
 103                 phn_next_set(a_type, a_field, phn0, NULL);              \
 104                 phn_prev_set(a_type, a_field, phn1, NULL);              \
 105                 phn_next_set(a_type, a_field, phn1, NULL);              \
 106                 phn_merge(a_type, a_field, phn0, phn1, a_cmp, phn0);    \
 107                 head = tail = phn0;                                     \
 108                 phn0 = phnrest;                                         \
 109                 while (phn0 != NULL) {                                  \
 110                         phn1 = phn_next_get(a_type, a_field, phn0);     \
 111                         if (phn1 != NULL) {                             \
 112                                 phnrest = phn_next_get(a_type, a_field, \
 113                                     phn1);                              \
 114                                 if (phnrest != NULL) {                  \
 115                                         phn_prev_set(a_type, a_field,   \
 116                                             phnrest, NULL);             \
 117                                 }                                       \
 118                                 phn_prev_set(a_type, a_field, phn0,     \
 119                                     NULL);                              \
 120                                 phn_next_set(a_type, a_field, phn0,     \
 121                                     NULL);                              \
 122                                 phn_prev_set(a_type, a_field, phn1,     \
 123                                     NULL);                              \
 124                                 phn_next_set(a_type, a_field, phn1,     \
 125                                     NULL);                              \
 126                                 phn_merge(a_type, a_field, phn0, phn1,  \
 127                                     a_cmp, phn0);                       \
 128                                 phn_next_set(a_type, a_field, tail,     \
 129                                     phn0);                              \
 130                                 tail = phn0;                            \
 131                                 phn0 = phnrest;                         \
 132                         } else {                                        \
 133                                 phn_next_set(a_type, a_field, tail,     \
 134                                     phn0);                              \
 135                                 tail = phn0;                            \
 136                                 phn0 = NULL;                            \
 137                         }                                               \
 138                 }                                                       \
 139                 phn0 = head;                                            \
 140                 phn1 = phn_next_get(a_type, a_field, phn0);             \
 141                 if (phn1 != NULL) {                                     \
 142                         while (true) {                                  \
 143                                 head = phn_next_get(a_type, a_field,    \
 144                                     phn1);                              \
 145                                 assert(phn_prev_get(a_type, a_field,    \
 146                                     phn0) == NULL);                     \
 147                                 phn_next_set(a_type, a_field, phn0,     \
 148                                     NULL);                              \
 149                                 assert(phn_prev_get(a_type, a_field,    \
 150                                     phn1) == NULL);                     \
 151                                 phn_next_set(a_type, a_field, phn1,     \
 152                                     NULL);                              \
 153                                 phn_merge(a_type, a_field, phn0, phn1,  \
 154                                     a_cmp, phn0);                       \
 155                                 if (head == NULL) {                     \
 156                                         break;                          \
 157                                 }                                       \
 158                                 phn_next_set(a_type, a_field, tail,     \
 159                                     phn0);                              \
 160                                 tail = phn0;                            \
 161                                 phn0 = head;                            \
 162                                 phn1 = phn_next_get(a_type, a_field,    \
 163                                     phn0);                              \
 164                         }                                               \
 165                 }                                                       \
 166         }                                                               \
 167         r_phn = phn0;                                                   \
 168 } while (0)
 169
 170 #define ph_merge_aux(a_type, a_field, a_ph, a_cmp) do {                 \
 171         a_type *phn = phn_next_get(a_type, a_field, a_ph->ph_root);     \
 172         if (phn != NULL) {                                              \
 173                 phn_prev_set(a_type, a_field, a_ph->ph_root, NULL);     \
 174                 phn_next_set(a_type, a_field, a_ph->ph_root, NULL);     \
 175                 phn_prev_set(a_type, a_field, phn, NULL);               \
 176                 ph_merge_siblings(a_type, a_field, phn, a_cmp, phn);    \
 177                 assert(phn_next_get(a_type, a_field, phn) == NULL);     \
 178                 phn_merge(a_type, a_field, a_ph->ph_root, phn, a_cmp,   \
 179                     a_ph->ph_root);                                     \
 180         }                                                               \
 181 } while (0)
 182
 183 #define ph_merge_children(a_type, a_field, a_phn, a_cmp, r_phn) do {    \
 184         a_type *lchild = phn_lchild_get(a_type, a_field, a_phn);        \
 185         if (lchild == NULL) {                                           \
 186                 r_phn = NULL;                                           \
 187         } else {                                                        \
 188                 ph_merge_siblings(a_type, a_field, lchild, a_cmp,       \
 189                     r_phn);                                             \
 190         }                                                               \
 191 } while (0)
 192
 193 /*
 194  * The ph_proto() macro generates function prototypes that correspond to the
 195  * functions generated by an equivalently parameterized call to ph_gen().
 196  */
 197 #define ph_proto(a_attr, a_prefix, a_ph_type, a_type)                   \
 198 a_attr void     a_prefix##new(a_ph_type *ph);                           \
 199 a_attr bool     a_prefix##empty(a_ph_type *ph);                         \
 200 a_attr a_type   *a_prefix##first(a_ph_type *ph);                        \
 201 a_attr a_type   *a_prefix##any(a_ph_type *ph);                          \
 202 a_attr void     a_prefix##insert(a_ph_type *ph, a_type *phn);           \
 203 a_attr a_type   *a_prefix##remove_first(a_ph_type *ph);                 \
 204 a_attr a_type   *a_prefix##remove_any(a_ph_type *ph);                   \
 205 a_attr void     a_prefix##remove(a_ph_type *ph, a_type *phn);
 206
 207 /*
 208  * The ph_gen() macro generates a type-specific pairing heap implementation,
 209  * based on the above cpp macros.
 210  */
 211 #define ph_gen(a_attr, a_prefix, a_ph_type, a_type, a_field, a_cmp)     \
 212 a_attr void                                                             \
 213 a_prefix##new(a_ph_type *ph) {                                          \
 214         memset(ph, 0, sizeof(ph(a_type)));                              \
 215 }                                                                       \
 216 a_attr bool                                                             \
 217 a_prefix##empty(a_ph_type *ph) {                                        \
 218         return (ph->ph_root == NULL);                                   \
 219 }                                                                       \
 220 a_attr a_type *                                                         \
 221 a_prefix##first(a_ph_type *ph) {                                        \
 222         if (ph->ph_root == NULL) {                                      \
 223                 return NULL;                                            \
 224         }                                                               \
 225         ph_merge_aux(a_type, a_field, ph, a_cmp);                       \
 226         return ph->ph_root;                                             \
 227 }                                                                       \
 228 a_attr a_type *                                                         \
 229 a_prefix##any(a_ph_type *ph) {                                          \
 230         if (ph->ph_root == NULL) {                                      \
 231                 return NULL;                                            \
 232         }                                                               \
 233         a_type *aux = phn_next_get(a_type, a_field, ph->ph_root);       \
 234         if (aux != NULL) {                                              \
 235                 return aux;                                             \
 236         }                                                               \
 237         return ph->ph_root;                                             \
 238 }                                                                       \
 239 a_attr void                                                             \
 240 a_prefix##insert(a_ph_type *ph, a_type *phn) {                          \
 241         memset(&phn->a_field, 0, sizeof(phn(a_type)));                  \
 242                                                                         \
 243         /*                                                              \
 244          * Treat the root as an aux list during insertion, and lazily   \
 245          * merge during a_prefix##remove_first().  For elements that    \
 246          * are inserted, then removed via a_prefix##remove() before the \
 247          * aux list is ever processed, this makes insert/remove         \
 248          * constant-time, whereas eager merging would make insert       \
 249          * O(log n).                                                    \
 250          */                                                             \
 251         if (ph->ph_root == NULL) {                                      \
 252                 ph->ph_root = phn;                                      \
 253         } else {                                                        \
 254                 phn_next_set(a_type, a_field, phn, phn_next_get(a_type, \
 255                     a_field, ph->ph_root));                             \
 256                 if (phn_next_get(a_type, a_field, ph->ph_root) !=       \
 257                     NULL) {                                             \
 258                         phn_prev_set(a_type, a_field,                   \
 259                             phn_next_get(a_type, a_field, ph->ph_root), \
 260                             phn);                                       \
 261                 }                                                       \
 262                 phn_prev_set(a_type, a_field, phn, ph->ph_root);        \
 263                 phn_next_set(a_type, a_field, ph->ph_root, phn);        \
 264         }                                                               \
 265 }                                                                       \
 266 a_attr a_type *                                                         \
 267 a_prefix##remove_first(a_ph_type *ph) {                                 \
 268         a_type *ret;                                                    \
 269                                                                         \
 270         if (ph->ph_root == NULL) {                                      \
 271                 return NULL;                                            \
 272         }                                                               \
 273         ph_merge_aux(a_type, a_field, ph, a_cmp);                       \
 274                                                                         \
 275         ret = ph->ph_root;                                              \
 276                                                                         \
 277         ph_merge_children(a_type, a_field, ph->ph_root, a_cmp,          \
 278             ph->ph_root);                                               \
 279                                                                         \
 280         return ret;                                                     \
 281 }                                                                       \
 282 a_attr a_type *                                                         \
 283 a_prefix##remove_any(a_ph_type *ph) {                                   \
 284         /*                                                              \
 285          * Remove the most recently inserted aux list element, or the   \
 286          * root if the aux list is empty.  This has the effect of       \
 287          * behaving as a LIFO (and insertion/removal is therefore       \
 288          * constant-time) if a_prefix##[remove_]first() are never       \
 289          * called.                                                      \
 290          */                                                             \
 291         if (ph->ph_root == NULL) {                                      \
 292                 return NULL;                                            \
 293         }                                                               \
 294         a_type *ret = phn_next_get(a_type, a_field, ph->ph_root);       \
 295         if (ret != NULL) {                                              \
 296                 a_type *aux = phn_next_get(a_type, a_field, ret);       \
 297                 phn_next_set(a_type, a_field, ph->ph_root, aux);        \
 298                 if (aux != NULL) {                                      \
 299                         phn_prev_set(a_type, a_field, aux,              \
 300                             ph->ph_root);                               \
 301                 }                                                       \
 302                 return ret;                                             \
 303         }                                                               \
 304         ret = ph->ph_root;                                              \
 305         ph_merge_children(a_type, a_field, ph->ph_root, a_cmp,          \
 306             ph->ph_root);                                               \
 307         return ret;                                                     \
 308 }                                                                       \
 309 a_attr void                                                             \
 310 a_prefix##remove(a_ph_type *ph, a_type *phn) {                          \
 311         a_type *replace, *parent;                                       \
 312                                                                         \
 313         if (ph->ph_root == phn) {                                       \
 314                 /*                                                      \
 315                  * We can delete from aux list without merging it, but  \
 316                  * we need to merge if we are dealing with the root     \
 317                  * node and it has children.                            \
 318                  */                                                     \
 319                 if (phn_lchild_get(a_type, a_field, phn) == NULL) {     \
 320                         ph->ph_root = phn_next_get(a_type, a_field,     \
 321                             phn);                                       \
 322                         if (ph->ph_root != NULL) {                      \
 323                                 phn_prev_set(a_type, a_field,           \
 324                                     ph->ph_root, NULL);                 \
 325                         }                                               \
 326                         return;                                         \
 327                 }                                                       \
 328                 ph_merge_aux(a_type, a_field, ph, a_cmp);               \
 329                 if (ph->ph_root == phn) {                               \
 330                         ph_merge_children(a_type, a_field, ph->ph_root, \
 331                             a_cmp, ph->ph_root);                        \
 332                         return;                                         \
 333                 }                                                       \
 334         }                                                               \
 335                                                                         \
 336         /* Get parent (if phn is leftmost child) before mutating. */    \
 337         if ((parent = phn_prev_get(a_type, a_field, phn)) != NULL) {    \
 338                 if (phn_lchild_get(a_type, a_field, parent) != phn) {   \
 339                         parent = NULL;                                  \
 340                 }                                                       \
 341         }                                                               \
 342         /* Find a possible replacement node, and link to parent. */     \
 343         ph_merge_children(a_type, a_field, phn, a_cmp, replace);        \
 344         /* Set next/prev for sibling linked list. */                    \
 345         if (replace != NULL) {                                          \
 346                 if (parent != NULL) {                                   \
 347                         phn_prev_set(a_type, a_field, replace, parent); \
 348                         phn_lchild_set(a_type, a_field, parent,         \
 349                             replace);                                   \
 350                 } else {                                                \
 351                         phn_prev_set(a_type, a_field, replace,          \
 352                             phn_prev_get(a_type, a_field, phn));        \
 353                         if (phn_prev_get(a_type, a_field, phn) !=       \
 354                             NULL) {                                     \
 355                                 phn_next_set(a_type, a_field,           \
 356                                     phn_prev_get(a_type, a_field, phn), \
 357                                     replace);                           \
 358                         }                                               \
 359                 }                                                       \
 360                 phn_next_set(a_type, a_field, replace,                  \
 361                     phn_next_get(a_type, a_field, phn));                \
 362                 if (phn_next_get(a_type, a_field, phn) != NULL) {       \
 363                         phn_prev_set(a_type, a_field,                   \
 364                             phn_next_get(a_type, a_field, phn),         \
 365                             replace);                                   \
 366                 }                                                       \
 367         } else {                                                        \
 368                 if (parent != NULL) {                                   \
 369                         a_type *next = phn_next_get(a_type, a_field,    \
 370                             phn);                                       \
 371                         phn_lchild_set(a_type, a_field, parent, next);  \
 372                         if (next != NULL) {                             \
 373                                 phn_prev_set(a_type, a_field, next,     \
 374                                     parent);                            \
 375                         }                                               \
 376                 } else {                                                \
 377                         assert(phn_prev_get(a_type, a_field, phn) !=    \
 378                             NULL);                                      \
 379                         phn_next_set(a_type, a_field,                   \
 380                             phn_prev_get(a_type, a_field, phn),         \
 381                             phn_next_get(a_type, a_field, phn));        \
 382                 }                                                       \
 383                 if (phn_next_get(a_type, a_field, phn) != NULL) {       \
 384                         phn_prev_set(a_type, a_field,                   \
 385                             phn_next_get(a_type, a_field, phn),         \
 386                             phn_prev_get(a_type, a_field, phn));        \
 387                 }                                                       \
 388         }                                                               \
 389 }
 390
 391 #endif /* PH_H_ */