plugins/elements/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., 59 Temple Place - Suite 330,
  19  * Boston, MA 02111-1307, USA.
  20  */
  21
  22 #include <string.h>
  23 #include <gst/gst.h>
  24 #include "gstqueuearray.h"
  25
  26 GstQueueArray *
  27 gst_queue_array_new (guint initial_size)
  28 {
  29   GstQueueArray *array = g_malloc (sizeof (GstQueueArray));
  30
  31   array->size = initial_size;
  32   array->array = g_new0 (gpointer, initial_size);
  33   array->head = 0;
  34   array->tail = 0;
  35   array->length = 0;
  36
  37   return array;
  38 }
  39
  40 gpointer
  41 gst_queue_array_pop_head (GstQueueArray * array)
  42 {
  43   gpointer ret;
  44
  45   /* empty array */
  46   if (G_UNLIKELY (array->length == 0))
  47     return NULL;
  48   ret = array->array[array->head];
  49   array->head++;
  50   array->head %= array->size;
  51   array->length--;
  52   return ret;
  53 }
  54
  55 void
  56 gst_queue_array_push_tail (GstQueueArray * array, gpointer data)
  57 {
  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;
  62
  63     /* copy over data */
  64     if (array->tail != 0) {
  65       gpointer *array2 = g_new0 (gpointer, newsize);
  66       guint t1 = array->head;
  67       guint t2 = array->size - array->head;
  68
  69       /* [0-----TAIL][HEAD------SIZE]
  70        *
  71        * We want to end up with
  72        * [HEAD------------------TAIL][----FREEDATA------NEWSIZE]
  73        *
  74        * 1) move [HEAD-----SIZE] part to beginning of new array
  75        * 2) move [0-------TAIL] part new array, after previous part
  76        */
  77
  78       memcpy (array2, &array->array[array->head], t2 * sizeof (gpointer));
  79       memcpy (&array2[t2], array->array, t1 * sizeof (gpointer));
  80
  81       g_free (array->array);
  82       array->array = array2;
  83       array->head = 0;
  84     } else {
  85       /* Fast path, we just need to grow the array */
  86       array->array = g_renew (gpointer, array->array, newsize);
  87     }
  88     array->tail = array->size;
  89     array->size = newsize;
  90   }
  91
  92   array->array[array->tail] = data;
  93   array->tail++;
  94   array->tail %= array->size;
  95   array->length++;
  96 }
  97
  98 gboolean
  99 gst_queue_array_is_empty (GstQueueArray * array)
 100 {
 101   return (array->length == 0);
 102 }
 103
 104 void
 105 gst_queue_array_free (GstQueueArray * array)
 106 {
 107   g_free (array->array);
 108   g_free (array);
 109 }
 110
 111 void
 112 gst_queue_array_drop_element (GstQueueArray * array, guint idx)
 113 {
 114   if (idx == array->head) {
 115     /* just move the head */
 116     array->head++;
 117     array->head %= array->size;
 118     return;
 119   }
 120   if (idx == array->tail - 1) {
 121     /* just move the tail */
 122     array->tail = (array->tail - 1 + array->size) % array->size;
 123     return;
 124   }
 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));
 133     array->tail--;
 134   } else {
 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));
 140       array->tail--;
 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));
 146       array->head++;
 147     } else
 148       g_assert_not_reached ();
 149   }
 150 }
 151
 152 guint
 153 gst_queue_array_find (GstQueueArray * array, GCompareFunc func, gpointer data)
 154 {
 155   guint i;
 156
 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)
 160       return i;
 161   return -1;
 162 }