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