src/libs/ck-libs/metis/GKlib/gk_mkpqueue.h

   1 /*!
   2 \file  gk_mkpqueue.h
   3 \brief Templates for priority queues
   4
   5 \date   Started 4/09/07
   6 \author George
   7 \version\verbatim $Id: gk_mkpqueue.h 13005 2012-10-23 22:34:36Z karypis $ \endverbatim
   8 */
   9
  10
  11 #ifndef _GK_MKPQUEUE_H
  12 #define _GK_MKPQUEUE_H
  13
  14
  15 #define GK_MKPQUEUE(FPRFX, PQT, KVT, KT, VT, KVMALLOC, KMAX, KEY_LT)\
  16 /*************************************************************************/\
  17 /*! This function creates and initializes a priority queue */\
  18 /**************************************************************************/\
  19 PQT *FPRFX ## Create(size_t maxnodes)\
  20 {\
  21   PQT *queue; \
  22 \
  23   queue = (PQT *)gk_malloc(sizeof(PQT), "gk_pqCreate: queue");\
  24   FPRFX ## Init(queue, maxnodes);\
  25 \
  26   return queue;\
  27 }\
  28 \
  29 \
  30 /*************************************************************************/\
  31 /*! This function initializes the data structures of the priority queue */\
  32 /**************************************************************************/\
  33 void FPRFX ## Init(PQT *queue, size_t maxnodes)\
  34 {\
  35   queue->nnodes = 0;\
  36   queue->maxnodes = maxnodes;\
  37 \
  38   queue->heap    = KVMALLOC(maxnodes, "gk_PQInit: heap");\
  39   queue->locator = gk_idxsmalloc(maxnodes, -1, "gk_PQInit: locator");\
  40 }\
  41 \
  42 \
  43 /*************************************************************************/\
  44 /*! This function resets the priority queue */\
  45 /**************************************************************************/\
  46 void FPRFX ## Reset(PQT *queue)\
  47 {\
  48   gk_idx_t i;\
  49   gk_idx_t *locator=queue->locator;\
  50   KVT *heap=queue->heap;\
  51 \
  52   for (i=queue->nnodes-1; i>=0; i--)\
  53     locator[heap[i].val] = -1;\
  54   queue->nnodes = 0;\
  55 }\
  56 \
  57 \
  58 /*************************************************************************/\
  59 /*! This function frees the internal datastructures of the priority queue */\
  60 /**************************************************************************/\
  61 void FPRFX ## Free(PQT *queue)\
  62 {\
  63   if (queue == NULL) return;\
  64   gk_free((void **)&queue->heap, &queue->locator, LTERM);\
  65   queue->maxnodes = 0;\
  66 }\
  67 \
  68 \
  69 /*************************************************************************/\
  70 /*! This function frees the internal datastructures of the priority queue \
  71     and the queue itself */\
  72 /**************************************************************************/\
  73 void FPRFX ## Destroy(PQT *queue)\
  74 {\
  75   if (queue == NULL) return;\
  76   FPRFX ## Free(queue);\
  77   gk_free((void **)&queue, LTERM);\
  78 }\
  79 \
  80 \
  81 /*************************************************************************/\
  82 /*! This function returns the length of the queue */\
  83 /**************************************************************************/\
  84 size_t FPRFX ## Length(PQT *queue)\
  85 {\
  86   return queue->nnodes;\
  87 }\
  88 \
  89 \
  90 /*************************************************************************/\
  91 /*! This function adds an item in the priority queue */\
  92 /**************************************************************************/\
  93 int FPRFX ## Insert(PQT *queue, VT node, KT key)\
  94 {\
  95   gk_idx_t i, j;\
  96   gk_idx_t *locator=queue->locator;\
  97   KVT *heap=queue->heap;\
  98 \
  99   ASSERT2(FPRFX ## CheckHeap(queue));\
 100 \
 101   ASSERT(locator[node] == -1);\
 102 \
 103   i = queue->nnodes++;\
 104   while (i > 0) {\
 105     j = (i-1)>>1;\
 106     if (KEY_LT(key, heap[j].key)) {\
 107       heap[i] = heap[j];\
 108       locator[heap[i].val] = i;\
 109       i = j;\
 110     }\
 111     else\
 112       break;\
 113   }\
 114   ASSERT(i >= 0);\
 115   heap[i].key   = key;\
 116   heap[i].val   = node;\
 117   locator[node] = i;\
 118 \
 119   ASSERT2(FPRFX ## CheckHeap(queue));\
 120 \
 121   return 0;\
 122 }\
 123 \
 124 \
 125 /*************************************************************************/\
 126 /*! This function deletes an item from the priority queue */\
 127 /**************************************************************************/\
 128 int FPRFX ## Delete(PQT *queue, VT node)\
 129 {\
 130   gk_idx_t i, j, nnodes;\
 131   KT newkey, oldkey;\
 132   gk_idx_t *locator=queue->locator;\
 133   KVT *heap=queue->heap;\
 134 \
 135   ASSERT(locator[node] != -1);\
 136   ASSERT(heap[locator[node]].val == node);\
 137 \
 138   ASSERT2(FPRFX ## CheckHeap(queue));\
 139 \
 140   i = locator[node];\
 141   locator[node] = -1;\
 142 \
 143   if (--queue->nnodes > 0 && heap[queue->nnodes].val != node) {\
 144     node   = heap[queue->nnodes].val;\
 145     newkey = heap[queue->nnodes].key;\
 146     oldkey = heap[i].key;\
 147 \
 148     if (KEY_LT(newkey, oldkey)) { /* Filter-up */\
 149       while (i > 0) {\
 150         j = (i-1)>>1;\
 151         if (KEY_LT(newkey, heap[j].key)) {\
 152           heap[i] = heap[j];\
 153           locator[heap[i].val] = i;\
 154           i = j;\
 155         }\
 156         else\
 157           break;\
 158       }\
 159     }\
 160     else { /* Filter down */\
 161       nnodes = queue->nnodes;\
 162       while ((j=(i<<1)+1) < nnodes) {\
 163         if (KEY_LT(heap[j].key, newkey)) {\
 164           if (j+1 < nnodes && KEY_LT(heap[j+1].key, heap[j].key))\
 165             j++;\
 166           heap[i] = heap[j];\
 167           locator[heap[i].val] = i;\
 168           i = j;\
 169         }\
 170         else if (j+1 < nnodes && KEY_LT(heap[j+1].key, newkey)) {\
 171           j++;\
 172           heap[i] = heap[j];\
 173           locator[heap[i].val] = i;\
 174           i = j;\
 175         }\
 176         else\
 177           break;\
 178       }\
 179     }\
 180 \
 181     heap[i].key   = newkey;\
 182     heap[i].val   = node;\
 183     locator[node] = i;\
 184   }\
 185 \
 186   ASSERT2(FPRFX ## CheckHeap(queue));\
 187 \
 188   return 0;\
 189 }\
 190 \
 191 \
 192 /*************************************************************************/\
 193 /*! This function updates the key values associated for a particular item */ \
 194 /**************************************************************************/\
 195 void FPRFX ## Update(PQT *queue, VT node, KT newkey)\
 196 {\
 197   gk_idx_t i, j, nnodes;\
 198   KT oldkey;\
 199   gk_idx_t *locator=queue->locator;\
 200   KVT *heap=queue->heap;\
 201 \
 202   oldkey = heap[locator[node]].key;\
 203 \
 204   ASSERT(locator[node] != -1);\
 205   ASSERT(heap[locator[node]].val == node);\
 206   ASSERT2(FPRFX ## CheckHeap(queue));\
 207 \
 208   i = locator[node];\
 209 \
 210   if (KEY_LT(newkey, oldkey)) { /* Filter-up */\
 211     while (i > 0) {\
 212       j = (i-1)>>1;\
 213       if (KEY_LT(newkey, heap[j].key)) {\
 214         heap[i] = heap[j];\
 215         locator[heap[i].val] = i;\
 216         i = j;\
 217       }\
 218       else\
 219         break;\
 220     }\
 221   }\
 222   else { /* Filter down */\
 223     nnodes = queue->nnodes;\
 224     while ((j=(i<<1)+1) < nnodes) {\
 225       if (KEY_LT(heap[j].key, newkey)) {\
 226         if (j+1 < nnodes && KEY_LT(heap[j+1].key, heap[j].key))\
 227           j++;\
 228         heap[i] = heap[j];\
 229         locator[heap[i].val] = i;\
 230         i = j;\
 231       }\
 232       else if (j+1 < nnodes && KEY_LT(heap[j+1].key, newkey)) {\
 233         j++;\
 234         heap[i] = heap[j];\
 235         locator[heap[i].val] = i;\
 236         i = j;\
 237       }\
 238       else\
 239         break;\
 240     }\
 241   }\
 242 \
 243   heap[i].key   = newkey;\
 244   heap[i].val   = node;\
 245   locator[node] = i;\
 246 \
 247   ASSERT2(FPRFX ## CheckHeap(queue));\
 248 \
 249   return;\
 250 }\
 251 \
 252 \
 253 /*************************************************************************/\
 254 /*! This function returns the item at the top of the queue and removes\
 255     it from the priority queue */\
 256 /**************************************************************************/\
 257 VT FPRFX ## GetTop(PQT *queue)\
 258 {\
 259   gk_idx_t i, j;\
 260   gk_idx_t *locator;\
 261   KVT *heap;\
 262   VT vtx, node;\
 263   KT key;\
 264 \
 265   ASSERT2(FPRFX ## CheckHeap(queue));\
 266 \
 267   if (queue->nnodes == 0)\
 268     return -1;\
 269 \
 270   queue->nnodes--;\
 271 \
 272   heap    = queue->heap;\
 273   locator = queue->locator;\
 274 \
 275   vtx = heap[0].val;\
 276   locator[vtx] = -1;\
 277 \
 278   if ((i = queue->nnodes) > 0) {\
 279     key  = heap[i].key;\
 280     node = heap[i].val;\
 281     i = 0;\
 282     while ((j=2*i+1) < queue->nnodes) {\
 283       if (KEY_LT(heap[j].key, key)) {\
 284         if (j+1 < queue->nnodes && KEY_LT(heap[j+1].key, heap[j].key))\
 285           j = j+1;\
 286         heap[i] = heap[j];\
 287         locator[heap[i].val] = i;\
 288         i = j;\
 289       }\
 290       else if (j+1 < queue->nnodes && KEY_LT(heap[j+1].key, key)) {\
 291         j = j+1;\
 292         heap[i] = heap[j];\
 293         locator[heap[i].val] = i;\
 294         i = j;\
 295       }\
 296       else\
 297         break;\
 298     }\
 299 \
 300     heap[i].key   = key;\
 301     heap[i].val   = node;\
 302     locator[node] = i;\
 303   }\
 304 \
 305   ASSERT2(FPRFX ## CheckHeap(queue));\
 306   return vtx;\
 307 }\
 308 \
 309 \
 310 /*************************************************************************/\
 311 /*! This function returns the item at the top of the queue. The item is not\
 312     deleted from the queue. */\
 313 /**************************************************************************/\
 314 VT FPRFX ## SeeTopVal(PQT *queue)\
 315 {\
 316   return (queue->nnodes == 0 ? -1 : queue->heap[0].val);\
 317 }\
 318 \
 319 \
 320 /*************************************************************************/\
 321 /*! This function returns the key of the top item. The item is not\
 322     deleted from the queue. */\
 323 /**************************************************************************/\
 324 KT FPRFX ## SeeTopKey(PQT *queue)\
 325 {\
 326   return (queue->nnodes == 0 ? KMAX : queue->heap[0].key);\
 327 }\
 328 \
 329 \
 330 /*************************************************************************/\
 331 /*! This function returns the key of a specific item */\
 332 /**************************************************************************/\
 333 KT FPRFX ## SeeKey(PQT *queue, VT node)\
 334 {\
 335   gk_idx_t *locator;\
 336   KVT *heap;\
 337 \
 338   heap    = queue->heap;\
 339   locator = queue->locator;\
 340 \
 341   return heap[locator[node]].key;\
 342 }\
 343 \
 344 \
 345 /*************************************************************************/\
 346 /*! This function returns the first item in a breadth-first traversal of\
 347     the heap whose key is less than maxwgt. This function is here due to\
 348     hMETIS and is not general!*/\
 349 /**************************************************************************/\
 350 /*\
 351 VT FPRFX ## SeeConstraintTop(PQT *queue, KT maxwgt, KT *wgts)\
 352 {\
 353   gk_idx_t i;\
 354 \
 355   if (queue->nnodes == 0)\
 356     return -1;\
 357 \
 358   if (maxwgt <= 1000)\
 359     return FPRFX ## SeeTopVal(queue);\
 360 \
 361   for (i=0; i<queue->nnodes; i++) {\
 362     if (queue->heap[i].key > 0) {\
 363       if (wgts[queue->heap[i].val] <= maxwgt)\
 364         return queue->heap[i].val;\
 365     }\
 366     else {\
 367       if (queue->heap[i/2].key <= 0)\
 368         break;\
 369     }\
 370   }\
 371 \
 372   return queue->heap[0].val;\
 373 \
 374 }\
 375 */\
 376 \
 377 \
 378 /*************************************************************************/\
 379 /*! This functions checks the consistency of the heap */\
 380 /**************************************************************************/\
 381 int FPRFX ## CheckHeap(PQT *queue)\
 382 {\
 383   gk_idx_t i, j;\
 384   size_t nnodes;\
 385   gk_idx_t *locator;\
 386   KVT *heap;\
 387 \
 388   heap    = queue->heap;\
 389   locator = queue->locator;\
 390   nnodes  = queue->nnodes;\
 391 \
 392   if (nnodes == 0)\
 393     return 1;\
 394 \
 395   ASSERT(locator[heap[0].val] == 0);\
 396   for (i=1; i<nnodes; i++) {\
 397     ASSERT(locator[heap[i].val] == i);\
 398     ASSERT(!KEY_LT(heap[i].key, heap[(i-1)/2].key));\
 399   }\
 400   for (i=1; i<nnodes; i++)\
 401     ASSERT(!KEY_LT(heap[i].key, heap[0].key));\
 402 \
 403   for (j=i=0; i<queue->maxnodes; i++) {\
 404     if (locator[i] != -1)\
 405       j++;\
 406   }\
 407   ASSERTP(j == nnodes, ("%jd %jd\n", (intmax_t)j, (intmax_t)nnodes));\
 408 \
 409   return 1;\
 410 }\
 411
 412
 413 #define GK_MKPQUEUE_PROTO(FPRFX, PQT, KT, VT)\
 414   PQT *  FPRFX ## Create(size_t maxnodes);\
 415   void   FPRFX ## Init(PQT *queue, size_t maxnodes);\
 416   void   FPRFX ## Reset(PQT *queue);\
 417   void   FPRFX ## Free(PQT *queue);\
 418   void   FPRFX ## Destroy(PQT *queue);\
 419   size_t FPRFX ## Length(PQT *queue);\
 420   int    FPRFX ## Insert(PQT *queue, VT node, KT key);\
 421   int    FPRFX ## Delete(PQT *queue, VT node);\
 422   void   FPRFX ## Update(PQT *queue, VT node, KT newkey);\
 423   VT     FPRFX ## GetTop(PQT *queue);\
 424   VT     FPRFX ## SeeTopVal(PQT *queue);\
 425   KT     FPRFX ## SeeTopKey(PQT *queue);\
 426   KT     FPRFX ## SeeKey(PQT *queue, VT node);\
 427   VT     FPRFX ## SeeConstraintTop(PQT *queue, KT maxwgt, KT *wgts);\
 428   int    FPRFX ## CheckHeap(PQT *queue);\
 429
 430
 431 /* This is how these macros are used
 432 GK_MKPQUEUE(gk_dkvPQ, gk_dkvPQ_t, double, gk_idx_t, gk_dkvmalloc, DBL_MAX)
 433 GK_MKPQUEUE_PROTO(gk_dkvPQ, gk_dkvPQ_t, double, gk_idx_t)
 434 */
 435
 436
 437 #endif