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