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
 164   /* empty array */
 165   if (G_UNLIKELY (array->length == 0))
 166     return NULL;
 167
 168   ret = *(gpointer *) (array->array + (sizeof (gpointer) * array->head));
 169   array->head++;
 170   array->head %= array->size;
 171   array->length--;
 172   return ret;
 173 }
 174
 175 /**
 176  * gst_queue_array_peek_head_struct: (skip)
 177  * @array: a #GstQueueArray object
 178  *
 179  * Returns the head of the queue @array without removing it from the queue.
 180  *
 181  * Returns: pointer to element or struct, or NULL if @array was empty. The
 182  *    data pointed to by the returned pointer stays valid only as long as
 183  *    the queue array is not modified further!
 184  *
 185  * Since: 1.6
 186  */
 187 gpointer
 188 gst_queue_array_peek_head_struct (GstQueueArray * array)
 189 {
 190   g_return_val_if_fail (array != NULL, NULL);
 191   /* empty array */
 192   if (G_UNLIKELY (array->length == 0))
 193     return NULL;
 194
 195   return array->array + (array->elt_size * array->head);
 196 }
 197
 198 /**
 199  * gst_queue_array_peek_head: (skip)
 200  * @array: a #GstQueueArray object
 201  *
 202  * Returns the head of the queue @array and does not
 203  * remove it from the queue.
 204  *
 205  * Returns: The head of the queue
 206  *
 207  * Since: 1.2
 208  */
 209 gpointer
 210 gst_queue_array_peek_head (GstQueueArray * array)
 211 {
 212   g_return_val_if_fail (array != NULL, NULL);
 213   /* empty array */
 214   if (G_UNLIKELY (array->length == 0))
 215     return NULL;
 216
 217   return *(gpointer *) (array->array + (sizeof (gpointer) * array->head));
 218 }
 219
 220 /**
 221  * gst_queue_array_peek_nth: (skip)
 222  *
 223  * Returns the item at @idx in @array, but does not remove it from the queue.
 224  *
 225  * Returns: The item, or %NULL if @idx was out of bounds
 226  *
 227  * Since: 1.16
 228  */
 229 gpointer
 230 gst_queue_array_peek_nth (GstQueueArray * array, guint idx)
 231 {
 232   g_return_val_if_fail (array != NULL, NULL);
 233   g_return_val_if_fail (idx < array->length, NULL);
 234
 235   idx = (array->head + idx) % array->size;
 236
 237   return *(gpointer *) (array->array + (sizeof (gpointer) * idx));
 238 }
 239
 240 /**
 241  * gst_queue_array_peek_nth_struct: (skip)
 242  *
 243  * Returns the item at @idx in @array, but does not remove it from the queue.
 244  *
 245  * Returns: The item, or %NULL if @idx was out of bounds
 246  *
 247  * Since: 1.16
 248  */
 249 gpointer
 250 gst_queue_array_peek_nth_struct (GstQueueArray * array, guint idx)
 251 {
 252   g_return_val_if_fail (array != NULL, NULL);
 253   g_return_val_if_fail (idx < array->length, NULL);
 254
 255   idx = (array->head + idx) % array->size;
 256
 257   return array->array + (array->elt_size * idx);
 258 }
 259
 260 static void
 261 gst_queue_array_do_expand (GstQueueArray * array)
 262 {
 263   guint elt_size = array->elt_size;
 264   /* newsize is 50% bigger */
 265   guint oldsize = array->size;
 266   guint newsize = MAX ((3 * oldsize) / 2, oldsize + 1);
 267
 268   /* copy over data */
 269   if (array->tail != 0) {
 270     guint8 *array2 = g_malloc0 (elt_size * newsize);
 271     guint t1 = array->head;
 272     guint t2 = oldsize - array->head;
 273
 274     /* [0-----TAIL][HEAD------SIZE]
 275      *
 276      * We want to end up with
 277      * [HEAD------------------TAIL][----FREEDATA------NEWSIZE]
 278      *
 279      * 1) move [HEAD-----SIZE] part to beginning of new array
 280      * 2) move [0-------TAIL] part new array, after previous part
 281      */
 282
 283     memcpy (array2, array->array + (elt_size * array->head), t2 * elt_size);
 284     memcpy (array2 + t2 * elt_size, array->array, t1 * elt_size);
 285
 286     g_free (array->array);
 287     array->array = array2;
 288     array->head = 0;
 289   } else {
 290     /* Fast path, we just need to grow the array */
 291     array->array = g_realloc (array->array, elt_size * newsize);
 292     memset (array->array + elt_size * oldsize, 0,
 293         elt_size * (newsize - oldsize));
 294   }
 295   array->tail = oldsize;
 296   array->size = newsize;
 297 }
 298
 299 /**
 300  * gst_queue_array_push_element_tail: (skip)
 301  * @array: a #GstQueueArray object
 302  * @p_struct: address of element or structure to push to the tail of the queue
 303  *
 304  * Pushes the element at address @p_struct to the tail of the queue @array
 305  * (Copies the contents of a structure of the struct_size specified when
 306  * creating the queue into the array).
 307  *
 308  * Since: 1.6
 309  */
 310 void
 311 gst_queue_array_push_tail_struct (GstQueueArray * array, gpointer p_struct)
 312 {
 313   guint elt_size;
 314
 315   g_return_if_fail (p_struct != NULL);
 316   g_return_if_fail (array != NULL);
 317   elt_size = array->elt_size;
 318
 319   /* Check if we need to make room */
 320   if (G_UNLIKELY (array->length == array->size))
 321     gst_queue_array_do_expand (array);
 322
 323   memcpy (array->array + elt_size * array->tail, p_struct, elt_size);
 324   array->tail++;
 325   array->tail %= array->size;
 326   array->length++;
 327 }
 328
 329 /**
 330  * gst_queue_array_push_tail: (skip)
 331  * @array: a #GstQueueArray object
 332  * @data: object to push
 333  *
 334  * Pushes @data to the tail of the queue @array.
 335  *
 336  * Since: 1.2
 337  */
 338 void
 339 gst_queue_array_push_tail (GstQueueArray * array, gpointer data)
 340 {
 341   g_return_if_fail (array != NULL);
 342
 343   /* Check if we need to make room */
 344   if (G_UNLIKELY (array->length == array->size))
 345     gst_queue_array_do_expand (array);
 346
 347   *(gpointer *) (array->array + sizeof (gpointer) * array->tail) = data;
 348   array->tail++;
 349   array->tail %= array->size;
 350   array->length++;
 351 }
 352
 353 /**
 354  * gst_queue_array_peek_tail: (skip)
 355  * @array: a #GstQueueArray object
 356  *
 357  * Returns the tail of the queue @array, but does not remove it from the queue.
 358  *
 359  * Returns: The tail of the queue
 360  *
 361  * Since: 1.14
 362  */
 363 gpointer
 364 gst_queue_array_peek_tail (GstQueueArray * array)
 365 {
 366   guint len, idx;
 367
 368   g_return_val_if_fail (array != NULL, NULL);
 369
 370   len = array->length;
 371
 372   /* empty array */
 373   if (len == 0)
 374     return NULL;
 375
 376   idx = (array->head + (len - 1)) % array->size;
 377
 378   return *(gpointer *) (array->array + (sizeof (gpointer) * idx));
 379 }
 380
 381 /**
 382  * gst_queue_array_peek_tail_struct: (skip)
 383  * @array: a #GstQueueArray object
 384  *
 385  * Returns the tail of the queue @array, but does not remove it from the queue.
 386  *
 387  * Returns: The tail of the queue
 388  *
 389  * Since: 1.14
 390  */
 391 gpointer
 392 gst_queue_array_peek_tail_struct (GstQueueArray * array)
 393 {
 394   guint len, idx;
 395
 396   g_return_val_if_fail (array != NULL, NULL);
 397
 398   len = array->length;
 399
 400   /* empty array */
 401   if (len == 0)
 402     return NULL;
 403
 404   idx = (array->head + (len - 1)) % array->size;
 405
 406   return array->array + (array->elt_size * idx);
 407 }
 408
 409 /**
 410  * gst_queue_array_pop_tail: (skip)
 411  * @array: a #GstQueueArray object
 412  *
 413  * Returns the tail of the queue @array and removes
 414  * it from the queue.
 415  *
 416  * Returns: The tail of the queue
 417  *
 418  * Since: 1.14
 419  */
 420 gpointer
 421 gst_queue_array_pop_tail (GstQueueArray * array)
 422 {
 423   gpointer ret;
 424   guint len, idx;
 425
 426   g_return_val_if_fail (array != NULL, NULL);
 427
 428   len = array->length;
 429
 430   /* empty array */
 431   if (len == 0)
 432     return NULL;
 433
 434   idx = (array->head + (len - 1)) % array->size;
 435
 436   ret = *(gpointer *) (array->array + (sizeof (gpointer) * idx));
 437
 438   array->tail = idx;
 439   array->length--;
 440
 441   return ret;
 442 }
 443
 444 /**
 445  * gst_queue_array_pop_tail_struct: (skip)
 446  * @array: a #GstQueueArray object
 447  *
 448  * Returns the tail of the queue @array and removes
 449  * it from the queue.
 450  *
 451  * Returns: The tail of the queue
 452  *
 453  * Since: 1.14
 454  */
 455 gpointer
 456 gst_queue_array_pop_tail_struct (GstQueueArray * array)
 457 {
 458   gpointer ret;
 459   guint len, idx;
 460
 461   g_return_val_if_fail (array != NULL, NULL);
 462
 463   len = array->length;
 464
 465   /* empty array */
 466   if (len == 0)
 467     return NULL;
 468
 469   idx = (array->head + (len - 1)) % array->size;
 470
 471   ret = array->array + (array->elt_size * idx);
 472
 473   array->tail = idx;
 474   array->length--;
 475
 476   return ret;
 477 }
 478
 479 /**
 480  * gst_queue_array_is_empty: (skip)
 481  * @array: a #GstQueueArray object
 482  *
 483  * Checks if the queue @array is empty.
 484  *
 485  * Returns: %TRUE if the queue @array is empty
 486  *
 487  * Since: 1.2
 488  */
 489 gboolean
 490 gst_queue_array_is_empty (GstQueueArray * array)
 491 {
 492   g_return_val_if_fail (array != NULL, FALSE);
 493   return (array->length == 0);
 494 }
 495
 496
 497 /**
 498  * gst_queue_array_drop_struct: (skip)
 499  * @array: a #GstQueueArray object
 500  * @idx: index to drop
 501  * @p_struct: address into which to store the data of the dropped structure, or NULL
 502  *
 503  * Drops the queue element at position @idx from queue @array and copies the
 504  * data of the element or structure that was removed into @p_struct if
 505  * @p_struct is set (not NULL).
 506  *
 507  * Returns: TRUE on success, or FALSE on error
 508  *
 509  * Since: 1.6
 510  */
 511 gboolean
 512 gst_queue_array_drop_struct (GstQueueArray * array, guint idx,
 513     gpointer p_struct)
 514 {
 515   int first_item_index, last_item_index;
 516   guint elt_size;
 517
 518   g_return_val_if_fail (array != NULL, FALSE);
 519   idx = (array->head + idx) % array->size;
 520
 521   g_return_val_if_fail (array->length > 0, FALSE);
 522   g_return_val_if_fail (idx < array->size, FALSE);
 523
 524   elt_size = array->elt_size;
 525
 526   first_item_index = array->head;
 527
 528   /* tail points to the first free spot */
 529   last_item_index = (array->tail - 1 + array->size) % array->size;
 530
 531   if (p_struct != NULL)
 532     memcpy (p_struct, array->array + elt_size * idx, elt_size);
 533
 534   /* simple case idx == first item */
 535   if (idx == first_item_index) {
 536     /* move the head plus one */
 537     array->head++;
 538     array->head %= array->size;
 539     array->length--;
 540     return TRUE;
 541   }
 542
 543   /* simple case idx == last item */
 544   if (idx == last_item_index) {
 545     /* move tail minus one, potentially wrapping */
 546     array->tail = (array->tail - 1 + array->size) % array->size;
 547     array->length--;
 548     return TRUE;
 549   }
 550
 551   /* non-wrapped case */
 552   if (first_item_index < last_item_index) {
 553     g_assert (first_item_index < idx && idx < last_item_index);
 554     /* move everything beyond idx one step towards zero in array */
 555     memmove (array->array + elt_size * idx,
 556         array->array + elt_size * (idx + 1),
 557         (last_item_index - idx) * elt_size);
 558     /* tail might wrap, ie if tail == 0 (and last_item_index == size) */
 559     array->tail = (array->tail - 1 + array->size) % array->size;
 560     array->length--;
 561     return TRUE;
 562   }
 563
 564   /* only wrapped cases left */
 565   g_assert (first_item_index > last_item_index);
 566
 567   if (idx < last_item_index) {
 568     /* idx is before last_item_index, move data towards zero */
 569     memmove (array->array + elt_size * idx,
 570         array->array + elt_size * (idx + 1),
 571         (last_item_index - idx) * elt_size);
 572     /* tail should not wrap in this case! */
 573     g_assert (array->tail > 0);
 574     array->tail--;
 575     array->length--;
 576     return TRUE;
 577   }
 578
 579   if (idx > first_item_index) {
 580     /* idx is after first_item_index, move data to higher indices */
 581     memmove (array->array + elt_size * (first_item_index + 1),
 582         array->array + elt_size * first_item_index,
 583         (idx - first_item_index) * elt_size);
 584     array->head++;
 585     /* head should not wrap in this case! */
 586     g_assert (array->head < array->size);
 587     array->length--;
 588     return TRUE;
 589   }
 590
 591   g_return_val_if_reached (FALSE);
 592 }
 593
 594 /**
 595  * gst_queue_array_drop_element: (skip)
 596  * @array: a #GstQueueArray object
 597  * @idx: index to drop
 598  *
 599  * Drops the queue element at position @idx from queue @array.
 600  *
 601  * Returns: the dropped element
 602  *
 603  * Since: 1.2
 604  */
 605 gpointer
 606 gst_queue_array_drop_element (GstQueueArray * array, guint idx)
 607 {
 608   gpointer ptr;
 609
 610   if (!gst_queue_array_drop_struct (array, idx, &ptr))
 611     return NULL;
 612
 613   return ptr;
 614 }
 615
 616 /**
 617  * gst_queue_array_find: (skip)
 618  * @array: a #GstQueueArray object
 619  * @func: (allow-none): comparison function, or %NULL to find @data by value
 620  * @data: data for comparison function
 621  *
 622  * Finds an element in the queue @array, either by comparing every element
 623  * with @func or by looking up @data if no compare function @func is provided,
 624  * and returning the index of the found element.
 625  *
 626  * Returns: Index of the found element or -1 if nothing was found.
 627  *
 628  * Since: 1.2
 629  */
 630 guint
 631 gst_queue_array_find (GstQueueArray * array, GCompareFunc func, gpointer data)
 632 {
 633   gpointer p_element;
 634   guint elt_size;
 635   guint i;
 636
 637   /* For struct arrays we need to implement this differently so that
 638    * the user gets a pointer to the element data not the dereferenced
 639    * pointer itself */
 640
 641   g_return_val_if_fail (array != NULL, -1);
 642   g_return_val_if_fail (array->struct_array == FALSE, -1);
 643
 644   elt_size = array->elt_size;
 645
 646   if (func != NULL) {
 647     /* Scan from head to tail */
 648     for (i = 0; i < array->length; i++) {
 649       p_element = array->array + ((i + array->head) % array->size) * elt_size;
 650       if (func (*(gpointer *) p_element, data) == 0)
 651         return i;
 652     }
 653   } else {
 654     for (i = 0; i < array->length; i++) {
 655       p_element = array->array + ((i + array->head) % array->size) * elt_size;
 656       if (*(gpointer *) p_element == data)
 657         return i;
 658     }
 659   }
 660
 661   return -1;
 662 }
 663
 664 /**
 665  * gst_queue_array_get_length: (skip)
 666  * @array: a #GstQueueArray object
 667  *
 668  * Returns the length of the queue @array
 669  *
 670  * Returns: the length of the queue @array.
 671  *
 672  * Since: 1.2
 673  */
 674 guint
 675 gst_queue_array_get_length (GstQueueArray * array)
 676 {
 677   g_return_val_if_fail (array != NULL, 0);
 678   return array->length;
 679 }