Pileus Git - grits/blob - src/gpqueue.c

   1 #include <glib.h>
   2 #include "gpqueue.h"
   3
   4 /**
   5  * SECTION:gpqueue
   6  * @short_description: Priority queue implemention
   7  *
   8  * <para>
   9  * The #GPQueue structure and its associated functions provide a sorted
  10  * collection of objects. Entries can be inserted in any order and at any time,
  11  * and an entry's priority can be changed after it has been inserted into the
  12  * queue. Entries are supposed to be removed one at a time in order of priority
  13  * with g_pqueue_pop(), but deleting entries out of order is possible.
  14  * </para>
  15  * <para>
  16  * The entries <emphasis>cannot</emphasis> be iterated over in any way other
  17  * than removing them one by one in order of priority, but when doing that,
  18  * this structure is far more efficient than sorted lists or balanced trees,
  19  * which on the other hand do not suffer from this restriction.
  20  * </para>
  21  * <para>
  22  * You will want to be very careful with calls that use #GPQueueHandle.
  23  * Handles immediately become invalid when an entry is removed from a #GPQueue,
  24  * but the current implementation cannot detect this and will do unfortunate
  25  * things to undefined memory locations if you try to use an invalid handle.
  26  * </para>
  27  * <note>
  28  *   <para>
  29  *     Internally, #GPQueue currently uses a Fibonacci heap to store
  30  *     the entries. This implementation detail may change.
  31  *   </para>
  32  * </note>
  33  **/
  34
  35 struct _GPQueueNode {
  36   GPQueueNode *next;
  37   GPQueueNode *prev;
  38   GPQueueNode *parent;
  39   GPQueueNode *child;
  40
  41   gpointer data;
  42
  43   gint degree;
  44   gboolean marked;
  45 };
  46
  47 struct _GPQueue {
  48   GPQueueNode *root;
  49   GCompareDataFunc cmp;
  50   gpointer *cmpdata;
  51 };
  52
  53 /**
  54  * g_pqueue_new:
  55  * @compare_func: the #GCompareDataFunc used to sort the new priority queue.
  56  *   This function is passed two elements of the queue and should return 0 if
  57  *   they are equal, a negative value if the first comes before the second, and
  58  *   a positive value if the second comes before the first.
  59  * @compare_userdata: user data passed to @compare_func
  60  *
  61  * Creates a new #GPQueue.
  62  *
  63  * Returns: a new #GPQueue.
  64  *
  65  * Since: 2.x
  66  **/
  67 GPQueue*
  68 g_pqueue_new (GCompareDataFunc compare_func,
  69               gpointer *compare_userdata)
  70 {
  71   g_return_val_if_fail (compare_func != NULL, NULL);
  72
  73   GPQueue *pqueue = g_slice_new (GPQueue);
  74   pqueue->root = NULL;
  75   pqueue->cmp = compare_func;
  76   pqueue->cmpdata = compare_userdata;
  77   return pqueue;
  78 }
  79
  80 /**
  81  * g_pqueue_is_empty:
  82  * @pqueue: a #GPQueue.
  83  *
  84  * Returns %TRUE if the queue is empty.
  85  *
  86  * Returns: %TRUE if the queue is empty.
  87  *
  88  * Since: 2.x
  89  **/
  90 gboolean
  91 g_pqueue_is_empty (GPQueue *pqueue)
  92 {
  93   return (pqueue->root == NULL);
  94 }
  95
  96 static void
  97 g_pqueue_node_foreach (GPQueueNode *node,
  98                        GPQueueNode *stop,
  99                        GFunc func,
 100                        gpointer user_data)
 101 {
 102   if (node == NULL || node == stop) return;
 103   func(node->data, user_data);
 104   if (stop == NULL) stop = node;
 105   g_pqueue_node_foreach (node->next,  stop, func, user_data);
 106   g_pqueue_node_foreach (node->child, NULL, func, user_data);
 107 }
 108
 109 /**
 110  * g_pqueue_foreach:
 111  * @pqueue: a #GQueue.
 112  * @func: the function to call for each element's data
 113  * @user_data: user data to pass to func
 114  *
 115  * Calls func for each element in the pqueue passing user_data to the function.
 116  *
 117  * Since: 2.x
 118  */
 119 void
 120 g_pqueue_foreach (GPQueue *pqueue,
 121                   GFunc func,
 122                   gpointer user_data)
 123 {
 124   g_pqueue_node_foreach (pqueue->root, NULL, func, user_data);
 125 }
 126
 127 static void
 128 g_pqueue_add_ptr_cb (gpointer obj, GPtrArray *ptrs)
 129 {
 130         g_ptr_array_add(ptrs, obj);
 131 }
 132 /**
 133  * g_pqueue_get_array:
 134  * @pqueue: a #GQueue.
 135  *
 136  * Construct a GPtrArray for the items in pqueue. This can be useful when
 137  * updating the priorities of all the elements in pqueue.
 138  *
 139  * Returns: A GPtrArray containing a pointer to each item in pqueue
 140  *
 141  * Since: 2.x
 142  */
 143 GPtrArray *
 144 g_pqueue_get_array (GPQueue *pqueue)
 145 {
 146         GPtrArray *ptrs = g_ptr_array_new();
 147         g_pqueue_foreach(pqueue, (GFunc)g_pqueue_add_ptr_cb, ptrs);
 148         return ptrs;
 149 }
 150
 151 static inline gint
 152 cmp (GPQueue *pqueue,
 153      GPQueueNode *a,
 154      GPQueueNode *b)
 155 {
 156   return pqueue->cmp (a->data, b->data, pqueue->cmpdata);
 157 }
 158
 159 static inline void
 160 g_pqueue_node_cut (GPQueueNode *src)
 161 {
 162   src->prev->next = src->next;
 163   src->next->prev = src->prev;
 164   src->next = src;
 165   src->prev = src;
 166 }
 167
 168 static inline void
 169 g_pqueue_node_insert_before (GPQueueNode *dest,
 170                              GPQueueNode *src)
 171 {
 172   GPQueueNode *prev;
 173
 174   prev = dest->prev;
 175   dest->prev = src->prev;
 176   src->prev->next = dest;
 177   src->prev = prev;
 178   prev->next = src;
 179 }
 180
 181 static inline void
 182 g_pqueue_node_insert_after (GPQueueNode *dest,
 183                             GPQueueNode *src)
 184 {
 185   GPQueueNode *next;
 186
 187   next = dest->next;
 188   dest->next = src;
 189   src->prev->next = next;
 190   next->prev = src->prev;
 191   src->prev = dest;
 192 }
 193
 194 /**
 195  * g_pqueue_push:
 196  * @pqueue: a #GPQueue.
 197  * @data: the object to insert into the priority queue.
 198  *
 199  * Inserts a new entry into a #GPQueue.
 200  *
 201  * The returned handle can be used in calls to g_pqueue_remove() and
 202  * g_pqueue_priority_changed(). Never make such calls for entries that have
 203  * already been removed from the queue. The same @data can be inserted into
 204  * a #GPQueue more than once, but remember that in this case,
 205  * g_pqueue_priority_changed() needs to be called for
 206  * <emphasis>every</emphasis> handle for that object if its priority changes.
 207  *
 208  * Returns: a handle for the freshly inserted entry.
 209  *
 210  * Since: 2.x
 211  **/
 212 GPQueueHandle
 213 g_pqueue_push (GPQueue *pqueue,
 214                gpointer data)
 215 {
 216   GPQueueNode *e;
 217
 218   e = g_slice_new (GPQueueNode);
 219   e->next = e;
 220   e->prev = e;
 221   e->parent = NULL;
 222   e->child = NULL;
 223   e->data = data;
 224   e->degree = 0;
 225   e->marked = FALSE;
 226
 227   if (pqueue->root != NULL) {
 228     g_pqueue_node_insert_before (pqueue->root, e);
 229     if (cmp (pqueue, e, pqueue->root) < 0)
 230       pqueue->root = e;
 231   } else {
 232     pqueue->root = e;
 233   }
 234
 235   return e;
 236 }
 237
 238 /**
 239  * g_pqueue_peek:
 240  * @pqueue: a #GPQueue.
 241  *
 242  * Returns the topmost entry's data pointer, or %NULL if the queue is empty.
 243  *
 244  * If you need to tell the difference between an empty queue and a queue
 245  * that happens to have a %NULL pointer at the top, check if the queue is
 246  * empty first.
 247  *
 248  * Returns: the topmost entry's data pointer, or %NULL if the queue is empty.
 249  *
 250  * Since: 2.x
 251  **/
 252 gpointer
 253 g_pqueue_peek (GPQueue *pqueue)
 254 {
 255   return (pqueue->root != NULL) ? pqueue->root->data : NULL;
 256 }
 257
 258 static inline GPQueueNode*
 259 g_pqueue_make_child (GPQueueNode *a,
 260                      GPQueueNode *b)
 261 {
 262   g_pqueue_node_cut(b);
 263   if (a->child != NULL) {
 264     g_pqueue_node_insert_before (a->child, b);
 265     a->degree += 1;
 266   } else {
 267     a->child = b;
 268     a->degree = 1;
 269   }
 270   b->parent = a;
 271   return a;
 272 }
 273
 274 static inline GPQueueNode*
 275 g_pqueue_join_trees (GPQueue *pqueue,
 276                      GPQueueNode *a,
 277                      GPQueueNode *b)
 278 {
 279   if (cmp (pqueue, a, b) < 0)
 280     return g_pqueue_make_child (a, b);
 281   return g_pqueue_make_child (b, a);
 282 }
 283
 284 static void
 285 g_pqueue_fix_rootlist (GPQueue* pqueue)
 286 {
 287   gsize degnode_size;
 288   GPQueueNode **degnode;
 289   GPQueueNode sentinel;
 290   GPQueueNode *current;
 291   GPQueueNode *minimum;
 292
 293   /* We need to iterate over the circular list we are given and do
 294    * several things:
 295    * - Make sure all the elements are unmarked
 296    * - Make sure to return the element in the list with smallest
 297    *   priority value
 298    * - Find elements of identical degree and join them into trees
 299    * The last point is irrelevant for correctness, but essential
 300    * for performance. If we did not do this, our data structure would
 301    * degrade into an unsorted linked list.
 302    */
 303
 304   degnode_size = (8 * sizeof(gpointer) + 1) * sizeof(gpointer);
 305   degnode = g_slice_alloc0 (degnode_size);
 306
 307   sentinel.next = &sentinel;
 308   sentinel.prev = &sentinel;
 309   g_pqueue_node_insert_before (pqueue->root, &sentinel);
 310
 311   current = pqueue->root;
 312   while (current != &sentinel) {
 313     current->marked = FALSE;
 314     current->parent = NULL;
 315     gint d = current->degree;
 316     if (degnode[d] == NULL) {
 317       degnode[d] = current;
 318       current = current->next;
 319     } else {
 320       if (degnode[d] != current) {
 321         current = g_pqueue_join_trees (pqueue, degnode[d], current);
 322         degnode[d] = NULL;
 323       } else {
 324         current = current->next;
 325       }
 326     }
 327   }
 328
 329   current = sentinel.next;
 330   minimum = current;
 331   while (current != &sentinel) {
 332     if (cmp (pqueue, current, minimum) < 0)
 333       minimum = current;
 334     current = current->next;
 335   }
 336   pqueue->root = minimum;
 337
 338   g_pqueue_node_cut (&sentinel);
 339
 340   g_slice_free1 (degnode_size, degnode);
 341 }
 342
 343 static void
 344 g_pqueue_remove_root (GPQueue *pqueue,
 345                       GPQueueNode *root)
 346 {
 347   /* This removes a node at the root _level_ of the structure, which can be,
 348    * but does not have to be, the actual pqueue->root node. That is why
 349    * we require an explicit pointer to the node to be removed instead of just
 350    * removing pqueue->root implictly.
 351    */
 352
 353   /* Step one:
 354    * If root has any children, pull them up to root level.
 355    * At this time, we only deal with their next/prev pointers,
 356    * further changes are made later in g_pqueue_fix_rootlist().
 357    */
 358   if (root->child) {
 359     g_pqueue_node_insert_after (root, root->child);
 360     root->child = NULL;
 361     root->degree = 0;
 362   }
 363
 364   /* Step two:
 365    * Cut root out of the list.
 366    */
 367   if (root->next != root) {
 368     pqueue->root = root->next;
 369     g_pqueue_node_cut (root);
 370     /* Step three:
 371      * Clean up the remaining list.
 372      */
 373     g_pqueue_fix_rootlist (pqueue);
 374   } else {
 375     pqueue->root = NULL;
 376   }
 377
 378   g_slice_free (GPQueueNode, root);
 379 }
 380
 381 /**
 382  * g_pqueue_pop:
 383  * @pqueue: a #GPQueue.
 384  *
 385  * Removes the topmost entry from a #GPQueue and returns its data pointer.
 386  * Calling this on an empty #GPQueue is not an error, but removes nothing
 387  * and returns %NULL.
 388  *
 389  * If you need to tell the difference between an empty queue and a queue
 390  * that happens to have a %NULL pointer at the top, check if the queue is
 391  * empty first.
 392  *
 393  * Returns: the topmost entry's data pointer, or %NULL if the queue was empty.
 394  *
 395  * Since: 2.x
 396  **/
 397 gpointer
 398 g_pqueue_pop (GPQueue *pqueue)
 399 {
 400   gpointer data;
 401
 402   if (pqueue->root == NULL) return NULL;
 403   data = pqueue->root->data;
 404   g_pqueue_remove_root (pqueue, pqueue->root);
 405   return data;
 406 }
 407
 408 static inline void
 409 g_pqueue_make_root (GPQueue *pqueue,
 410                     GPQueueNode *entry)
 411 {
 412   /* This moves a node up to the root _level_ of the structure.
 413    * It does not always become the actual root element (pqueue->root).
 414    */
 415
 416   GPQueueNode *parent;
 417
 418   parent = entry->parent;
 419   entry->parent = NULL;
 420   entry->marked = FALSE;
 421   if (parent != NULL) {
 422     if (entry->next != entry) {
 423       if (parent->child == entry) parent->child = entry->next;
 424       g_pqueue_node_cut (entry);
 425       parent->degree -= 1;
 426     } else {
 427       parent->child = NULL;
 428       parent->degree = 0;
 429     }
 430     g_pqueue_node_insert_before (pqueue->root, entry);
 431   }
 432
 433   if (cmp (pqueue, entry, pqueue->root) < 0)
 434     pqueue->root = entry;
 435 }
 436
 437 static void
 438 g_pqueue_cut_tree (GPQueue *pqueue,
 439                    GPQueueNode *entry)
 440 {
 441   /* This function moves an entry up to the root level of the structure.
 442    * It extends g_pqueue_make_root() in that the entry's parent, grandparent
 443    * etc. may also be moved to the root level if they are "marked". This is
 444    * not essential for correctness, it just maintains the so-called "potential"
 445    * of the structure, which is necessary for the amortized runtime analysis.
 446    */
 447
 448   GPQueueNode *current;
 449   GPQueueNode *parent;
 450
 451   current = entry;
 452   while ((current != NULL) && (current->parent != NULL)) {
 453     parent = current->parent;
 454     g_pqueue_make_root (pqueue, entry);
 455     if (parent->marked) {
 456       current = parent;
 457     } else {
 458       parent->marked = TRUE;
 459       current = NULL;
 460     }
 461   }
 462   if (cmp (pqueue, entry, pqueue->root) < 0)
 463     pqueue->root = entry;
 464 }
 465
 466 /**
 467  * g_pqueue_remove:
 468  * @pqueue: a #GPQueue.
 469  * @entry: a #GPQueueHandle for an entry in @pqueue.
 470  *
 471  * Removes one entry from a #GPQueue.
 472  *
 473  * Make sure that @entry refers to an entry that is actually part of
 474  * @pqueue at the time, otherwise the behavior of this function is
 475  * undefined (expect crashes).
 476  *
 477  * Since: 2.x
 478  **/
 479 void
 480 g_pqueue_remove (GPQueue* pqueue,
 481                  GPQueueHandle entry)
 482 {
 483   g_pqueue_cut_tree (pqueue, entry);
 484   g_pqueue_remove_root (pqueue, entry);
 485 }
 486
 487 /**
 488  * g_pqueue_priority_changed:
 489  * @pqueue: a #GPQueue.
 490  * @entry: a #GPQueueHandle for an entry in @pqueue.
 491  *
 492  * Notifies the #GPQueue that the priority of one entry has changed.
 493  * The internal representation is updated accordingly.
 494  *
 495  * Make sure that @entry refers to an entry that is actually part of
 496  * @pqueue at the time, otherwise the behavior of this function is
 497  * undefined (expect crashes).
 498  *
 499  * Do not attempt to change the priorities of several entries at once.
 500  * Every time a single object is changed, the #GPQueue needs to be updated
 501  * by calling g_pqueue_priority_changed() for that object.
 502  *
 503  * Since: 2.x
 504  **/
 505 void
 506 g_pqueue_priority_changed (GPQueue* pqueue,
 507                            GPQueueHandle entry)
 508 {
 509   g_pqueue_cut_tree (pqueue, entry);
 510
 511   if (entry->child) {
 512     g_pqueue_node_insert_after (entry, entry->child);
 513     entry->child = NULL;
 514     entry->degree = 0;
 515   }
 516
 517   g_pqueue_fix_rootlist (pqueue);
 518 }
 519
 520 /**
 521  * g_pqueue_priority_decreased:
 522  * @pqueue: a #GPQueue.
 523  * @entry: a #GPQueueHandle for an entry in @pqueue.
 524  *
 525  * Notifies the #GPQueue that the priority of one entry has
 526  * <emphasis>decreased</emphasis>.
 527  *
 528  * This is a special case of g_pqueue_priority_changed(). If you are absolutely
 529  * sure that the new priority of @entry is lower than it was before, you
 530  * may call this function instead of g_pqueue_priority_changed().
 531  *
 532  * <note>
 533  *   <para>
 534  *     In the current implementation, an expensive step in
 535  *     g_pqueue_priority_changed() can be skipped if the new priority is known
 536  *     to be lower, leading to an amortized running time of O(1) instead of
 537  *     O(log n). Of course, if the priority is not actually lower, behavior
 538  *     is undefined.
 539  *   </para>
 540  * </note>
 541  *
 542  * Since: 2.x
 543  **/
 544 void
 545 g_pqueue_priority_decreased (GPQueue* pqueue,
 546                              GPQueueHandle entry)
 547 {
 548   g_pqueue_cut_tree (pqueue, entry);
 549 }
 550
 551 static void
 552 g_pqueue_node_free_all (GPQueueNode *node)
 553 {
 554   if (node == NULL) return;
 555   g_pqueue_node_free_all (node->child);
 556   node->prev->next = NULL;
 557   g_pqueue_node_free_all (node->next);
 558   g_slice_free (GPQueueNode, node);
 559 }
 560
 561 /**
 562  * g_pqueue_clear:
 563  * @pqueue: a #GPQueue.
 564  *
 565  * Removes all entries from a @pqueue.
 566  *
 567  * Since: 2.x
 568  **/
 569 void
 570 g_pqueue_clear (GPQueue* pqueue)
 571 {
 572   g_pqueue_node_free_all (pqueue->root);
 573   pqueue->root = NULL;
 574 }
 575
 576 /**
 577  * g_pqueue_free:
 578  * @pqueue: a #GPQueue.
 579  *
 580  * Deallocates the memory used by @pqueue itself, but not any memory pointed
 581  * to by the data pointers of its entries.
 582  *
 583  * Since: 2.x
 584  **/
 585 void
 586 g_pqueue_free (GPQueue* pqueue)
 587 {
 588   g_pqueue_clear (pqueue);
 589   g_slice_free (GPQueue, pqueue);
 590 }