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
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.
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.
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.
30 * Internally, #GPQueue currently uses a Fibonacci heap to store
31 * the entries. This implementation detail may change.
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
62 * Creates a new #GPQueue.
64 * Returns: a new #GPQueue.
69 g_pqueue_new (GCompareDataFunc compare_func,
70 gpointer *compare_userdata)
72 g_return_val_if_fail (compare_func != NULL, NULL);
74 GPQueue *pqueue = g_slice_new (GPQueue);
76 pqueue->cmp = compare_func;
77 pqueue->cmpdata = compare_userdata;
83 * @pqueue: a #GPQueue.
85 * Returns %TRUE if the queue is empty.
87 * Returns: %TRUE if the queue is empty.
92 g_pqueue_is_empty (GPQueue *pqueue)
94 return (pqueue->root == NULL);
98 g_pqueue_node_foreach (GPQueueNode *node,
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);
112 * @pqueue: a #GQueue.
113 * @func: the function to call for each element's data
114 * @user_data: user data to pass to func
116 * Calls func for each element in the pqueue passing user_data to the function.
121 g_pqueue_foreach (GPQueue *pqueue,
125 g_pqueue_node_foreach (pqueue->root, NULL, func, user_data);
129 g_pqueue_add_ptr_cb (gpointer obj, GPtrArray *ptrs)
131 g_ptr_array_add(ptrs, obj);
134 * g_pqueue_get_array:
135 * @pqueue: a #GQueue.
137 * Construct a GPtrArray for the items in pqueue. This can be useful when
138 * updating the priorities of all the elements in pqueue.
140 * Returns: A GPtrArray containing a pointer to each item in pqueue
145 g_pqueue_get_array (GPQueue *pqueue)
147 GPtrArray *ptrs = g_ptr_array_new();
148 g_pqueue_foreach(pqueue, (GFunc)g_pqueue_add_ptr_cb, ptrs);
153 cmp (GPQueue *pqueue,
157 return pqueue->cmp (a->data, b->data, pqueue->cmpdata);
161 g_pqueue_node_cut (GPQueueNode *src)
163 src->prev->next = src->next;
164 src->next->prev = src->prev;
170 g_pqueue_node_insert_before (GPQueueNode *dest,
176 dest->prev = src->prev;
177 src->prev->next = dest;
183 g_pqueue_node_insert_after (GPQueueNode *dest,
190 src->prev->next = next;
191 next->prev = src->prev;
197 * @pqueue: a #GPQueue.
198 * @data: the object to insert into the priority queue.
200 * Inserts a new entry into a #GPQueue.
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.
209 * Returns: a handle for the freshly inserted entry.
214 g_pqueue_push (GPQueue *pqueue,
219 e = g_slice_new (GPQueueNode);
228 if (pqueue->root != NULL) {
229 g_pqueue_node_insert_before (pqueue->root, e);
230 if (cmp (pqueue, e, pqueue->root) < 0)
241 * @pqueue: a #GPQueue.
243 * Returns the topmost entry's data pointer, or %NULL if the queue is empty.
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
249 * Returns: the topmost entry's data pointer, or %NULL if the queue is empty.
254 g_pqueue_peek (GPQueue *pqueue)
256 return (pqueue->root != NULL) ? pqueue->root->data : NULL;
259 static inline GPQueueNode*
260 g_pqueue_make_child (GPQueueNode *a,
263 g_pqueue_node_cut(b);
264 if (a->child != NULL) {
265 g_pqueue_node_insert_before (a->child, b);
275 static inline GPQueueNode*
276 g_pqueue_join_trees (GPQueue *pqueue,
280 if (cmp (pqueue, a, b) < 0)
281 return g_pqueue_make_child (a, b);
282 return g_pqueue_make_child (b, a);
286 g_pqueue_fix_rootlist (GPQueue* pqueue)
289 GPQueueNode **degnode;
290 GPQueueNode sentinel;
291 GPQueueNode *current;
292 GPQueueNode *minimum;
294 /* We need to iterate over the circular list we are given and do
296 * - Make sure all the elements are unmarked
297 * - Make sure to return the element in the list with smallest
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.
305 degnode_size = (8 * sizeof(gpointer) + 1) * sizeof(gpointer);
306 degnode = g_slice_alloc0 (degnode_size);
308 sentinel.next = &sentinel;
309 sentinel.prev = &sentinel;
310 g_pqueue_node_insert_before (pqueue->root, &sentinel);
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;
321 if (degnode[d] != current) {
322 current = g_pqueue_join_trees (pqueue, degnode[d], current);
325 current = current->next;
330 current = sentinel.next;
332 while (current != &sentinel) {
333 if (cmp (pqueue, current, minimum) < 0)
335 current = current->next;
337 pqueue->root = minimum;
339 g_pqueue_node_cut (&sentinel);
341 g_slice_free1 (degnode_size, degnode);
345 g_pqueue_remove_root (GPQueue *pqueue,
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.
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().
360 g_pqueue_node_insert_after (root, root->child);
366 * Cut root out of the list.
368 if (root->next != root) {
369 pqueue->root = root->next;
370 g_pqueue_node_cut (root);
372 * Clean up the remaining list.
374 g_pqueue_fix_rootlist (pqueue);
379 g_slice_free (GPQueueNode, root);
384 * @pqueue: a #GPQueue.
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
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
394 * Returns: the topmost entry's data pointer, or %NULL if the queue was empty.
399 g_pqueue_pop (GPQueue *pqueue)
403 if (pqueue->root == NULL) return NULL;
404 data = pqueue->root->data;
405 g_pqueue_remove_root (pqueue, pqueue->root);
410 g_pqueue_make_root (GPQueue *pqueue,
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).
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);
428 parent->child = NULL;
431 g_pqueue_node_insert_before (pqueue->root, entry);
434 if (cmp (pqueue, entry, pqueue->root) < 0)
435 pqueue->root = entry;
439 g_pqueue_cut_tree (GPQueue *pqueue,
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.
449 GPQueueNode *current;
453 while ((current != NULL) && (current->parent != NULL)) {
454 parent = current->parent;
455 g_pqueue_make_root (pqueue, entry);
456 if (parent->marked) {
459 parent->marked = TRUE;
463 if (cmp (pqueue, entry, pqueue->root) < 0)
464 pqueue->root = entry;
469 * @pqueue: a #GPQueue.
470 * @entry: a #GPQueueHandle for an entry in @pqueue.
472 * Removes one entry from a #GPQueue.
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).
481 g_pqueue_remove (GPQueue* pqueue,
484 g_pqueue_cut_tree (pqueue, entry);
485 g_pqueue_remove_root (pqueue, entry);
489 * g_pqueue_priority_changed:
490 * @pqueue: a #GPQueue.
491 * @entry: a #GPQueueHandle for an entry in @pqueue.
493 * Notifies the #GPQueue that the priority of one entry has changed.
494 * The internal representation is updated accordingly.
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).
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.
507 g_pqueue_priority_changed (GPQueue* pqueue,
510 g_pqueue_cut_tree (pqueue, entry);
513 g_pqueue_node_insert_after (entry, entry->child);
518 g_pqueue_fix_rootlist (pqueue);
522 * g_pqueue_priority_decreased:
523 * @pqueue: a #GPQueue.
524 * @entry: a #GPQueueHandle for an entry in @pqueue.
526 * Notifies the #GPQueue that the priority of one entry has
527 * <emphasis>decreased</emphasis>.
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().
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
546 g_pqueue_priority_decreased (GPQueue* pqueue,
549 g_pqueue_cut_tree (pqueue, entry);
553 g_pqueue_node_free_all (GPQueueNode *node)
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);
564 * @pqueue: a #GPQueue.
566 * Removes all entries from a @pqueue.
571 g_pqueue_clear (GPQueue* pqueue)
573 g_pqueue_node_free_all (pqueue->root);
579 * @pqueue: a #GPQueue.
581 * Deallocates the memory used by @pqueue itself, but not any memory pointed
582 * to by the data pointers of its entries.
587 g_pqueue_free (GPQueue* pqueue)
589 g_pqueue_clear (pqueue);
590 g_slice_free (GPQueue, pqueue);