gst/gstcaps.c

   1 /* GStreamer
   2  * Copyright (C) <2003> David A. Schleef <ds@schleef.org>
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor,
  17  * Boston, MA 02110-1301, USA.
  18  */
  19
  20 /**
  21  * SECTION:gstcaps
  22  * @short_description: Structure describing sets of media formats
  23  * @see_also: #GstStructure, #GstMiniObject
  24  *
  25  * Caps (capabilities) are lightweight refcounted objects describing media types.
  26  * They are composed of an array of #GstStructure.
  27  *
  28  * Caps are exposed on #GstPadTemplate to describe all possible types a
  29  * given pad can handle. They are also stored in the #GstRegistry along with
  30  * a description of the #GstElement.
  31  *
  32  * Caps are exposed on the element pads using the gst_pad_query_caps() pad
  33  * function. This function describes the possible types that the pad can
  34  * handle or produce at runtime.
  35  *
  36  * A #GstCaps can be constructed with the following code fragment:
  37  *
  38  * <example>
  39  *  <title>Creating caps</title>
  40  *  <programlisting>
  41  *  GstCaps *caps;
  42  *  caps = gst_caps_new_simple ("video/x-raw",
  43  *       "format", G_TYPE_STRING, "I420",
  44  *       "framerate", GST_TYPE_FRACTION, 25, 1,
  45  *       "pixel-aspect-ratio", GST_TYPE_FRACTION, 1, 1,
  46  *       "width", G_TYPE_INT, 320,
  47  *       "height", G_TYPE_INT, 240,
  48  *       NULL);
  49  *  </programlisting>
  50  * </example>
  51  *
  52  * A #GstCaps is fixed when it has no properties with ranges or lists. Use
  53  * gst_caps_is_fixed() to test for fixed caps. Fixed caps can be used in a
  54  * caps event to notify downstream elements of the current media type.
  55  *
  56  * Various methods exist to work with the media types such as subtracting
  57  * or intersecting.
  58  *
  59  * Be aware that the current #GstCaps / #GstStructure serialization into string
  60  * has limited support for nested #GstCaps / #GstStructure fields. It can only
  61  * support one level of nesting. Using more levels will lead to unexpected
  62  * behavior when using serialization features, such as gst_caps_to_string() or
  63  * gst_value_serialize() and their counterparts.
  64  *
  65  * Last reviewed on 2011-03-28 (0.11.3)
  66  */
  67
  68 #ifdef HAVE_CONFIG_H
  69 #include "config.h"
  70 #endif
  71 #include <string.h>
  72 #include <signal.h>
  73
  74 #include "gst_private.h"
  75 #include <gst/gst.h>
  76 #include <gobject/gvaluecollector.h>
  77
  78 #define DEBUG_REFCOUNT
  79
  80 typedef struct _GstCapsArrayElement
  81 {
  82   GstStructure *structure;
  83   GstCapsFeatures *features;
  84 } GstCapsArrayElement;
  85
  86 typedef struct _GstCapsImpl
  87 {
  88   GstCaps caps;
  89
  90   GArray *array;
  91 } GstCapsImpl;
  92
  93 #define GST_CAPS_ARRAY(c) (((GstCapsImpl *)(c))->array)
  94
  95 #define GST_CAPS_LEN(c)   (GST_CAPS_ARRAY(c)->len)
  96
  97 #define IS_WRITABLE(caps) \
  98   (GST_CAPS_REFCOUNT_VALUE (caps) == 1)
  99
 100 /* same as gst_caps_is_any () */
 101 #define CAPS_IS_ANY(caps)                               \
 102   (GST_CAPS_FLAGS(caps) & GST_CAPS_FLAG_ANY)
 103
 104 /* same as gst_caps_is_empty () */
 105 #define CAPS_IS_EMPTY(caps)                             \
 106   (!CAPS_IS_ANY(caps) && CAPS_IS_EMPTY_SIMPLE(caps))
 107
 108 #define CAPS_IS_EMPTY_SIMPLE(caps)                                      \
 109   ((GST_CAPS_ARRAY (caps) == NULL) || (GST_CAPS_LEN (caps) == 0))
 110
 111 #define gst_caps_features_copy_conditional(f) ((f && (gst_caps_features_is_any (f) || !gst_caps_features_is_equal (f, GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY))) ? gst_caps_features_copy (f) : NULL)
 112
 113 /* quick way to get a caps structure at an index without doing a type or array
 114  * length check */
 115 #define gst_caps_get_structure_unchecked(caps, index) \
 116      (g_array_index (GST_CAPS_ARRAY (caps), GstCapsArrayElement, (index)).structure)
 117 #define gst_caps_get_features_storage_unchecked(caps, index) \
 118      (&g_array_index (GST_CAPS_ARRAY (caps), GstCapsArrayElement, (index)).features)
 119 #define gst_caps_get_features_unchecked(caps, index) \
 120      (g_atomic_pointer_get (gst_caps_get_features_storage_unchecked (caps, index)))
 121 /* quick way to append a structure without checking the args */
 122 #define gst_caps_append_structure_unchecked(caps, s, f) G_STMT_START{\
 123   GstCapsArrayElement __e={s, f};                                      \
 124   if (gst_structure_set_parent_refcount (__e.structure, &GST_MINI_OBJECT_REFCOUNT(caps)) && \
 125       (!__e.features || gst_caps_features_set_parent_refcount (__e.features, &GST_MINI_OBJECT_REFCOUNT(caps))))         \
 126     g_array_append_val (GST_CAPS_ARRAY (caps), __e);                             \
 127 }G_STMT_END
 128
 129 /* lock to protect multiple invocations of static caps to caps conversion */
 130 G_LOCK_DEFINE_STATIC (static_caps_lock);
 131
 132 static void gst_caps_transform_to_string (const GValue * src_value,
 133     GValue * dest_value);
 134 static gboolean gst_caps_from_string_inplace (GstCaps * caps,
 135     const gchar * string);
 136
 137 GType _gst_caps_type = 0;
 138 GstCaps *_gst_caps_any;
 139 GstCaps *_gst_caps_none;
 140
 141 GST_DEFINE_MINI_OBJECT_TYPE (GstCaps, gst_caps);
 142
 143 void
 144 _priv_gst_caps_initialize (void)
 145 {
 146   _gst_caps_type = gst_caps_get_type ();
 147
 148   _gst_caps_any = gst_caps_new_any ();
 149   _gst_caps_none = gst_caps_new_empty ();
 150
 151   g_value_register_transform_func (_gst_caps_type,
 152       G_TYPE_STRING, gst_caps_transform_to_string);
 153 }
 154
 155 static GstCaps *
 156 _gst_caps_copy (const GstCaps * caps)
 157 {
 158   GstCaps *newcaps;
 159   GstStructure *structure;
 160   GstCapsFeatures *features;
 161   guint i, n;
 162
 163   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 164
 165   newcaps = gst_caps_new_empty ();
 166   GST_CAPS_FLAGS (newcaps) = GST_CAPS_FLAGS (caps);
 167   n = GST_CAPS_LEN (caps);
 168
 169   GST_CAT_DEBUG_OBJECT (GST_CAT_PERFORMANCE, caps, "doing copy %p -> %p",
 170       caps, newcaps);
 171
 172   for (i = 0; i < n; i++) {
 173     structure = gst_caps_get_structure_unchecked (caps, i);
 174     features = gst_caps_get_features_unchecked (caps, i);
 175     gst_caps_append_structure_full (newcaps, gst_structure_copy (structure),
 176         gst_caps_features_copy_conditional (features));
 177   }
 178
 179   return newcaps;
 180 }
 181
 182 /* creation/deletion */
 183 static void
 184 _gst_caps_free (GstCaps * caps)
 185 {
 186   GstStructure *structure;
 187   GstCapsFeatures *features;
 188   guint i, len;
 189
 190   /* The refcount must be 0, but since we're only called by gst_caps_unref,
 191    * don't bother testing. */
 192   len = GST_CAPS_LEN (caps);
 193   /* This can be used to get statistics about caps sizes */
 194   /*GST_CAT_INFO (GST_CAT_CAPS, "caps size: %d", len); */
 195   for (i = 0; i < len; i++) {
 196     structure = gst_caps_get_structure_unchecked (caps, i);
 197     gst_structure_set_parent_refcount (structure, NULL);
 198     gst_structure_free (structure);
 199     features = gst_caps_get_features_unchecked (caps, i);
 200     if (features) {
 201       gst_caps_features_set_parent_refcount (features, NULL);
 202       gst_caps_features_free (features);
 203     }
 204   }
 205   g_array_free (GST_CAPS_ARRAY (caps), TRUE);
 206
 207 #ifdef DEBUG_REFCOUNT
 208   GST_CAT_TRACE (GST_CAT_CAPS, "freeing caps %p", caps);
 209 #endif
 210   g_slice_free1 (sizeof (GstCapsImpl), caps);
 211 }
 212
 213 static void
 214 gst_caps_init (GstCaps * caps)
 215 {
 216   gst_mini_object_init (GST_MINI_OBJECT_CAST (caps), 0, _gst_caps_type,
 217       (GstMiniObjectCopyFunction) _gst_caps_copy, NULL,
 218       (GstMiniObjectFreeFunction) _gst_caps_free);
 219
 220   /* the 32 has been determined by logging caps sizes in _gst_caps_free
 221    * but g_ptr_array uses 16 anyway if it expands once, so this does not help
 222    * in practice
 223    * GST_CAPS_ARRAY (caps) = g_ptr_array_sized_new (32);
 224    */
 225   GST_CAPS_ARRAY (caps) =
 226       g_array_new (FALSE, TRUE, sizeof (GstCapsArrayElement));
 227 }
 228
 229 /**
 230  * gst_caps_new_empty:
 231  *
 232  * Creates a new #GstCaps that is empty.  That is, the returned
 233  * #GstCaps contains no media formats.
 234  * The #GstCaps is guaranteed to be writable.
 235  * Caller is responsible for unreffing the returned caps.
 236  *
 237  * Returns: (transfer full): the new #GstCaps
 238  */
 239 GstCaps *
 240 gst_caps_new_empty (void)
 241 {
 242   GstCaps *caps;
 243
 244   caps = (GstCaps *) g_slice_new (GstCapsImpl);
 245
 246   gst_caps_init (caps);
 247
 248 #ifdef DEBUG_REFCOUNT
 249   GST_CAT_TRACE (GST_CAT_CAPS, "created caps %p", caps);
 250 #endif
 251
 252   return caps;
 253 }
 254
 255 /**
 256  * gst_caps_new_any:
 257  *
 258  * Creates a new #GstCaps that indicates that it is compatible with
 259  * any media format.
 260  *
 261  * Returns: (transfer full): the new #GstCaps
 262  */
 263 GstCaps *
 264 gst_caps_new_any (void)
 265 {
 266   GstCaps *caps = gst_caps_new_empty ();
 267
 268   GST_CAPS_FLAG_SET (caps, GST_CAPS_FLAG_ANY);
 269
 270   return caps;
 271 }
 272
 273 /**
 274  * gst_caps_new_empty_simple:
 275  * @media_type: the media type of the structure
 276  *
 277  * Creates a new #GstCaps that contains one #GstStructure with name
 278  * @media_type.
 279  * Caller is responsible for unreffing the returned caps.
 280  *
 281  * Returns: (transfer full): the new #GstCaps
 282  */
 283 GstCaps *
 284 gst_caps_new_empty_simple (const char *media_type)
 285 {
 286   GstCaps *caps;
 287   GstStructure *structure;
 288
 289   caps = gst_caps_new_empty ();
 290   structure = gst_structure_new_empty (media_type);
 291   if (structure)
 292     gst_caps_append_structure_unchecked (caps, structure, NULL);
 293
 294   return caps;
 295 }
 296
 297 /**
 298  * gst_caps_new_simple:
 299  * @media_type: the media type of the structure
 300  * @fieldname: first field to set
 301  * @...: additional arguments
 302  *
 303  * Creates a new #GstCaps that contains one #GstStructure.  The
 304  * structure is defined by the arguments, which have the same format
 305  * as gst_structure_new().
 306  * Caller is responsible for unreffing the returned caps.
 307  *
 308  * Returns: (transfer full): the new #GstCaps
 309  */
 310 GstCaps *
 311 gst_caps_new_simple (const char *media_type, const char *fieldname, ...)
 312 {
 313   GstCaps *caps;
 314   GstStructure *structure;
 315   va_list var_args;
 316
 317   caps = gst_caps_new_empty ();
 318
 319   va_start (var_args, fieldname);
 320   structure = gst_structure_new_valist (media_type, fieldname, var_args);
 321   va_end (var_args);
 322
 323   if (structure)
 324     gst_caps_append_structure_unchecked (caps, structure, NULL);
 325   else
 326     gst_caps_replace (&caps, NULL);
 327
 328   return caps;
 329 }
 330
 331 /**
 332  * gst_caps_new_full:
 333  * @struct1: the first structure to add
 334  * @...: additional structures to add
 335  *
 336  * Creates a new #GstCaps and adds all the structures listed as
 337  * arguments.  The list must be NULL-terminated.  The structures
 338  * are not copied; the returned #GstCaps owns the structures.
 339  *
 340  * Returns: (transfer full): the new #GstCaps
 341  */
 342 GstCaps *
 343 gst_caps_new_full (GstStructure * struct1, ...)
 344 {
 345   GstCaps *caps;
 346   va_list var_args;
 347
 348   va_start (var_args, struct1);
 349   caps = gst_caps_new_full_valist (struct1, var_args);
 350   va_end (var_args);
 351
 352   return caps;
 353 }
 354
 355 /**
 356  * gst_caps_new_full_valist:
 357  * @structure: the first structure to add
 358  * @var_args: additional structures to add
 359  *
 360  * Creates a new #GstCaps and adds all the structures listed as
 361  * arguments.  The list must be NULL-terminated.  The structures
 362  * are not copied; the returned #GstCaps owns the structures.
 363  *
 364  * Returns: (transfer full): the new #GstCaps
 365  */
 366 GstCaps *
 367 gst_caps_new_full_valist (GstStructure * structure, va_list var_args)
 368 {
 369   GstCaps *caps;
 370
 371   caps = gst_caps_new_empty ();
 372
 373   while (structure) {
 374     gst_caps_append_structure_unchecked (caps, structure, NULL);
 375     structure = va_arg (var_args, GstStructure *);
 376   }
 377
 378   return caps;
 379 }
 380
 381 G_DEFINE_POINTER_TYPE (GstStaticCaps, gst_static_caps);
 382
 383 /**
 384  * gst_static_caps_get:
 385  * @static_caps: the #GstStaticCaps to convert
 386  *
 387  * Converts a #GstStaticCaps to a #GstCaps.
 388  *
 389  * Returns: (transfer full): a pointer to the #GstCaps. Unref after usage.
 390  *     Since the core holds an additional ref to the returned caps,
 391  *     use gst_caps_make_writable() on the returned caps to modify it.
 392  */
 393 GstCaps *
 394 gst_static_caps_get (GstStaticCaps * static_caps)
 395 {
 396   GstCaps **caps;
 397
 398   g_return_val_if_fail (static_caps != NULL, NULL);
 399
 400   caps = &static_caps->caps;
 401
 402   /* refcount is 0 when we need to convert */
 403   if (G_UNLIKELY (*caps == NULL)) {
 404     const char *string;
 405
 406     G_LOCK (static_caps_lock);
 407     /* check if other thread already updated */
 408     if (G_UNLIKELY (*caps != NULL))
 409       goto done;
 410
 411     string = static_caps->string;
 412
 413     if (G_UNLIKELY (string == NULL))
 414       goto no_string;
 415
 416     *caps = gst_caps_from_string (string);
 417
 418     /* convert to string */
 419     if (G_UNLIKELY (*caps == NULL))
 420       g_critical ("Could not convert static caps \"%s\"", string);
 421
 422     GST_CAT_TRACE (GST_CAT_CAPS, "created %p from string %s", static_caps,
 423         string);
 424   done:
 425     G_UNLOCK (static_caps_lock);
 426   }
 427   /* ref the caps, makes it not writable */
 428   if (G_LIKELY (*caps != NULL))
 429     gst_caps_ref (*caps);
 430
 431   return *caps;
 432
 433   /* ERRORS */
 434 no_string:
 435   {
 436     G_UNLOCK (static_caps_lock);
 437     g_warning ("static caps %p string is NULL", static_caps);
 438     return NULL;
 439   }
 440 }
 441
 442 /**
 443  * gst_static_caps_cleanup:
 444  * @static_caps: the #GstStaticCaps to clean
 445  *
 446  * Clean up the cached caps contained in @static_caps.
 447  */
 448 void
 449 gst_static_caps_cleanup (GstStaticCaps * static_caps)
 450 {
 451   G_LOCK (static_caps_lock);
 452   gst_caps_replace (&static_caps->caps, NULL);
 453   G_UNLOCK (static_caps_lock);
 454 }
 455
 456 /* manipulation */
 457
 458 static void
 459 gst_caps_remove_and_get_structure_and_features (GstCaps * caps, guint idx,
 460     GstStructure ** s, GstCapsFeatures ** f)
 461 {
 462   GstStructure *s_;
 463   GstCapsFeatures *f_;
 464
 465   s_ = gst_caps_get_structure_unchecked (caps, idx);
 466   f_ = gst_caps_get_features_unchecked (caps, idx);
 467
 468   /* don't use index_fast, gst_caps_simplify relies on the order */
 469   g_array_remove_index (GST_CAPS_ARRAY (caps), idx);
 470
 471   gst_structure_set_parent_refcount (s_, NULL);
 472   if (f_) {
 473     gst_caps_features_set_parent_refcount (f_, NULL);
 474   }
 475
 476   *s = s_;
 477   *f = f_;
 478 }
 479
 480 static GstStructure *
 481 gst_caps_remove_and_get_structure (GstCaps * caps, guint idx)
 482 {
 483   GstStructure *s;
 484   GstCapsFeatures *f;
 485
 486   gst_caps_remove_and_get_structure_and_features (caps, idx, &s, &f);
 487
 488   if (f)
 489     gst_caps_features_free (f);
 490
 491   return s;
 492 }
 493
 494
 495
 496 /**
 497  * gst_caps_steal_structure:
 498  * @caps: the #GstCaps to retrieve from
 499  * @index: Index of the structure to retrieve
 500  *
 501  * Retrieves the structure with the given index from the list of structures
 502  * contained in @caps. The caller becomes the owner of the returned structure.
 503  *
 504  * Returns: (transfer full): a pointer to the #GstStructure corresponding
 505  *     to @index.
 506  */
 507 GstStructure *
 508 gst_caps_steal_structure (GstCaps * caps, guint index)
 509 {
 510   g_return_val_if_fail (caps != NULL, NULL);
 511   g_return_val_if_fail (IS_WRITABLE (caps), NULL);
 512
 513   if (G_UNLIKELY (index >= GST_CAPS_LEN (caps)))
 514     return NULL;
 515
 516   return gst_caps_remove_and_get_structure (caps, index);
 517 }
 518
 519 /**
 520  * gst_caps_append:
 521  * @caps1: the #GstCaps that will be appended to
 522  * @caps2: (transfer full): the #GstCaps to append
 523  *
 524  * Appends the structures contained in @caps2 to @caps1. The structures in
 525  * @caps2 are not copied -- they are transferred to @caps1, and then @caps2 is
 526  * freed. If either caps is ANY, the resulting caps will be ANY.
 527  */
 528 void
 529 gst_caps_append (GstCaps * caps1, GstCaps * caps2)
 530 {
 531   GstStructure *structure;
 532   GstCapsFeatures *features;
 533   int i;
 534
 535   g_return_if_fail (GST_IS_CAPS (caps1));
 536   g_return_if_fail (GST_IS_CAPS (caps2));
 537   g_return_if_fail (IS_WRITABLE (caps1));
 538
 539   if (G_UNLIKELY (CAPS_IS_ANY (caps1) || CAPS_IS_ANY (caps2))) {
 540     GST_CAPS_FLAGS (caps1) |= GST_CAPS_FLAG_ANY;
 541     gst_caps_unref (caps2);
 542   } else {
 543     caps2 = gst_caps_make_writable (caps2);
 544
 545     for (i = GST_CAPS_LEN (caps2); i; i--) {
 546       gst_caps_remove_and_get_structure_and_features (caps2, 0, &structure,
 547           &features);
 548       gst_caps_append_structure_unchecked (caps1, structure, features);
 549     }
 550     gst_caps_unref (caps2);     /* guaranteed to free it */
 551   }
 552 }
 553
 554 /**
 555  * gst_caps_merge:
 556  * @caps1: (transfer full): the #GstCaps that will take the new entries
 557  * @caps2: (transfer full): the #GstCaps to merge in
 558  *
 559  * Appends the structures contained in @caps2 to @caps1 if they are not yet
 560  * expressed by @caps1. The structures in @caps2 are not copied -- they are
 561  * transferred to a writable copy of @caps1, and then @caps2 is freed.
 562  * If either caps is ANY, the resulting caps will be ANY.
 563  *
 564  * Returns: (transfer full): the merged caps.
 565  */
 566 GstCaps *
 567 gst_caps_merge (GstCaps * caps1, GstCaps * caps2)
 568 {
 569   GstStructure *structure;
 570   GstCapsFeatures *features;
 571   int i;
 572   GstCaps *result;
 573
 574   g_return_val_if_fail (GST_IS_CAPS (caps1), NULL);
 575   g_return_val_if_fail (GST_IS_CAPS (caps2), NULL);
 576
 577   if (G_UNLIKELY (CAPS_IS_ANY (caps1))) {
 578     gst_caps_unref (caps2);
 579     result = caps1;
 580   } else if (G_UNLIKELY (CAPS_IS_ANY (caps2))) {
 581     gst_caps_unref (caps1);
 582     result = caps2;
 583   } else {
 584     caps2 = gst_caps_make_writable (caps2);
 585
 586     for (i = GST_CAPS_LEN (caps2); i; i--) {
 587       gst_caps_remove_and_get_structure_and_features (caps2, 0, &structure,
 588           &features);
 589       caps1 = gst_caps_merge_structure_full (caps1, structure, features);
 590     }
 591     gst_caps_unref (caps2);
 592     result = caps1;
 593
 594     /* this is too naive
 595        GstCaps *com = gst_caps_intersect (caps1, caps2);
 596        GstCaps *add = gst_caps_subtract (caps2, com);
 597
 598        GST_DEBUG ("common : %d", gst_caps_get_size (com));
 599        GST_DEBUG ("adding : %d", gst_caps_get_size (add));
 600        gst_caps_append (caps1, add);
 601        gst_caps_unref (com);
 602      */
 603   }
 604
 605   return result;
 606 }
 607
 608 /**
 609  * gst_caps_append_structure:
 610  * @caps: the #GstCaps that will be appended to
 611  * @structure: (transfer full): the #GstStructure to append
 612  *
 613  * Appends @structure to @caps.  The structure is not copied; @caps
 614  * becomes the owner of @structure.
 615  */
 616 void
 617 gst_caps_append_structure (GstCaps * caps, GstStructure * structure)
 618 {
 619   g_return_if_fail (GST_IS_CAPS (caps));
 620   g_return_if_fail (IS_WRITABLE (caps));
 621
 622   if (G_LIKELY (structure)) {
 623     gst_caps_append_structure_unchecked (caps, structure, NULL);
 624   }
 625 }
 626
 627 /**
 628  * gst_caps_append_structure_full:
 629  * @caps: the #GstCaps that will be appended to
 630  * @structure: (transfer full): the #GstStructure to append
 631  * @features: (transfer full) (allow-none): the #GstCapsFeatures to append
 632  *
 633  * Appends @structure with @features to @caps.  The structure is not copied; @caps
 634  * becomes the owner of @structure.
 635  *
 636  * Since: 1.2
 637  */
 638 void
 639 gst_caps_append_structure_full (GstCaps * caps, GstStructure * structure,
 640     GstCapsFeatures * features)
 641 {
 642   g_return_if_fail (GST_IS_CAPS (caps));
 643   g_return_if_fail (IS_WRITABLE (caps));
 644
 645   if (G_LIKELY (structure)) {
 646     gst_caps_append_structure_unchecked (caps, structure, features);
 647   }
 648 }
 649
 650 /**
 651  * gst_caps_remove_structure:
 652  * @caps: the #GstCaps to remove from
 653  * @idx: Index of the structure to remove
 654  *
 655  * removes the structure with the given index from the list of structures
 656  * contained in @caps.
 657  */
 658 void
 659 gst_caps_remove_structure (GstCaps * caps, guint idx)
 660 {
 661   GstStructure *structure;
 662
 663   g_return_if_fail (caps != NULL);
 664   g_return_if_fail (idx <= gst_caps_get_size (caps));
 665   g_return_if_fail (IS_WRITABLE (caps));
 666
 667   structure = gst_caps_remove_and_get_structure (caps, idx);
 668   gst_structure_free (structure);
 669 }
 670
 671 /**
 672  * gst_caps_merge_structure:
 673  * @caps: (transfer full): the #GstCaps to merge into
 674  * @structure: (transfer full): the #GstStructure to merge
 675  *
 676  * Appends @structure to @caps if its not already expressed by @caps.
 677  *
 678  * Returns: (transfer full): the merged caps.
 679  */
 680 GstCaps *
 681 gst_caps_merge_structure (GstCaps * caps, GstStructure * structure)
 682 {
 683   GstStructure *structure1;
 684   GstCapsFeatures *features1;
 685   int i;
 686   gboolean unique = TRUE;
 687
 688   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 689
 690   if (G_UNLIKELY (structure == NULL))
 691     return caps;
 692
 693   /* check each structure */
 694   for (i = GST_CAPS_LEN (caps) - 1; i >= 0; i--) {
 695     structure1 = gst_caps_get_structure_unchecked (caps, i);
 696     features1 = gst_caps_get_features_unchecked (caps, i);
 697     if (!features1)
 698       features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
 699
 700     /* if structure is a subset of structure1 and the
 701      * there are no existing features, then skip it */
 702     if (gst_caps_features_is_equal (features1,
 703             GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY)
 704         && gst_structure_is_subset (structure, structure1)) {
 705       unique = FALSE;
 706       break;
 707     }
 708   }
 709   if (unique) {
 710     caps = gst_caps_make_writable (caps);
 711     gst_caps_append_structure_unchecked (caps, structure, NULL);
 712   } else {
 713     gst_structure_free (structure);
 714   }
 715   return caps;
 716 }
 717
 718 /**
 719  * gst_caps_merge_structure_full:
 720  * @caps: (transfer full): the #GstCaps to merge into
 721  * @structure: (transfer full): the #GstStructure to merge
 722  * @features: (transfer full) (allow-none): the #GstCapsFeatures to merge
 723  *
 724  * Appends @structure with @features to @caps if its not already expressed by @caps.
 725  *
 726  * Returns: (transfer full): the merged caps.
 727  *
 728  * Since: 1.2
 729  */
 730 GstCaps *
 731 gst_caps_merge_structure_full (GstCaps * caps, GstStructure * structure,
 732     GstCapsFeatures * features)
 733 {
 734   GstStructure *structure1;
 735   GstCapsFeatures *features1, *features_tmp;
 736   int i;
 737   gboolean unique = TRUE;
 738
 739   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 740
 741   if (G_UNLIKELY (structure == NULL))
 742     return caps;
 743
 744   /* To make comparisons easier below */
 745   features_tmp = features ? features : GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
 746
 747   /* check each structure */
 748   for (i = GST_CAPS_LEN (caps) - 1; i >= 0; i--) {
 749     structure1 = gst_caps_get_structure_unchecked (caps, i);
 750     features1 = gst_caps_get_features_unchecked (caps, i);
 751     if (!features1)
 752       features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
 753     /* if structure is a subset of structure1 and the
 754      * the features are a subset, then skip it */
 755     /* FIXME: We only skip if none of the features are
 756      * ANY and are still equal. That way all ANY structures
 757      * show up in the caps and no non-ANY structures are
 758      * swallowed by ANY structures
 759      */
 760     if (((!gst_caps_features_is_any (features_tmp)
 761                 || gst_caps_features_is_any (features1))
 762             && gst_caps_features_is_equal (features_tmp, features1))
 763         && gst_structure_is_subset (structure, structure1)) {
 764       unique = FALSE;
 765       break;
 766     }
 767   }
 768   if (unique) {
 769     caps = gst_caps_make_writable (caps);
 770     gst_caps_append_structure_unchecked (caps, structure, features);
 771   } else {
 772     gst_structure_free (structure);
 773     if (features)
 774       gst_caps_features_free (features);
 775   }
 776   return caps;
 777 }
 778
 779 /**
 780  * gst_caps_get_size:
 781  * @caps: a #GstCaps
 782  *
 783  * Gets the number of structures contained in @caps.
 784  *
 785  * Returns: the number of structures that @caps contains
 786  */
 787 guint
 788 gst_caps_get_size (const GstCaps * caps)
 789 {
 790   g_return_val_if_fail (GST_IS_CAPS (caps), 0);
 791
 792   return GST_CAPS_LEN (caps);
 793 }
 794
 795 /**
 796  * gst_caps_get_structure:
 797  * @caps: a #GstCaps
 798  * @index: the index of the structure
 799  *
 800  * Finds the structure in @caps that has the index @index, and
 801  * returns it.
 802  *
 803  * WARNING: This function takes a const GstCaps *, but returns a
 804  * non-const GstStructure *.  This is for programming convenience --
 805  * the caller should be aware that structures inside a constant
 806  * #GstCaps should not be modified. However, if you know the caps
 807  * are writable, either because you have just copied them or made
 808  * them writable with gst_caps_make_writable(), you may modify the
 809  * structure returned in the usual way, e.g. with functions like
 810  * gst_structure_set().
 811  *
 812  * You do not need to free or unref the structure returned, it
 813  * belongs to the #GstCaps.
 814  *
 815  * Returns: (transfer none): a pointer to the #GstStructure corresponding
 816  *     to @index
 817  */
 818 GstStructure *
 819 gst_caps_get_structure (const GstCaps * caps, guint index)
 820 {
 821   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 822   g_return_val_if_fail (index < GST_CAPS_LEN (caps), NULL);
 823
 824   return gst_caps_get_structure_unchecked (caps, index);
 825 }
 826
 827 /**
 828  * gst_caps_get_features:
 829  * @caps: a #GstCaps
 830  * @index: the index of the structure
 831  *
 832  * Finds the features in @caps that has the index @index, and
 833  * returns it.
 834  *
 835  * WARNING: This function takes a const GstCaps *, but returns a
 836  * non-const GstCapsFeatures *.  This is for programming convenience --
 837  * the caller should be aware that structures inside a constant
 838  * #GstCaps should not be modified. However, if you know the caps
 839  * are writable, either because you have just copied them or made
 840  * them writable with gst_caps_make_writable(), you may modify the
 841  * features returned in the usual way, e.g. with functions like
 842  * gst_caps_features_add().
 843  *
 844  * You do not need to free or unref the structure returned, it
 845  * belongs to the #GstCaps.
 846  *
 847  * Returns: (transfer none): a pointer to the #GstCapsFeatures corresponding
 848  *     to @index
 849  *
 850  * Since: 1.2
 851  */
 852 GstCapsFeatures *
 853 gst_caps_get_features (const GstCaps * caps, guint index)
 854 {
 855   GstCapsFeatures *features;
 856
 857   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 858   g_return_val_if_fail (index < GST_CAPS_LEN (caps), NULL);
 859
 860   features = gst_caps_get_features_unchecked (caps, index);
 861   if (!features) {
 862     GstCapsFeatures **storage;
 863
 864     /* We have to do some atomic pointer magic here as the caps
 865      * might not be writable and someone else calls this function
 866      * at the very same time */
 867     features = gst_caps_features_copy (GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY);
 868     gst_caps_features_set_parent_refcount (features, &GST_CAPS_REFCOUNT (caps));
 869
 870     storage = gst_caps_get_features_storage_unchecked (caps, index);
 871     if (!g_atomic_pointer_compare_and_exchange (storage, NULL, features)) {
 872       /* Someone did the same we just tried in the meantime */
 873       gst_caps_features_set_parent_refcount (features, NULL);
 874       gst_caps_features_free (features);
 875
 876       features = gst_caps_get_features_unchecked (caps, index);
 877       g_assert (features != NULL);
 878     }
 879   }
 880
 881   return features;
 882 }
 883
 884 /**
 885  * gst_caps_set_features:
 886  * @caps: a #GstCaps
 887  * @index: the index of the structure
 888  * @features: (allow-none) (transfer full): the #GstCapsFeatures to set
 889  *
 890  * Sets the #GstCapsFeatures @features for the structure at @index.
 891  *
 892  * Since: 1.2
 893  */
 894 void
 895 gst_caps_set_features (GstCaps * caps, guint index, GstCapsFeatures * features)
 896 {
 897   GstCapsFeatures **storage, *old;
 898
 899   g_return_if_fail (caps != NULL);
 900   g_return_if_fail (index <= gst_caps_get_size (caps));
 901   g_return_if_fail (IS_WRITABLE (caps));
 902
 903   storage = gst_caps_get_features_storage_unchecked (caps, index);
 904   /* Not much problem here as caps are writable */
 905   old = g_atomic_pointer_get (storage);
 906   g_atomic_pointer_set (storage, features);
 907
 908   if (features)
 909     gst_caps_features_set_parent_refcount (features, &GST_CAPS_REFCOUNT (caps));
 910
 911   if (old)
 912     gst_caps_features_free (old);
 913 }
 914
 915 /**
 916  * gst_caps_copy_nth:
 917  * @caps: the #GstCaps to copy
 918  * @nth: the nth structure to copy
 919  *
 920  * Creates a new #GstCaps and appends a copy of the nth structure
 921  * contained in @caps.
 922  *
 923  * Returns: (transfer full): the new #GstCaps
 924  */
 925 GstCaps *
 926 gst_caps_copy_nth (const GstCaps * caps, guint nth)
 927 {
 928   GstCaps *newcaps;
 929   GstStructure *structure;
 930   GstCapsFeatures *features;
 931
 932   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 933
 934   newcaps = gst_caps_new_empty ();
 935   GST_CAPS_FLAGS (newcaps) = GST_CAPS_FLAGS (caps);
 936
 937   if (G_LIKELY (GST_CAPS_LEN (caps) > nth)) {
 938     structure = gst_caps_get_structure_unchecked (caps, nth);
 939     features = gst_caps_get_features_unchecked (caps, nth);
 940     gst_caps_append_structure_unchecked (newcaps,
 941         gst_structure_copy (structure),
 942         gst_caps_features_copy_conditional (features));
 943   }
 944
 945   return newcaps;
 946 }
 947
 948 /**
 949  * gst_caps_truncate:
 950  * @caps: (transfer full): the #GstCaps to truncate
 951  *
 952  * Discard all but the first structure from @caps. Useful when
 953  * fixating.
 954  *
 955  * Returns: (transfer full): truncated caps
 956  */
 957 GstCaps *
 958 gst_caps_truncate (GstCaps * caps)
 959 {
 960   gint i;
 961
 962   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 963
 964   i = GST_CAPS_LEN (caps) - 1;
 965   if (i == 0)
 966     return caps;
 967
 968   caps = gst_caps_make_writable (caps);
 969   while (i > 0)
 970     gst_caps_remove_structure (caps, i--);
 971
 972   return caps;
 973 }
 974
 975 /**
 976  * gst_caps_set_value:
 977  * @caps: a writable caps
 978  * @field: name of the field to set
 979  * @value: value to set the field to
 980  *
 981  * Sets the given @field on all structures of @caps to the given @value.
 982  * This is a convenience function for calling gst_structure_set_value() on
 983  * all structures of @caps.
 984  **/
 985 void
 986 gst_caps_set_value (GstCaps * caps, const char *field, const GValue * value)
 987 {
 988   guint i, len;
 989
 990   g_return_if_fail (GST_IS_CAPS (caps));
 991   g_return_if_fail (IS_WRITABLE (caps));
 992   g_return_if_fail (field != NULL);
 993   g_return_if_fail (G_IS_VALUE (value));
 994
 995   len = GST_CAPS_LEN (caps);
 996   for (i = 0; i < len; i++) {
 997     GstStructure *structure = gst_caps_get_structure_unchecked (caps, i);
 998     gst_structure_set_value (structure, field, value);
 999   }
1000 }
1001
1002 /**
1003  * gst_caps_set_simple_valist:
1004  * @caps: the #GstCaps to set
1005  * @field: first field to set
1006  * @varargs: additional parameters
1007  *
1008  * Sets fields in a #GstCaps.  The arguments must be passed in the same
1009  * manner as gst_structure_set(), and be NULL-terminated.
1010  */
1011 void
1012 gst_caps_set_simple_valist (GstCaps * caps, const char *field, va_list varargs)
1013 {
1014   GValue value = { 0, };
1015
1016   g_return_if_fail (GST_IS_CAPS (caps));
1017   g_return_if_fail (IS_WRITABLE (caps));
1018
1019   while (field) {
1020     GType type;
1021     char *err;
1022
1023     type = va_arg (varargs, GType);
1024
1025     G_VALUE_COLLECT_INIT (&value, type, varargs, 0, &err);
1026     if (G_UNLIKELY (err)) {
1027       g_critical ("%s", err);
1028       return;
1029     }
1030
1031     gst_caps_set_value (caps, field, &value);
1032
1033     g_value_unset (&value);
1034
1035     field = va_arg (varargs, const gchar *);
1036   }
1037 }
1038
1039 /**
1040  * gst_caps_set_simple:
1041  * @caps: the #GstCaps to set
1042  * @field: first field to set
1043  * @...: additional parameters
1044  *
1045  * Sets fields in a #GstCaps.  The arguments must be passed in the same
1046  * manner as gst_structure_set(), and be NULL-terminated.
1047  */
1048 void
1049 gst_caps_set_simple (GstCaps * caps, const char *field, ...)
1050 {
1051   va_list var_args;
1052
1053   g_return_if_fail (GST_IS_CAPS (caps));
1054   g_return_if_fail (IS_WRITABLE (caps));
1055
1056   va_start (var_args, field);
1057   gst_caps_set_simple_valist (caps, field, var_args);
1058   va_end (var_args);
1059 }
1060
1061 /* tests */
1062
1063 /**
1064  * gst_caps_is_any:
1065  * @caps: the #GstCaps to test
1066  *
1067  * Determines if @caps represents any media format.
1068  *
1069  * Returns: TRUE if @caps represents any format.
1070  */
1071 gboolean
1072 gst_caps_is_any (const GstCaps * caps)
1073 {
1074   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
1075
1076   return (CAPS_IS_ANY (caps));
1077 }
1078
1079 /**
1080  * gst_caps_is_empty:
1081  * @caps: the #GstCaps to test
1082  *
1083  * Determines if @caps represents no media formats.
1084  *
1085  * Returns: TRUE if @caps represents no formats.
1086  */
1087 gboolean
1088 gst_caps_is_empty (const GstCaps * caps)
1089 {
1090   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
1091
1092   if (CAPS_IS_ANY (caps))
1093     return FALSE;
1094
1095   return CAPS_IS_EMPTY_SIMPLE (caps);
1096 }
1097
1098 static gboolean
1099 gst_caps_is_fixed_foreach (GQuark field_id, const GValue * value,
1100     gpointer unused)
1101 {
1102   return gst_value_is_fixed (value);
1103 }
1104
1105 /**
1106  * gst_caps_is_fixed:
1107  * @caps: the #GstCaps to test
1108  *
1109  * Fixed #GstCaps describe exactly one format, that is, they have exactly
1110  * one structure, and each field in the structure describes a fixed type.
1111  * Examples of non-fixed types are GST_TYPE_INT_RANGE and GST_TYPE_LIST.
1112  *
1113  * Returns: TRUE if @caps is fixed
1114  */
1115 gboolean
1116 gst_caps_is_fixed (const GstCaps * caps)
1117 {
1118   GstStructure *structure;
1119   GstCapsFeatures *features;
1120
1121   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
1122
1123   if (GST_CAPS_LEN (caps) != 1)
1124     return FALSE;
1125
1126   features = gst_caps_get_features_unchecked (caps, 0);
1127   if (features && gst_caps_features_is_any (features))
1128     return FALSE;
1129
1130   structure = gst_caps_get_structure_unchecked (caps, 0);
1131
1132   return gst_structure_foreach (structure, gst_caps_is_fixed_foreach, NULL);
1133 }
1134
1135 /**
1136  * gst_caps_is_equal_fixed:
1137  * @caps1: the #GstCaps to test
1138  * @caps2: the #GstCaps to test
1139  *
1140  * Tests if two #GstCaps are equal.  This function only works on fixed
1141  * #GstCaps.
1142  *
1143  * Returns: TRUE if the arguments represent the same format
1144  */
1145 gboolean
1146 gst_caps_is_equal_fixed (const GstCaps * caps1, const GstCaps * caps2)
1147 {
1148   GstStructure *struct1, *struct2;
1149   GstCapsFeatures *features1, *features2;
1150
1151   g_return_val_if_fail (gst_caps_is_fixed (caps1), FALSE);
1152   g_return_val_if_fail (gst_caps_is_fixed (caps2), FALSE);
1153
1154   struct1 = gst_caps_get_structure_unchecked (caps1, 0);
1155   features1 = gst_caps_get_features_unchecked (caps1, 0);
1156   if (!features1)
1157     features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1158   struct2 = gst_caps_get_structure_unchecked (caps2, 0);
1159   features2 = gst_caps_get_features_unchecked (caps2, 0);
1160   if (!features2)
1161     features2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1162
1163   return gst_structure_is_equal (struct1, struct2) &&
1164       gst_caps_features_is_equal (features1, features2);
1165 }
1166
1167 /**
1168  * gst_caps_is_always_compatible:
1169  * @caps1: the #GstCaps to test
1170  * @caps2: the #GstCaps to test
1171  *
1172  * A given #GstCaps structure is always compatible with another if
1173  * every media format that is in the first is also contained in the
1174  * second.  That is, @caps1 is a subset of @caps2.
1175  *
1176  * Returns: TRUE if @caps1 is a subset of @caps2.
1177  */
1178 gboolean
1179 gst_caps_is_always_compatible (const GstCaps * caps1, const GstCaps * caps2)
1180 {
1181   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
1182   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
1183
1184   return gst_caps_is_subset (caps1, caps2);
1185 }
1186
1187 /**
1188  * gst_caps_is_subset:
1189  * @subset: a #GstCaps
1190  * @superset: a potentially greater #GstCaps
1191  *
1192  * Checks if all caps represented by @subset are also represented by @superset.
1193  *
1194  * Returns: %TRUE if @subset is a subset of @superset
1195  */
1196 gboolean
1197 gst_caps_is_subset (const GstCaps * subset, const GstCaps * superset)
1198 {
1199   GstStructure *s1, *s2;
1200   GstCapsFeatures *f1, *f2;
1201   gboolean ret = TRUE;
1202   gint i, j;
1203
1204   g_return_val_if_fail (subset != NULL, FALSE);
1205   g_return_val_if_fail (superset != NULL, FALSE);
1206
1207   if (CAPS_IS_EMPTY (subset) || CAPS_IS_ANY (superset))
1208     return TRUE;
1209   if (CAPS_IS_ANY (subset) || CAPS_IS_EMPTY (superset))
1210     return FALSE;
1211
1212   for (i = GST_CAPS_LEN (subset) - 1; i >= 0; i--) {
1213     for (j = GST_CAPS_LEN (superset) - 1; j >= 0; j--) {
1214       s1 = gst_caps_get_structure_unchecked (subset, i);
1215       f1 = gst_caps_get_features_unchecked (subset, i);
1216       if (!f1)
1217         f1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1218       s2 = gst_caps_get_structure_unchecked (superset, j);
1219       f2 = gst_caps_get_features_unchecked (superset, j);
1220       if (!f2)
1221         f2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1222       if ((!gst_caps_features_is_any (f1) || gst_caps_features_is_any (f2)) &&
1223           gst_caps_features_is_equal (f1, f2)
1224           && gst_structure_is_subset (s1, s2)) {
1225         /* If we found a superset, continue with the next
1226          * subset structure */
1227         break;
1228       }
1229     }
1230     /* If we found no superset for this subset structure
1231      * we return FALSE immediately */
1232     if (j == -1) {
1233       ret = FALSE;
1234       break;
1235     }
1236   }
1237
1238   return ret;
1239 }
1240
1241 /**
1242  * gst_caps_is_subset_structure:
1243  * @caps: a #GstCaps
1244  * @structure: a potential #GstStructure subset of @caps
1245  *
1246  * Checks if @structure is a subset of @caps. See gst_caps_is_subset()
1247  * for more information.
1248  *
1249  * Returns: %TRUE if @structure is a subset of @caps
1250  */
1251 gboolean
1252 gst_caps_is_subset_structure (const GstCaps * caps,
1253     const GstStructure * structure)
1254 {
1255   GstStructure *s;
1256   gint i;
1257
1258   g_return_val_if_fail (caps != NULL, FALSE);
1259   g_return_val_if_fail (structure != NULL, FALSE);
1260
1261   if (CAPS_IS_ANY (caps))
1262     return TRUE;
1263   if (CAPS_IS_EMPTY (caps))
1264     return FALSE;
1265
1266   for (i = GST_CAPS_LEN (caps) - 1; i >= 0; i--) {
1267     s = gst_caps_get_structure_unchecked (caps, i);
1268     if (gst_structure_is_subset (structure, s)) {
1269       /* If we found a superset return TRUE */
1270       return TRUE;
1271     }
1272   }
1273
1274   return FALSE;
1275 }
1276
1277 /**
1278  * gst_caps_is_subset_structure_full:
1279  * @caps: a #GstCaps
1280  * @structure: a potential #GstStructure subset of @caps
1281  * @features: (allow-none): a #GstCapsFeatures for @structure
1282  *
1283  * Checks if @structure is a subset of @caps. See gst_caps_is_subset()
1284  * for more information.
1285  *
1286  * Returns: %TRUE if @structure is a subset of @caps
1287  *
1288  * Since: 1.2
1289  */
1290 gboolean
1291 gst_caps_is_subset_structure_full (const GstCaps * caps,
1292     const GstStructure * structure, const GstCapsFeatures * features)
1293 {
1294   GstStructure *s;
1295   GstCapsFeatures *f;
1296   gint i;
1297
1298   g_return_val_if_fail (caps != NULL, FALSE);
1299   g_return_val_if_fail (structure != NULL, FALSE);
1300
1301   if (CAPS_IS_ANY (caps))
1302     return TRUE;
1303   if (CAPS_IS_EMPTY (caps))
1304     return FALSE;
1305
1306   if (!features)
1307     features = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1308
1309   for (i = GST_CAPS_LEN (caps) - 1; i >= 0; i--) {
1310     s = gst_caps_get_structure_unchecked (caps, i);
1311     f = gst_caps_get_features_unchecked (caps, i);
1312     if (!f)
1313       f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1314     if ((!gst_caps_features_is_any (features) || gst_caps_features_is_any (f))
1315         && gst_caps_features_is_equal (features, f)
1316         && gst_structure_is_subset (structure, s)) {
1317       /* If we found a superset return TRUE */
1318       return TRUE;
1319     }
1320   }
1321
1322   return FALSE;
1323 }
1324
1325 /**
1326  * gst_caps_is_equal:
1327  * @caps1: a #GstCaps
1328  * @caps2: another #GstCaps
1329  *
1330  * Checks if the given caps represent the same set of caps.
1331  *
1332  * Returns: TRUE if both caps are equal.
1333  */
1334 gboolean
1335 gst_caps_is_equal (const GstCaps * caps1, const GstCaps * caps2)
1336 {
1337   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
1338   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
1339
1340   if (G_UNLIKELY (caps1 == caps2))
1341     return TRUE;
1342
1343   if (G_UNLIKELY (gst_caps_is_fixed (caps1) && gst_caps_is_fixed (caps2)))
1344     return gst_caps_is_equal_fixed (caps1, caps2);
1345
1346   return gst_caps_is_subset (caps1, caps2) && gst_caps_is_subset (caps2, caps1);
1347 }
1348
1349 /**
1350  * gst_caps_is_strictly_equal:
1351  * @caps1: a #GstCaps
1352  * @caps2: another #GstCaps
1353  *
1354  * Checks if the given caps are exactly the same set of caps.
1355  *
1356  * Returns: TRUE if both caps are strictly equal.
1357  */
1358 gboolean
1359 gst_caps_is_strictly_equal (const GstCaps * caps1, const GstCaps * caps2)
1360 {
1361   int i;
1362   GstStructure *s1, *s2;
1363   GstCapsFeatures *f1, *f2;
1364
1365   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
1366   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
1367
1368   if (G_UNLIKELY (caps1 == caps2))
1369     return TRUE;
1370
1371   if (GST_CAPS_LEN (caps1) != GST_CAPS_LEN (caps2))
1372     return FALSE;
1373
1374   for (i = 0; i < GST_CAPS_LEN (caps1); i++) {
1375     s1 = gst_caps_get_structure_unchecked (caps1, i);
1376     f1 = gst_caps_get_features_unchecked (caps1, i);
1377     if (!f1)
1378       f1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1379     s2 = gst_caps_get_structure_unchecked (caps2, i);
1380     f2 = gst_caps_get_features_unchecked (caps2, i);
1381     if (!f2)
1382       f2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1383
1384     if (gst_caps_features_is_any (f1) != gst_caps_features_is_any (f2) ||
1385         !gst_caps_features_is_equal (f1, f2) ||
1386         !gst_structure_is_equal (s1, s2))
1387       return FALSE;
1388   }
1389
1390   return TRUE;
1391 }
1392
1393 /* intersect operation */
1394
1395 /**
1396  * gst_caps_can_intersect:
1397  * @caps1: a #GstCaps to intersect
1398  * @caps2: a #GstCaps to intersect
1399  *
1400  * Tries intersecting @caps1 and @caps2 and reports whether the result would not
1401  * be empty
1402  *
1403  * Returns: %TRUE if intersection would be not empty
1404  */
1405 gboolean
1406 gst_caps_can_intersect (const GstCaps * caps1, const GstCaps * caps2)
1407 {
1408   guint64 i;                    /* index can be up to 2 * G_MAX_UINT */
1409   guint j, k, len1, len2;
1410   GstStructure *struct1;
1411   GstStructure *struct2;
1412   GstCapsFeatures *features1;
1413   GstCapsFeatures *features2;
1414
1415   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
1416   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
1417
1418   /* caps are exactly the same pointers */
1419   if (G_UNLIKELY (caps1 == caps2))
1420     return TRUE;
1421
1422   /* empty caps on either side, return empty */
1423   if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
1424     return FALSE;
1425
1426   /* one of the caps is any */
1427   if (G_UNLIKELY (CAPS_IS_ANY (caps1) || CAPS_IS_ANY (caps2)))
1428     return TRUE;
1429
1430   /* run zigzag on top line then right line, this preserves the caps order
1431    * much better than a simple loop.
1432    *
1433    * This algorithm zigzags over the caps structures as demonstrated in
1434    * the following matrix:
1435    *
1436    *          caps1                              0  1  2  3
1437    *       +-------------     total distance:  +-------------
1438    *       | 1  2  4  7                      0 | 0  1  2  3
1439    * caps2 | 3  5  8 10                      1 | 1  2  3  4
1440    *       | 6  9 11 12                      2 | 2  3  4  5
1441    *
1442    * First we iterate over the caps1 structures (top line) intersecting
1443    * the structures diagonally down, then we iterate over the caps2
1444    * structures. The result is that the intersections are ordered based on the
1445    * sum of the indexes in the list.
1446    */
1447   len1 = GST_CAPS_LEN (caps1);
1448   len2 = GST_CAPS_LEN (caps2);
1449   for (i = 0; i < len1 + len2 - 1; i++) {
1450     /* superset index goes from 0 to sgst_caps_structure_intersectuperset->structs->len-1 */
1451     j = MIN (i, len1 - 1);
1452     /* subset index stays 0 until i reaches superset->structs->len, then it
1453      * counts up from 1 to subset->structs->len - 1 */
1454     k = (i > j) ? (i - j) : 0;  /* MAX (0, i - j) */
1455     /* now run the diagonal line, end condition is the left or bottom
1456      * border */
1457     while (k < len2) {
1458       struct1 = gst_caps_get_structure_unchecked (caps1, j);
1459       features1 = gst_caps_get_features_unchecked (caps1, j);
1460       if (!features1)
1461         features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1462       struct2 = gst_caps_get_structure_unchecked (caps2, k);
1463       features2 = gst_caps_get_features_unchecked (caps2, k);
1464       if (!features2)
1465         features2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1466       if (gst_caps_features_is_equal (features1, features2) &&
1467           gst_structure_can_intersect (struct1, struct2)) {
1468         return TRUE;
1469       }
1470       /* move down left */
1471       k++;
1472       if (G_UNLIKELY (j == 0))
1473         break;                  /* so we don't roll back to G_MAXUINT */
1474       j--;
1475     }
1476   }
1477
1478   return FALSE;
1479 }
1480
1481 static GstCaps *
1482 gst_caps_intersect_zig_zag (GstCaps * caps1, GstCaps * caps2)
1483 {
1484   guint64 i;                    /* index can be up to 2 * G_MAX_UINT */
1485   guint j, k, len1, len2;
1486   GstStructure *struct1;
1487   GstStructure *struct2;
1488   GstCapsFeatures *features1;
1489   GstCapsFeatures *features2;
1490   GstCaps *dest;
1491   GstStructure *istruct;
1492
1493   /* caps are exactly the same pointers, just copy one caps */
1494   if (G_UNLIKELY (caps1 == caps2))
1495     return gst_caps_ref (caps1);
1496
1497   /* empty caps on either side, return empty */
1498   if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
1499     return gst_caps_ref (GST_CAPS_NONE);
1500
1501   /* one of the caps is any, just copy the other caps */
1502   if (G_UNLIKELY (CAPS_IS_ANY (caps1)))
1503     return gst_caps_ref (caps2);
1504
1505   if (G_UNLIKELY (CAPS_IS_ANY (caps2)))
1506     return gst_caps_ref (caps1);
1507
1508   dest = gst_caps_new_empty ();
1509   /* run zigzag on top line then right line, this preserves the caps order
1510    * much better than a simple loop.
1511    *
1512    * This algorithm zigzags over the caps structures as demonstrated in
1513    * the following matrix:
1514    *
1515    *          caps1
1516    *       +-------------
1517    *       | 1  2  4  7
1518    * caps2 | 3  5  8 10
1519    *       | 6  9 11 12
1520    *
1521    * First we iterate over the caps1 structures (top line) intersecting
1522    * the structures diagonally down, then we iterate over the caps2
1523    * structures.
1524    */
1525   len1 = GST_CAPS_LEN (caps1);
1526   len2 = GST_CAPS_LEN (caps2);
1527   for (i = 0; i < len1 + len2 - 1; i++) {
1528     /* caps1 index goes from 0 to GST_CAPS_LEN (caps1)-1 */
1529     j = MIN (i, len1 - 1);
1530     /* caps2 index stays 0 until i reaches GST_CAPS_LEN (caps1), then it counts
1531      * up from 1 to GST_CAPS_LEN (caps2) - 1 */
1532     k = (i > j) ? (i - j) : 0;  /* MAX (0, i - j) */
1533     /* now run the diagonal line, end condition is the left or bottom
1534      * border */
1535     while (k < len2) {
1536       struct1 = gst_caps_get_structure_unchecked (caps1, j);
1537       features1 = gst_caps_get_features_unchecked (caps1, j);
1538       if (!features1)
1539         features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1540       struct2 = gst_caps_get_structure_unchecked (caps2, k);
1541       features2 = gst_caps_get_features_unchecked (caps2, k);
1542       if (!features2)
1543         features2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1544       if (gst_caps_features_is_equal (features1, features2)) {
1545         istruct = gst_structure_intersect (struct1, struct2);
1546         if (istruct) {
1547           if (gst_caps_features_is_any (features1))
1548             dest =
1549                 gst_caps_merge_structure_full (dest, istruct,
1550                 gst_caps_features_copy_conditional (features2));
1551           else
1552             dest =
1553                 gst_caps_merge_structure_full (dest, istruct,
1554                 gst_caps_features_copy_conditional (features1));
1555         }
1556       }
1557       /* move down left */
1558       k++;
1559       if (G_UNLIKELY (j == 0))
1560         break;                  /* so we don't roll back to G_MAXUINT */
1561       j--;
1562     }
1563   }
1564   return dest;
1565 }
1566
1567 /**
1568  * gst_caps_intersect_first:
1569  * @caps1: a #GstCaps to intersect
1570  * @caps2: a #GstCaps to intersect
1571  *
1572  * Creates a new #GstCaps that contains all the formats that are common
1573  * to both @caps1 and @caps2.
1574  *
1575  * Unlike @gst_caps_intersect, the returned caps will be ordered in a similar
1576  * fashion as @caps1.
1577  *
1578  * Returns: the new #GstCaps
1579  */
1580 static GstCaps *
1581 gst_caps_intersect_first (GstCaps * caps1, GstCaps * caps2)
1582 {
1583   guint i;
1584   guint j, len1, len2;
1585   GstStructure *struct1;
1586   GstStructure *struct2;
1587   GstCapsFeatures *features1;
1588   GstCapsFeatures *features2;
1589   GstCaps *dest;
1590   GstStructure *istruct;
1591
1592   /* caps are exactly the same pointers, just copy one caps */
1593   if (G_UNLIKELY (caps1 == caps2))
1594     return gst_caps_ref (caps1);
1595
1596   /* empty caps on either side, return empty */
1597   if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
1598     return gst_caps_ref (GST_CAPS_NONE);
1599
1600   /* one of the caps is any, just copy the other caps */
1601   if (G_UNLIKELY (CAPS_IS_ANY (caps1)))
1602     return gst_caps_ref (caps2);
1603
1604   if (G_UNLIKELY (CAPS_IS_ANY (caps2)))
1605     return gst_caps_ref (caps1);
1606
1607   dest = gst_caps_new_empty ();
1608   len1 = GST_CAPS_LEN (caps1);
1609   len2 = GST_CAPS_LEN (caps2);
1610   for (i = 0; i < len1; i++) {
1611     struct1 = gst_caps_get_structure_unchecked (caps1, i);
1612     features1 = gst_caps_get_features_unchecked (caps1, i);
1613     if (!features1)
1614       features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1615     for (j = 0; j < len2; j++) {
1616       struct2 = gst_caps_get_structure_unchecked (caps2, j);
1617       features2 = gst_caps_get_features_unchecked (caps2, j);
1618       if (!features2)
1619         features2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1620       if (gst_caps_features_is_equal (features1, features2)) {
1621         istruct = gst_structure_intersect (struct1, struct2);
1622         if (istruct) {
1623           if (gst_caps_features_is_any (features1))
1624             dest =
1625                 gst_caps_merge_structure_full (dest, istruct,
1626                 gst_caps_features_copy_conditional (features2));
1627           else
1628             dest =
1629                 gst_caps_merge_structure_full (dest, istruct,
1630                 gst_caps_features_copy_conditional (features1));
1631         }
1632       }
1633     }
1634   }
1635
1636   return dest;
1637 }
1638
1639 /**
1640  * gst_caps_intersect_full:
1641  * @caps1: a #GstCaps to intersect
1642  * @caps2: a #GstCaps to intersect
1643  * @mode: The intersection algorithm/mode to use
1644  *
1645  * Creates a new #GstCaps that contains all the formats that are common
1646  * to both @caps1 and @caps2, the order is defined by the #GstCapsIntersectMode
1647  * used.
1648  *
1649  * Returns: the new #GstCaps
1650  */
1651 GstCaps *
1652 gst_caps_intersect_full (GstCaps * caps1, GstCaps * caps2,
1653     GstCapsIntersectMode mode)
1654 {
1655   g_return_val_if_fail (GST_IS_CAPS (caps1), NULL);
1656   g_return_val_if_fail (GST_IS_CAPS (caps2), NULL);
1657
1658   switch (mode) {
1659     case GST_CAPS_INTERSECT_FIRST:
1660       return gst_caps_intersect_first (caps1, caps2);
1661     default:
1662       g_warning ("Unknown caps intersect mode: %d", mode);
1663       /* fallthrough */
1664     case GST_CAPS_INTERSECT_ZIG_ZAG:
1665       return gst_caps_intersect_zig_zag (caps1, caps2);
1666   }
1667 }
1668
1669 /**
1670  * gst_caps_intersect:
1671  * @caps1: a #GstCaps to intersect
1672  * @caps2: a #GstCaps to intersect
1673  *
1674  * Creates a new #GstCaps that contains all the formats that are common
1675  * to both @caps1 and @caps2. Defaults to %GST_CAPS_INTERSECT_ZIG_ZAG mode.
1676  *
1677  * Returns: the new #GstCaps
1678  */
1679 GstCaps *
1680 gst_caps_intersect (GstCaps * caps1, GstCaps * caps2)
1681 {
1682   return gst_caps_intersect_full (caps1, caps2, GST_CAPS_INTERSECT_ZIG_ZAG);
1683 }
1684
1685 /* subtract operation */
1686
1687 typedef struct
1688 {
1689   const GstStructure *subtract_from;
1690   GSList *put_into;
1691 } SubtractionEntry;
1692
1693 static gboolean
1694 gst_caps_structure_subtract_field (GQuark field_id, const GValue * value,
1695     gpointer user_data)
1696 {
1697   SubtractionEntry *e = user_data;
1698   GValue subtraction = { 0, };
1699   const GValue *other;
1700   GstStructure *structure;
1701
1702   other = gst_structure_id_get_value (e->subtract_from, field_id);
1703
1704   if (!other) {
1705     return FALSE;
1706   }
1707
1708   if (!gst_value_subtract (&subtraction, other, value))
1709     return TRUE;
1710
1711   if (gst_value_compare (&subtraction, other) == GST_VALUE_EQUAL) {
1712     g_value_unset (&subtraction);
1713     return FALSE;
1714   } else {
1715     structure = gst_structure_copy (e->subtract_from);
1716     gst_structure_id_take_value (structure, field_id, &subtraction);
1717     e->put_into = g_slist_prepend (e->put_into, structure);
1718     return TRUE;
1719   }
1720 }
1721
1722 static gboolean
1723 gst_caps_structure_subtract (GSList ** into, const GstStructure * minuend,
1724     const GstStructure * subtrahend)
1725 {
1726   SubtractionEntry e;
1727   gboolean ret;
1728
1729   e.subtract_from = minuend;
1730   e.put_into = NULL;
1731   ret = gst_structure_foreach ((GstStructure *) subtrahend,
1732       gst_caps_structure_subtract_field, &e);
1733
1734   if (ret) {
1735     *into = e.put_into;
1736   } else {
1737     GSList *walk;
1738
1739     for (walk = e.put_into; walk; walk = g_slist_next (walk)) {
1740       gst_structure_free (walk->data);
1741     }
1742     g_slist_free (e.put_into);
1743   }
1744
1745   return ret;
1746 }
1747
1748 /**
1749  * gst_caps_subtract:
1750  * @minuend: #GstCaps to subtract from
1751  * @subtrahend: #GstCaps to subtract
1752  *
1753  * Subtracts the @subtrahend from the @minuend.
1754  * <note>This function does not work reliably if optional properties for caps
1755  * are included on one caps and omitted on the other.</note>
1756  *
1757  * Returns: the resulting caps
1758  */
1759 GstCaps *
1760 gst_caps_subtract (GstCaps * minuend, GstCaps * subtrahend)
1761 {
1762   guint i, j, sublen;
1763   GstStructure *min;
1764   GstStructure *sub;
1765   GstCapsFeatures *min_f, *sub_f;
1766   GstCaps *dest = NULL, *src;
1767
1768   g_return_val_if_fail (minuend != NULL, NULL);
1769   g_return_val_if_fail (subtrahend != NULL, NULL);
1770
1771   if (CAPS_IS_EMPTY (minuend) || CAPS_IS_ANY (subtrahend)) {
1772     return gst_caps_new_empty ();
1773   }
1774
1775   if (CAPS_IS_EMPTY_SIMPLE (subtrahend))
1776     return gst_caps_ref (minuend);
1777
1778   /* FIXME: Do we want this here or above?
1779      The reason we need this is that there is no definition about what
1780      ANY means for specific types, so it's not possible to reduce ANY partially
1781      You can only remove everything or nothing and that is done above.
1782      Note: there's a test that checks this behaviour. */
1783
1784   g_return_val_if_fail (!CAPS_IS_ANY (minuend), NULL);
1785   sublen = GST_CAPS_LEN (subtrahend);
1786   g_assert (sublen > 0);
1787
1788   src = _gst_caps_copy (minuend);
1789   for (i = 0; i < sublen; i++) {
1790     guint srclen;
1791
1792     sub = gst_caps_get_structure_unchecked (subtrahend, i);
1793     sub_f = gst_caps_get_features_unchecked (subtrahend, i);
1794     if (!sub_f)
1795       sub_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1796     if (dest) {
1797       gst_caps_unref (src);
1798       src = dest;
1799     }
1800     dest = gst_caps_new_empty ();
1801     srclen = GST_CAPS_LEN (src);
1802     for (j = 0; j < srclen; j++) {
1803       min = gst_caps_get_structure_unchecked (src, j);
1804       min_f = gst_caps_get_features_unchecked (src, j);
1805       if (!min_f)
1806         min_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1807
1808       /* Same reason as above for ANY caps */
1809       g_return_val_if_fail (!gst_caps_features_is_any (min_f), NULL);
1810
1811       if (gst_structure_get_name_id (min) == gst_structure_get_name_id (sub) &&
1812           gst_caps_features_is_equal (min_f, sub_f)) {
1813         GSList *list;
1814
1815         if (gst_caps_structure_subtract (&list, min, sub)) {
1816           GSList *walk;
1817
1818           for (walk = list; walk; walk = g_slist_next (walk)) {
1819             gst_caps_append_structure_unchecked (dest,
1820                 (GstStructure *) walk->data,
1821                 gst_caps_features_copy_conditional (min_f));
1822           }
1823           g_slist_free (list);
1824         } else {
1825           gst_caps_append_structure_unchecked (dest, gst_structure_copy (min),
1826               gst_caps_features_copy_conditional (min_f));
1827         }
1828       } else {
1829         gst_caps_append_structure_unchecked (dest, gst_structure_copy (min),
1830             gst_caps_features_copy_conditional (min_f));
1831       }
1832     }
1833
1834     if (CAPS_IS_EMPTY_SIMPLE (dest)) {
1835       gst_caps_unref (src);
1836       return dest;
1837     }
1838   }
1839
1840   gst_caps_unref (src);
1841   dest = gst_caps_simplify (dest);
1842
1843   return dest;
1844 }
1845
1846 /* normalize/simplify operations */
1847
1848 typedef struct _NormalizeForeach
1849 {
1850   GstCaps *caps;
1851   GstStructure *structure;
1852   GstCapsFeatures *features;
1853 } NormalizeForeach;
1854
1855 static gboolean
1856 gst_caps_normalize_foreach (GQuark field_id, const GValue * value, gpointer ptr)
1857 {
1858   NormalizeForeach *nf = (NormalizeForeach *) ptr;
1859   GValue val = { 0 };
1860   guint i;
1861
1862   if (G_VALUE_TYPE (value) == GST_TYPE_LIST) {
1863     guint len = gst_value_list_get_size (value);
1864
1865     for (i = 1; i < len; i++) {
1866       const GValue *v = gst_value_list_get_value (value, i);
1867       GstStructure *structure = gst_structure_copy (nf->structure);
1868
1869       gst_structure_id_set_value (structure, field_id, v);
1870       gst_caps_append_structure_unchecked (nf->caps, structure,
1871           gst_caps_features_copy_conditional (nf->features));
1872     }
1873
1874     gst_value_init_and_copy (&val, gst_value_list_get_value (value, 0));
1875     gst_structure_id_take_value (nf->structure, field_id, &val);
1876     return FALSE;
1877   }
1878
1879   return TRUE;
1880 }
1881
1882 /**
1883  * gst_caps_normalize:
1884  * @caps: (transfer full): a #GstCaps to normalize
1885  *
1886  * Returns a #GstCaps that represents the same set of formats as
1887  * @caps, but contains no lists.  Each list is expanded into separate
1888  * @GstStructures.
1889  *
1890  * This function takes ownership of @caps.
1891  *
1892  * Returns: (transfer full): the normalized #GstCaps
1893  */
1894 GstCaps *
1895 gst_caps_normalize (GstCaps * caps)
1896 {
1897   NormalizeForeach nf;
1898   guint i;
1899
1900   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
1901
1902   caps = gst_caps_make_writable (caps);
1903   nf.caps = caps;
1904
1905   for (i = 0; i < gst_caps_get_size (nf.caps); i++) {
1906     nf.structure = gst_caps_get_structure_unchecked (nf.caps, i);
1907     nf.features = gst_caps_get_features_unchecked (nf.caps, i);
1908     while (!gst_structure_foreach (nf.structure,
1909             gst_caps_normalize_foreach, &nf));
1910   }
1911
1912   return nf.caps;
1913 }
1914
1915 static gint
1916 gst_caps_compare_structures (gconstpointer one, gconstpointer two)
1917 {
1918   gint ret;
1919   const GstStructure *struct1 = ((const GstCapsArrayElement *) one)->structure;
1920   const GstStructure *struct2 = ((const GstCapsArrayElement *) two)->structure;
1921
1922   /* FIXME: this orders alphabetically, but ordering the quarks might be faster
1923      So what's the best way? */
1924   ret = strcmp (gst_structure_get_name (struct1),
1925       gst_structure_get_name (struct2));
1926
1927   if (ret)
1928     return ret;
1929
1930   return gst_structure_n_fields (struct2) - gst_structure_n_fields (struct1);
1931 }
1932
1933 typedef struct
1934 {
1935   GQuark name;
1936   GValue value;
1937   GstStructure *compare;
1938 } UnionField;
1939
1940 static gboolean
1941 gst_caps_structure_figure_out_union (GQuark field_id, const GValue * value,
1942     gpointer user_data)
1943 {
1944   UnionField *u = user_data;
1945   const GValue *val = gst_structure_id_get_value (u->compare, field_id);
1946
1947   if (!val) {
1948     if (u->name)
1949       g_value_unset (&u->value);
1950     return FALSE;
1951   }
1952
1953   if (gst_value_compare (val, value) == GST_VALUE_EQUAL)
1954     return TRUE;
1955
1956   if (u->name) {
1957     g_value_unset (&u->value);
1958     return FALSE;
1959   }
1960
1961   u->name = field_id;
1962   gst_value_union (&u->value, val, value);
1963
1964   return TRUE;
1965 }
1966
1967 static gboolean
1968 gst_caps_structure_simplify (GstStructure ** result,
1969     GstStructure * simplify, GstStructure * compare)
1970 {
1971   GSList *list;
1972   UnionField field = { 0, {0,}, NULL };
1973
1974   /* try to subtract to get a real subset */
1975   if (gst_caps_structure_subtract (&list, simplify, compare)) {
1976     if (list == NULL) {         /* no result */
1977       *result = NULL;
1978       return TRUE;
1979     } else if (list->next == NULL) {    /* one result */
1980       *result = list->data;
1981       g_slist_free (list);
1982       return TRUE;
1983     } else {                    /* multiple results */
1984       g_slist_foreach (list, (GFunc) gst_structure_free, NULL);
1985       g_slist_free (list);
1986       list = NULL;
1987     }
1988   }
1989
1990   /* try to union both structs */
1991   field.compare = compare;
1992   if (gst_structure_foreach (simplify,
1993           gst_caps_structure_figure_out_union, &field)) {
1994     gboolean ret = FALSE;
1995
1996     /* now we know all of simplify's fields are the same in compare
1997      * but at most one field: field.name */
1998     if (G_IS_VALUE (&field.value)) {
1999       if (gst_structure_n_fields (simplify) == gst_structure_n_fields (compare)) {
2000         gst_structure_id_take_value (compare, field.name, &field.value);
2001         *result = NULL;
2002         ret = TRUE;
2003       } else {
2004         g_value_unset (&field.value);
2005       }
2006     } else
2007         if (gst_structure_n_fields (simplify) <=
2008         gst_structure_n_fields (compare)) {
2009       /* compare is just more specific, will be optimized away later */
2010       /* FIXME: do this here? */
2011       GST_LOG ("found a case that will be optimized later.");
2012     } else {
2013       gchar *one = gst_structure_to_string (simplify);
2014       gchar *two = gst_structure_to_string (compare);
2015
2016       GST_ERROR
2017           ("caps mismatch: structures %s and %s claim to be possible to unify, but aren't",
2018           one, two);
2019       g_free (one);
2020       g_free (two);
2021     }
2022     return ret;
2023   }
2024
2025   return FALSE;
2026 }
2027
2028 static void
2029 gst_caps_switch_structures (GstCaps * caps, GstStructure * old,
2030     GstStructure * new, gint i)
2031 {
2032   gst_structure_set_parent_refcount (old, NULL);
2033   gst_structure_free (old);
2034   gst_structure_set_parent_refcount (new, &GST_CAPS_REFCOUNT (caps));
2035   g_array_index (GST_CAPS_ARRAY (caps), GstCapsArrayElement, i).structure = new;
2036 }
2037
2038 /**
2039  * gst_caps_simplify:
2040  * @caps: (transfer full): a #GstCaps to simplify
2041  *
2042  * Converts the given @caps into a representation that represents the
2043  * same set of formats, but in a simpler form.  Component structures that are
2044  * identical are merged.  Component structures that have values that can be
2045  * merged are also merged.
2046  *
2047  * This method does not preserve the original order of @caps.
2048  *
2049  * Returns: The simplified caps.
2050  */
2051 GstCaps *
2052 gst_caps_simplify (GstCaps * caps)
2053 {
2054   GstStructure *simplify, *compare, *result = NULL;
2055   GstCapsFeatures *simplify_f, *compare_f;
2056   gint i, j, start;
2057
2058   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
2059
2060   start = GST_CAPS_LEN (caps) - 1;
2061   /* one caps, already as simple as can be */
2062   if (start == 0)
2063     return caps;
2064
2065   caps = gst_caps_make_writable (caps);
2066
2067   g_array_sort (GST_CAPS_ARRAY (caps), gst_caps_compare_structures);
2068
2069   for (i = start; i >= 0; i--) {
2070     simplify = gst_caps_get_structure_unchecked (caps, i);
2071     simplify_f = gst_caps_get_features_unchecked (caps, i);
2072     if (!simplify_f)
2073       simplify_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
2074     compare = gst_caps_get_structure_unchecked (caps, start);
2075     compare_f = gst_caps_get_features_unchecked (caps, start);
2076     if (!compare_f)
2077       compare_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
2078     if (gst_structure_get_name_id (simplify) !=
2079         gst_structure_get_name_id (compare) ||
2080         !gst_caps_features_is_equal (simplify_f, compare_f))
2081       start = i;
2082     for (j = start; j >= 0; j--) {
2083       if (j == i)
2084         continue;
2085       compare = gst_caps_get_structure_unchecked (caps, j);
2086       compare_f = gst_caps_get_features_unchecked (caps, j);
2087       if (!compare_f)
2088         compare_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
2089       if (gst_structure_get_name_id (simplify) !=
2090           gst_structure_get_name_id (compare) ||
2091           !gst_caps_features_is_equal (simplify_f, compare_f)) {
2092         break;
2093       }
2094       if (gst_caps_structure_simplify (&result, simplify, compare)) {
2095         if (result) {
2096           gst_caps_switch_structures (caps, simplify, result, i);
2097           simplify = result;
2098         } else {
2099           gst_caps_remove_structure (caps, i);
2100           start--;
2101           break;
2102         }
2103       }
2104     }
2105   }
2106   return caps;
2107 }
2108
2109 /**
2110  * gst_caps_fixate:
2111  * @caps: (transfer full): a #GstCaps to fixate
2112  *
2113  * Modifies the given @caps into a representation with only fixed
2114  * values. First the caps will be truncated and then the first structure will be
2115  * fixated with gst_structure_fixate().
2116  *
2117  * Returns: (transfer full): the fixated caps
2118  */
2119 GstCaps *
2120 gst_caps_fixate (GstCaps * caps)
2121 {
2122   GstStructure *s;
2123   GstCapsFeatures *f;
2124
2125   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
2126
2127   /* default fixation */
2128   caps = gst_caps_truncate (caps);
2129   caps = gst_caps_make_writable (caps);
2130   s = gst_caps_get_structure (caps, 0);
2131   gst_structure_fixate (s);
2132
2133   /* Set features to sysmem if they're still ANY */
2134   f = gst_caps_get_features_unchecked (caps, 0);
2135   if (f && gst_caps_features_is_any (f)) {
2136     f = gst_caps_features_new_empty ();
2137     gst_caps_set_features (caps, 0, f);
2138   }
2139
2140   return caps;
2141 }
2142
2143 /* utility */
2144
2145 /**
2146  * gst_caps_to_string:
2147  * @caps: a #GstCaps
2148  *
2149  * Converts @caps to a string representation.  This string representation
2150  * can be converted back to a #GstCaps by gst_caps_from_string().
2151  *
2152  * For debugging purposes its easier to do something like this:
2153  * |[
2154  * GST_LOG ("caps are %" GST_PTR_FORMAT, caps);
2155  * ]|
2156  * This prints the caps in human readable form.
2157  *
2158  * The current implementation of serialization will lead to unexpected results
2159  * when there are nested #GstCaps / #GstStructure deeper than one level.
2160  *
2161  * Returns: (transfer full): a newly allocated string representing @caps.
2162  */
2163 gchar *
2164 gst_caps_to_string (const GstCaps * caps)
2165 {
2166   guint i, slen, clen;
2167   GString *s;
2168
2169   /* NOTE:  This function is potentially called by the debug system,
2170    * so any calls to gst_log() (and GST_DEBUG(), GST_LOG(), etc.)
2171    * should be careful to avoid recursion.  This includes any functions
2172    * called by gst_caps_to_string.  In particular, calls should
2173    * not use the GST_PTR_FORMAT extension.  */
2174
2175   if (caps == NULL) {
2176     return g_strdup ("NULL");
2177   }
2178   if (CAPS_IS_ANY (caps)) {
2179     return g_strdup ("ANY");
2180   }
2181   if (CAPS_IS_EMPTY_SIMPLE (caps)) {
2182     return g_strdup ("EMPTY");
2183   }
2184
2185   /* estimate a rough string length to avoid unnecessary reallocs in GString */
2186   slen = 0;
2187   clen = GST_CAPS_LEN (caps);
2188   for (i = 0; i < clen; i++) {
2189     GstCapsFeatures *f;
2190
2191     slen +=
2192         STRUCTURE_ESTIMATED_STRING_LEN (gst_caps_get_structure_unchecked
2193         (caps, i));
2194     f = gst_caps_get_features_unchecked (caps, i);
2195     if (f)
2196       slen += FEATURES_ESTIMATED_STRING_LEN (f);
2197   }
2198
2199   s = g_string_sized_new (slen);
2200   for (i = 0; i < clen; i++) {
2201     GstStructure *structure;
2202     GstCapsFeatures *features;
2203
2204     if (i > 0) {
2205       /* ';' is now added by gst_structure_to_string */
2206       g_string_append_c (s, ' ');
2207     }
2208
2209     structure = gst_caps_get_structure_unchecked (caps, i);
2210     features = gst_caps_get_features_unchecked (caps, i);
2211
2212     g_string_append (s, gst_structure_get_name (structure));
2213     if (features && (gst_caps_features_is_any (features)
2214             || !gst_caps_features_is_equal (features,
2215                 GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY))) {
2216       g_string_append_c (s, '(');
2217       priv_gst_caps_features_append_to_gstring (features, s);
2218       g_string_append_c (s, ')');
2219     }
2220     priv_gst_structure_append_to_gstring (structure, s);
2221   }
2222   if (s->len && s->str[s->len - 1] == ';') {
2223     /* remove latest ';' */
2224     s->str[--s->len] = '\0';
2225   }
2226   return g_string_free (s, FALSE);
2227 }
2228
2229 static gboolean
2230 gst_caps_from_string_inplace (GstCaps * caps, const gchar * string)
2231 {
2232   GstStructure *structure;
2233   gchar *s, *copy, *end, *next, save;
2234
2235   if (strcmp ("ANY", string) == 0) {
2236     GST_CAPS_FLAGS (caps) = GST_CAPS_FLAG_ANY;
2237     return TRUE;
2238   }
2239
2240   if (strcmp ("EMPTY", string) == 0 || strcmp ("NONE", string) == 0) {
2241     return TRUE;
2242   }
2243
2244   copy = s = g_strdup (string);
2245   do {
2246     GstCapsFeatures *features = NULL;
2247
2248     while (g_ascii_isspace (*s))
2249       s++;
2250     if (*s == '\0') {
2251       break;
2252     }
2253
2254     if (!priv_gst_structure_parse_name (s, &s, &end, &next)) {
2255       g_free (copy);
2256       return FALSE;
2257     }
2258
2259     save = *end;
2260     *end = '\0';
2261     structure = gst_structure_new_empty (s);
2262     *end = save;
2263
2264     if (structure == NULL) {
2265       g_free (copy);
2266       return FALSE;
2267     }
2268
2269     s = next;
2270
2271     if (*s == '\0') {
2272       goto append;
2273     }
2274
2275     if (*s == '(') {
2276       s++;
2277       end = s;
2278
2279       while (TRUE) {
2280         if (*end == '\0') {
2281           break;
2282         } else if (*end == ')') {
2283           break;
2284         } else {
2285           end++;
2286         }
2287       }
2288
2289       save = *end;
2290       *end = '\0';
2291       features = gst_caps_features_from_string (s);
2292       if (!features) {
2293         gst_structure_free (structure);
2294         g_free (copy);
2295         return FALSE;
2296       }
2297       *end = save;
2298       s = end;
2299       if (save == ')')
2300         s++;
2301     }
2302
2303     if (*s == '\0') {
2304       goto append;
2305     }
2306
2307     if (!priv_gst_structure_parse_fields (s, &s, structure)) {
2308       gst_structure_free (structure);
2309       g_free (copy);
2310       return FALSE;
2311     }
2312
2313   append:
2314     gst_caps_append_structure_unchecked (caps, structure, features);
2315     if (*s == '\0')
2316       break;
2317   } while (TRUE);
2318
2319   g_free (copy);
2320
2321   return TRUE;
2322 }
2323
2324 /**
2325  * gst_caps_from_string:
2326  * @string: a string to convert to #GstCaps
2327  *
2328  * Converts @caps from a string representation.
2329  *
2330  * The current implementation of serialization will lead to unexpected results
2331  * when there are nested #GstCaps / #GstStructure deeper than one level.
2332  *
2333  * Returns: (transfer full): a newly allocated #GstCaps
2334  */
2335 GstCaps *
2336 gst_caps_from_string (const gchar * string)
2337 {
2338   GstCaps *caps;
2339
2340   g_return_val_if_fail (string, FALSE);
2341
2342   caps = gst_caps_new_empty ();
2343   if (gst_caps_from_string_inplace (caps, string)) {
2344     return caps;
2345   } else {
2346     gst_caps_unref (caps);
2347     return NULL;
2348   }
2349 }
2350
2351 static void
2352 gst_caps_transform_to_string (const GValue * src_value, GValue * dest_value)
2353 {
2354   g_return_if_fail (G_IS_VALUE (src_value));
2355   g_return_if_fail (G_IS_VALUE (dest_value));
2356   g_return_if_fail (G_VALUE_HOLDS (src_value, GST_TYPE_CAPS));
2357   g_return_if_fail (G_VALUE_HOLDS (dest_value, G_TYPE_STRING)
2358       || G_VALUE_HOLDS (dest_value, G_TYPE_POINTER));
2359
2360   g_value_take_string (dest_value,
2361       gst_caps_to_string (gst_value_get_caps (src_value)));
2362 }