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