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

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