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