libs/gst/base/gstqueuearray.c

   1 /* GStreamer
   2  * Copyright (C) 2009 Edward Hervey <bilboed@bilboed.com>
   3  * Copyright (C) 2015 Tim-Philipp Müller <tim@centricular.com>
   4  *
   5  * gstqueuearray.c:
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Library 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.
  11  *
  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  * Library General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Library General Public
  18  * License along with this library; if not, write to the
  19  * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor,
  20  * Boston, MA 02110-1301, USA.
  21  */
  22
  23 /**
  24  * SECTION:gstqueuearray
  25  * @title: GstQueueArray
  26  * @short_description: Array based queue object
  27  *
  28  * #GstQueueArray is an object that provides standard queue functionality
  29  * based on an array instead of linked lists. This reduces the overhead
  30  * caused by memory management by a large factor.
  31  */
  32
  33
  34 #include <string.h>
  35 #include <gst/gst.h>
  36 #include "gstqueuearray.h"
  37
  38 struct _GstQueueArray
  39 {
  40   /* < private > */
  41   guint8 *array;
  42   guint size;
  43   guint head;
  44   guint tail;
  45   guint length;
  46   guint elt_size;
  47   gboolean struct_array;
  48 };
  49
  50 /**
  51  * gst_queue_array_new_for_struct: (skip)
  52  * @struct_size: Size of each element (e.g. structure) in the array
  53  * @initial_size: Initial size of the new queue
  54  *
  55  * Allocates a new #GstQueueArray object for elements (e.g. structures)
  56  * of size @struct_size, with an initial queue size of @initial_size.
  57  *
  58  * Returns: a new #GstQueueArray object
  59  *
  60  * Since: 1.6
  61  */
  62 GstQueueArray *
  63 gst_queue_array_new_for_struct (gsize struct_size, guint initial_size)
  64 {
  65   GstQueueArray *array;
  66
  67   g_return_val_if_fail (struct_size > 0, NULL);
  68
  69   array = g_slice_new (GstQueueArray);
  70   array->elt_size = struct_size;
  71   array->size = initial_size;
  72   array->array = g_malloc0 (struct_size * initial_size);
  73   array->head = 0;
  74   array->tail = 0;
  75   array->length = 0;
  76   array->struct_array = TRUE;
  77   return array;
  78 }
  79
  80 /**
  81  * gst_queue_array_new: (skip)
  82  * @initial_size: Initial size of the new queue
  83  *
  84  * Allocates a new #GstQueueArray object with an initial
  85  * queue size of @initial_size.
  86  *
  87  * Returns: a new #GstQueueArray object
  88  *
  89  * Since: 1.2
  90  */
  91 GstQueueArray *
  92 gst_queue_array_new (guint initial_size)
  93 {
  94   GstQueueArray *array;
  95
  96   array = gst_queue_array_new_for_struct (sizeof (gpointer), initial_size);
  97   array->struct_array = FALSE;
  98   return array;
  99 }
 100
 101 /**
 102  * gst_queue_array_free: (skip)
 103  * @array: a #GstQueueArray object
 104  *
 105  * Frees queue @array and all memory associated to it.
 106  *
 107  * Since: 1.2
 108  */
 109 void
 110 gst_queue_array_free (GstQueueArray * array)
 111 {
 112   g_return_if_fail (array != NULL);
 113   g_free (array->array);
 114   g_slice_free (GstQueueArray, array);
 115 }
 116
 117 /**
 118  * gst_queue_array_pop_head_struct: (skip)
 119  * @array: a #GstQueueArray object
 120  *
 121  * Returns the head of the queue @array and removes it from the queue.
 122  *
 123  * Returns: pointer to element or struct, or NULL if @array was empty. The
 124  *    data pointed to by the returned pointer stays valid only as long as
 125  *    the queue array is not modified further!
 126  *
 127  * Since: 1.6
 128  */
 129 gpointer
 130 gst_queue_array_pop_head_struct (GstQueueArray * array)
 131 {
 132   gpointer p_struct;
 133   g_return_val_if_fail (array != NULL, NULL);
 134   /* empty array */
 135   if (G_UNLIKELY (array->length == 0))
 136     return NULL;
 137
 138   p_struct = array->array + (array->elt_size * array->head);
 139
 140   array->head++;
 141   array->head %= array->size;
 142   array->length--;
 143
 144   return p_struct;
 145 }
 146
 147 /**
 148  * gst_queue_array_pop_head: (skip)
 149  * @array: a #GstQueueArray object
 150  *
 151  * Returns and head of the queue @array and removes
 152  * it from the queue.
 153  *
 154  * Returns: The head of the queue
 155  *
 156  * Since: 1.2
 157  */
 158 gpointer
 159 gst_queue_array_pop_head (GstQueueArray * array)
 160 {
 161   gpointer ret;
 162   g_return_val_if_fail (array != NULL, NULL);
 163   /* empty array */
 164   if (G_UNLIKELY (array->length == 0))
 165     return NULL;
 166
 167   ret = *(gpointer *) (array->array + (sizeof (gpointer) * array->head));
 168   array->head++;
 169   array->head %= array->size;
 170   array->length--;
 171   return ret;
 172 }
 173
 174 /**
 175  * gst_queue_array_peek_head_struct: (skip)
 176  * @array: a #GstQueueArray object
 177  *
 178  * Returns the head of the queue @array without removing it from the queue.
 179  *
 180  * Returns: pointer to element or struct, or NULL if @array was empty. The
 181  *    data pointed to by the returned pointer stays valid only as long as
 182  *    the queue array is not modified further!
 183  *
 184  * Since: 1.6
 185  */
 186 gpointer
 187 gst_queue_array_peek_head_struct (GstQueueArray * array)
 188 {
 189   g_return_val_if_fail (array != NULL, NULL);
 190   /* empty array */
 191   if (G_UNLIKELY (array->length == 0))
 192     return NULL;
 193
 194   return array->array + (array->elt_size * array->head);
 195 }
 196
 197 /**
 198  * gst_queue_array_peek_head: (skip)
 199  * @array: a #GstQueueArray object
 200  *
 201  * Returns the head of the queue @array and does not
 202  * remove it from the queue.
 203  *
 204  * Returns: The head of the queue
 205  *
 206  * Since: 1.2
 207  */
 208 gpointer
 209 gst_queue_array_peek_head (GstQueueArray * array)
 210 {
 211   g_return_val_if_fail (array != NULL, NULL);
 212   /* empty array */
 213   if (G_UNLIKELY (array->length == 0))
 214     return NULL;
 215
 216   return *(gpointer *) (array->array + (sizeof (gpointer) * array->head));
 217 }
 218
 219 static void
 220 gst_queue_array_do_expand (GstQueueArray * array)
 221 {
 222   guint elt_size = array->elt_size;
 223   /* newsize is 50% bigger */
 224   guint oldsize = array->size;
 225   guint newsize = MAX ((3 * oldsize) / 2, oldsize + 1);
 226
 227   /* copy over data */
 228   if (array->tail != 0) {
 229     guint8 *array2 = g_malloc0 (elt_size * newsize);
 230     guint t1 = array->head;
 231     guint t2 = oldsize - array->head;
 232
 233     /* [0-----TAIL][HEAD------SIZE]
 234      *
 235      * We want to end up with
 236      * [HEAD------------------TAIL][----FREEDATA------NEWSIZE]
 237      *
 238      * 1) move [HEAD-----SIZE] part to beginning of new array
 239      * 2) move [0-------TAIL] part new array, after previous part
 240      */
 241
 242     memcpy (array2, array->array + (elt_size * array->head), t2 * elt_size);
 243     memcpy (array2 + t2 * elt_size, array->array, t1 * elt_size);
 244
 245     g_free (array->array);
 246     array->array = array2;
 247     array->head = 0;
 248   } else {
 249     /* Fast path, we just need to grow the array */
 250     array->array = g_realloc (array->array, elt_size * newsize);
 251     memset (array->array + elt_size * oldsize, 0,
 252         elt_size * (newsize - oldsize));
 253   }
 254   array->tail = oldsize;
 255   array->size = newsize;
 256 }
 257
 258 /**
 259  * gst_queue_array_push_element_tail: (skip)
 260  * @array: a #GstQueueArray object
 261  * @p_struct: address of element or structure to push to the tail of the queue
 262  *
 263  * Pushes the element at address @p_struct to the tail of the queue @array
 264  * (Copies the contents of a structure of the struct_size specified when
 265  * creating the queue into the array).
 266  *
 267  * Since: 1.6
 268  */
 269 void
 270 gst_queue_array_push_tail_struct (GstQueueArray * array, gpointer p_struct)
 271 {
 272   guint elt_size;
 273
 274   g_return_if_fail (p_struct != NULL);
 275   g_return_if_fail (array != NULL);
 276   elt_size = array->elt_size;
 277
 278   /* Check if we need to make room */
 279   if (G_UNLIKELY (array->length == array->size))
 280     gst_queue_array_do_expand (array);
 281
 282   memcpy (array->array + elt_size * array->tail, p_struct, elt_size);
 283   array->tail++;
 284   array->tail %= array->size;
 285   array->length++;
 286 }
 287
 288 /**
 289  * gst_queue_array_push_tail: (skip)
 290  * @array: a #GstQueueArray object
 291  * @data: object to push
 292  *
 293  * Pushes @data to the tail of the queue @array.
 294  *
 295  * Since: 1.2
 296  */
 297 void
 298 gst_queue_array_push_tail (GstQueueArray * array, gpointer data)
 299 {
 300   g_return_if_fail (array != NULL);
 301   /* Check if we need to make room */
 302   if (G_UNLIKELY (array->length == array->size))
 303     gst_queue_array_do_expand (array);
 304
 305   *(gpointer *) (array->array + sizeof (gpointer) * array->tail) = data;
 306   array->tail++;
 307   array->tail %= array->size;
 308   array->length++;
 309 }
 310
 311 /**
 312  * gst_queue_array_is_empty: (skip)
 313  * @array: a #GstQueueArray object
 314  *
 315  * Checks if the queue @array is empty.
 316  *
 317  * Returns: %TRUE if the queue @array is empty
 318  *
 319  * Since: 1.2
 320  */
 321 gboolean
 322 gst_queue_array_is_empty (GstQueueArray * array)
 323 {
 324   g_return_val_if_fail (array != NULL, FALSE);
 325   return (array->length == 0);
 326 }
 327
 328
 329 /**
 330  * gst_queue_array_drop_struct: (skip)
 331  * @array: a #GstQueueArray object
 332  * @idx: index to drop
 333  * @p_struct: address into which to store the data of the dropped structure, or NULL
 334  *
 335  * Drops the queue element at position @idx from queue @array and copies the
 336  * data of the element or structure that was removed into @p_struct if
 337  * @p_struct is set (not NULL).
 338  *
 339  * Returns: TRUE on success, or FALSE on error
 340  *
 341  * Since: 1.6
 342  */
 343 gboolean
 344 gst_queue_array_drop_struct (GstQueueArray * array, guint idx,
 345     gpointer p_struct)
 346 {
 347   int first_item_index, last_item_index;
 348   guint elt_size;
 349
 350   g_return_val_if_fail (array != NULL, FALSE);
 351   g_return_val_if_fail (array->length > 0, FALSE);
 352   g_return_val_if_fail (idx < array->size, FALSE);
 353
 354   elt_size = array->elt_size;
 355
 356   first_item_index = array->head;
 357
 358   /* tail points to the first free spot */
 359   last_item_index = (array->tail - 1 + array->size) % array->size;
 360
 361   if (p_struct != NULL)
 362     memcpy (p_struct, array->array + elt_size * idx, elt_size);
 363
 364   /* simple case idx == first item */
 365   if (idx == first_item_index) {
 366     /* move the head plus one */
 367     array->head++;
 368     array->head %= array->size;
 369     array->length--;
 370     return TRUE;
 371   }
 372
 373   /* simple case idx == last item */
 374   if (idx == last_item_index) {
 375     /* move tail minus one, potentially wrapping */
 376     array->tail = (array->tail - 1 + array->size) % array->size;
 377     array->length--;
 378     return TRUE;
 379   }
 380
 381   /* non-wrapped case */
 382   if (first_item_index < last_item_index) {
 383     g_assert (first_item_index < idx && idx < last_item_index);
 384     /* move everything beyond idx one step towards zero in array */
 385     memmove (array->array + elt_size * idx,
 386         array->array + elt_size * (idx + 1),
 387         (last_item_index - idx) * elt_size);
 388     /* tail might wrap, ie if tail == 0 (and last_item_index == size) */
 389     array->tail = (array->tail - 1 + array->size) % array->size;
 390     array->length--;
 391     return TRUE;
 392   }
 393
 394   /* only wrapped cases left */
 395   g_assert (first_item_index > last_item_index);
 396
 397   if (idx < last_item_index) {
 398     /* idx is before last_item_index, move data towards zero */
 399     memmove (array->array + elt_size * idx,
 400         array->array + elt_size * (idx + 1),
 401         (last_item_index - idx) * elt_size);
 402     /* tail should not wrap in this case! */
 403     g_assert (array->tail > 0);
 404     array->tail--;
 405     array->length--;
 406     return TRUE;
 407   }
 408
 409   if (idx > first_item_index) {
 410     /* idx is after first_item_index, move data to higher indices */
 411     memmove (array->array + elt_size * (first_item_index + 1),
 412         array->array + elt_size * first_item_index,
 413         (idx - first_item_index) * elt_size);
 414     array->head++;
 415     /* head should not wrap in this case! */
 416     g_assert (array->head < array->size);
 417     array->length--;
 418     return TRUE;
 419   }
 420
 421   g_return_val_if_reached (FALSE);
 422 }
 423
 424 /**
 425  * gst_queue_array_drop_element: (skip)
 426  * @array: a #GstQueueArray object
 427  * @idx: index to drop
 428  *
 429  * Drops the queue element at position @idx from queue @array.
 430  *
 431  * Returns: the dropped element
 432  *
 433  * Since: 1.2
 434  */
 435 gpointer
 436 gst_queue_array_drop_element (GstQueueArray * array, guint idx)
 437 {
 438   gpointer ptr;
 439
 440   if (!gst_queue_array_drop_struct (array, idx, &ptr))
 441     return NULL;
 442
 443   return ptr;
 444 }
 445
 446 /**
 447  * gst_queue_array_find: (skip)
 448  * @array: a #GstQueueArray object
 449  * @func: (allow-none): comparison function, or %NULL to find @data by value
 450  * @data: data for comparison function
 451  *
 452  * Finds an element in the queue @array, either by comparing every element
 453  * with @func or by looking up @data if no compare function @func is provided,
 454  * and returning the index of the found element.
 455  *
 456  * Note that the index is not 0-based, but an internal index number with a
 457  * random offset. The index can be used in connection with
 458  * gst_queue_array_drop_element(). FIXME: return index 0-based and make
 459  * gst_queue_array_drop_element() take a 0-based index.
 460  *
 461  * Returns: Index of the found element or -1 if nothing was found.
 462  *
 463  * Since: 1.2
 464  */
 465 guint
 466 gst_queue_array_find (GstQueueArray * array, GCompareFunc func, gpointer data)
 467 {
 468   gpointer p_element;
 469   guint elt_size;
 470   guint i;
 471
 472   /* For struct arrays we need to implement this differently so that
 473    * the user gets a pointer to the element data not the dereferenced
 474    * pointer itself */
 475
 476   g_return_val_if_fail (array != NULL, -1);
 477   g_return_val_if_fail (array->struct_array == FALSE, -1);
 478
 479   elt_size = array->elt_size;
 480
 481   if (func != NULL) {
 482     /* Scan from head to tail */
 483     for (i = 0; i < array->length; i++) {
 484       p_element = array->array + ((i + array->head) % array->size) * elt_size;
 485       if (func (*(gpointer *) p_element, data) == 0)
 486         return (i + array->head) % array->size;
 487     }
 488   } else {
 489     for (i = 0; i < array->length; i++) {
 490       p_element = array->array + ((i + array->head) % array->size) * elt_size;
 491       if (*(gpointer *) p_element == data)
 492         return (i + array->head) % array->size;
 493     }
 494   }
 495
 496   return -1;
 497 }
 498
 499 /**
 500  * gst_queue_array_get_length: (skip)
 501  * @array: a #GstQueueArray object
 502  *
 503  * Returns the length of the queue @array
 504  *
 505  * Returns: the length of the queue @array.
 506  *
 507  * Since: 1.2
 508  */
 509 guint
 510 gst_queue_array_get_length (GstQueueArray * array)
 511 {
 512   g_return_val_if_fail (array != NULL, 0);
 513   return array->length;
 514 }