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