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