1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
4 * GAsyncQueue: asynchronous queue implementation, based on GQueue.
5 * Copyright (C) 2000 Sebastian Wilhelmi; University of Karlsruhe
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2 of the License, or (at your option) any later version.
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the
19 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
20 * Boston, MA 02111-1307, USA.
29 #include "gasyncqueue.h"
30 #include "gasyncqueueprivate.h"
34 #include "gtestutils.h"
36 #include "deprecated/gthread.h"
40 * SECTION:async_queues
41 * @title: Asynchronous Queues
42 * @short_description: asynchronous communication between threads
43 * @see_also: #GThreadPool
45 * Often you need to communicate between different threads. In general
46 * it's safer not to do this by shared memory, but by explicit message
47 * passing. These messages only make sense asynchronously for
48 * multi-threaded applications though, as a synchronous operation could
49 * as well be done in the same thread.
51 * Asynchronous queues are an exception from most other GLib data
52 * structures, as they can be used simultaneously from multiple threads
53 * without explicit locking and they bring their own builtin reference
54 * counting. This is because the nature of an asynchronous queue is that
55 * it will always be used by at least 2 concurrent threads.
57 * For using an asynchronous queue you first have to create one with
58 * g_async_queue_new(). #GAsyncQueue structs are reference counted,
59 * use g_async_queue_ref() and g_async_queue_unref() to manage your
62 * A thread which wants to send a message to that queue simply calls
63 * g_async_queue_push() to push the message to the queue.
65 * A thread which is expecting messages from an asynchronous queue
66 * simply calls g_async_queue_pop() for that queue. If no message is
67 * available in the queue at that point, the thread is now put to sleep
68 * until a message arrives. The message will be removed from the queue
69 * and returned. The functions g_async_queue_try_pop() and
70 * g_async_queue_timed_pop() can be used to only check for the presence
71 * of messages or to only wait a certain time for messages respectively.
73 * For almost every function there exist two variants, one that locks
74 * the queue and one that doesn't. That way you can hold the queue lock
75 * (acquire it with g_async_queue_lock() and release it with
76 * g_async_queue_unlock()) over multiple queue accessing instructions.
77 * This can be necessary to ensure the integrity of the queue, but should
78 * only be used when really necessary, as it can make your life harder
79 * if used unwisely. Normally you should only use the locking function
80 * variants (those without the _unlocked suffix).
82 * In many cases, it may be more convenient to use #GThreadPool when
83 * you need to distribute work to a set of worker threads instead of
84 * using #GAsyncQueue manually. #GThreadPool uses a GAsyncQueue
91 * The GAsyncQueue struct is an opaque data structure which represents
92 * an asynchronous queue. It should only be accessed through the
93 * <function>g_async_queue_*</function> functions.
100 GDestroyNotify item_free_func
;
101 guint waiting_threads
;
107 GCompareDataFunc func
;
114 * Creates a new asynchronous queue.
116 * Return value: a new #GAsyncQueue. Free with g_async_queue_unref()
119 g_async_queue_new (void)
121 return g_async_queue_new_full (NULL
);
125 * g_async_queue_new_full:
126 * @item_free_func: function to free queue elements
128 * Creates a new asynchronous queue and sets up a destroy notify
129 * function that is used to free any remaining queue items when
130 * the queue is destroyed after the final unref.
132 * Return value: a new #GAsyncQueue. Free with g_async_queue_unref()
137 g_async_queue_new_full (GDestroyNotify item_free_func
)
141 queue
= g_new (GAsyncQueue
, 1);
142 g_mutex_init (&queue
->mutex
);
143 g_cond_init (&queue
->cond
);
144 g_queue_init (&queue
->queue
);
145 queue
->waiting_threads
= 0;
146 queue
->ref_count
= 1;
147 queue
->item_free_func
= item_free_func
;
154 * @queue: a #GAsyncQueue
156 * Increases the reference count of the asynchronous @queue by 1.
157 * You do not need to hold the lock to call this function.
159 * Returns: the @queue that was passed in (since 2.6)
162 g_async_queue_ref (GAsyncQueue
*queue
)
164 g_return_val_if_fail (queue
, NULL
);
166 g_atomic_int_inc (&queue
->ref_count
);
172 * g_async_queue_ref_unlocked:
173 * @queue: a #GAsyncQueue
175 * Increases the reference count of the asynchronous @queue by 1.
177 * @Deprecated: Since 2.8, reference counting is done atomically
178 * so g_async_queue_ref() can be used regardless of the @queue's
182 g_async_queue_ref_unlocked (GAsyncQueue
*queue
)
184 g_return_if_fail (queue
);
186 g_atomic_int_inc (&queue
->ref_count
);
190 * g_async_queue_unref_and_unlock:
191 * @queue: a #GAsyncQueue
193 * Decreases the reference count of the asynchronous @queue by 1
194 * and releases the lock. This function must be called while holding
195 * the @queue's lock. If the reference count went to 0, the @queue
196 * will be destroyed and the memory allocated will be freed.
198 * @Deprecated: Since 2.8, reference counting is done atomically
199 * so g_async_queue_unref() can be used regardless of the @queue's
203 g_async_queue_unref_and_unlock (GAsyncQueue
*queue
)
205 g_return_if_fail (queue
);
207 g_mutex_unlock (&queue
->mutex
);
208 g_async_queue_unref (queue
);
212 * g_async_queue_unref:
213 * @queue: a #GAsyncQueue.
215 * Decreases the reference count of the asynchronous @queue by 1.
217 * If the reference count went to 0, the @queue will be destroyed
218 * and the memory allocated will be freed. So you are not allowed
219 * to use the @queue afterwards, as it might have disappeared.
220 * You do not need to hold the lock to call this function.
223 g_async_queue_unref (GAsyncQueue
*queue
)
225 g_return_if_fail (queue
);
227 if (g_atomic_int_dec_and_test (&queue
->ref_count
))
229 g_return_if_fail (queue
->waiting_threads
== 0);
230 g_mutex_clear (&queue
->mutex
);
231 g_cond_clear (&queue
->cond
);
232 if (queue
->item_free_func
)
233 g_queue_foreach (&queue
->queue
, (GFunc
) queue
->item_free_func
, NULL
);
234 g_queue_clear (&queue
->queue
);
240 * g_async_queue_lock:
241 * @queue: a #GAsyncQueue
243 * Acquires the @queue's lock. If another thread is already
244 * holding the lock, this call will block until the lock
247 * Call g_async_queue_unlock() to drop the lock again.
249 * While holding the lock, you can only call the
250 * <function>g_async_queue_*_unlocked()</function> functions
251 * on @queue. Otherwise, deadlock may occur.
254 g_async_queue_lock (GAsyncQueue
*queue
)
256 g_return_if_fail (queue
);
258 g_mutex_lock (&queue
->mutex
);
262 * g_async_queue_unlock:
263 * @queue: a #GAsyncQueue
265 * Releases the queue's lock.
267 * Calling this function when you have not acquired
268 * the with g_async_queue_lock() leads to undefined
272 g_async_queue_unlock (GAsyncQueue
*queue
)
274 g_return_if_fail (queue
);
276 g_mutex_unlock (&queue
->mutex
);
280 * g_async_queue_push:
281 * @queue: a #GAsyncQueue
282 * @data: @data to push into the @queue
284 * Pushes the @data into the @queue. @data must not be %NULL.
287 g_async_queue_push (GAsyncQueue
*queue
,
290 g_return_if_fail (queue
);
291 g_return_if_fail (data
);
293 g_mutex_lock (&queue
->mutex
);
294 g_async_queue_push_unlocked (queue
, data
);
295 g_mutex_unlock (&queue
->mutex
);
299 * g_async_queue_push_unlocked:
300 * @queue: a #GAsyncQueue
301 * @data: @data to push into the @queue
303 * Pushes the @data into the @queue. @data must not be %NULL.
305 * This function must be called while holding the @queue's lock.
308 g_async_queue_push_unlocked (GAsyncQueue
*queue
,
311 g_return_if_fail (queue
);
312 g_return_if_fail (data
);
314 g_queue_push_head (&queue
->queue
, data
);
315 if (queue
->waiting_threads
> 0)
316 g_cond_signal (&queue
->cond
);
320 * g_async_queue_push_sorted:
321 * @queue: a #GAsyncQueue
322 * @data: the @data to push into the @queue
323 * @func: the #GCompareDataFunc is used to sort @queue
324 * @user_data: user data passed to @func.
326 * Inserts @data into @queue using @func to determine the new
329 * This function requires that the @queue is sorted before pushing on
330 * new elements, see g_async_queue_sort().
332 * This function will lock @queue before it sorts the queue and unlock
333 * it when it is finished.
335 * For an example of @func see g_async_queue_sort().
340 g_async_queue_push_sorted (GAsyncQueue
*queue
,
342 GCompareDataFunc func
,
345 g_return_if_fail (queue
!= NULL
);
347 g_mutex_lock (&queue
->mutex
);
348 g_async_queue_push_sorted_unlocked (queue
, data
, func
, user_data
);
349 g_mutex_unlock (&queue
->mutex
);
353 g_async_queue_invert_compare (gpointer v1
,
357 return -sd
->func (v1
, v2
, sd
->user_data
);
361 * g_async_queue_push_sorted_unlocked:
362 * @queue: a #GAsyncQueue
363 * @data: the @data to push into the @queue
364 * @func: the #GCompareDataFunc is used to sort @queue
365 * @user_data: user data passed to @func.
367 * Inserts @data into @queue using @func to determine the new
370 * The sort function @func is passed two elements of the @queue.
371 * It should return 0 if they are equal, a negative value if the
372 * first element should be higher in the @queue or a positive value
373 * if the first element should be lower in the @queue than the second
376 * This function requires that the @queue is sorted before pushing on
377 * new elements, see g_async_queue_sort().
379 * This function must be called while holding the @queue's lock.
381 * For an example of @func see g_async_queue_sort().
386 g_async_queue_push_sorted_unlocked (GAsyncQueue
*queue
,
388 GCompareDataFunc func
,
393 g_return_if_fail (queue
!= NULL
);
396 sd
.user_data
= user_data
;
398 g_queue_insert_sorted (&queue
->queue
,
400 (GCompareDataFunc
)g_async_queue_invert_compare
,
402 if (queue
->waiting_threads
> 0)
403 g_cond_signal (&queue
->cond
);
407 g_async_queue_pop_intern_unlocked (GAsyncQueue
*queue
,
413 if (!g_queue_peek_tail_link (&queue
->queue
) && wait
)
415 queue
->waiting_threads
++;
416 while (!g_queue_peek_tail_link (&queue
->queue
))
418 if (!g_cond_timed_wait (&queue
->cond
, &queue
->mutex
, end_time
))
421 queue
->waiting_threads
--;
424 retval
= g_queue_pop_tail (&queue
->queue
);
426 g_assert (retval
|| !wait
|| end_time
);
433 * @queue: a #GAsyncQueue
435 * Pops data from the @queue. If @queue is empty, this function
436 * blocks until data becomes available.
438 * Return value: data from the queue
441 g_async_queue_pop (GAsyncQueue
*queue
)
445 g_return_val_if_fail (queue
, NULL
);
447 g_mutex_lock (&queue
->mutex
);
448 retval
= g_async_queue_pop_intern_unlocked (queue
, TRUE
, NULL
);
449 g_mutex_unlock (&queue
->mutex
);
455 * g_async_queue_pop_unlocked:
456 * @queue: a #GAsyncQueue
458 * Pops data from the @queue. If @queue is empty, this function
459 * blocks until data becomes available.
461 * This function must be called while holding the @queue's lock.
463 * Return value: data from the queue.
466 g_async_queue_pop_unlocked (GAsyncQueue
*queue
)
468 g_return_val_if_fail (queue
, NULL
);
470 return g_async_queue_pop_intern_unlocked (queue
, TRUE
, NULL
);
474 * g_async_queue_try_pop:
475 * @queue: a #GAsyncQueue
477 * Tries to pop data from the @queue. If no data is available,
480 * Return value: data from the queue or %NULL, when no data is
481 * available immediately.
484 g_async_queue_try_pop (GAsyncQueue
*queue
)
488 g_return_val_if_fail (queue
, NULL
);
490 g_mutex_lock (&queue
->mutex
);
491 retval
= g_async_queue_pop_intern_unlocked (queue
, FALSE
, NULL
);
492 g_mutex_unlock (&queue
->mutex
);
498 * g_async_queue_try_pop_unlocked:
499 * @queue: a #GAsyncQueue
501 * Tries to pop data from the @queue. If no data is available,
504 * This function must be called while holding the @queue's lock.
506 * Return value: data from the queue or %NULL, when no data is
507 * available immediately.
510 g_async_queue_try_pop_unlocked (GAsyncQueue
*queue
)
512 g_return_val_if_fail (queue
, NULL
);
514 return g_async_queue_pop_intern_unlocked (queue
, FALSE
, NULL
);
518 * g_async_queue_timed_pop:
519 * @queue: a #GAsyncQueue
520 * @end_time: a #GTimeVal, determining the final time
522 * Pops data from the @queue. If the queue is empty, blocks until
523 * @end_time or until data becomes available.
525 * If no data is received before @end_time, %NULL is returned.
527 * To easily calculate @end_time, a combination of g_get_current_time()
528 * and g_time_val_add() can be used.
530 * Return value: data from the queue or %NULL, when no data is
531 * received before @end_time.
534 g_async_queue_timed_pop (GAsyncQueue
*queue
,
539 g_return_val_if_fail (queue
, NULL
);
541 g_mutex_lock (&queue
->mutex
);
542 retval
= g_async_queue_pop_intern_unlocked (queue
, TRUE
, end_time
);
543 g_mutex_unlock (&queue
->mutex
);
549 * g_async_queue_timed_pop_unlocked:
550 * @queue: a #GAsyncQueue
551 * @end_time: a #GTimeVal, determining the final time
553 * Pops data from the @queue. If the queue is empty, blocks until
554 * @end_time or until data becomes available.
556 * If no data is received before @end_time, %NULL is returned.
558 * To easily calculate @end_time, a combination of g_get_current_time()
559 * and g_time_val_add() can be used.
561 * This function must be called while holding the @queue's lock.
563 * Return value: data from the queue or %NULL, when no data is
564 * received before @end_time.
567 g_async_queue_timed_pop_unlocked (GAsyncQueue
*queue
,
570 g_return_val_if_fail (queue
, NULL
);
572 return g_async_queue_pop_intern_unlocked (queue
, TRUE
, end_time
);
576 * g_async_queue_length:
577 * @queue: a #GAsyncQueue.
579 * Returns the length of the queue.
581 * Actually this function returns the number of data items in
582 * the queue minus the number of waiting threads, so a negative
583 * value means waiting threads, and a positive value means available
584 * entries in the @queue. A return value of 0 could mean n entries
585 * in the queue and n threads waiting. This can happen due to locking
586 * of the queue or due to scheduling.
588 * Return value: the length of the @queue
591 g_async_queue_length (GAsyncQueue
*queue
)
595 g_return_val_if_fail (queue
, 0);
597 g_mutex_lock (&queue
->mutex
);
598 retval
= queue
->queue
.length
- queue
->waiting_threads
;
599 g_mutex_unlock (&queue
->mutex
);
605 * g_async_queue_length_unlocked:
606 * @queue: a #GAsyncQueue
608 * Returns the length of the queue.
610 * Actually this function returns the number of data items in
611 * the queue minus the number of waiting threads, so a negative
612 * value means waiting threads, and a positive value means available
613 * entries in the @queue. A return value of 0 could mean n entries
614 * in the queue and n threads waiting. This can happen due to locking
615 * of the queue or due to scheduling.
617 * This function must be called while holding the @queue's lock.
619 * Return value: the length of the @queue.
622 g_async_queue_length_unlocked (GAsyncQueue
*queue
)
624 g_return_val_if_fail (queue
, 0);
626 return queue
->queue
.length
- queue
->waiting_threads
;
630 * g_async_queue_sort:
631 * @queue: a #GAsyncQueue
632 * @func: the #GCompareDataFunc is used to sort @queue
633 * @user_data: user data passed to @func
635 * Sorts @queue using @func.
637 * The sort function @func is passed two elements of the @queue.
638 * It should return 0 if they are equal, a negative value if the
639 * first element should be higher in the @queue or a positive value
640 * if the first element should be lower in the @queue than the second
643 * This function will lock @queue before it sorts the queue and unlock
644 * it when it is finished.
646 * If you were sorting a list of priority numbers to make sure the
647 * lowest priority would be at the top of the queue, you could use:
652 * id1 = GPOINTER_TO_INT (element1);
653 * id2 = GPOINTER_TO_INT (element2);
655 * return (id1 > id2 ? +1 : id1 == id2 ? 0 : -1);
661 g_async_queue_sort (GAsyncQueue
*queue
,
662 GCompareDataFunc func
,
665 g_return_if_fail (queue
!= NULL
);
666 g_return_if_fail (func
!= NULL
);
668 g_mutex_lock (&queue
->mutex
);
669 g_async_queue_sort_unlocked (queue
, func
, user_data
);
670 g_mutex_unlock (&queue
->mutex
);
674 * g_async_queue_sort_unlocked:
675 * @queue: a #GAsyncQueue
676 * @func: the #GCompareDataFunc is used to sort @queue
677 * @user_data: user data passed to @func
679 * Sorts @queue using @func.
681 * The sort function @func is passed two elements of the @queue.
682 * It should return 0 if they are equal, a negative value if the
683 * first element should be higher in the @queue or a positive value
684 * if the first element should be lower in the @queue than the second
687 * This function must be called while holding the @queue's lock.
692 g_async_queue_sort_unlocked (GAsyncQueue
*queue
,
693 GCompareDataFunc func
,
698 g_return_if_fail (queue
!= NULL
);
699 g_return_if_fail (func
!= NULL
);
702 sd
.user_data
= user_data
;
704 g_queue_sort (&queue
->queue
,
705 (GCompareDataFunc
)g_async_queue_invert_compare
,
714 _g_async_queue_get_mutex (GAsyncQueue
*queue
)
716 g_return_val_if_fail (queue
, NULL
);
718 return &queue
->mutex
;