2 * Copyright (C) 2009 Edward Hervey <bilboed@bilboed.com>
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Library General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Library General Public License for more details.
16 * You should have received a copy of the GNU Library General Public
17 * License along with this library; if not, write to the
18 * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor,
19 * Boston, MA 02110-1301, USA.
23 * SECTION:gstqueuearray
24 * @short_description: Array based queue object
26 * #GstQueueArray is an object that provides standard queue functionality
27 * based on an array instead of linked lists. This reduces the overhead
28 * caused by memory management by a large factor.
34 #include "gstqueuearray.h"
47 * gst_queue_array_new: (skip)
48 * @initial_size: Initial size of the new queue
50 * Allocates a new #GstQueueArray object with an initial
51 * queue size of @initial_size.
53 * Returns: a new #GstQueueArray object
58 gst_queue_array_new (guint initial_size)
62 array = g_slice_new (GstQueueArray);
63 array->size = initial_size;
64 array->array = g_new0 (gpointer, initial_size);
73 * gst_queue_array_free: (skip)
74 * @array: a #GstQueueArray object
76 * Frees queue @array and all memory associated to it.
81 gst_queue_array_free (GstQueueArray * array)
83 g_free (array->array);
84 g_slice_free (GstQueueArray, array);
88 * gst_queue_array_pop_head: (skip)
89 * @array: a #GstQueueArray object
91 * Returns and head of the queue @array and removes
94 * Returns: The head of the queue
99 gst_queue_array_pop_head (GstQueueArray * array)
104 if (G_UNLIKELY (array->length == 0))
106 ret = array->array[array->head];
108 array->head %= array->size;
114 * gst_queue_array_peek_head: (skip)
115 * @array: a #GstQueueArray object
117 * Returns and head of the queue @array and does not
118 * remove it from the queue.
120 * Returns: The head of the queue
125 gst_queue_array_peek_head (GstQueueArray * array)
128 if (G_UNLIKELY (array->length == 0))
130 return array->array[array->head];
134 * gst_queue_array_push_tail: (skip)
135 * @array: a #GstQueueArray object
136 * @data: object to push
138 * Pushes @data to the tail of the queue @array.
143 gst_queue_array_push_tail (GstQueueArray * array, gpointer data)
145 /* Check if we need to make room */
146 if (G_UNLIKELY (array->length == array->size)) {
147 /* newsize is 50% bigger */
148 guint newsize = MAX ((3 * array->size) / 2, array->size + 1);
151 if (array->tail != 0) {
152 gpointer *array2 = g_new0 (gpointer, newsize);
153 guint t1 = array->head;
154 guint t2 = array->size - array->head;
156 /* [0-----TAIL][HEAD------SIZE]
158 * We want to end up with
159 * [HEAD------------------TAIL][----FREEDATA------NEWSIZE]
161 * 1) move [HEAD-----SIZE] part to beginning of new array
162 * 2) move [0-------TAIL] part new array, after previous part
165 memcpy (array2, &array->array[array->head], t2 * sizeof (gpointer));
166 memcpy (&array2[t2], array->array, t1 * sizeof (gpointer));
168 g_free (array->array);
169 array->array = array2;
172 /* Fast path, we just need to grow the array */
173 array->array = g_renew (gpointer, array->array, newsize);
175 array->tail = array->size;
176 array->size = newsize;
179 array->array[array->tail] = data;
181 array->tail %= array->size;
186 * gst_queue_array_is_empty: (skip)
187 * @array: a #GstQueueArray object
189 * Checks if the queue @array is empty.
191 * Returns: %TRUE if the queue @array is empty
196 gst_queue_array_is_empty (GstQueueArray * array)
198 return (array->length == 0);
202 * gst_queue_array_drop_element: (skip)
203 * @array: a #GstQueueArray object
204 * @idx: index to drop
206 * Drops the queue element at position @idx from queue @array.
208 * Returns: the dropped element
213 gst_queue_array_drop_element (GstQueueArray * array, guint idx)
215 int first_item_index, last_item_index;
218 g_return_val_if_fail (array->length > 0, NULL);
219 g_return_val_if_fail (idx < array->size, NULL);
221 first_item_index = array->head;
223 /* tail points to the first free spot */
224 last_item_index = (array->tail - 1 + array->size) % array->size;
226 element = array->array[idx];
228 /* simple case idx == first item */
229 if (idx == first_item_index) {
230 /* move the head plus one */
232 array->head %= array->size;
237 /* simple case idx == last item */
238 if (idx == last_item_index) {
239 /* move tail minus one, potentially wrapping */
240 array->tail = (array->tail - 1 + array->size) % array->size;
245 /* non-wrapped case */
246 if (first_item_index < last_item_index) {
247 g_assert (first_item_index < idx && idx < last_item_index);
248 /* move everything beyond idx one step towards zero in array */
249 memmove (&array->array[idx],
250 &array->array[idx + 1], (last_item_index - idx) * sizeof (gpointer));
251 /* tail might wrap, ie if tail == 0 (and last_item_index == size) */
252 array->tail = (array->tail - 1 + array->size) % array->size;
257 /* only wrapped cases left */
258 g_assert (first_item_index > last_item_index);
260 if (idx < last_item_index) {
261 /* idx is before last_item_index, move data towards zero */
262 memmove (&array->array[idx],
263 &array->array[idx + 1], (last_item_index - idx) * sizeof (gpointer));
264 /* tail should not wrap in this case! */
265 g_assert (array->tail > 0);
271 if (idx > first_item_index) {
272 /* idx is after first_item_index, move data to higher indices */
273 memmove (&array->array[first_item_index + 1],
274 &array->array[first_item_index],
275 (idx - first_item_index) * sizeof (gpointer));
277 /* head should not wrap in this case! */
278 g_assert (array->head < array->size);
283 g_return_val_if_reached (NULL);
287 * gst_queue_array_find: (skip)
288 * @array: a #GstQueueArray object
289 * @func: (allow-none): comparison function, or %NULL to find @data by value
290 * @data: data for comparison function
292 * Finds an element in the queue @array, either by comparing every element
293 * with @func or by looking up @data if no compare function @func is provided,
294 * and returning the index of the found element.
296 * Note that the index is not 0-based, but an internal index number with a
297 * random offset. The index can be used in connection with
298 * gst_queue_array_drop_element(). FIXME: return index 0-based and make
299 * gst_queue_array_drop_element() take a 0-based index.
301 * Returns: Index of the found element or -1 if nothing was found.
306 gst_queue_array_find (GstQueueArray * array, GCompareFunc func, gpointer data)
311 /* Scan from head to tail */
312 for (i = 0; i < array->length; i++) {
313 if (func (array->array[(i + array->head) % array->size], data) == 0)
314 return (i + array->head) % array->size;
317 for (i = 0; i < array->length; i++) {
318 if (array->array[(i + array->head) % array->size] == data)
319 return (i + array->head) % array->size;
327 * gst_queue_array_get_length: (skip)
328 * @array: a #GstQueueArray object
330 * Returns the length of the queue @array
332 * Returns: the length of the queue @array.
337 gst_queue_array_get_length (GstQueueArray * array)
339 return array->length;