libs/gst/base/gstqueuearray.c

   1 /* GStreamer
   2  * Copyright (C) 2009 Edward Hervey <bilboed@bilboed.com>
   3  *
   4  * gstqueuearray.c:
   5  *
   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.
  10  *
  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.
  15  *
  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.
  20  */
  21
  22 /**
  23  * SECTION:gstqueuearray
  24  * @short_description: Array based queue object
  25  *
  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.
  29  */
  30
  31
  32 #include <string.h>
  33 #include <gst/gst.h>
  34 #include "gstqueuearray.h"
  35
  36 struct _GstQueueArray
  37 {
  38   /* < private > */
  39   gpointer *array;
  40   guint size;
  41   guint head;
  42   guint tail;
  43   guint length;
  44 };
  45
  46 /**
  47  * gst_queue_array_new:
  48  * @initial_size: Initial size of the new queue
  49  *
  50  * Allocates a new #GstQueueArray object with an initial
  51  * queue size of @initial_size.
  52  *
  53  * Returns: a new #GstQueueArray object
  54  *
  55  * Since: 1.2
  56  */
  57 GstQueueArray *
  58 gst_queue_array_new (guint initial_size)
  59 {
  60   GstQueueArray *array;
  61
  62   array = g_slice_new (GstQueueArray);
  63   array->size = initial_size;
  64   array->array = g_new0 (gpointer, initial_size);
  65   array->head = 0;
  66   array->tail = 0;
  67   array->length = 0;
  68   return array;
  69 }
  70
  71
  72 /**
  73  * gst_queue_array_free:
  74  * @array: a #GstQueueArray object
  75  *
  76  * Frees queue @array and all memory associated to it.
  77  *
  78  * Since: 1.2
  79  */
  80 void
  81 gst_queue_array_free (GstQueueArray * array)
  82 {
  83   g_free (array->array);
  84   g_slice_free (GstQueueArray, array);
  85 }
  86
  87 /**
  88  * gst_queue_array_pop_head:
  89  * @array: a #GstQueueArray object
  90  *
  91  * Returns and head of the queue @array and removes
  92  * it from the queue.
  93  *
  94  * Returns: The head of the queue
  95  *
  96  * Since: 1.2
  97  */
  98 gpointer
  99 gst_queue_array_pop_head (GstQueueArray * array)
 100 {
 101   gpointer ret;
 102
 103   /* empty array */
 104   if (G_UNLIKELY (array->length == 0))
 105     return NULL;
 106   ret = array->array[array->head];
 107   array->head++;
 108   array->head %= array->size;
 109   array->length--;
 110   return ret;
 111 }
 112
 113 /**
 114  * gst_queue_array_peek_head:
 115  * @array: a #GstQueueArray object
 116  *
 117  * Returns and head of the queue @array and does not
 118  * remove it from the queue.
 119  *
 120  * Returns: The head of the queue
 121  *
 122  * Since: 1.2
 123  */
 124 gpointer
 125 gst_queue_array_peek_head (GstQueueArray * array)
 126 {
 127   /* empty array */
 128   if (G_UNLIKELY (array->length == 0))
 129     return NULL;
 130   return array->array[array->head];
 131 }
 132
 133 /**
 134  * gst_queue_array_push_tail:
 135  * @array: a #GstQueueArray object
 136  * @data: object to push
 137  *
 138  * Pushes @data to the tail of the queue @array.
 139  *
 140  * Since: 1.2
 141  */
 142 void
 143 gst_queue_array_push_tail (GstQueueArray * array, gpointer data)
 144 {
 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);
 149
 150     /* copy over data */
 151     if (array->tail != 0) {
 152       gpointer *array2 = g_new0 (gpointer, newsize);
 153       guint t1 = array->head;
 154       guint t2 = array->size - array->head;
 155
 156       /* [0-----TAIL][HEAD------SIZE]
 157        *
 158        * We want to end up with
 159        * [HEAD------------------TAIL][----FREEDATA------NEWSIZE]
 160        *
 161        * 1) move [HEAD-----SIZE] part to beginning of new array
 162        * 2) move [0-------TAIL] part new array, after previous part
 163        */
 164
 165       memcpy (array2, &array->array[array->head], t2 * sizeof (gpointer));
 166       memcpy (&array2[t2], array->array, t1 * sizeof (gpointer));
 167
 168       g_free (array->array);
 169       array->array = array2;
 170       array->head = 0;
 171     } else {
 172       /* Fast path, we just need to grow the array */
 173       array->array = g_renew (gpointer, array->array, newsize);
 174     }
 175     array->tail = array->size;
 176     array->size = newsize;
 177   }
 178
 179   array->array[array->tail] = data;
 180   array->tail++;
 181   array->tail %= array->size;
 182   array->length++;
 183 }
 184
 185 /**
 186  * gst_queue_array_is_empty:
 187  * @array: a #GstQueueArray object
 188  *
 189  * Checks if the queue @array is empty.
 190  *
 191  * Returns: %TRUE if the queue @array is empty
 192  *
 193  * Since: 1.2
 194  */
 195 gboolean
 196 gst_queue_array_is_empty (GstQueueArray * array)
 197 {
 198   return (array->length == 0);
 199 }
 200
 201 /**
 202  * gst_queue_array_drop_element:
 203  * @array: a #GstQueueArray object
 204  * @idx: index to drop
 205  *
 206  * Drops the queue element at position @idx from queue @array.
 207  *
 208  * Returns: the dropped element
 209  *
 210  * Since: 1.2
 211  */
 212 gpointer
 213 gst_queue_array_drop_element (GstQueueArray * array, guint idx)
 214 {
 215   int first_item_index, last_item_index;
 216   gpointer element;
 217
 218   g_return_val_if_fail (array->length > 0, NULL);
 219   g_return_val_if_fail (idx < array->size, NULL);
 220
 221   first_item_index = array->head;
 222
 223   /* tail points to the first free spot */
 224   last_item_index = (array->tail - 1 + array->size) % array->size;
 225
 226   element = array->array[idx];
 227
 228   /* simple case idx == first item */
 229   if (idx == first_item_index) {
 230     /* move the head plus one */
 231     array->head++;
 232     array->head %= array->size;
 233     array->length--;
 234     return element;
 235   }
 236
 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;
 241     array->length--;
 242     return element;
 243   }
 244
 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;
 253     array->length--;
 254     return element;
 255   }
 256
 257   /* only wrapped cases left */
 258   g_assert (first_item_index > last_item_index);
 259
 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);
 266     array->tail--;
 267     array->length--;
 268     return element;
 269   }
 270
 271   if (idx > first_item_index) {
 272     element = array->array[idx];
 273     /* idx is after first_item_index, move data to higher indices */
 274     memmove (&array->array[first_item_index + 1],
 275         &array->array[first_item_index],
 276         (idx - first_item_index) * sizeof (gpointer));
 277     array->head++;
 278     /* head should not wrap in this case! */
 279     g_assert (array->head < array->size);
 280     array->length--;
 281     return element;
 282   }
 283
 284   g_return_val_if_reached (NULL);
 285 }
 286
 287 /**
 288  * gst_queue_array_find:
 289  * @array: a #GstQueueArray object
 290  * @func: (allow-none): comparison function, or %NULL to find @data by value
 291  * @data: data for comparison function
 292  *
 293  * Finds an element in the queue @array, either by comparing every element
 294  * with @func or by looking up @data if no compare function @func is provided,
 295  * and returning the index of the found element.
 296  *
 297  * Note that the index is not 0-based, but an internal index number with a
 298  * random offset. The index can be used in connection with
 299  * gst_queue_array_drop_element(). FIXME: return index 0-based and make
 300  * gst_queue_array_drop_element() take a 0-based index.
 301  *
 302  * Returns: Index of the found element or -1 if nothing was found.
 303  *
 304  * Since: 1.2
 305  */
 306 guint
 307 gst_queue_array_find (GstQueueArray * array, GCompareFunc func, gpointer data)
 308 {
 309   guint i;
 310
 311   if (func != NULL) {
 312     /* Scan from head to tail */
 313     for (i = 0; i < array->length; i++) {
 314       if (func (array->array[(i + array->head) % array->size], data) == 0)
 315         return (i + array->head) % array->size;
 316     }
 317   } else {
 318     for (i = 0; i < array->length; i++) {
 319       if (array->array[(i + array->head) % array->size] == data)
 320         return (i + array->head) % array->size;
 321     }
 322   }
 323
 324   return -1;
 325 }
 326
 327 /**
 328  * gst_queue_array_get_length:
 329  * @array: a #GstQueueArray object
 330  *
 331  * Returns the length of the queue @array
 332  *
 333  * Returns: the length of the queue @array.
 334  *
 335  * Since: 1.2
 336  */
 337 guint
 338 gst_queue_array_get_length (GstQueueArray * array)
 339 {
 340   return array->length;
 341 }