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