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