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 #ifdef HAVE_CONFIG_H
  33 #include "config.h"
  34 #endif
  35
  36 #include <string.h>
  37 #include <gst/gst.h>
  38 #include "gstqueuearray.h"
  39
  40 struct _GstQueueArray
  41 {
  42   /* < private > */
  43   guint8 *array;
  44   guint size;
  45   guint head;
  46   guint tail;
  47   guint length;
  48   guint elt_size;
  49   gboolean struct_array;
  50   GDestroyNotify clear_func;
  51 };
  52
  53 /**
  54  * gst_queue_array_new_for_struct: (skip)
  55  * @struct_size: Size of each element (e.g. structure) in the array
  56  * @initial_size: Initial size of the new queue
  57  *
  58  * Allocates a new #GstQueueArray object for elements (e.g. structures)
  59  * of size @struct_size, with an initial queue size of @initial_size.
  60  *
  61  * Returns: a new #GstQueueArray object
  62  *
  63  * Since: 1.6
  64  */
  65 GstQueueArray *
  66 gst_queue_array_new_for_struct (gsize struct_size, guint initial_size)
  67 {
  68   GstQueueArray *array;
  69
  70   g_return_val_if_fail (struct_size > 0, NULL);
  71
  72   array = g_slice_new (GstQueueArray);
  73   array->elt_size = struct_size;
  74   array->size = initial_size;
  75   array->array = g_malloc0 (struct_size * initial_size);
  76   array->head = 0;
  77   array->tail = 0;
  78   array->length = 0;
  79   array->struct_array = TRUE;
  80   array->clear_func = NULL;
  81   return array;
  82 }
  83
  84 /**
  85  * gst_queue_array_new: (skip)
  86  * @initial_size: Initial size of the new queue
  87  *
  88  * Allocates a new #GstQueueArray object with an initial
  89  * queue size of @initial_size.
  90  *
  91  * Returns: a new #GstQueueArray object
  92  *
  93  * Since: 1.2
  94  */
  95 GstQueueArray *
  96 gst_queue_array_new (guint initial_size)
  97 {
  98   GstQueueArray *array;
  99
 100   array = gst_queue_array_new_for_struct (sizeof (gpointer), initial_size);
 101   array->struct_array = FALSE;
 102   return array;
 103 }
 104
 105 /**
 106  * gst_queue_array_free: (skip)
 107  * @array: a #GstQueueArray object
 108  *
 109  * Frees queue @array and all memory associated to it.
 110  *
 111  * Since: 1.2
 112  */
 113 void
 114 gst_queue_array_free (GstQueueArray * array)
 115 {
 116   g_return_if_fail (array != NULL);
 117   gst_queue_array_clear (array);
 118   g_free (array->array);
 119   g_slice_free (GstQueueArray, array);
 120 }
 121
 122 /**
 123  * gst_queue_array_set_clear_func: (skip)
 124  * @array: a #GstQueueArray object
 125  * @clear_func: a function to clear an element of @array
 126  *
 127  * Sets a function to clear an element of @array.
 128  *
 129  * The @clear_func will be called when an element in the array
 130  * data segment is removed and when the array is freed and data
 131  * segment is deallocated as well. @clear_func will be passed a
 132  * pointer to the element to clear, rather than the element itself.
 133  *
 134  * Note that in contrast with other uses of #GDestroyNotify
 135  * functions, @clear_func is expected to clear the contents of
 136  * the array element it is given, but not free the element itself.
 137  *
 138  * Since: 1.16
 139  */
 140 void
 141 gst_queue_array_set_clear_func (GstQueueArray * array,
 142     GDestroyNotify clear_func)
 143 {
 144   g_return_if_fail (array != NULL);
 145   array->clear_func = clear_func;
 146 }
 147
 148 static void
 149 gst_queue_array_clear_idx (GstQueueArray * array, guint idx)
 150 {
 151   guint pos;
 152
 153   if (!array->clear_func)
 154     return;
 155
 156   pos = (idx + array->head) % array->size;
 157   if (array->struct_array)
 158     array->clear_func (array->array + pos * array->elt_size);
 159   else
 160     array->clear_func (*(gpointer *) (array->array + pos * array->elt_size));
 161 }
 162
 163 /**
 164  * gst_queue_array_clear: (skip)
 165  * @array: a #GstQueueArray object
 166  *
 167  * Clears queue @array and frees all memory associated to it.
 168  *
 169  * Since: 1.16
 170  */
 171 void
 172 gst_queue_array_clear (GstQueueArray * array)
 173 {
 174   g_return_if_fail (array != NULL);
 175
 176   if (array->clear_func != NULL) {
 177     guint i;
 178
 179     for (i = 0; i < array->length; i++) {
 180       gst_queue_array_clear_idx (array, i);
 181     }
 182   }
 183
 184   array->head = 0;
 185   array->tail = 0;
 186   array->length = 0;
 187 }
 188
 189 /**
 190  * gst_queue_array_pop_head_struct: (skip)
 191  * @array: a #GstQueueArray object
 192  *
 193  * Returns the head of the queue @array and removes it from the queue.
 194  *
 195  * Returns: pointer to element or struct, or NULL if @array was empty. The
 196  *    data pointed to by the returned pointer stays valid only as long as
 197  *    the queue array is not modified further!
 198  *
 199  * Since: 1.6
 200  */
 201 gpointer
 202 gst_queue_array_pop_head_struct (GstQueueArray * array)
 203 {
 204   gpointer p_struct;
 205   g_return_val_if_fail (array != NULL, NULL);
 206   /* empty array */
 207   if (G_UNLIKELY (array->length == 0))
 208     return NULL;
 209
 210   p_struct = array->array + (array->elt_size * array->head);
 211
 212   array->head++;
 213   array->head %= array->size;
 214   array->length--;
 215
 216   return p_struct;
 217 }
 218
 219 /**
 220  * gst_queue_array_pop_head: (skip)
 221  * @array: a #GstQueueArray object
 222  *
 223  * Returns and head of the queue @array and removes
 224  * it from the queue.
 225  *
 226  * Returns: The head of the queue
 227  *
 228  * Since: 1.2
 229  */
 230 gpointer
 231 gst_queue_array_pop_head (GstQueueArray * array)
 232 {
 233   gpointer ret;
 234   g_return_val_if_fail (array != NULL, NULL);
 235
 236   /* empty array */
 237   if (G_UNLIKELY (array->length == 0))
 238     return NULL;
 239
 240   ret = *(gpointer *) (array->array + (sizeof (gpointer) * array->head));
 241   array->head++;
 242   array->head %= array->size;
 243   array->length--;
 244   return ret;
 245 }
 246
 247 /**
 248  * gst_queue_array_peek_head_struct: (skip)
 249  * @array: a #GstQueueArray object
 250  *
 251  * Returns the head of the queue @array without removing it from the queue.
 252  *
 253  * Returns: pointer to element or struct, or NULL if @array was empty. The
 254  *    data pointed to by the returned pointer stays valid only as long as
 255  *    the queue array is not modified further!
 256  *
 257  * Since: 1.6
 258  */
 259 gpointer
 260 gst_queue_array_peek_head_struct (GstQueueArray * array)
 261 {
 262   g_return_val_if_fail (array != NULL, NULL);
 263   /* empty array */
 264   if (G_UNLIKELY (array->length == 0))
 265     return NULL;
 266
 267   return array->array + (array->elt_size * array->head);
 268 }
 269
 270 /**
 271  * gst_queue_array_peek_head: (skip)
 272  * @array: a #GstQueueArray object
 273  *
 274  * Returns the head of the queue @array and does not
 275  * remove it from the queue.
 276  *
 277  * Returns: The head of the queue
 278  *
 279  * Since: 1.2
 280  */
 281 gpointer
 282 gst_queue_array_peek_head (GstQueueArray * array)
 283 {
 284   g_return_val_if_fail (array != NULL, NULL);
 285   /* empty array */
 286   if (G_UNLIKELY (array->length == 0))
 287     return NULL;
 288
 289   return *(gpointer *) (array->array + (sizeof (gpointer) * array->head));
 290 }
 291
 292 /**
 293  * gst_queue_array_peek_nth: (skip)
 294  *
 295  * Returns the item at @idx in @array, but does not remove it from the queue.
 296  *
 297  * Returns: The item, or %NULL if @idx was out of bounds
 298  *
 299  * Since: 1.16
 300  */
 301 gpointer
 302 gst_queue_array_peek_nth (GstQueueArray * array, guint idx)
 303 {
 304   g_return_val_if_fail (array != NULL, NULL);
 305   g_return_val_if_fail (idx < array->length, NULL);
 306
 307   idx = (array->head + idx) % array->size;
 308
 309   return *(gpointer *) (array->array + (sizeof (gpointer) * idx));
 310 }
 311
 312 /**
 313  * gst_queue_array_peek_nth_struct: (skip)
 314  *
 315  * Returns the item at @idx in @array, but does not remove it from the queue.
 316  *
 317  * Returns: The item, or %NULL if @idx was out of bounds
 318  *
 319  * Since: 1.16
 320  */
 321 gpointer
 322 gst_queue_array_peek_nth_struct (GstQueueArray * array, guint idx)
 323 {
 324   g_return_val_if_fail (array != NULL, NULL);
 325   g_return_val_if_fail (idx < array->length, NULL);
 326
 327   idx = (array->head + idx) % array->size;
 328
 329   return array->array + (array->elt_size * idx);
 330 }
 331
 332 static void
 333 gst_queue_array_do_expand (GstQueueArray * array)
 334 {
 335   guint elt_size = array->elt_size;
 336   /* newsize is 50% bigger */
 337   guint oldsize = array->size;
 338   guint newsize = MAX ((3 * oldsize) / 2, oldsize + 1);
 339
 340   /* copy over data */
 341   if (array->tail != 0) {
 342     guint8 *array2 = g_malloc0 (elt_size * newsize);
 343     guint t1 = array->head;
 344     guint t2 = oldsize - array->head;
 345
 346     /* [0-----TAIL][HEAD------SIZE]
 347      *
 348      * We want to end up with
 349      * [HEAD------------------TAIL][----FREEDATA------NEWSIZE]
 350      *
 351      * 1) move [HEAD-----SIZE] part to beginning of new array
 352      * 2) move [0-------TAIL] part new array, after previous part
 353      */
 354
 355     memcpy (array2, array->array + (elt_size * array->head), t2 * elt_size);
 356     memcpy (array2 + t2 * elt_size, array->array, t1 * elt_size);
 357
 358     g_free (array->array);
 359     array->array = array2;
 360     array->head = 0;
 361   } else {
 362     /* Fast path, we just need to grow the array */
 363     array->array = g_realloc (array->array, elt_size * newsize);
 364     memset (array->array + elt_size * oldsize, 0,
 365         elt_size * (newsize - oldsize));
 366   }
 367   array->tail = oldsize;
 368   array->size = newsize;
 369 }
 370
 371 /**
 372  * gst_queue_array_push_element_tail: (skip)
 373  * @array: a #GstQueueArray object
 374  * @p_struct: address of element or structure to push to the tail of the queue
 375  *
 376  * Pushes the element at address @p_struct to the tail of the queue @array
 377  * (Copies the contents of a structure of the struct_size specified when
 378  * creating the queue into the array).
 379  *
 380  * Since: 1.6
 381  */
 382 void
 383 gst_queue_array_push_tail_struct (GstQueueArray * array, gpointer p_struct)
 384 {
 385   guint elt_size;
 386
 387   g_return_if_fail (p_struct != NULL);
 388   g_return_if_fail (array != NULL);
 389   elt_size = array->elt_size;
 390
 391   /* Check if we need to make room */
 392   if (G_UNLIKELY (array->length == array->size))
 393     gst_queue_array_do_expand (array);
 394
 395   memcpy (array->array + elt_size * array->tail, p_struct, elt_size);
 396   array->tail++;
 397   array->tail %= array->size;
 398   array->length++;
 399 }
 400
 401 /**
 402  * gst_queue_array_push_tail: (skip)
 403  * @array: a #GstQueueArray object
 404  * @data: object to push
 405  *
 406  * Pushes @data to the tail of the queue @array.
 407  *
 408  * Since: 1.2
 409  */
 410 void
 411 gst_queue_array_push_tail (GstQueueArray * array, gpointer data)
 412 {
 413   g_return_if_fail (array != NULL);
 414
 415   /* Check if we need to make room */
 416   if (G_UNLIKELY (array->length == array->size))
 417     gst_queue_array_do_expand (array);
 418
 419   *(gpointer *) (array->array + sizeof (gpointer) * array->tail) = data;
 420   array->tail++;
 421   array->tail %= array->size;
 422   array->length++;
 423 }
 424
 425 /**
 426  * gst_queue_array_peek_tail: (skip)
 427  * @array: a #GstQueueArray object
 428  *
 429  * Returns the tail of the queue @array, but does not remove it from the queue.
 430  *
 431  * Returns: The tail of the queue
 432  *
 433  * Since: 1.14
 434  */
 435 gpointer
 436 gst_queue_array_peek_tail (GstQueueArray * array)
 437 {
 438   guint len, idx;
 439
 440   g_return_val_if_fail (array != NULL, NULL);
 441
 442   len = array->length;
 443
 444   /* empty array */
 445   if (len == 0)
 446     return NULL;
 447
 448   idx = (array->head + (len - 1)) % array->size;
 449
 450   return *(gpointer *) (array->array + (sizeof (gpointer) * idx));
 451 }
 452
 453 /**
 454  * gst_queue_array_peek_tail_struct: (skip)
 455  * @array: a #GstQueueArray object
 456  *
 457  * Returns the tail of the queue @array, but does not remove it from the queue.
 458  *
 459  * Returns: The tail of the queue
 460  *
 461  * Since: 1.14
 462  */
 463 gpointer
 464 gst_queue_array_peek_tail_struct (GstQueueArray * array)
 465 {
 466   guint len, idx;
 467
 468   g_return_val_if_fail (array != NULL, NULL);
 469
 470   len = array->length;
 471
 472   /* empty array */
 473   if (len == 0)
 474     return NULL;
 475
 476   idx = (array->head + (len - 1)) % array->size;
 477
 478   return array->array + (array->elt_size * idx);
 479 }
 480
 481 /**
 482  * gst_queue_array_pop_tail: (skip)
 483  * @array: a #GstQueueArray object
 484  *
 485  * Returns the tail of the queue @array and removes
 486  * it from the queue.
 487  *
 488  * Returns: The tail of the queue
 489  *
 490  * Since: 1.14
 491  */
 492 gpointer
 493 gst_queue_array_pop_tail (GstQueueArray * array)
 494 {
 495   gpointer ret;
 496   guint len, idx;
 497
 498   g_return_val_if_fail (array != NULL, NULL);
 499
 500   len = array->length;
 501
 502   /* empty array */
 503   if (len == 0)
 504     return NULL;
 505
 506   idx = (array->head + (len - 1)) % array->size;
 507
 508   ret = *(gpointer *) (array->array + (sizeof (gpointer) * idx));
 509
 510   array->tail = idx;
 511   array->length--;
 512
 513   return ret;
 514 }
 515
 516 /**
 517  * gst_queue_array_pop_tail_struct: (skip)
 518  * @array: a #GstQueueArray object
 519  *
 520  * Returns the tail of the queue @array and removes
 521  * it from the queue.
 522  *
 523  * Returns: The tail of the queue
 524  *
 525  * Since: 1.14
 526  */
 527 gpointer
 528 gst_queue_array_pop_tail_struct (GstQueueArray * array)
 529 {
 530   gpointer ret;
 531   guint len, idx;
 532
 533   g_return_val_if_fail (array != NULL, NULL);
 534
 535   len = array->length;
 536
 537   /* empty array */
 538   if (len == 0)
 539     return NULL;
 540
 541   idx = (array->head + (len - 1)) % array->size;
 542
 543   ret = array->array + (array->elt_size * idx);
 544
 545   array->tail = idx;
 546   array->length--;
 547
 548   return ret;
 549 }
 550
 551 /**
 552  * gst_queue_array_is_empty: (skip)
 553  * @array: a #GstQueueArray object
 554  *
 555  * Checks if the queue @array is empty.
 556  *
 557  * Returns: %TRUE if the queue @array is empty
 558  *
 559  * Since: 1.2
 560  */
 561 gboolean
 562 gst_queue_array_is_empty (GstQueueArray * array)
 563 {
 564   g_return_val_if_fail (array != NULL, FALSE);
 565   return (array->length == 0);
 566 }
 567
 568
 569 /**
 570  * gst_queue_array_drop_struct: (skip)
 571  * @array: a #GstQueueArray object
 572  * @idx: index to drop
 573  * @p_struct: address into which to store the data of the dropped structure, or NULL
 574  *
 575  * Drops the queue element at position @idx from queue @array and copies the
 576  * data of the element or structure that was removed into @p_struct if
 577  * @p_struct is set (not NULL).
 578  *
 579  * Returns: TRUE on success, or FALSE on error
 580  *
 581  * Since: 1.6
 582  */
 583 gboolean
 584 gst_queue_array_drop_struct (GstQueueArray * array, guint idx,
 585     gpointer p_struct)
 586 {
 587   int first_item_index, last_item_index;
 588   guint actual_idx;
 589   guint elt_size;
 590
 591   g_return_val_if_fail (array != NULL, FALSE);
 592   actual_idx = (array->head + idx) % array->size;
 593
 594   g_return_val_if_fail (array->length > 0, FALSE);
 595   g_return_val_if_fail (actual_idx < array->size, FALSE);
 596
 597   elt_size = array->elt_size;
 598
 599   first_item_index = array->head;
 600
 601   /* tail points to the first free spot */
 602   last_item_index = (array->tail - 1 + array->size) % array->size;
 603
 604   if (p_struct != NULL)
 605     memcpy (p_struct, array->array + elt_size * actual_idx, elt_size);
 606
 607   /* simple case actual_idx == first item */
 608   if (actual_idx == first_item_index) {
 609     /* clear current head position if needed */
 610     if (p_struct == NULL)
 611       gst_queue_array_clear_idx (array, idx);
 612
 613     /* move the head plus one */
 614     array->head++;
 615     array->head %= array->size;
 616     array->length--;
 617     return TRUE;
 618   }
 619
 620   /* simple case idx == last item */
 621   if (actual_idx == last_item_index) {
 622     /* clear current tail position if needed */
 623     if (p_struct == NULL)
 624       gst_queue_array_clear_idx (array, idx);
 625
 626     /* move tail minus one, potentially wrapping */
 627     array->tail = (array->tail - 1 + array->size) % array->size;
 628     array->length--;
 629     return TRUE;
 630   }
 631
 632   /* non-wrapped case */
 633   if (first_item_index < last_item_index) {
 634     /* clear idx if needed */
 635     if (p_struct == NULL)
 636       gst_queue_array_clear_idx (array, idx);
 637
 638     g_assert (first_item_index < actual_idx && actual_idx < last_item_index);
 639     /* move everything beyond actual_idx one step towards zero in array */
 640     memmove (array->array + elt_size * actual_idx,
 641         array->array + elt_size * (actual_idx + 1),
 642         (last_item_index - actual_idx) * elt_size);
 643     /* tail might wrap, ie if tail == 0 (and last_item_index == size) */
 644     array->tail = (array->tail - 1 + array->size) % array->size;
 645     array->length--;
 646     return TRUE;
 647   }
 648
 649   /* only wrapped cases left */
 650   g_assert (first_item_index > last_item_index);
 651
 652   if (actual_idx < last_item_index) {
 653     /* clear idx if needed */
 654     if (p_struct == NULL)
 655       gst_queue_array_clear_idx (array, idx);
 656
 657     /* actual_idx is before last_item_index, move data towards zero */
 658     memmove (array->array + elt_size * actual_idx,
 659         array->array + elt_size * (actual_idx + 1),
 660         (last_item_index - actual_idx) * elt_size);
 661     /* tail should not wrap in this case! */
 662     g_assert (array->tail > 0);
 663     array->tail--;
 664     array->length--;
 665     return TRUE;
 666   }
 667
 668   if (actual_idx > first_item_index) {
 669     /* clear idx if needed */
 670     if (p_struct == NULL)
 671       gst_queue_array_clear_idx (array, idx);
 672
 673     /* actual_idx is after first_item_index, move data to higher indices */
 674     memmove (array->array + elt_size * (first_item_index + 1),
 675         array->array + elt_size * first_item_index,
 676         (actual_idx - first_item_index) * elt_size);
 677     array->head++;
 678     /* head should not wrap in this case! */
 679     g_assert (array->head < array->size);
 680     array->length--;
 681     return TRUE;
 682   }
 683
 684   g_return_val_if_reached (FALSE);
 685 }
 686
 687 /**
 688  * gst_queue_array_drop_element: (skip)
 689  * @array: a #GstQueueArray object
 690  * @idx: index to drop
 691  *
 692  * Drops the queue element at position @idx from queue @array.
 693  *
 694  * Returns: the dropped element
 695  *
 696  * Since: 1.2
 697  */
 698 gpointer
 699 gst_queue_array_drop_element (GstQueueArray * array, guint idx)
 700 {
 701   gpointer ptr;
 702
 703   if (!gst_queue_array_drop_struct (array, idx, &ptr))
 704     return NULL;
 705
 706   return ptr;
 707 }
 708
 709 /**
 710  * gst_queue_array_find: (skip)
 711  * @array: a #GstQueueArray object
 712  * @func: (allow-none): comparison function, or %NULL to find @data by value
 713  * @data: data for comparison function
 714  *
 715  * Finds an element in the queue @array, either by comparing every element
 716  * with @func or by looking up @data if no compare function @func is provided,
 717  * and returning the index of the found element.
 718  *
 719  * Returns: Index of the found element or -1 if nothing was found.
 720  *
 721  * Since: 1.2
 722  */
 723 guint
 724 gst_queue_array_find (GstQueueArray * array, GCompareFunc func, gpointer data)
 725 {
 726   gpointer p_element;
 727   guint elt_size;
 728   guint i;
 729
 730   /* For struct arrays we need to implement this differently so that
 731    * the user gets a pointer to the element data not the dereferenced
 732    * pointer itself */
 733
 734   g_return_val_if_fail (array != NULL, -1);
 735   g_return_val_if_fail (array->struct_array == FALSE, -1);
 736
 737   elt_size = array->elt_size;
 738
 739   if (func != NULL) {
 740     /* Scan from head to tail */
 741     for (i = 0; i < array->length; i++) {
 742       p_element = array->array + ((i + array->head) % array->size) * elt_size;
 743       if (func (*(gpointer *) p_element, data) == 0)
 744         return i;
 745     }
 746   } else {
 747     for (i = 0; i < array->length; i++) {
 748       p_element = array->array + ((i + array->head) % array->size) * elt_size;
 749       if (*(gpointer *) p_element == data)
 750         return i;
 751     }
 752   }
 753
 754   return -1;
 755 }
 756
 757 /**
 758  * gst_queue_array_get_length: (skip)
 759  * @array: a #GstQueueArray object
 760  *
 761  * Returns the length of the queue @array
 762  *
 763  * Returns: the length of the queue @array.
 764  *
 765  * Since: 1.2
 766  */
 767 guint
 768 gst_queue_array_get_length (GstQueueArray * array)
 769 {
 770   g_return_val_if_fail (array != NULL, 0);
 771   return array->length;
 772 }