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., 59 Temple Place - Suite 330,
19 * Boston, MA 02111-1307, USA.
24 #include "gstqueuearray.h"
27 gst_queue_array_new (guint initial_size)
29 GstQueueArray *array = g_malloc (sizeof (GstQueueArray));
31 array->size = initial_size;
32 array->array = g_new0 (gpointer, initial_size);
41 gst_queue_array_pop_head (GstQueueArray * array)
46 if (G_UNLIKELY (array->length == 0))
48 ret = array->array[array->head];
50 array->head %= array->size;
56 gst_queue_array_push_tail (GstQueueArray * array, gpointer data)
58 /* Check if we need to make room */
59 if (G_UNLIKELY (array->length == array->size)) {
60 /* newsize is 50% bigger */
61 guint newsize = (3 * array->size) / 2;
64 if (array->tail != 0) {
65 gpointer *array2 = g_new0 (gpointer, newsize);
66 guint t1 = array->head;
67 guint t2 = array->size - array->head;
69 /* [0-----TAIL][HEAD------SIZE]
71 * We want to end up with
72 * [HEAD------------------TAIL][----FREEDATA------NEWSIZE]
74 * 1) move [HEAD-----SIZE] part to beginning of new array
75 * 2) move [0-------TAIL] part new array, after previous part
78 memcpy (array2, &array->array[array->head], t2 * sizeof (gpointer));
79 memcpy (&array2[t2], array->array, t1 * sizeof (gpointer));
81 g_free (array->array);
82 array->array = array2;
85 /* Fast path, we just need to grow the array */
86 array->array = g_renew (gpointer, array->array, newsize);
88 array->tail = array->size;
89 array->size = newsize;
92 array->array[array->tail] = data;
94 array->tail %= array->size;
99 gst_queue_array_is_empty (GstQueueArray * array)
101 return (array->length == 0);
105 gst_queue_array_free (GstQueueArray * array)
107 g_free (array->array);
112 gst_queue_array_drop_element (GstQueueArray * array, guint idx)
114 if (idx == array->head) {
115 /* just move the head */
117 array->head %= array->size;
120 if (idx == array->tail - 1) {
121 /* just move the tail */
122 array->tail = (array->tail - 1 + array->size) % array->size;
125 /* drop the element #idx... and readjust the array */
126 if (array->head < array->tail) {
127 /* Make sure it's within the boundaries */
128 g_assert (array->head < idx && idx <= array->tail);
129 /* ends not wrapped */
130 /* move head-idx to head+1 */
131 memcpy (&array->array[array->head + 1],
132 &array->array[array->head], (idx - array->head) * sizeof (gpointer));
135 /* ends are wrapped */
136 if (idx < array->tail) {
137 /* move idx-tail backwards one */
138 memcpy (&array->array[idx - 1],
139 &array->array[idx], (array->tail - idx) * sizeof (gpointer));
141 } else if (idx >= array->head) {
142 /* move head-idx forwards one */
143 memcpy (&array->array[array->head],
144 &array->array[array->head + 1],
145 (idx - array->head) * sizeof (gpointer));
148 g_assert_not_reached ();
153 gst_queue_array_find (GstQueueArray * array, GCompareFunc func, gpointer data)
157 /* Scan from head to tail */
158 for (i = array->head; i < array->length; i = (i + 1) % array->size)
159 if (func (array->array[i], data) == 0)