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_any (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_caps_features_is_equal (features1,
 693             GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY)
 694         && gst_structure_is_subset (structure, structure1)) {
 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     /* FIXME: We only skip if none of the features are
 744      * ANY and are still equal. That way all ANY structures
 745      * show up in the caps and no non-ANY structures are
 746      * swallowed by ANY structures
 747      */
 748     if (((!gst_caps_features_is_any (features_tmp)
 749                 || gst_caps_features_is_any (features1))
 750             && gst_caps_features_is_equal (features_tmp, features1))
 751         && gst_structure_is_subset (structure, structure1)) {
 752       unique = FALSE;
 753       break;
 754     }
 755   }
 756   if (unique) {
 757     caps = gst_caps_make_writable (caps);
 758     gst_caps_append_structure_unchecked (caps, structure, features);
 759   } else {
 760     gst_structure_free (structure);
 761     if (features)
 762       gst_caps_features_free (features);
 763   }
 764   return caps;
 765 }
 766
 767 /**
 768  * gst_caps_get_size:
 769  * @caps: a #GstCaps
 770  *
 771  * Gets the number of structures contained in @caps.
 772  *
 773  * Returns: the number of structures that @caps contains
 774  */
 775 guint
 776 gst_caps_get_size (const GstCaps * caps)
 777 {
 778   g_return_val_if_fail (GST_IS_CAPS (caps), 0);
 779
 780   return GST_CAPS_LEN (caps);
 781 }
 782
 783 /**
 784  * gst_caps_get_structure:
 785  * @caps: a #GstCaps
 786  * @index: the index of the structure
 787  *
 788  * Finds the structure in @caps that has the index @index, and
 789  * returns it.
 790  *
 791  * WARNING: This function takes a const GstCaps *, but returns a
 792  * non-const GstStructure *.  This is for programming convenience --
 793  * the caller should be aware that structures inside a constant
 794  * #GstCaps should not be modified. However, if you know the caps
 795  * are writable, either because you have just copied them or made
 796  * them writable with gst_caps_make_writable(), you may modify the
 797  * structure returned in the usual way, e.g. with functions like
 798  * gst_structure_set().
 799  *
 800  * You do not need to free or unref the structure returned, it
 801  * belongs to the #GstCaps.
 802  *
 803  * Returns: (transfer none): a pointer to the #GstStructure corresponding
 804  *     to @index
 805  */
 806 GstStructure *
 807 gst_caps_get_structure (const GstCaps * caps, guint index)
 808 {
 809   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 810   g_return_val_if_fail (index < GST_CAPS_LEN (caps), NULL);
 811
 812   return gst_caps_get_structure_unchecked (caps, index);
 813 }
 814
 815 /**
 816  * gst_caps_get_features:
 817  * @caps: a #GstCaps
 818  * @index: the index of the structure
 819  *
 820  * Finds the features in @caps that has the index @index, and
 821  * returns it.
 822  *
 823  * WARNING: This function takes a const GstCaps *, but returns a
 824  * non-const GstCapsFeatures *.  This is for programming convenience --
 825  * the caller should be aware that structures inside a constant
 826  * #GstCaps should not be modified. However, if you know the caps
 827  * are writable, either because you have just copied them or made
 828  * them writable with gst_caps_make_writable(), you may modify the
 829  * features returned in the usual way, e.g. with functions like
 830  * gst_caps_features_add().
 831  *
 832  * You do not need to free or unref the structure returned, it
 833  * belongs to the #GstCaps.
 834  *
 835  * Returns: (transfer none): a pointer to the #GstCapsFeatures corresponding
 836  *     to @index
 837  */
 838 GstCapsFeatures *
 839 gst_caps_get_features (const GstCaps * caps, guint index)
 840 {
 841   GstCapsFeatures *features;
 842
 843   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 844   g_return_val_if_fail (index < GST_CAPS_LEN (caps), NULL);
 845
 846   features = gst_caps_get_features_unchecked (caps, index);
 847   if (!features)
 848     features = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
 849
 850   return features;
 851 }
 852
 853 /**
 854  * gst_caps_set_features:
 855  * @caps: a #GstCaps
 856  * @index: the index of the structure
 857  * @features: (allow-none) (transfer full): the #GstFeatures to set
 858  *
 859  * Sets the #GstCapsFeatures @features for the structure at @index.
 860  */
 861 void
 862 gst_caps_set_features (GstCaps * caps, guint index, GstCapsFeatures * features)
 863 {
 864   GstCapsFeatures **storage, *old;
 865
 866   g_return_if_fail (caps != NULL);
 867   g_return_if_fail (index <= gst_caps_get_size (caps));
 868   g_return_if_fail (IS_WRITABLE (caps));
 869
 870   storage = &gst_caps_get_features_unchecked (caps, index);
 871   old = *storage;
 872   *storage = features;
 873
 874   if (features)
 875     gst_caps_features_set_parent_refcount (features, &GST_CAPS_REFCOUNT (caps));
 876
 877   if (old)
 878     gst_caps_features_free (old);
 879 }
 880
 881 /**
 882  * gst_caps_copy_nth:
 883  * @caps: the #GstCaps to copy
 884  * @nth: the nth structure to copy
 885  *
 886  * Creates a new #GstCaps and appends a copy of the nth structure
 887  * contained in @caps.
 888  *
 889  * Returns: (transfer full): the new #GstCaps
 890  */
 891 GstCaps *
 892 gst_caps_copy_nth (const GstCaps * caps, guint nth)
 893 {
 894   GstCaps *newcaps;
 895   GstStructure *structure;
 896   GstCapsFeatures *features;
 897
 898   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 899
 900   newcaps = gst_caps_new_empty ();
 901   GST_CAPS_FLAGS (newcaps) = GST_CAPS_FLAGS (caps);
 902
 903   if (G_LIKELY (GST_CAPS_LEN (caps) > nth)) {
 904     structure = gst_caps_get_structure_unchecked (caps, nth);
 905     features = gst_caps_get_features_unchecked (caps, nth);
 906     gst_caps_append_structure_unchecked (newcaps,
 907         gst_structure_copy (structure),
 908         gst_caps_features_copy_conditional (features));
 909   }
 910
 911   return newcaps;
 912 }
 913
 914 /**
 915  * gst_caps_truncate:
 916  * @caps: (transfer full): the #GstCaps to truncate
 917  *
 918  * Discard all but the first structure from @caps. Useful when
 919  * fixating.
 920  *
 921  * Returns: (transfer full): truncated caps
 922  */
 923 GstCaps *
 924 gst_caps_truncate (GstCaps * caps)
 925 {
 926   gint i;
 927
 928   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 929
 930   i = GST_CAPS_LEN (caps) - 1;
 931   if (i == 0)
 932     return caps;
 933
 934   caps = gst_caps_make_writable (caps);
 935   while (i > 0)
 936     gst_caps_remove_structure (caps, i--);
 937
 938   return caps;
 939 }
 940
 941 /**
 942  * gst_caps_set_value:
 943  * @caps: a writable caps
 944  * @field: name of the field to set
 945  * @value: value to set the field to
 946  *
 947  * Sets the given @field on all structures of @caps to the given @value.
 948  * This is a convenience function for calling gst_structure_set_value() on
 949  * all structures of @caps.
 950  **/
 951 void
 952 gst_caps_set_value (GstCaps * caps, const char *field, const GValue * value)
 953 {
 954   guint i, len;
 955
 956   g_return_if_fail (GST_IS_CAPS (caps));
 957   g_return_if_fail (IS_WRITABLE (caps));
 958   g_return_if_fail (field != NULL);
 959   g_return_if_fail (G_IS_VALUE (value));
 960
 961   len = GST_CAPS_LEN (caps);
 962   for (i = 0; i < len; i++) {
 963     GstStructure *structure = gst_caps_get_structure_unchecked (caps, i);
 964     gst_structure_set_value (structure, field, value);
 965   }
 966 }
 967
 968 /**
 969  * gst_caps_set_simple_valist:
 970  * @caps: the #GstCaps to set
 971  * @field: first field to set
 972  * @varargs: additional parameters
 973  *
 974  * Sets fields in a #GstCaps.  The arguments must be passed in the same
 975  * manner as gst_structure_set(), and be NULL-terminated.
 976  */
 977 void
 978 gst_caps_set_simple_valist (GstCaps * caps, const char *field, va_list varargs)
 979 {
 980   GValue value = { 0, };
 981
 982   g_return_if_fail (GST_IS_CAPS (caps));
 983   g_return_if_fail (IS_WRITABLE (caps));
 984
 985   while (field) {
 986     GType type;
 987     char *err;
 988
 989     type = va_arg (varargs, GType);
 990
 991     G_VALUE_COLLECT_INIT (&value, type, varargs, 0, &err);
 992     if (G_UNLIKELY (err)) {
 993       g_critical ("%s", err);
 994       return;
 995     }
 996
 997     gst_caps_set_value (caps, field, &value);
 998
 999     g_value_unset (&value);
1000
1001     field = va_arg (varargs, const gchar *);
1002   }
1003 }
1004
1005 /**
1006  * gst_caps_set_simple:
1007  * @caps: the #GstCaps to set
1008  * @field: first field to set
1009  * @...: additional parameters
1010  *
1011  * Sets fields in a #GstCaps.  The arguments must be passed in the same
1012  * manner as gst_structure_set(), and be NULL-terminated.
1013  */
1014 void
1015 gst_caps_set_simple (GstCaps * caps, const char *field, ...)
1016 {
1017   va_list var_args;
1018
1019   g_return_if_fail (GST_IS_CAPS (caps));
1020   g_return_if_fail (IS_WRITABLE (caps));
1021
1022   va_start (var_args, field);
1023   gst_caps_set_simple_valist (caps, field, var_args);
1024   va_end (var_args);
1025 }
1026
1027 /* tests */
1028
1029 /**
1030  * gst_caps_is_any:
1031  * @caps: the #GstCaps to test
1032  *
1033  * Determines if @caps represents any media format.
1034  *
1035  * Returns: TRUE if @caps represents any format.
1036  */
1037 gboolean
1038 gst_caps_is_any (const GstCaps * caps)
1039 {
1040   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
1041
1042   return (CAPS_IS_ANY (caps));
1043 }
1044
1045 /**
1046  * gst_caps_is_empty:
1047  * @caps: the #GstCaps to test
1048  *
1049  * Determines if @caps represents no media formats.
1050  *
1051  * Returns: TRUE if @caps represents no formats.
1052  */
1053 gboolean
1054 gst_caps_is_empty (const GstCaps * caps)
1055 {
1056   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
1057
1058   if (CAPS_IS_ANY (caps))
1059     return FALSE;
1060
1061   return CAPS_IS_EMPTY_SIMPLE (caps);
1062 }
1063
1064 static gboolean
1065 gst_caps_is_fixed_foreach (GQuark field_id, const GValue * value,
1066     gpointer unused)
1067 {
1068   return gst_value_is_fixed (value);
1069 }
1070
1071 /**
1072  * gst_caps_is_fixed:
1073  * @caps: the #GstCaps to test
1074  *
1075  * Fixed #GstCaps describe exactly one format, that is, they have exactly
1076  * one structure, and each field in the structure describes a fixed type.
1077  * Examples of non-fixed types are GST_TYPE_INT_RANGE and GST_TYPE_LIST.
1078  *
1079  * Returns: TRUE if @caps is fixed
1080  */
1081 gboolean
1082 gst_caps_is_fixed (const GstCaps * caps)
1083 {
1084   GstStructure *structure;
1085   GstCapsFeatures *features;
1086
1087   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
1088
1089   if (GST_CAPS_LEN (caps) != 1)
1090     return FALSE;
1091
1092   features = gst_caps_get_features (caps, 0);
1093   if (features && gst_caps_features_is_any (features))
1094     return FALSE;
1095
1096   structure = gst_caps_get_structure_unchecked (caps, 0);
1097
1098   return gst_structure_foreach (structure, gst_caps_is_fixed_foreach, NULL);
1099 }
1100
1101 /**
1102  * gst_caps_is_equal_fixed:
1103  * @caps1: the #GstCaps to test
1104  * @caps2: the #GstCaps to test
1105  *
1106  * Tests if two #GstCaps are equal.  This function only works on fixed
1107  * #GstCaps.
1108  *
1109  * Returns: TRUE if the arguments represent the same format
1110  */
1111 gboolean
1112 gst_caps_is_equal_fixed (const GstCaps * caps1, const GstCaps * caps2)
1113 {
1114   GstStructure *struct1, *struct2;
1115   GstCapsFeatures *features1, *features2;
1116
1117   g_return_val_if_fail (gst_caps_is_fixed (caps1), FALSE);
1118   g_return_val_if_fail (gst_caps_is_fixed (caps2), FALSE);
1119
1120   struct1 = gst_caps_get_structure_unchecked (caps1, 0);
1121   features1 = gst_caps_get_features_unchecked (caps1, 0);
1122   if (!features1)
1123     features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1124   struct2 = gst_caps_get_structure_unchecked (caps2, 0);
1125   features2 = gst_caps_get_features_unchecked (caps2, 0);
1126   if (!features2)
1127     features2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1128
1129   return gst_structure_is_equal (struct1, struct2) &&
1130       gst_caps_features_is_equal (features1, features2);
1131 }
1132
1133 /**
1134  * gst_caps_is_always_compatible:
1135  * @caps1: the #GstCaps to test
1136  * @caps2: the #GstCaps to test
1137  *
1138  * A given #GstCaps structure is always compatible with another if
1139  * every media format that is in the first is also contained in the
1140  * second.  That is, @caps1 is a subset of @caps2.
1141  *
1142  * Returns: TRUE if @caps1 is a subset of @caps2.
1143  */
1144 gboolean
1145 gst_caps_is_always_compatible (const GstCaps * caps1, const GstCaps * caps2)
1146 {
1147   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
1148   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
1149
1150   return gst_caps_is_subset (caps1, caps2);
1151 }
1152
1153 /**
1154  * gst_caps_is_subset:
1155  * @subset: a #GstCaps
1156  * @superset: a potentially greater #GstCaps
1157  *
1158  * Checks if all caps represented by @subset are also represented by @superset.
1159  *
1160  * Returns: %TRUE if @subset is a subset of @superset
1161  */
1162 gboolean
1163 gst_caps_is_subset (const GstCaps * subset, const GstCaps * superset)
1164 {
1165   GstStructure *s1, *s2;
1166   GstCapsFeatures *f1, *f2;
1167   gboolean ret = TRUE;
1168   gint i, j;
1169
1170   g_return_val_if_fail (subset != NULL, FALSE);
1171   g_return_val_if_fail (superset != NULL, FALSE);
1172
1173   if (CAPS_IS_EMPTY (subset) || CAPS_IS_ANY (superset))
1174     return TRUE;
1175   if (CAPS_IS_ANY (subset) || CAPS_IS_EMPTY (superset))
1176     return FALSE;
1177
1178   for (i = GST_CAPS_LEN (subset) - 1; i >= 0; i--) {
1179     for (j = GST_CAPS_LEN (superset) - 1; j >= 0; j--) {
1180       s1 = gst_caps_get_structure_unchecked (subset, i);
1181       f1 = gst_caps_get_features_unchecked (subset, i);
1182       if (!f1)
1183         f1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1184       s2 = gst_caps_get_structure_unchecked (superset, j);
1185       f2 = gst_caps_get_features_unchecked (superset, j);
1186       if (!f2)
1187         f2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1188       if ((!gst_caps_features_is_any (f1) || gst_caps_features_is_any (f2)) &&
1189           gst_caps_features_is_equal (f1, f2)
1190           && gst_structure_is_subset (s1, s2)) {
1191         /* If we found a superset, continue with the next
1192          * subset structure */
1193         break;
1194       }
1195     }
1196     /* If we found no superset for this subset structure
1197      * we return FALSE immediately */
1198     if (j == -1) {
1199       ret = FALSE;
1200       break;
1201     }
1202   }
1203
1204   return ret;
1205 }
1206
1207 /**
1208  * gst_caps_is_subset_structure:
1209  * @caps: a #GstCaps
1210  * @structure: a potential #GstStructure subset of @caps
1211  *
1212  * Checks if @structure is a subset of @caps. See gst_caps_is_subset()
1213  * for more information.
1214  *
1215  * Returns: %TRUE if @structure is a subset of @caps
1216  */
1217 gboolean
1218 gst_caps_is_subset_structure (const GstCaps * caps,
1219     const GstStructure * structure)
1220 {
1221   GstStructure *s;
1222   gint i;
1223
1224   g_return_val_if_fail (caps != NULL, FALSE);
1225   g_return_val_if_fail (structure != NULL, FALSE);
1226
1227   if (CAPS_IS_ANY (caps))
1228     return TRUE;
1229   if (CAPS_IS_EMPTY (caps))
1230     return FALSE;
1231
1232   for (i = GST_CAPS_LEN (caps) - 1; i >= 0; i--) {
1233     s = gst_caps_get_structure_unchecked (caps, i);
1234     if (gst_structure_is_subset (structure, s)) {
1235       /* If we found a superset return TRUE */
1236       return TRUE;
1237     }
1238   }
1239
1240   return FALSE;
1241 }
1242
1243 /**
1244  * gst_caps_is_subset_structure_full:
1245  * @caps: a #GstCaps
1246  * @structure: a potential #GstStructure subset of @caps
1247  * @features: (allow-none): a #GstCapsFeatures for @structure
1248  *
1249  * Checks if @structure is a subset of @caps. See gst_caps_is_subset()
1250  * for more information.
1251  *
1252  * Returns: %TRUE if @structure is a subset of @caps
1253  */
1254 gboolean
1255 gst_caps_is_subset_structure_full (const GstCaps * caps,
1256     const GstStructure * structure, const GstCapsFeatures * features)
1257 {
1258   GstStructure *s;
1259   GstCapsFeatures *f;
1260   gint i;
1261
1262   g_return_val_if_fail (caps != NULL, FALSE);
1263   g_return_val_if_fail (structure != NULL, FALSE);
1264
1265   if (CAPS_IS_ANY (caps))
1266     return TRUE;
1267   if (CAPS_IS_EMPTY (caps))
1268     return FALSE;
1269
1270   if (!features)
1271     features = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1272
1273   for (i = GST_CAPS_LEN (caps) - 1; i >= 0; i--) {
1274     s = gst_caps_get_structure_unchecked (caps, i);
1275     f = gst_caps_get_features_unchecked (caps, i);
1276     if (!f)
1277       f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1278     if ((!gst_caps_features_is_any (features) || gst_caps_features_is_any (f))
1279         && gst_caps_features_is_equal (features, f)
1280         && gst_structure_is_subset (structure, s)) {
1281       /* If we found a superset return TRUE */
1282       return TRUE;
1283     }
1284   }
1285
1286   return FALSE;
1287 }
1288
1289 /**
1290  * gst_caps_is_equal:
1291  * @caps1: a #GstCaps
1292  * @caps2: another #GstCaps
1293  *
1294  * Checks if the given caps represent the same set of caps.
1295  *
1296  * Returns: TRUE if both caps are equal.
1297  */
1298 gboolean
1299 gst_caps_is_equal (const GstCaps * caps1, const GstCaps * caps2)
1300 {
1301   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
1302   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
1303
1304   if (G_UNLIKELY (caps1 == caps2))
1305     return TRUE;
1306
1307   if (G_UNLIKELY (gst_caps_is_fixed (caps1) && gst_caps_is_fixed (caps2)))
1308     return gst_caps_is_equal_fixed (caps1, caps2);
1309
1310   return gst_caps_is_subset (caps1, caps2) && gst_caps_is_subset (caps2, caps1);
1311 }
1312
1313 /**
1314  * gst_caps_is_strictly_equal:
1315  * @caps1: a #GstCaps
1316  * @caps2: another #GstCaps
1317  *
1318  * Checks if the given caps are exactly the same set of caps.
1319  *
1320  * Returns: TRUE if both caps are strictly equal.
1321  */
1322 gboolean
1323 gst_caps_is_strictly_equal (const GstCaps * caps1, const GstCaps * caps2)
1324 {
1325   int i;
1326   GstStructure *s1, *s2;
1327   GstCapsFeatures *f1, *f2;
1328
1329   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
1330   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
1331
1332   if (G_UNLIKELY (caps1 == caps2))
1333     return TRUE;
1334
1335   if (GST_CAPS_LEN (caps1) != GST_CAPS_LEN (caps2))
1336     return FALSE;
1337
1338   for (i = 0; i < GST_CAPS_LEN (caps1); i++) {
1339     s1 = gst_caps_get_structure_unchecked (caps1, i);
1340     f1 = gst_caps_get_features_unchecked (caps1, i);
1341     if (!f1)
1342       f1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1343     s2 = gst_caps_get_structure_unchecked (caps2, i);
1344     f2 = gst_caps_get_features_unchecked (caps2, i);
1345     if (!f2)
1346       f2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1347
1348     if (gst_caps_features_is_any (f1) != gst_caps_features_is_any (f2) ||
1349         !gst_caps_features_is_equal (f1, f2) ||
1350         !gst_structure_is_equal (s1, s2))
1351       return FALSE;
1352   }
1353
1354   return TRUE;
1355 }
1356
1357 /* intersect operation */
1358
1359 /**
1360  * gst_caps_can_intersect:
1361  * @caps1: a #GstCaps to intersect
1362  * @caps2: a #GstCaps to intersect
1363  *
1364  * Tries intersecting @caps1 and @caps2 and reports whether the result would not
1365  * be empty
1366  *
1367  * Returns: %TRUE if intersection would be not empty
1368  */
1369 gboolean
1370 gst_caps_can_intersect (const GstCaps * caps1, const GstCaps * caps2)
1371 {
1372   guint64 i;                    /* index can be up to 2 * G_MAX_UINT */
1373   guint j, k, len1, len2;
1374   GstStructure *struct1;
1375   GstStructure *struct2;
1376   GstCapsFeatures *features1;
1377   GstCapsFeatures *features2;
1378
1379   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
1380   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
1381
1382   /* caps are exactly the same pointers */
1383   if (G_UNLIKELY (caps1 == caps2))
1384     return TRUE;
1385
1386   /* empty caps on either side, return empty */
1387   if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
1388     return FALSE;
1389
1390   /* one of the caps is any */
1391   if (G_UNLIKELY (CAPS_IS_ANY (caps1) || CAPS_IS_ANY (caps2)))
1392     return TRUE;
1393
1394   /* run zigzag on top line then right line, this preserves the caps order
1395    * much better than a simple loop.
1396    *
1397    * This algorithm zigzags over the caps structures as demonstrated in
1398    * the following matrix:
1399    *
1400    *          caps1                              0  1  2  3
1401    *       +-------------     total distance:  +-------------
1402    *       | 1  2  4  7                      0 | 0  1  2  3
1403    * caps2 | 3  5  8 10                      1 | 1  2  3  4
1404    *       | 6  9 11 12                      2 | 2  3  4  5
1405    *
1406    * First we iterate over the caps1 structures (top line) intersecting
1407    * the structures diagonally down, then we iterate over the caps2
1408    * structures. The result is that the intersections are ordered based on the
1409    * sum of the indexes in the list.
1410    */
1411   len1 = GST_CAPS_LEN (caps1);
1412   len2 = GST_CAPS_LEN (caps2);
1413   for (i = 0; i < len1 + len2 - 1; i++) {
1414     /* superset index goes from 0 to sgst_caps_structure_intersectuperset->structs->len-1 */
1415     j = MIN (i, len1 - 1);
1416     /* subset index stays 0 until i reaches superset->structs->len, then it
1417      * counts up from 1 to subset->structs->len - 1 */
1418     k = (i > j) ? (i - j) : 0;  /* MAX (0, i - j) */
1419     /* now run the diagonal line, end condition is the left or bottom
1420      * border */
1421     while (k < len2) {
1422       struct1 = gst_caps_get_structure_unchecked (caps1, j);
1423       features1 = gst_caps_get_features_unchecked (caps1, j);
1424       if (!features1)
1425         features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1426       struct2 = gst_caps_get_structure_unchecked (caps2, k);
1427       features2 = gst_caps_get_features_unchecked (caps2, k);
1428       if (!features2)
1429         features2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1430       if (gst_caps_features_is_equal (features1, features2) &&
1431           gst_structure_can_intersect (struct1, struct2)) {
1432         return TRUE;
1433       }
1434       /* move down left */
1435       k++;
1436       if (G_UNLIKELY (j == 0))
1437         break;                  /* so we don't roll back to G_MAXUINT */
1438       j--;
1439     }
1440   }
1441
1442   return FALSE;
1443 }
1444
1445 static GstCaps *
1446 gst_caps_intersect_zig_zag (GstCaps * caps1, GstCaps * caps2)
1447 {
1448   guint64 i;                    /* index can be up to 2 * G_MAX_UINT */
1449   guint j, k, len1, len2;
1450   GstStructure *struct1;
1451   GstStructure *struct2;
1452   GstCapsFeatures *features1;
1453   GstCapsFeatures *features2;
1454   GstCaps *dest;
1455   GstStructure *istruct;
1456
1457   /* caps are exactly the same pointers, just copy one caps */
1458   if (G_UNLIKELY (caps1 == caps2))
1459     return gst_caps_ref (caps1);
1460
1461   /* empty caps on either side, return empty */
1462   if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
1463     return gst_caps_ref (GST_CAPS_NONE);
1464
1465   /* one of the caps is any, just copy the other caps */
1466   if (G_UNLIKELY (CAPS_IS_ANY (caps1)))
1467     return gst_caps_ref (caps2);
1468
1469   if (G_UNLIKELY (CAPS_IS_ANY (caps2)))
1470     return gst_caps_ref (caps1);
1471
1472   dest = gst_caps_new_empty ();
1473   /* run zigzag on top line then right line, this preserves the caps order
1474    * much better than a simple loop.
1475    *
1476    * This algorithm zigzags over the caps structures as demonstrated in
1477    * the following matrix:
1478    *
1479    *          caps1
1480    *       +-------------
1481    *       | 1  2  4  7
1482    * caps2 | 3  5  8 10
1483    *       | 6  9 11 12
1484    *
1485    * First we iterate over the caps1 structures (top line) intersecting
1486    * the structures diagonally down, then we iterate over the caps2
1487    * structures.
1488    */
1489   len1 = GST_CAPS_LEN (caps1);
1490   len2 = GST_CAPS_LEN (caps2);
1491   for (i = 0; i < len1 + len2 - 1; i++) {
1492     /* caps1 index goes from 0 to GST_CAPS_LEN (caps1)-1 */
1493     j = MIN (i, len1 - 1);
1494     /* caps2 index stays 0 until i reaches GST_CAPS_LEN (caps1), then it counts
1495      * up from 1 to GST_CAPS_LEN (caps2) - 1 */
1496     k = (i > j) ? (i - j) : 0;  /* MAX (0, i - j) */
1497     /* now run the diagonal line, end condition is the left or bottom
1498      * border */
1499     while (k < len2) {
1500       struct1 = gst_caps_get_structure_unchecked (caps1, j);
1501       features1 = gst_caps_get_features_unchecked (caps1, j);
1502       if (!features1)
1503         features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1504       struct2 = gst_caps_get_structure_unchecked (caps2, k);
1505       features2 = gst_caps_get_features_unchecked (caps2, k);
1506       if (!features2)
1507         features2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1508       if (gst_caps_features_is_equal (features1, features2)) {
1509         istruct = gst_structure_intersect (struct1, struct2);
1510         if (istruct) {
1511           if (gst_caps_features_is_any (features1))
1512             dest =
1513                 gst_caps_merge_structure_full (dest, istruct,
1514                 gst_caps_features_copy_conditional (features2));
1515           else
1516             dest =
1517                 gst_caps_merge_structure_full (dest, istruct,
1518                 gst_caps_features_copy_conditional (features1));
1519         }
1520       }
1521       /* move down left */
1522       k++;
1523       if (G_UNLIKELY (j == 0))
1524         break;                  /* so we don't roll back to G_MAXUINT */
1525       j--;
1526     }
1527   }
1528   return dest;
1529 }
1530
1531 /**
1532  * gst_caps_intersect_first:
1533  * @caps1: a #GstCaps to intersect
1534  * @caps2: a #GstCaps to intersect
1535  *
1536  * Creates a new #GstCaps that contains all the formats that are common
1537  * to both @caps1 and @caps2.
1538  *
1539  * Unlike @gst_caps_intersect, the returned caps will be ordered in a similar
1540  * fashion as @caps1.
1541  *
1542  * Returns: the new #GstCaps
1543  */
1544 static GstCaps *
1545 gst_caps_intersect_first (GstCaps * caps1, GstCaps * caps2)
1546 {
1547   guint i;
1548   guint j, len1, len2;
1549   GstStructure *struct1;
1550   GstStructure *struct2;
1551   GstCapsFeatures *features1;
1552   GstCapsFeatures *features2;
1553   GstCaps *dest;
1554   GstStructure *istruct;
1555
1556   /* caps are exactly the same pointers, just copy one caps */
1557   if (G_UNLIKELY (caps1 == caps2))
1558     return gst_caps_ref (caps1);
1559
1560   /* empty caps on either side, return empty */
1561   if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
1562     return gst_caps_ref (GST_CAPS_NONE);
1563
1564   /* one of the caps is any, just copy the other caps */
1565   if (G_UNLIKELY (CAPS_IS_ANY (caps1)))
1566     return gst_caps_ref (caps2);
1567
1568   if (G_UNLIKELY (CAPS_IS_ANY (caps2)))
1569     return gst_caps_ref (caps1);
1570
1571   dest = gst_caps_new_empty ();
1572   len1 = GST_CAPS_LEN (caps1);
1573   len2 = GST_CAPS_LEN (caps2);
1574   for (i = 0; i < len1; i++) {
1575     struct1 = gst_caps_get_structure_unchecked (caps1, i);
1576     features1 = gst_caps_get_features_unchecked (caps1, i);
1577     if (!features1)
1578       features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1579     for (j = 0; j < len2; j++) {
1580       struct2 = gst_caps_get_structure_unchecked (caps2, j);
1581       features2 = gst_caps_get_features_unchecked (caps2, j);
1582       if (!features2)
1583         features2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1584       if (gst_caps_features_is_equal (features1, features2)) {
1585         istruct = gst_structure_intersect (struct1, struct2);
1586         if (istruct) {
1587           if (gst_caps_features_is_any (features1))
1588             dest =
1589                 gst_caps_merge_structure_full (dest, istruct,
1590                 gst_caps_features_copy_conditional (features2));
1591           else
1592             dest =
1593                 gst_caps_merge_structure_full (dest, istruct,
1594                 gst_caps_features_copy_conditional (features1));
1595         }
1596       }
1597     }
1598   }
1599
1600   return dest;
1601 }
1602
1603 /**
1604  * gst_caps_intersect_full:
1605  * @caps1: a #GstCaps to intersect
1606  * @caps2: a #GstCaps to intersect
1607  * @mode: The intersection algorithm/mode to use
1608  *
1609  * Creates a new #GstCaps that contains all the formats that are common
1610  * to both @caps1 and @caps2, the order is defined by the #GstCapsIntersectMode
1611  * used.
1612  *
1613  * Returns: the new #GstCaps
1614  */
1615 GstCaps *
1616 gst_caps_intersect_full (GstCaps * caps1, GstCaps * caps2,
1617     GstCapsIntersectMode mode)
1618 {
1619   g_return_val_if_fail (GST_IS_CAPS (caps1), NULL);
1620   g_return_val_if_fail (GST_IS_CAPS (caps2), NULL);
1621
1622   switch (mode) {
1623     case GST_CAPS_INTERSECT_FIRST:
1624       return gst_caps_intersect_first (caps1, caps2);
1625     default:
1626       g_warning ("Unknown caps intersect mode: %d", mode);
1627       /* fallthrough */
1628     case GST_CAPS_INTERSECT_ZIG_ZAG:
1629       return gst_caps_intersect_zig_zag (caps1, caps2);
1630   }
1631 }
1632
1633 /**
1634  * gst_caps_intersect:
1635  * @caps1: a #GstCaps to intersect
1636  * @caps2: a #GstCaps to intersect
1637  *
1638  * Creates a new #GstCaps that contains all the formats that are common
1639  * to both @caps1 and @caps2. Defaults to %GST_CAPS_INTERSECT_ZIG_ZAG mode.
1640  *
1641  * Returns: the new #GstCaps
1642  */
1643 GstCaps *
1644 gst_caps_intersect (GstCaps * caps1, GstCaps * caps2)
1645 {
1646   return gst_caps_intersect_full (caps1, caps2, GST_CAPS_INTERSECT_ZIG_ZAG);
1647 }
1648
1649 /* subtract operation */
1650
1651 typedef struct
1652 {
1653   const GstStructure *subtract_from;
1654   GSList *put_into;
1655 } SubtractionEntry;
1656
1657 static gboolean
1658 gst_caps_structure_subtract_field (GQuark field_id, const GValue * value,
1659     gpointer user_data)
1660 {
1661   SubtractionEntry *e = user_data;
1662   GValue subtraction = { 0, };
1663   const GValue *other;
1664   GstStructure *structure;
1665
1666   other = gst_structure_id_get_value (e->subtract_from, field_id);
1667
1668   if (!other) {
1669     return FALSE;
1670   }
1671
1672   if (!gst_value_subtract (&subtraction, other, value))
1673     return TRUE;
1674
1675   if (gst_value_compare (&subtraction, other) == GST_VALUE_EQUAL) {
1676     g_value_unset (&subtraction);
1677     return FALSE;
1678   } else {
1679     structure = gst_structure_copy (e->subtract_from);
1680     gst_structure_id_take_value (structure, field_id, &subtraction);
1681     e->put_into = g_slist_prepend (e->put_into, structure);
1682     return TRUE;
1683   }
1684 }
1685
1686 static gboolean
1687 gst_caps_structure_subtract (GSList ** into, const GstStructure * minuend,
1688     const GstStructure * subtrahend)
1689 {
1690   SubtractionEntry e;
1691   gboolean ret;
1692
1693   e.subtract_from = minuend;
1694   e.put_into = NULL;
1695   ret = gst_structure_foreach ((GstStructure *) subtrahend,
1696       gst_caps_structure_subtract_field, &e);
1697
1698   if (ret) {
1699     *into = e.put_into;
1700   } else {
1701     GSList *walk;
1702
1703     for (walk = e.put_into; walk; walk = g_slist_next (walk)) {
1704       gst_structure_free (walk->data);
1705     }
1706     g_slist_free (e.put_into);
1707   }
1708
1709   return ret;
1710 }
1711
1712 /**
1713  * gst_caps_subtract:
1714  * @minuend: #GstCaps to subtract from
1715  * @subtrahend: #GstCaps to subtract
1716  *
1717  * Subtracts the @subtrahend from the @minuend.
1718  * <note>This function does not work reliably if optional properties for caps
1719  * are included on one caps and omitted on the other.</note>
1720  *
1721  * Returns: the resulting caps
1722  */
1723 GstCaps *
1724 gst_caps_subtract (GstCaps * minuend, GstCaps * subtrahend)
1725 {
1726   guint i, j, sublen;
1727   GstStructure *min;
1728   GstStructure *sub;
1729   GstCapsFeatures *min_f, *sub_f;
1730   GstCaps *dest = NULL, *src;
1731
1732   g_return_val_if_fail (minuend != NULL, NULL);
1733   g_return_val_if_fail (subtrahend != NULL, NULL);
1734
1735   if (CAPS_IS_EMPTY (minuend) || CAPS_IS_ANY (subtrahend)) {
1736     return gst_caps_new_empty ();
1737   }
1738
1739   if (CAPS_IS_EMPTY_SIMPLE (subtrahend))
1740     return gst_caps_ref (minuend);
1741
1742   /* FIXME: Do we want this here or above?
1743      The reason we need this is that there is no definition about what
1744      ANY means for specific types, so it's not possible to reduce ANY partially
1745      You can only remove everything or nothing and that is done above.
1746      Note: there's a test that checks this behaviour. */
1747
1748   g_return_val_if_fail (!CAPS_IS_ANY (minuend), NULL);
1749   sublen = GST_CAPS_LEN (subtrahend);
1750   g_assert (sublen > 0);
1751
1752   src = _gst_caps_copy (minuend);
1753   for (i = 0; i < sublen; i++) {
1754     guint srclen;
1755
1756     sub = gst_caps_get_structure_unchecked (subtrahend, i);
1757     sub_f = gst_caps_get_features_unchecked (subtrahend, i);
1758     if (!sub_f)
1759       sub_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1760     if (dest) {
1761       gst_caps_unref (src);
1762       src = dest;
1763     }
1764     dest = gst_caps_new_empty ();
1765     srclen = GST_CAPS_LEN (src);
1766     for (j = 0; j < srclen; j++) {
1767       min = gst_caps_get_structure_unchecked (src, j);
1768       min_f = gst_caps_get_features_unchecked (src, j);
1769       if (!min_f)
1770         min_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1771
1772       /* Same reason as above for ANY caps */
1773       g_return_val_if_fail (!gst_caps_features_is_any (min_f), NULL);
1774
1775       if (gst_structure_get_name_id (min) == gst_structure_get_name_id (sub) &&
1776           gst_caps_features_is_equal (min_f, sub_f)) {
1777         GSList *list;
1778
1779         if (gst_caps_structure_subtract (&list, min, sub)) {
1780           GSList *walk;
1781
1782           for (walk = list; walk; walk = g_slist_next (walk)) {
1783             gst_caps_append_structure_unchecked (dest,
1784                 (GstStructure *) walk->data,
1785                 gst_caps_features_copy_conditional (min_f));
1786           }
1787           g_slist_free (list);
1788         } else {
1789           gst_caps_append_structure_unchecked (dest, gst_structure_copy (min),
1790               gst_caps_features_copy_conditional (min_f));
1791         }
1792       } else {
1793         gst_caps_append_structure_unchecked (dest, gst_structure_copy (min),
1794             gst_caps_features_copy_conditional (min_f));
1795       }
1796     }
1797
1798     if (CAPS_IS_EMPTY_SIMPLE (dest)) {
1799       gst_caps_unref (src);
1800       return dest;
1801     }
1802   }
1803
1804   gst_caps_unref (src);
1805   dest = gst_caps_simplify (dest);
1806
1807   return dest;
1808 }
1809
1810 /* normalize/simplify operations */
1811
1812 typedef struct _NormalizeForeach
1813 {
1814   GstCaps *caps;
1815   GstStructure *structure;
1816   GstCapsFeatures *features;
1817 } NormalizeForeach;
1818
1819 static gboolean
1820 gst_caps_normalize_foreach (GQuark field_id, const GValue * value, gpointer ptr)
1821 {
1822   NormalizeForeach *nf = (NormalizeForeach *) ptr;
1823   GValue val = { 0 };
1824   guint i;
1825
1826   if (G_VALUE_TYPE (value) == GST_TYPE_LIST) {
1827     guint len = gst_value_list_get_size (value);
1828
1829     for (i = 1; i < len; i++) {
1830       const GValue *v = gst_value_list_get_value (value, i);
1831       GstStructure *structure = gst_structure_copy (nf->structure);
1832
1833       gst_structure_id_set_value (structure, field_id, v);
1834       gst_caps_append_structure_unchecked (nf->caps, structure,
1835           gst_caps_features_copy_conditional (nf->features));
1836     }
1837
1838     gst_value_init_and_copy (&val, gst_value_list_get_value (value, 0));
1839     gst_structure_id_take_value (nf->structure, field_id, &val);
1840     return FALSE;
1841   }
1842
1843   return TRUE;
1844 }
1845
1846 /**
1847  * gst_caps_normalize:
1848  * @caps: (transfer full): a #GstCaps to normalize
1849  *
1850  * Returns a #GstCaps that represents the same set of formats as
1851  * @caps, but contains no lists.  Each list is expanded into separate
1852  * @GstStructures.
1853  *
1854  * This function takes ownership of @caps.
1855  *
1856  * Returns: (transfer full): the normalized #GstCaps
1857  */
1858 GstCaps *
1859 gst_caps_normalize (GstCaps * caps)
1860 {
1861   NormalizeForeach nf;
1862   guint i;
1863
1864   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
1865
1866   caps = gst_caps_make_writable (caps);
1867   nf.caps = caps;
1868
1869   for (i = 0; i < gst_caps_get_size (nf.caps); i++) {
1870     nf.structure = gst_caps_get_structure_unchecked (nf.caps, i);
1871     nf.features = gst_caps_get_features_unchecked (nf.caps, i);
1872     while (!gst_structure_foreach (nf.structure,
1873             gst_caps_normalize_foreach, &nf));
1874   }
1875
1876   return nf.caps;
1877 }
1878
1879 static gint
1880 gst_caps_compare_structures (gconstpointer one, gconstpointer two)
1881 {
1882   gint ret;
1883   const GstStructure *struct1 = ((const GstCapsArrayElement *) one)->structure;
1884   const GstStructure *struct2 = ((const GstCapsArrayElement *) two)->structure;
1885
1886   /* FIXME: this orders alphabetically, but ordering the quarks might be faster
1887      So what's the best way? */
1888   ret = strcmp (gst_structure_get_name (struct1),
1889       gst_structure_get_name (struct2));
1890
1891   if (ret)
1892     return ret;
1893
1894   return gst_structure_n_fields (struct2) - gst_structure_n_fields (struct1);
1895 }
1896
1897 typedef struct
1898 {
1899   GQuark name;
1900   GValue value;
1901   GstStructure *compare;
1902 } UnionField;
1903
1904 static gboolean
1905 gst_caps_structure_figure_out_union (GQuark field_id, const GValue * value,
1906     gpointer user_data)
1907 {
1908   UnionField *u = user_data;
1909   const GValue *val = gst_structure_id_get_value (u->compare, field_id);
1910
1911   if (!val) {
1912     if (u->name)
1913       g_value_unset (&u->value);
1914     return FALSE;
1915   }
1916
1917   if (gst_value_compare (val, value) == GST_VALUE_EQUAL)
1918     return TRUE;
1919
1920   if (u->name) {
1921     g_value_unset (&u->value);
1922     return FALSE;
1923   }
1924
1925   u->name = field_id;
1926   gst_value_union (&u->value, val, value);
1927
1928   return TRUE;
1929 }
1930
1931 static gboolean
1932 gst_caps_structure_simplify (GstStructure ** result,
1933     GstStructure * simplify, GstStructure * compare)
1934 {
1935   GSList *list;
1936   UnionField field = { 0, {0,}, NULL };
1937
1938   /* try to subtract to get a real subset */
1939   if (gst_caps_structure_subtract (&list, simplify, compare)) {
1940     if (list == NULL) {         /* no result */
1941       *result = NULL;
1942       return TRUE;
1943     } else if (list->next == NULL) {    /* one result */
1944       *result = list->data;
1945       g_slist_free (list);
1946       return TRUE;
1947     } else {                    /* multiple results */
1948       g_slist_foreach (list, (GFunc) gst_structure_free, NULL);
1949       g_slist_free (list);
1950       list = NULL;
1951     }
1952   }
1953
1954   /* try to union both structs */
1955   field.compare = compare;
1956   if (gst_structure_foreach (simplify,
1957           gst_caps_structure_figure_out_union, &field)) {
1958     gboolean ret = FALSE;
1959
1960     /* now we know all of simplify's fields are the same in compare
1961      * but at most one field: field.name */
1962     if (G_IS_VALUE (&field.value)) {
1963       if (gst_structure_n_fields (simplify) == gst_structure_n_fields (compare)) {
1964         gst_structure_id_take_value (compare, field.name, &field.value);
1965         *result = NULL;
1966         ret = TRUE;
1967       } else {
1968         g_value_unset (&field.value);
1969       }
1970     } else
1971         if (gst_structure_n_fields (simplify) <=
1972         gst_structure_n_fields (compare)) {
1973       /* compare is just more specific, will be optimized away later */
1974       /* FIXME: do this here? */
1975       GST_LOG ("found a case that will be optimized later.");
1976     } else {
1977       gchar *one = gst_structure_to_string (simplify);
1978       gchar *two = gst_structure_to_string (compare);
1979
1980       GST_ERROR
1981           ("caps mismatch: structures %s and %s claim to be possible to unify, but aren't",
1982           one, two);
1983       g_free (one);
1984       g_free (two);
1985     }
1986     return ret;
1987   }
1988
1989   return FALSE;
1990 }
1991
1992 static void
1993 gst_caps_switch_structures (GstCaps * caps, GstStructure * old,
1994     GstStructure * new, gint i)
1995 {
1996   gst_structure_set_parent_refcount (old, NULL);
1997   gst_structure_free (old);
1998   gst_structure_set_parent_refcount (new, &GST_CAPS_REFCOUNT (caps));
1999   g_array_index (GST_CAPS_ARRAY (caps), GstCapsArrayElement, i).structure = new;
2000 }
2001
2002 /**
2003  * gst_caps_simplify:
2004  * @caps: (transfer full): a #GstCaps to simplify
2005  *
2006  * Converts the given @caps into a representation that represents the
2007  * same set of formats, but in a simpler form.  Component structures that are
2008  * identical are merged.  Component structures that have values that can be
2009  * merged are also merged.
2010  *
2011  * This method does not preserve the original order of @caps.
2012  *
2013  * Returns: The simplified caps.
2014  */
2015 GstCaps *
2016 gst_caps_simplify (GstCaps * caps)
2017 {
2018   GstStructure *simplify, *compare, *result = NULL;
2019   GstCapsFeatures *simplify_f, *compare_f;
2020   gint i, j, start;
2021
2022   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
2023
2024   start = GST_CAPS_LEN (caps) - 1;
2025   /* one caps, already as simple as can be */
2026   if (start == 0)
2027     return caps;
2028
2029   caps = gst_caps_make_writable (caps);
2030
2031   g_array_sort (GST_CAPS_ARRAY (caps), gst_caps_compare_structures);
2032
2033   for (i = start; i >= 0; i--) {
2034     simplify = gst_caps_get_structure_unchecked (caps, i);
2035     simplify_f = gst_caps_get_features_unchecked (caps, i);
2036     if (!simplify_f)
2037       simplify_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
2038     compare = gst_caps_get_structure_unchecked (caps, start);
2039     compare_f = gst_caps_get_features_unchecked (caps, start);
2040     if (!compare_f)
2041       compare_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
2042     if (gst_structure_get_name_id (simplify) !=
2043         gst_structure_get_name_id (compare) ||
2044         !gst_caps_features_is_equal (simplify_f, compare_f))
2045       start = i;
2046     for (j = start; j >= 0; j--) {
2047       if (j == i)
2048         continue;
2049       compare = gst_caps_get_structure_unchecked (caps, j);
2050       compare_f = gst_caps_get_features_unchecked (caps, j);
2051       if (!compare_f)
2052         compare_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
2053       if (gst_structure_get_name_id (simplify) !=
2054           gst_structure_get_name_id (compare) ||
2055           !gst_caps_features_is_equal (simplify_f, compare_f)) {
2056         break;
2057       }
2058       if (gst_caps_structure_simplify (&result, simplify, compare)) {
2059         if (result) {
2060           gst_caps_switch_structures (caps, simplify, result, i);
2061           simplify = result;
2062         } else {
2063           gst_caps_remove_structure (caps, i);
2064           start--;
2065           break;
2066         }
2067       }
2068     }
2069   }
2070   return caps;
2071 }
2072
2073 /**
2074  * gst_caps_fixate:
2075  * @caps: (transfer full): a #GstCaps to fixate
2076  *
2077  * Modifies the given @caps into a representation with only fixed
2078  * values. First the caps will be truncated and then the first structure will be
2079  * fixated with gst_structure_fixate().
2080  *
2081  * Returns: (transfer full): the fixated caps
2082  */
2083 GstCaps *
2084 gst_caps_fixate (GstCaps * caps)
2085 {
2086   GstStructure *s;
2087   GstCapsFeatures *f;
2088
2089   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
2090
2091   /* default fixation */
2092   caps = gst_caps_truncate (caps);
2093   caps = gst_caps_make_writable (caps);
2094   s = gst_caps_get_structure (caps, 0);
2095   gst_structure_fixate (s);
2096
2097   /* Set features to sysmem if they're still ANY */
2098   f = gst_caps_get_features (caps, 0);
2099   if (f && gst_caps_features_is_any (f)) {
2100     f = gst_caps_features_new_empty ();
2101     gst_caps_set_features (caps, 0, f);
2102   }
2103
2104   return caps;
2105 }
2106
2107 /* utility */
2108
2109 /**
2110  * gst_caps_to_string:
2111  * @caps: a #GstCaps
2112  *
2113  * Converts @caps to a string representation.  This string representation
2114  * can be converted back to a #GstCaps by gst_caps_from_string().
2115  *
2116  * For debugging purposes its easier to do something like this:
2117  * |[
2118  * GST_LOG ("caps are %" GST_PTR_FORMAT, caps);
2119  * ]|
2120  * This prints the caps in human readable form.
2121  *
2122  * Returns: (transfer full): a newly allocated string representing @caps.
2123  */
2124 gchar *
2125 gst_caps_to_string (const GstCaps * caps)
2126 {
2127   guint i, slen, clen;
2128   GString *s;
2129
2130   /* NOTE:  This function is potentially called by the debug system,
2131    * so any calls to gst_log() (and GST_DEBUG(), GST_LOG(), etc.)
2132    * should be careful to avoid recursion.  This includes any functions
2133    * called by gst_caps_to_string.  In particular, calls should
2134    * not use the GST_PTR_FORMAT extension.  */
2135
2136   if (caps == NULL) {
2137     return g_strdup ("NULL");
2138   }
2139   if (CAPS_IS_ANY (caps)) {
2140     return g_strdup ("ANY");
2141   }
2142   if (CAPS_IS_EMPTY_SIMPLE (caps)) {
2143     return g_strdup ("EMPTY");
2144   }
2145
2146   /* estimate a rough string length to avoid unnecessary reallocs in GString */
2147   slen = 0;
2148   clen = GST_CAPS_LEN (caps);
2149   for (i = 0; i < clen; i++) {
2150     GstCapsFeatures *f;
2151
2152     slen +=
2153         STRUCTURE_ESTIMATED_STRING_LEN (gst_caps_get_structure_unchecked
2154         (caps, i));
2155     f = gst_caps_get_features_unchecked (caps, i);
2156     if (f)
2157       slen += FEATURES_ESTIMATED_STRING_LEN (f);
2158   }
2159
2160   s = g_string_sized_new (slen);
2161   for (i = 0; i < clen; i++) {
2162     GstStructure *structure;
2163     GstCapsFeatures *features;
2164
2165     if (i > 0) {
2166       /* ';' is now added by gst_structure_to_string */
2167       g_string_append_c (s, ' ');
2168     }
2169
2170     structure = gst_caps_get_structure_unchecked (caps, i);
2171     features = gst_caps_get_features_unchecked (caps, i);
2172
2173     g_string_append (s, gst_structure_get_name (structure));
2174     if (features && (gst_caps_features_is_any (features)
2175             || !gst_caps_features_is_equal (features,
2176                 GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY))) {
2177       g_string_append_c (s, '(');
2178       priv_gst_caps_features_append_to_gstring (features, s);
2179       g_string_append_c (s, ')');
2180     }
2181     priv_gst_structure_append_to_gstring (structure, s);
2182   }
2183   if (s->len && s->str[s->len - 1] == ';') {
2184     /* remove latest ';' */
2185     s->str[--s->len] = '\0';
2186   }
2187   return g_string_free (s, FALSE);
2188 }
2189
2190 static gboolean
2191 gst_caps_from_string_inplace (GstCaps * caps, const gchar * string)
2192 {
2193   GstStructure *structure;
2194   gchar *s, *copy, *end, *next, save;
2195
2196   if (strcmp ("ANY", string) == 0) {
2197     GST_CAPS_FLAGS (caps) = GST_CAPS_FLAG_ANY;
2198     return TRUE;
2199   }
2200
2201   if (strcmp ("EMPTY", string) == 0 || strcmp ("NONE", string) == 0) {
2202     return TRUE;
2203   }
2204
2205   copy = s = g_strdup (string);
2206   do {
2207     GstCapsFeatures *features = NULL;
2208
2209     while (g_ascii_isspace (*s))
2210       s++;
2211     if (*s == '\0') {
2212       break;
2213     }
2214
2215     if (!priv_gst_structure_parse_name (s, &s, &end, &next)) {
2216       g_free (copy);
2217       return FALSE;
2218     }
2219
2220     save = *end;
2221     *end = '\0';
2222     structure = gst_structure_new_empty (s);
2223     *end = save;
2224
2225     if (structure == NULL) {
2226       g_free (copy);
2227       return FALSE;
2228     }
2229
2230     s = next;
2231
2232     if (*s == '\0') {
2233       goto append;
2234     }
2235
2236     if (*s == '(') {
2237       s++;
2238       end = s;
2239
2240       while (TRUE) {
2241         if (*end == '\0') {
2242           break;
2243         } else if (*end == ')') {
2244           break;
2245         } else {
2246           end++;
2247         }
2248       }
2249
2250       save = *end;
2251       *end = '\0';
2252       features = gst_caps_features_from_string (s);
2253       if (!features) {
2254         gst_structure_free (structure);
2255         g_free (copy);
2256         return FALSE;
2257       }
2258       *end = save;
2259       s = end;
2260       if (save == ')')
2261         s++;
2262     }
2263
2264     if (*s == '\0') {
2265       goto append;
2266     }
2267
2268     if (!priv_gst_structure_parse_fields (s, &s, structure)) {
2269       gst_structure_free (structure);
2270       g_free (copy);
2271       return FALSE;
2272     }
2273
2274   append:
2275     gst_caps_append_structure_unchecked (caps, structure, features);
2276     if (*s == '\0')
2277       break;
2278   } while (TRUE);
2279
2280   g_free (copy);
2281
2282   return TRUE;
2283 }
2284
2285 /**
2286  * gst_caps_from_string:
2287  * @string: a string to convert to #GstCaps
2288  *
2289  * Converts @caps from a string representation.
2290  *
2291  * Returns: (transfer full): a newly allocated #GstCaps
2292  */
2293 GstCaps *
2294 gst_caps_from_string (const gchar * string)
2295 {
2296   GstCaps *caps;
2297
2298   g_return_val_if_fail (string, FALSE);
2299
2300   caps = gst_caps_new_empty ();
2301   if (gst_caps_from_string_inplace (caps, string)) {
2302     return caps;
2303   } else {
2304     gst_caps_unref (caps);
2305     return NULL;
2306   }
2307 }
2308
2309 static void
2310 gst_caps_transform_to_string (const GValue * src_value, GValue * dest_value)
2311 {
2312   g_return_if_fail (G_IS_VALUE (src_value));
2313   g_return_if_fail (G_IS_VALUE (dest_value));
2314   g_return_if_fail (G_VALUE_HOLDS (src_value, GST_TYPE_CAPS));
2315   g_return_if_fail (G_VALUE_HOLDS (dest_value, G_TYPE_STRING)
2316       || G_VALUE_HOLDS (dest_value, G_TYPE_POINTER));
2317
2318   g_value_take_string (dest_value,
2319       gst_caps_to_string (gst_value_get_caps (src_value)));
2320 }