gst/gstcaps.c

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