Pileus Git - grits/blob - src/gis/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 inline gint
 129 cmp (GPQueue *pqueue,
 130      GPQueueNode *a,
 131      GPQueueNode *b)
 132 {
 133   return pqueue->cmp (a->data, b->data, pqueue->cmpdata);
 134 }
 135
 136 static inline void
 137 g_pqueue_node_cut (GPQueueNode *src)
 138 {
 139   src->prev->next = src->next;
 140   src->next->prev = src->prev;
 141   src->next = src;
 142   src->prev = src;
 143 }
 144
 145 static inline void
 146 g_pqueue_node_insert_before (GPQueueNode *dest,
 147                              GPQueueNode *src)
 148 {
 149   GPQueueNode *prev;
 150
 151   prev = dest->prev;
 152   dest->prev = src->prev;
 153   src->prev->next = dest;
 154   src->prev = prev;
 155   prev->next = src;
 156 }
 157
 158 static inline void
 159 g_pqueue_node_insert_after (GPQueueNode *dest,
 160                             GPQueueNode *src)
 161 {
 162   GPQueueNode *next;
 163
 164   next = dest->next;
 165   dest->next = src;
 166   src->prev->next = next;
 167   next->prev = src->prev;
 168   src->prev = dest;
 169 }
 170
 171 /**
 172  * g_pqueue_push:
 173  * @pqueue: a #GPQueue.
 174  * @data: the object to insert into the priority queue.
 175  *
 176  * Inserts a new entry into a #GPQueue.
 177  *
 178  * The returned handle can be used in calls to g_pqueue_remove() and
 179  * g_pqueue_priority_changed(). Never make such calls for entries that have
 180  * already been removed from the queue. The same @data can be inserted into
 181  * a #GPQueue more than once, but remember that in this case,
 182  * g_pqueue_priority_changed() needs to be called for
 183  * <emphasis>every</emphasis> handle for that object if its priority changes.
 184  *
 185  * Returns: a handle for the freshly inserted entry.
 186  *
 187  * Since: 2.x
 188  **/
 189 GPQueueHandle
 190 g_pqueue_push (GPQueue *pqueue,
 191                gpointer data)
 192 {
 193   GPQueueNode *e;
 194
 195   e = g_slice_new (GPQueueNode);
 196   e->next = e;
 197   e->prev = e;
 198   e->parent = NULL;
 199   e->child = NULL;
 200   e->data = data;
 201   e->degree = 0;
 202   e->marked = FALSE;
 203
 204   if (pqueue->root != NULL) {
 205     g_pqueue_node_insert_before (pqueue->root, e);
 206     if (cmp (pqueue, e, pqueue->root) < 0)
 207       pqueue->root = e;
 208   } else {
 209     pqueue->root = e;
 210   }
 211
 212   return e;
 213 }
 214
 215 /**
 216  * g_pqueue_peek:
 217  * @pqueue: a #GPQueue.
 218  *
 219  * Returns the topmost entry's data pointer, or %NULL if the queue is empty.
 220  *
 221  * If you need to tell the difference between an empty queue and a queue
 222  * that happens to have a %NULL pointer at the top, check if the queue is
 223  * empty first.
 224  *
 225  * Returns: the topmost entry's data pointer, or %NULL if the queue is empty.
 226  *
 227  * Since: 2.x
 228  **/
 229 gpointer
 230 g_pqueue_peek (GPQueue *pqueue)
 231 {
 232   return (pqueue->root != NULL) ? pqueue->root->data : NULL;
 233 }
 234
 235 static inline GPQueueNode*
 236 g_pqueue_make_child (GPQueueNode *a,
 237                      GPQueueNode *b)
 238 {
 239   g_pqueue_node_cut(b);
 240   if (a->child != NULL) {
 241     g_pqueue_node_insert_before (a->child, b);
 242     a->degree += 1;
 243   } else {
 244     a->child = b;
 245     a->degree = 1;
 246   }
 247   b->parent = a;
 248   return a;
 249 }
 250
 251 static inline GPQueueNode*
 252 g_pqueue_join_trees (GPQueue *pqueue,
 253                      GPQueueNode *a,
 254                      GPQueueNode *b)
 255 {
 256   if (cmp (pqueue, a, b) < 0)
 257     return g_pqueue_make_child (a, b);
 258   return g_pqueue_make_child (b, a);
 259 }
 260
 261 static void
 262 g_pqueue_fix_rootlist (GPQueue* pqueue)
 263 {
 264   gsize degnode_size;
 265   GPQueueNode **degnode;
 266   GPQueueNode sentinel;
 267   GPQueueNode *current;
 268   GPQueueNode *minimum;
 269
 270   /* We need to iterate over the circular list we are given and do
 271    * several things:
 272    * - Make sure all the elements are unmarked
 273    * - Make sure to return the element in the list with smallest
 274    *   priority value
 275    * - Find elements of identical degree and join them into trees
 276    * The last point is irrelevant for correctness, but essential
 277    * for performance. If we did not do this, our data structure would
 278    * degrade into an unsorted linked list.
 279    */
 280
 281   degnode_size = (8 * sizeof(gpointer) + 1) * sizeof(gpointer);
 282   degnode = g_slice_alloc0 (degnode_size);
 283
 284   sentinel.next = &sentinel;
 285   sentinel.prev = &sentinel;
 286   g_pqueue_node_insert_before (pqueue->root, &sentinel);
 287
 288   current = pqueue->root;
 289   while (current != &sentinel) {
 290     current->marked = FALSE;
 291     current->parent = NULL;
 292     gint d = current->degree;
 293     if (degnode[d] == NULL) {
 294       degnode[d] = current;
 295       current = current->next;
 296     } else {
 297       if (degnode[d] != current) {
 298         current = g_pqueue_join_trees (pqueue, degnode[d], current);
 299         degnode[d] = NULL;
 300       } else {
 301         current = current->next;
 302       }
 303     }
 304   }
 305
 306   current = sentinel.next;
 307   minimum = current;
 308   while (current != &sentinel) {
 309     if (cmp (pqueue, current, minimum) < 0)
 310       minimum = current;
 311     current = current->next;
 312   }
 313   pqueue->root = minimum;
 314
 315   g_pqueue_node_cut (&sentinel);
 316
 317   g_slice_free1 (degnode_size, degnode);
 318 }
 319
 320 static void
 321 g_pqueue_remove_root (GPQueue *pqueue,
 322                       GPQueueNode *root)
 323 {
 324   /* This removes a node at the root _level_ of the structure, which can be,
 325    * but does not have to be, the actual pqueue->root node. That is why
 326    * we require an explicit pointer to the node to be removed instead of just
 327    * removing pqueue->root implictly.
 328    */
 329
 330   /* Step one:
 331    * If root has any children, pull them up to root level.
 332    * At this time, we only deal with their next/prev pointers,
 333    * further changes are made later in g_pqueue_fix_rootlist().
 334    */
 335   if (root->child) {
 336     g_pqueue_node_insert_after (root, root->child);
 337     root->child = NULL;
 338     root->degree = 0;
 339   }
 340
 341   /* Step two:
 342    * Cut root out of the list.
 343    */
 344   if (root->next != root) {
 345     pqueue->root = root->next;
 346     g_pqueue_node_cut (root);
 347     /* Step three:
 348      * Clean up the remaining list.
 349      */
 350     g_pqueue_fix_rootlist (pqueue);
 351   } else {
 352     pqueue->root = NULL;
 353   }
 354
 355   g_slice_free (GPQueueNode, root);
 356 }
 357
 358 /**
 359  * g_pqueue_pop:
 360  * @pqueue: a #GPQueue.
 361  *
 362  * Removes the topmost entry from a #GPQueue and returns its data pointer.
 363  * Calling this on an empty #GPQueue is not an error, but removes nothing
 364  * and returns %NULL.
 365  *
 366  * If you need to tell the difference between an empty queue and a queue
 367  * that happens to have a %NULL pointer at the top, check if the queue is
 368  * empty first.
 369  *
 370  * Returns: the topmost entry's data pointer, or %NULL if the queue was empty.
 371  *
 372  * Since: 2.x
 373  **/
 374 gpointer
 375 g_pqueue_pop (GPQueue *pqueue)
 376 {
 377   gpointer data;
 378
 379   if (pqueue->root == NULL) return NULL;
 380   data = pqueue->root->data;
 381   g_pqueue_remove_root (pqueue, pqueue->root);
 382   return data;
 383 }
 384
 385 static inline void
 386 g_pqueue_make_root (GPQueue *pqueue,
 387                     GPQueueNode *entry)
 388 {
 389   /* This moves a node up to the root _level_ of the structure.
 390    * It does not always become the actual root element (pqueue->root).
 391    */
 392
 393   GPQueueNode *parent;
 394
 395   parent = entry->parent;
 396   entry->parent = NULL;
 397   entry->marked = FALSE;
 398   if (parent != NULL) {
 399     if (entry->next != entry) {
 400       if (parent->child == entry) parent->child = entry->next;
 401       g_pqueue_node_cut (entry);
 402       parent->degree -= 1;
 403     } else {
 404       parent->child = NULL;
 405       parent->degree = 0;
 406     }
 407     g_pqueue_node_insert_before (pqueue->root, entry);
 408   }
 409
 410   if (cmp (pqueue, entry, pqueue->root) < 0)
 411     pqueue->root = entry;
 412 }
 413
 414 static void
 415 g_pqueue_cut_tree (GPQueue *pqueue,
 416                    GPQueueNode *entry)
 417 {
 418   /* This function moves an entry up to the root level of the structure.
 419    * It extends g_pqueue_make_root() in that the entry's parent, grandparent
 420    * etc. may also be moved to the root level if they are "marked". This is
 421    * not essential for correctness, it just maintains the so-called "potential"
 422    * of the structure, which is necessary for the amortized runtime analysis.
 423    */
 424
 425   GPQueueNode *current;
 426   GPQueueNode *parent;
 427
 428   current = entry;
 429   while ((current != NULL) && (current->parent != NULL)) {
 430     parent = current->parent;
 431     g_pqueue_make_root (pqueue, entry);
 432     if (parent->marked) {
 433       current = parent;
 434     } else {
 435       parent->marked = TRUE;
 436       current = NULL;
 437     }
 438   }
 439   if (cmp (pqueue, entry, pqueue->root) < 0)
 440     pqueue->root = entry;
 441 }
 442
 443 /**
 444  * g_pqueue_remove:
 445  * @pqueue: a #GPQueue.
 446  * @entry: a #GPQueueHandle for an entry in @pqueue.
 447  *
 448  * Removes one entry from a #GPQueue.
 449  *
 450  * Make sure that @entry refers to an entry that is actually part of
 451  * @pqueue at the time, otherwise the behavior of this function is
 452  * undefined (expect crashes).
 453  *
 454  * Since: 2.x
 455  **/
 456 void
 457 g_pqueue_remove (GPQueue* pqueue,
 458                  GPQueueHandle entry)
 459 {
 460   g_pqueue_cut_tree (pqueue, entry);
 461   g_pqueue_remove_root (pqueue, entry);
 462 }
 463
 464 /**
 465  * g_pqueue_priority_changed:
 466  * @pqueue: a #GPQueue.
 467  * @entry: a #GPQueueHandle for an entry in @pqueue.
 468  *
 469  * Notifies the #GPQueue that the priority of one entry has changed.
 470  * The internal representation is updated accordingly.
 471  *
 472  * Make sure that @entry refers to an entry that is actually part of
 473  * @pqueue at the time, otherwise the behavior of this function is
 474  * undefined (expect crashes).
 475  *
 476  * Do not attempt to change the priorities of several entries at once.
 477  * Every time a single object is changed, the #GPQueue needs to be updated
 478  * by calling g_pqueue_priority_changed() for that object.
 479  *
 480  * Since: 2.x
 481  **/
 482 void
 483 g_pqueue_priority_changed (GPQueue* pqueue,
 484                            GPQueueHandle entry)
 485 {
 486   g_pqueue_cut_tree (pqueue, entry);
 487
 488   if (entry->child) {
 489     g_pqueue_node_insert_after (entry, entry->child);
 490     entry->child = NULL;
 491     entry->degree = 0;
 492   }
 493
 494   g_pqueue_fix_rootlist (pqueue);
 495 }
 496
 497 /**
 498  * g_pqueue_priority_decreased:
 499  * @pqueue: a #GPQueue.
 500  * @entry: a #GPQueueHandle for an entry in @pqueue.
 501  *
 502  * Notifies the #GPQueue that the priority of one entry has
 503  * <emphasis>decreased</emphasis>.
 504  *
 505  * This is a special case of g_pqueue_priority_changed(). If you are absolutely
 506  * sure that the new priority of @entry is lower than it was before, you
 507  * may call this function instead of g_pqueue_priority_changed().
 508  *
 509  * <note>
 510  *   <para>
 511  *     In the current implementation, an expensive step in
 512  *     g_pqueue_priority_changed() can be skipped if the new priority is known
 513  *     to be lower, leading to an amortized running time of O(1) instead of
 514  *     O(log n). Of course, if the priority is not actually lower, behavior
 515  *     is undefined.
 516  *   </para>
 517  * </note>
 518  *
 519  * Since: 2.x
 520  **/
 521 void
 522 g_pqueue_priority_decreased (GPQueue* pqueue,
 523                              GPQueueHandle entry)
 524 {
 525   g_pqueue_cut_tree (pqueue, entry);
 526 }
 527
 528 static void
 529 g_pqueue_node_free_all (GPQueueNode *node)
 530 {
 531   if (node == NULL) return;
 532   g_pqueue_node_free_all (node->child);
 533   node->prev->next = NULL;
 534   g_pqueue_node_free_all (node->next);
 535   g_slice_free (GPQueueNode, node);
 536 }
 537
 538 /**
 539  * g_pqueue_clear:
 540  * @pqueue: a #GPQueue.
 541  *
 542  * Removes all entries from a @pqueue.
 543  *
 544  * Since: 2.x
 545  **/
 546 void
 547 g_pqueue_clear (GPQueue* pqueue)
 548 {
 549   g_pqueue_node_free_all (pqueue->root);
 550   pqueue->root = NULL;
 551 }
 552
 553 /**
 554  * g_pqueue_free:
 555  * @pqueue: a #GPQueue.
 556  *
 557  * Deallocates the memory used by @pqueue itself, but not any memory pointed
 558  * to by the data pointers of its entries.
 559  *
 560  * Since: 2.x
 561  **/
 562 void
 563 g_pqueue_free (GPQueue* pqueue)
 564 {
 565   g_pqueue_clear (pqueue);
 566   g_slice_free (GPQueue, pqueue);
 567 }