gst/gstiterator.c

   1 /* GStreamer
   2  * Copyright (C) 2004 Wim Taymans <wim@fluendo.com>
   3  *
   4  * gstiterator.h: Base class for iterating datastructures.
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Library General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Library General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Library General Public
  17  * License along with this library; if not, write to the
  18  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19  * Boston, MA 02111-1307, USA.
  20  */
  21
  22 /**
  23  * SECTION:gstiterator
  24  * @short_description: Object to retrieve multiple elements in a threadsafe
  25  * way.
  26  * @see_also: #GstElement, #GstBin
  27  *
  28  * A GstIterator is used to retrieve multiple objects from another object in
  29  * a threadsafe way.
  30  *
  31  * Various GStreamer objects provide access to their internal structures using
  32  * an iterator.
  33  *
  34  * In general, whenever calling a GstIterator function results in your code
  35  * receiving a refcounted object, the refcount for that object will have been
  36  * increased.  Your code is responsible for unrefing that object after use.
  37  *
  38  * The basic use pattern of an iterator is as follows:
  39  *
  40  * <example>
  41  * <title>Using an iterator</title>
  42  *   <programlisting>
  43  *    it = _get_iterator(object);
  44  *    done = FALSE;
  45  *    while (!done) {
  46  *      switch (gst_iterator_next (it, &amp;item)) {
  47  *        case GST_ITERATOR_OK:
  48  *          ... use/change item here...
  49  *          gst_object_unref (item);
  50  *          break;
  51  *        case GST_ITERATOR_RESYNC:
  52  *          ...rollback changes to items...
  53  *          gst_iterator_resync (it);
  54  *          break;
  55  *        case GST_ITERATOR_ERROR:
  56  *          ...wrong parameters were given...
  57  *          done = TRUE;
  58  *          break;
  59  *        case GST_ITERATOR_DONE:
  60  *          done = TRUE;
  61  *          break;
  62  *      }
  63  *    }
  64  *    gst_iterator_free (it);
  65  *   </programlisting>
  66  * </example>
  67  *
  68  * Last reviewed on 2009-06-16 (0.10.24)
  69  */
  70
  71 #include "gst_private.h"
  72 #include <gst/gstiterator.h>
  73
  74 static void
  75 gst_iterator_init (GstIterator * it,
  76     GType type,
  77     GMutex * lock,
  78     guint32 * master_cookie,
  79     GstIteratorNextFunction next,
  80     GstIteratorItemFunction item,
  81     GstIteratorResyncFunction resync, GstIteratorFreeFunction free)
  82 {
  83   it->type = type;
  84   it->lock = lock;
  85   it->master_cookie = master_cookie;
  86   it->cookie = *master_cookie;
  87   it->next = next;
  88   it->item = item;
  89   it->resync = resync;
  90   it->free = free;
  91   it->pushed = NULL;
  92 }
  93
  94 /**
  95  * gst_iterator_new:
  96  * @size: the size of the iterator structure
  97  * @type: #GType of children
  98  * @lock: pointer to a #GMutex.
  99  * @master_cookie: pointer to a guint32 that is changed when the items in the
 100  *    iterator changed.
 101  * @next: function to get next item
 102  * @item: function to call on each item retrieved
 103  * @resync: function to resync the iterator
 104  * @free: function to free the iterator
 105  *
 106  * Create a new iterator. This function is mainly used for objects
 107  * implementing the next/resync/free function to iterate a data structure.
 108  *
 109  * For each item retrieved, the @item function is called with the lock
 110  * held. The @free function is called when the iterator is freed.
 111  *
 112  * Returns: the new #GstIterator.
 113  *
 114  * MT safe.
 115  */
 116 GstIterator *
 117 gst_iterator_new (guint size,
 118     GType type,
 119     GMutex * lock,
 120     guint32 * master_cookie,
 121     GstIteratorNextFunction next,
 122     GstIteratorItemFunction item,
 123     GstIteratorResyncFunction resync, GstIteratorFreeFunction free)
 124 {
 125   GstIterator *result;
 126
 127   g_return_val_if_fail (size >= sizeof (GstIterator), NULL);
 128   g_return_val_if_fail (g_type_qname (type) != 0, NULL);
 129   g_return_val_if_fail (master_cookie != NULL, NULL);
 130   g_return_val_if_fail (next != NULL, NULL);
 131   g_return_val_if_fail (resync != NULL, NULL);
 132   g_return_val_if_fail (free != NULL, NULL);
 133
 134   result = g_malloc (size);
 135   gst_iterator_init (result, type, lock, master_cookie, next, item, resync,
 136       free);
 137
 138   return result;
 139 }
 140
 141 /*
 142  * list iterator
 143  */
 144 typedef struct _GstListIterator
 145 {
 146   GstIterator iterator;
 147   gpointer owner;
 148   GList **orig;
 149   GList *list;                  /* pointer in list */
 150   GstIteratorDisposeFunction freefunc;
 151 } GstListIterator;
 152
 153 static GstIteratorResult
 154 gst_list_iterator_next (GstListIterator * it, gpointer * elem)
 155 {
 156   if (it->list == NULL)
 157     return GST_ITERATOR_DONE;
 158
 159   *elem = it->list->data;
 160   it->list = g_list_next (it->list);
 161
 162   return GST_ITERATOR_OK;
 163 }
 164
 165 static void
 166 gst_list_iterator_resync (GstListIterator * it)
 167 {
 168   it->list = *it->orig;
 169 }
 170
 171 static void
 172 gst_list_iterator_free (GstListIterator * it)
 173 {
 174   if (it->freefunc) {
 175     it->freefunc (it->owner);
 176   }
 177   g_free (it);
 178 }
 179
 180 /**
 181  * gst_iterator_new_list:
 182  * @type: #GType of elements
 183  * @lock: pointer to a #GMutex protecting the list.
 184  * @master_cookie: pointer to a guint32 that is incremented when the list
 185  *     is changed.
 186  * @list: pointer to the list
 187  * @owner: object owning the list
 188  * @item: function to call for each item
 189  * @free: function to call when the iterator is freed
 190  *
 191  * Create a new iterator designed for iterating @list.
 192  *
 193  * The list you iterate is usually part of a data structure @owner and is
 194  * protected with @lock.
 195  *
 196  * The iterator will use @lock to retrieve the next item of the list and it
 197  * will then call the @item function before releasing @lock again.
 198  *
 199  * The @item function usualy makes sure that the item remains alive while
 200  * @lock is released and the application is using the item. The application is
 201  * responsible for freeing/unreffing the item after usage as explained in
 202  * gst_iterator_next().
 203  *
 204  * When a concurrent update to the list is performed, usually by @owner while
 205  * holding @lock, @master_cookie will be updated. The iterator implementation
 206  * will notice the update of the cookie and will return %GST_ITERATOR_RESYNC to
 207  * the user of the iterator in the next call to gst_iterator_next().
 208  *
 209  * @owner will be passed to the @free function when the iterator is freed.
 210  *
 211  * Returns: the new #GstIterator for @list.
 212  *
 213  * MT safe.
 214  */
 215 GstIterator *
 216 gst_iterator_new_list (GType type,
 217     GMutex * lock,
 218     guint32 * master_cookie,
 219     GList ** list,
 220     gpointer owner,
 221     GstIteratorItemFunction item, GstIteratorDisposeFunction free)
 222 {
 223   GstListIterator *result;
 224
 225   /* no need to lock, nothing can change here */
 226   result = (GstListIterator *) gst_iterator_new (sizeof (GstListIterator),
 227       type,
 228       lock,
 229       master_cookie,
 230       (GstIteratorNextFunction) gst_list_iterator_next,
 231       (GstIteratorItemFunction) item,
 232       (GstIteratorResyncFunction) gst_list_iterator_resync,
 233       (GstIteratorFreeFunction) gst_list_iterator_free);
 234
 235   result->owner = owner;
 236   result->orig = list;
 237   result->list = *list;
 238   result->freefunc = free;
 239
 240   return GST_ITERATOR (result);
 241 }
 242
 243 static void
 244 gst_iterator_pop (GstIterator * it)
 245 {
 246   if (it->pushed) {
 247     gst_iterator_free (it->pushed);
 248     it->pushed = NULL;
 249   }
 250 }
 251
 252 /**
 253  * gst_iterator_next:
 254  * @it: The #GstIterator to iterate
 255  * @elem: pointer to hold next element
 256  *
 257  * Get the next item from the iterator in @elem.
 258  *
 259  * Only when this function returns %GST_ITERATOR_OK, @elem will contain a valid
 260  * value. For iterators that return refcounted objects, the returned object
 261  * will have its refcount increased and should therefore be unreffed after
 262  * usage.
 263  *
 264  * When this function returns %GST_ITERATOR_DONE, no more elements can be
 265  * retrieved from @it.
 266  *
 267  * A return value of %GST_ITERATOR_RESYNC indicates that the element list was
 268  * concurrently updated. The user of @it should call gst_iterator_resync() to
 269  * get the newly updated list.
 270  *
 271  * A return value of %GST_ITERATOR_ERROR indicates an unrecoverable fatal error.
 272  *
 273  * Returns: The result of the iteration. Unref @elem after usage if this
 274  * is a refcounted object.
 275  *
 276  * MT safe.
 277  */
 278 GstIteratorResult
 279 gst_iterator_next (GstIterator * it, gpointer * elem)
 280 {
 281   GstIteratorResult result;
 282
 283   g_return_val_if_fail (it != NULL, GST_ITERATOR_ERROR);
 284   g_return_val_if_fail (elem != NULL, GST_ITERATOR_ERROR);
 285
 286 restart:
 287   if (it->pushed) {
 288     result = gst_iterator_next (it->pushed, elem);
 289     if (result == GST_ITERATOR_DONE) {
 290       /* we are done with this iterator, pop it and
 291        * fallthrough iterating the main iterator again. */
 292       gst_iterator_pop (it);
 293     } else {
 294       return result;
 295     }
 296   }
 297
 298   if (G_LIKELY (it->lock))
 299     g_mutex_lock (it->lock);
 300
 301   if (G_UNLIKELY (*it->master_cookie != it->cookie)) {
 302     result = GST_ITERATOR_RESYNC;
 303     goto done;
 304   }
 305
 306   result = it->next (it, elem);
 307   if (result == GST_ITERATOR_OK && it->item) {
 308     GstIteratorItem itemres;
 309
 310     itemres = it->item (it, *elem);
 311     switch (itemres) {
 312       case GST_ITERATOR_ITEM_SKIP:
 313         if (G_LIKELY (it->lock))
 314           g_mutex_unlock (it->lock);
 315         goto restart;
 316       case GST_ITERATOR_ITEM_END:
 317         result = GST_ITERATOR_DONE;
 318         break;
 319       case GST_ITERATOR_ITEM_PASS:
 320         break;
 321     }
 322   }
 323
 324 done:
 325   if (G_LIKELY (it->lock))
 326     g_mutex_unlock (it->lock);
 327
 328   return result;
 329 }
 330
 331 /**
 332  * gst_iterator_resync:
 333  * @it: The #GstIterator to resync
 334  *
 335  * Resync the iterator. this function is mostly called
 336  * after gst_iterator_next() returned %GST_ITERATOR_RESYNC.
 337  *
 338  * When an iterator was pushed on @it, it will automatically be popped again
 339  * with this function.
 340  *
 341  * MT safe.
 342  */
 343 void
 344 gst_iterator_resync (GstIterator * it)
 345 {
 346   g_return_if_fail (it != NULL);
 347
 348   gst_iterator_pop (it);
 349
 350   if (G_LIKELY (it->lock))
 351     g_mutex_lock (it->lock);
 352   it->resync (it);
 353   it->cookie = *it->master_cookie;
 354   if (G_LIKELY (it->lock))
 355     g_mutex_unlock (it->lock);
 356 }
 357
 358 /**
 359  * gst_iterator_free:
 360  * @it: The #GstIterator to free
 361  *
 362  * Free the iterator.
 363  *
 364  * MT safe.
 365  */
 366 void
 367 gst_iterator_free (GstIterator * it)
 368 {
 369   g_return_if_fail (it != NULL);
 370
 371   gst_iterator_pop (it);
 372
 373   it->free (it);
 374 }
 375
 376 /**
 377  * gst_iterator_push:
 378  * @it: The #GstIterator to use
 379  * @other: The #GstIterator to push
 380  *
 381  * Pushes @other iterator onto @it. All calls performed on @it are
 382  * forwarded to @other. If @other returns %GST_ITERATOR_DONE, it is
 383  * popped again and calls are handled by @it again.
 384  *
 385  * This function is mainly used by objects implementing the iterator
 386  * next function to recurse into substructures.
 387  *
 388  * When gst_iterator_resync() is called on @it, @other will automatically be
 389  * popped.
 390  *
 391  * MT safe.
 392  */
 393 void
 394 gst_iterator_push (GstIterator * it, GstIterator * other)
 395 {
 396   g_return_if_fail (it != NULL);
 397   g_return_if_fail (other != NULL);
 398
 399   it->pushed = other;
 400 }
 401
 402 typedef struct _GstIteratorFilter
 403 {
 404   GstIterator iterator;
 405   GstIterator *slave;
 406
 407   GCompareFunc func;
 408   gpointer user_data;
 409 } GstIteratorFilter;
 410
 411 static GstIteratorResult
 412 filter_next (GstIteratorFilter * it, gpointer * elem)
 413 {
 414   GstIteratorResult result = GST_ITERATOR_ERROR;
 415   gboolean done = FALSE;
 416
 417   *elem = NULL;
 418
 419   while (G_LIKELY (!done)) {
 420     gpointer item;
 421
 422     result = gst_iterator_next (it->slave, &item);
 423     switch (result) {
 424       case GST_ITERATOR_OK:
 425         if (G_LIKELY (GST_ITERATOR (it)->lock))
 426           g_mutex_unlock (GST_ITERATOR (it)->lock);
 427         if (it->func (item, it->user_data) == 0) {
 428           *elem = item;
 429           done = TRUE;
 430         }
 431         if (G_LIKELY (GST_ITERATOR (it)->lock))
 432           g_mutex_lock (GST_ITERATOR (it)->lock);
 433         break;
 434       case GST_ITERATOR_RESYNC:
 435       case GST_ITERATOR_DONE:
 436         done = TRUE;
 437         break;
 438       default:
 439         g_assert_not_reached ();
 440         break;
 441     }
 442   }
 443   return result;
 444 }
 445
 446 static void
 447 filter_resync (GstIteratorFilter * it)
 448 {
 449   gst_iterator_resync (it->slave);
 450 }
 451
 452 static void
 453 filter_uninit (GstIteratorFilter * it)
 454 {
 455   it->slave->lock = GST_ITERATOR (it)->lock;
 456 }
 457
 458 static void
 459 filter_free (GstIteratorFilter * it)
 460 {
 461   filter_uninit (it);
 462   gst_iterator_free (it->slave);
 463   g_free (it);
 464 }
 465
 466 /**
 467  * gst_iterator_filter:
 468  * @it: The #GstIterator to filter
 469  * @func: the compare function to select elements
 470  * @user_data: user data passed to the compare function
 471  *
 472  * Create a new iterator from an existing iterator. The new iterator
 473  * will only return those elements that match the given compare function @func.
 474  * @func should return 0 for elements that should be included
 475  * in the iterator.
 476  *
 477  * When this iterator is freed, @it will also be freed.
 478  *
 479  * Returns: a new #GstIterator.
 480  *
 481  * MT safe.
 482  */
 483 GstIterator *
 484 gst_iterator_filter (GstIterator * it, GCompareFunc func, gpointer user_data)
 485 {
 486   GstIteratorFilter *result;
 487
 488   g_return_val_if_fail (it != NULL, NULL);
 489   g_return_val_if_fail (func != NULL, NULL);
 490
 491   result = (GstIteratorFilter *) gst_iterator_new (sizeof (GstIteratorFilter),
 492       it->type, it->lock, it->master_cookie,
 493       (GstIteratorNextFunction) filter_next,
 494       (GstIteratorItemFunction) NULL,
 495       (GstIteratorResyncFunction) filter_resync,
 496       (GstIteratorFreeFunction) filter_free);
 497   it->lock = NULL;
 498   result->func = func;
 499   result->user_data = user_data;
 500   result->slave = it;
 501
 502   return GST_ITERATOR (result);
 503 }
 504
 505 /**
 506  * gst_iterator_fold:
 507  * @it: The #GstIterator to fold over
 508  * @func: the fold function
 509  * @ret: the seed value passed to the fold function
 510  * @user_data: user data passed to the fold function
 511  *
 512  * Folds @func over the elements of @iter. That is to say, @func will be called
 513  * as @func (object, @ret, @user_data) for each object in @it. The normal use
 514  * of this procedure is to accumulate the results of operating on the objects in
 515  * @ret.  If object is a refcounted object its refcount will be increased
 516  * before @func is called, and it should be unrefed after use in @func.
 517  *
 518  * This procedure can be used (and is used internally) to implement the
 519  * gst_iterator_foreach() and gst_iterator_find_custom() operations.
 520  *
 521  * The fold will proceed as long as @func returns TRUE. When the iterator has no
 522  * more arguments, %GST_ITERATOR_DONE will be returned. If @func returns FALSE,
 523  * the fold will stop, and %GST_ITERATOR_OK will be returned. Errors or resyncs
 524  * will cause fold to return %GST_ITERATOR_ERROR or %GST_ITERATOR_RESYNC as
 525  * appropriate.
 526  *
 527  * The iterator will not be freed.
 528  *
 529  * Returns: A #GstIteratorResult, as described above.
 530  *
 531  * MT safe.
 532  */
 533 GstIteratorResult
 534 gst_iterator_fold (GstIterator * it, GstIteratorFoldFunction func,
 535     GValue * ret, gpointer user_data)
 536 {
 537   gpointer item;
 538   GstIteratorResult result;
 539
 540   while (1) {
 541     result = gst_iterator_next (it, &item);
 542     switch (result) {
 543       case GST_ITERATOR_OK:
 544         /* FIXME: is there a way to ref/unref items? */
 545         if (!func (item, ret, user_data))
 546           goto fold_done;
 547         else
 548           break;
 549       case GST_ITERATOR_RESYNC:
 550       case GST_ITERATOR_ERROR:
 551         goto fold_done;
 552       case GST_ITERATOR_DONE:
 553         goto fold_done;
 554     }
 555   }
 556
 557 fold_done:
 558   return result;
 559 }
 560
 561 typedef struct
 562 {
 563   GFunc func;
 564   gpointer user_data;
 565 } ForeachFoldData;
 566
 567 static gboolean
 568 foreach_fold_func (gpointer item, GValue * unused, ForeachFoldData * data)
 569 {
 570   data->func (item, data->user_data);
 571   return TRUE;
 572 }
 573
 574 /**
 575  * gst_iterator_foreach:
 576  * @it: The #GstIterator to iterate
 577  * @func: the function to call for each element.
 578  * @user_data: user data passed to the function
 579  *
 580  * Iterate over all element of @it and call the given function @func for
 581  * each element.  As in gst_iterator_fold(), the refcount of a refcounted
 582  * object will be increased before @func is called, and should be unrefed
 583  * after use.
 584  *
 585  * Returns: the result call to gst_iterator_fold(). The iterator will not be
 586  * freed.
 587  *
 588  * MT safe.
 589  */
 590 GstIteratorResult
 591 gst_iterator_foreach (GstIterator * it, GFunc func, gpointer user_data)
 592 {
 593   ForeachFoldData data;
 594
 595   data.func = func;
 596   data.user_data = user_data;
 597
 598   return gst_iterator_fold (it, (GstIteratorFoldFunction) foreach_fold_func,
 599       NULL, &data);
 600 }
 601
 602 typedef struct
 603 {
 604   GCompareFunc func;
 605   gpointer user_data;
 606 } FindCustomFoldData;
 607
 608 static gboolean
 609 find_custom_fold_func (gpointer item, GValue * ret, FindCustomFoldData * data)
 610 {
 611   if (data->func (item, data->user_data) == 0) {
 612     g_value_set_pointer (ret, item);
 613     return FALSE;
 614   } else {
 615     return TRUE;
 616   }
 617 }
 618
 619 /**
 620  * gst_iterator_find_custom:
 621  * @it: The #GstIterator to iterate
 622  * @func: the compare function to use
 623  * @user_data: user data passed to the compare function
 624  *
 625  * Find the first element in @it that matches the compare function @func.
 626  * @func should return 0 when the element is found.  As in gst_iterator_fold(),
 627  * the refcount of a refcounted object will be increased before @func is
 628  * called, and should be unrefed after use.
 629  *
 630  * The iterator will not be freed.
 631  *
 632  * This function will return NULL if an error or resync happened to
 633  * the iterator.
 634  *
 635  * Returns: The element in the iterator that matches the compare
 636  * function or NULL when no element matched.
 637  *
 638  * MT safe.
 639  */
 640 gpointer
 641 gst_iterator_find_custom (GstIterator * it, GCompareFunc func,
 642     gpointer user_data)
 643 {
 644   GValue ret = { 0, };
 645   GstIteratorResult res;
 646   FindCustomFoldData data;
 647
 648   g_value_init (&ret, G_TYPE_POINTER);
 649   data.func = func;
 650   data.user_data = user_data;
 651
 652   /* FIXME, we totally ignore RESYNC and return NULL so that the
 653    * app does not know if the element was not found or a resync happened */
 654   res =
 655       gst_iterator_fold (it, (GstIteratorFoldFunction) find_custom_fold_func,
 656       &ret, &data);
 657
 658   /* no need to unset, it's just a pointer */
 659   return g_value_get_pointer (&ret);
 660 }
 661
 662 typedef struct
 663 {
 664   GstIterator parent;
 665   gpointer object;
 666   GstCopyFunction copy;
 667   GFreeFunc free;
 668   gboolean visited;
 669 } GstSingleObjectIterator;
 670
 671 static guint32 _single_object_dummy_cookie = 0;
 672
 673 static GstIteratorResult
 674 gst_single_object_iterator_iterator_next (GstSingleObjectIterator * it,
 675     gpointer * result)
 676 {
 677   if (it->visited || !it->object) {
 678     *result = NULL;
 679     return GST_ITERATOR_DONE;
 680   }
 681
 682   *result = it->copy (it->object);
 683   return GST_ITERATOR_OK;
 684 }
 685
 686 static void
 687 gst_single_object_iterator_resync (GstSingleObjectIterator * it)
 688 {
 689   it->visited = FALSE;
 690 }
 691
 692 static void
 693 gst_single_object_iterator_free (GstSingleObjectIterator * it)
 694 {
 695   if (it->object)
 696     it->free (it->object);
 697   g_free (it);
 698 }
 699
 700 /**
 701  * gst_iterator_new:
 702  * @type: #GType of the passed object
 703  * @object: object that this iterator should return
 704  * @copy: Function that returns a copy of @object or increases its refcount
 705  * @free: Function to be called for freeing @object
 706  *
 707  * This #GstIterator is a convenient iterator for the common
 708  * case where a #GstIterator needs to be returned but only
 709  * a single object has the be considered. This happens often
 710  * for the #GstPadIterIntLinkFunction.
 711  *
 712  * Since: 0.10.25
 713  *
 714  */
 715 GstIterator *
 716 gst_iterator_new_single (GType type, gpointer object, GstCopyFunction copy,
 717     GFreeFunc free)
 718 {
 719   GstSingleObjectIterator *result;
 720
 721   g_return_val_if_fail (copy != NULL, NULL);
 722   g_return_val_if_fail (free != NULL, NULL);
 723
 724   result = (GstSingleObjectIterator *)
 725       gst_iterator_new (sizeof (GstSingleObjectIterator),
 726       G_TYPE_FROM_INSTANCE (object), NULL, &_single_object_dummy_cookie,
 727       (GstIteratorNextFunction) gst_single_object_iterator_iterator_next, NULL,
 728       (GstIteratorResyncFunction) gst_single_object_iterator_resync,
 729       (GstIteratorFreeFunction) gst_single_object_iterator_free);
 730
 731   result->object = (object) ? copy (object) : NULL;
 732   result->copy = copy;
 733   result->free = free;
 734   result->visited = FALSE;
 735
 736   return (GstIterator *) result;
 737 }