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 *
gst_queue_array_new_for_struct(gsize struct_size,guint initial_size)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 *
gst_queue_array_new(guint initial_size)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
gst_queue_array_free(GstQueueArray * array)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
gst_queue_array_set_clear_func(GstQueueArray * array,GDestroyNotify clear_func)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
gst_queue_array_clear_idx(GstQueueArray * array,guint idx)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
gst_queue_array_clear(GstQueueArray * array)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
gst_queue_array_pop_head_struct(GstQueueArray * array)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
gst_queue_array_pop_head(GstQueueArray * array)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
gst_queue_array_peek_head_struct(GstQueueArray * array)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
gst_queue_array_peek_head(GstQueueArray * array)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
gst_queue_array_peek_nth(GstQueueArray * array,guint idx)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
gst_queue_array_peek_nth_struct(GstQueueArray * array,guint idx)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
gst_queue_array_do_expand(GstQueueArray * array)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
gst_queue_array_push_tail_struct(GstQueueArray * array,gpointer p_struct)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
gst_queue_array_push_tail(GstQueueArray * array,gpointer data)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
gst_queue_array_peek_tail(GstQueueArray * array)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
gst_queue_array_peek_tail_struct(GstQueueArray * array)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
gst_queue_array_pop_tail(GstQueueArray * array)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
gst_queue_array_pop_tail_struct(GstQueueArray * array)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
gst_queue_array_is_empty(GstQueueArray * array)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
gst_queue_array_drop_struct(GstQueueArray * array,guint idx,gpointer p_struct)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
gst_queue_array_drop_element(GstQueueArray * array,guint idx)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
gst_queue_array_find(GstQueueArray * array,GCompareFunc func,gpointer data)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
gst_queue_array_get_length(GstQueueArray * array)768 gst_queue_array_get_length (GstQueueArray * array)
769 {
770 g_return_val_if_fail (array != NULL, 0);
771 return array->length;
772 }
773