gst/gstcaps.c

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