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     if (G_UNLIKELY (type == G_TYPE_DATE)) {
 815       g_warning ("Don't use G_TYPE_DATE, use GST_TYPE_DATE instead\n");
 816       type = GST_TYPE_DATE;
 817     }
 818     G_VALUE_COLLECT_INIT (&value, type, varargs, 0, &err);
 819     if (G_UNLIKELY (err)) {
 820       g_critical ("%s", err);
 821       return;
 822     }
 823
 824     gst_caps_set_value (caps, field, &value);
 825
 826     g_value_unset (&value);
 827
 828     field = va_arg (varargs, const gchar *);
 829   }
 830 }
 831
 832 /**
 833  * gst_caps_set_simple:
 834  * @caps: the #GstCaps to set
 835  * @field: first field to set
 836  * @...: additional parameters
 837  *
 838  * Sets fields in a #GstCaps.  The arguments must be passed in the same
 839  * manner as gst_structure_set(), and be NULL-terminated.
 840  * <note>Prior to GStreamer version 0.10.26, this function failed when
 841  * @caps was not simple. If your code needs to work with those versions
 842  * of GStreamer, you may only call this function when GST_CAPS_IS_SIMPLE()
 843  * is %TRUE for @caps.</note>
 844  */
 845 void
 846 gst_caps_set_simple (GstCaps * caps, const char *field, ...)
 847 {
 848   va_list var_args;
 849
 850   g_return_if_fail (GST_IS_CAPS (caps));
 851   g_return_if_fail (IS_WRITABLE (caps));
 852
 853   va_start (var_args, field);
 854   gst_caps_set_simple_valist (caps, field, var_args);
 855   va_end (var_args);
 856 }
 857
 858 /* tests */
 859
 860 /**
 861  * gst_caps_is_any:
 862  * @caps: the #GstCaps to test
 863  *
 864  * Determines if @caps represents any media format.
 865  *
 866  * Returns: TRUE if @caps represents any format.
 867  */
 868 gboolean
 869 gst_caps_is_any (const GstCaps * caps)
 870 {
 871   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
 872
 873   return (CAPS_IS_ANY (caps));
 874 }
 875
 876 /**
 877  * gst_caps_is_empty:
 878  * @caps: the #GstCaps to test
 879  *
 880  * Determines if @caps represents no media formats.
 881  *
 882  * Returns: TRUE if @caps represents no formats.
 883  */
 884 gboolean
 885 gst_caps_is_empty (const GstCaps * caps)
 886 {
 887   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
 888
 889   if (CAPS_IS_ANY (caps))
 890     return FALSE;
 891
 892   return CAPS_IS_EMPTY_SIMPLE (caps);
 893 }
 894
 895 static gboolean
 896 gst_caps_is_fixed_foreach (GQuark field_id, const GValue * value,
 897     gpointer unused)
 898 {
 899   return gst_value_is_fixed (value);
 900 }
 901
 902 /**
 903  * gst_caps_is_fixed:
 904  * @caps: the #GstCaps to test
 905  *
 906  * Fixed #GstCaps describe exactly one format, that is, they have exactly
 907  * one structure, and each field in the structure describes a fixed type.
 908  * Examples of non-fixed types are GST_TYPE_INT_RANGE and GST_TYPE_LIST.
 909  *
 910  * Returns: TRUE if @caps is fixed
 911  */
 912 gboolean
 913 gst_caps_is_fixed (const GstCaps * caps)
 914 {
 915   GstStructure *structure;
 916
 917   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
 918
 919   if (GST_CAPS_LEN (caps) != 1)
 920     return FALSE;
 921
 922   structure = gst_caps_get_structure_unchecked (caps, 0);
 923
 924   return gst_structure_foreach (structure, gst_caps_is_fixed_foreach, NULL);
 925 }
 926
 927 /**
 928  * gst_caps_is_equal_fixed:
 929  * @caps1: the #GstCaps to test
 930  * @caps2: the #GstCaps to test
 931  *
 932  * Tests if two #GstCaps are equal.  This function only works on fixed
 933  * #GstCaps.
 934  *
 935  * Returns: TRUE if the arguments represent the same format
 936  */
 937 gboolean
 938 gst_caps_is_equal_fixed (const GstCaps * caps1, const GstCaps * caps2)
 939 {
 940   GstStructure *struct1, *struct2;
 941
 942   g_return_val_if_fail (gst_caps_is_fixed (caps1), FALSE);
 943   g_return_val_if_fail (gst_caps_is_fixed (caps2), FALSE);
 944
 945   struct1 = gst_caps_get_structure_unchecked (caps1, 0);
 946   struct2 = gst_caps_get_structure_unchecked (caps2, 0);
 947
 948   return gst_structure_is_equal (struct1, struct2);
 949 }
 950
 951 /**
 952  * gst_caps_is_always_compatible:
 953  * @caps1: the #GstCaps to test
 954  * @caps2: the #GstCaps to test
 955  *
 956  * A given #GstCaps structure is always compatible with another if
 957  * every media format that is in the first is also contained in the
 958  * second.  That is, @caps1 is a subset of @caps2.
 959  *
 960  * Returns: TRUE if @caps1 is a subset of @caps2.
 961  */
 962 gboolean
 963 gst_caps_is_always_compatible (const GstCaps * caps1, const GstCaps * caps2)
 964 {
 965   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
 966   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
 967
 968   return gst_caps_is_subset (caps1, caps2);
 969 }
 970
 971 /**
 972  * gst_caps_is_subset:
 973  * @subset: a #GstCaps
 974  * @superset: a potentially greater #GstCaps
 975  *
 976  * Checks if all caps represented by @subset are also represented by @superset.
 977  * <note>This function does not work reliably if optional properties for caps
 978  * are included on one caps and omitted on the other.</note>
 979  *
 980  * Returns: %TRUE if @subset is a subset of @superset
 981  */
 982 gboolean
 983 gst_caps_is_subset (const GstCaps * subset, const GstCaps * superset)
 984 {
 985   GstStructure *s1, *s2;
 986   gboolean ret = TRUE;
 987   gint i, j;
 988
 989   g_return_val_if_fail (subset != NULL, FALSE);
 990   g_return_val_if_fail (superset != NULL, FALSE);
 991
 992   if (CAPS_IS_EMPTY (subset) || CAPS_IS_ANY (superset))
 993     return TRUE;
 994   if (CAPS_IS_ANY (subset) || CAPS_IS_EMPTY (superset))
 995     return FALSE;
 996
 997   for (i = GST_CAPS_LEN (subset) - 1; i >= 0; i--) {
 998     for (j = GST_CAPS_LEN (superset) - 1; j >= 0; j--) {
 999       s1 = gst_caps_get_structure_unchecked (subset, i);
1000       s2 = gst_caps_get_structure_unchecked (superset, j);
1001       if (gst_structure_is_subset (s1, s2)) {
1002         /* If we found a superset, continue with the next
1003          * subset structure */
1004         break;
1005       }
1006     }
1007     /* If we found no superset for this subset structure
1008      * we return FALSE immediately */
1009     if (j == -1) {
1010       ret = FALSE;
1011       break;
1012     }
1013   }
1014
1015   return ret;
1016 }
1017
1018 /**
1019  * gst_caps_is_subset_structure:
1020  * @caps: a #GstCaps
1021  * @structure: a potential #GstStructure subset of @caps
1022  *
1023  * Checks if @structure is a subset of @caps. See gst_caps_is_subset()
1024  * for more information.
1025  *
1026  * Returns: %TRUE if @structure is a subset of @caps
1027  *
1028  * Since: 0.10.36
1029  */
1030 gboolean
1031 gst_caps_is_subset_structure (const GstCaps * caps,
1032     const GstStructure * structure)
1033 {
1034   GstStructure *s;
1035   gint i;
1036
1037   g_return_val_if_fail (caps != NULL, FALSE);
1038   g_return_val_if_fail (structure != NULL, FALSE);
1039
1040   if (CAPS_IS_ANY (caps))
1041     return TRUE;
1042   if (CAPS_IS_EMPTY (caps))
1043     return FALSE;
1044
1045   for (i = GST_CAPS_LEN (caps) - 1; i >= 0; i--) {
1046     s = gst_caps_get_structure_unchecked (caps, i);
1047     if (gst_structure_is_subset (structure, s)) {
1048       /* If we found a superset return TRUE */
1049       return TRUE;
1050     }
1051   }
1052
1053   return FALSE;
1054 }
1055
1056 /**
1057  * gst_caps_is_equal:
1058  * @caps1: a #GstCaps
1059  * @caps2: another #GstCaps
1060  *
1061  * Checks if the given caps represent the same set of caps.
1062  * <note>This function does not work reliably if optional properties for caps
1063  * are included on one caps and omitted on the other.</note>
1064  *
1065  * This function deals correctly with passing NULL for any of the caps.
1066  *
1067  * Returns: TRUE if both caps are equal.
1068  */
1069 gboolean
1070 gst_caps_is_equal (const GstCaps * caps1, const GstCaps * caps2)
1071 {
1072   /* FIXME 0.11: NULL pointers are no valid Caps but indicate an error
1073    * So there should be an assertion that caps1 and caps2 != NULL */
1074
1075   /* NULL <-> NULL is allowed here */
1076   if (G_UNLIKELY (caps1 == caps2))
1077     return TRUE;
1078
1079   /* one of them NULL => they are different (can't be both NULL because
1080    * we checked that above) */
1081   if (G_UNLIKELY (caps1 == NULL || caps2 == NULL))
1082     return FALSE;
1083
1084   if (G_UNLIKELY (gst_caps_is_fixed (caps1) && gst_caps_is_fixed (caps2)))
1085     return gst_caps_is_equal_fixed (caps1, caps2);
1086
1087   return gst_caps_is_subset (caps1, caps2) && gst_caps_is_subset (caps2, caps1);
1088 }
1089
1090 /**
1091  * gst_caps_is_strictly_equal:
1092  * @caps1: a #GstCaps
1093  * @caps2: another #GstCaps
1094  *
1095  * Checks if the given caps are exactly the same set of caps.
1096  *
1097  * This function deals correctly with passing NULL for any of the caps.
1098  *
1099  * Returns: TRUE if both caps are strictly equal.
1100  *
1101  * Since: 0.10.36
1102  */
1103 gboolean
1104 gst_caps_is_strictly_equal (const GstCaps * caps1, const GstCaps * caps2)
1105 {
1106   int i;
1107   /* FIXME 0.11: NULL pointers are no valid Caps but indicate an error
1108    * So there should be an assertion that caps1 and caps2 != NULL */
1109
1110   /* NULL <-> NULL is allowed here */
1111   if (G_UNLIKELY (caps1 == caps2))
1112     return TRUE;
1113
1114   /* one of them NULL => they are different (can't be both NULL because
1115    * we checked that above) */
1116   if (G_UNLIKELY (caps1 == NULL || caps2 == NULL))
1117     return FALSE;
1118
1119   if (GST_CAPS_LEN (caps1) != GST_CAPS_LEN (caps2))
1120     return FALSE;
1121
1122   for (i = 0; i < GST_CAPS_LEN (caps1); i++) {
1123     if (!gst_structure_is_equal (gst_caps_get_structure_unchecked (caps1, i),
1124             gst_caps_get_structure_unchecked (caps2, i)))
1125       return FALSE;
1126   }
1127
1128   return TRUE;
1129 }
1130
1131 /* intersect operation */
1132
1133 /**
1134  * gst_caps_can_intersect:
1135  * @caps1: a #GstCaps to intersect
1136  * @caps2: a #GstCaps to intersect
1137  *
1138  * Tries intersecting @caps1 and @caps2 and reports whether the result would not
1139  * be empty
1140  *
1141  * Returns: %TRUE if intersection would be not empty
1142  *
1143  * Since: 0.10.25
1144  */
1145 gboolean
1146 gst_caps_can_intersect (const GstCaps * caps1, const GstCaps * caps2)
1147 {
1148   guint64 i;                    /* index can be up to 2 * G_MAX_UINT */
1149   guint j, k, len1, len2;
1150   GstStructure *struct1;
1151   GstStructure *struct2;
1152
1153   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
1154   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
1155
1156   /* caps are exactly the same pointers */
1157   if (G_UNLIKELY (caps1 == caps2))
1158     return TRUE;
1159
1160   /* empty caps on either side, return empty */
1161   if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
1162     return FALSE;
1163
1164   /* one of the caps is any */
1165   if (G_UNLIKELY (CAPS_IS_ANY (caps1) || CAPS_IS_ANY (caps2)))
1166     return TRUE;
1167
1168   /* run zigzag on top line then right line, this preserves the caps order
1169    * much better than a simple loop.
1170    *
1171    * This algorithm zigzags over the caps structures as demonstrated in
1172    * the folowing matrix:
1173    *
1174    *          caps1                              0  1  2  3
1175    *       +-------------     total distance:  +-------------
1176    *       | 1  2  4  7                      0 | 0  1  2  3
1177    * caps2 | 3  5  8 10                      1 | 1  2  3  4
1178    *       | 6  9 11 12                      2 | 2  3  4  5
1179    *
1180    * First we iterate over the caps1 structures (top line) intersecting
1181    * the structures diagonally down, then we iterate over the caps2
1182    * structures. The result is that the intersections are ordered based on the
1183    * sum of the indexes in the list.
1184    */
1185   len1 = GST_CAPS_LEN (caps1);
1186   len2 = GST_CAPS_LEN (caps2);
1187   for (i = 0; i < len1 + len2 - 1; i++) {
1188     /* superset index goes from 0 to sgst_caps_structure_intersectuperset->structs->len-1 */
1189     j = MIN (i, len1 - 1);
1190     /* subset index stays 0 until i reaches superset->structs->len, then it
1191      * counts up from 1 to subset->structs->len - 1 */
1192     k = (i > j) ? (i - j) : 0;  /* MAX (0, i - j) */
1193
1194     /* now run the diagonal line, end condition is the left or bottom
1195      * border */
1196     while (k < len2) {
1197       struct1 = gst_caps_get_structure_unchecked (caps1, j);
1198       struct2 = gst_caps_get_structure_unchecked (caps2, k);
1199
1200       if (gst_structure_can_intersect (struct1, struct2)) {
1201         return TRUE;
1202       }
1203       /* move down left */
1204       k++;
1205       if (G_UNLIKELY (j == 0))
1206         break;                  /* so we don't roll back to G_MAXUINT */
1207       j--;
1208     }
1209   }
1210   return FALSE;
1211 }
1212
1213 static GstCaps *
1214 gst_caps_intersect_zig_zag (const GstCaps * caps1, const GstCaps * caps2)
1215 {
1216   guint64 i;                    /* index can be up to 2 * G_MAX_UINT */
1217   guint j, k, len1, len2;
1218
1219   GstStructure *struct1;
1220   GstStructure *struct2;
1221   GstCaps *dest;
1222   GstStructure *istruct;
1223
1224   /* caps are exactly the same pointers, just copy one caps */
1225   if (G_UNLIKELY (caps1 == caps2))
1226     return _gst_caps_copy (caps1);
1227
1228   /* empty caps on either side, return empty */
1229   if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
1230     return gst_caps_new_empty ();
1231
1232   /* one of the caps is any, just copy the other caps */
1233   if (G_UNLIKELY (CAPS_IS_ANY (caps1)))
1234     return _gst_caps_copy (caps2);
1235   if (G_UNLIKELY (CAPS_IS_ANY (caps2)))
1236     return _gst_caps_copy (caps1);
1237
1238   dest = gst_caps_new_empty ();
1239
1240   /* run zigzag on top line then right line, this preserves the caps order
1241    * much better than a simple loop.
1242    *
1243    * This algorithm zigzags over the caps structures as demonstrated in
1244    * the folowing matrix:
1245    *
1246    *          caps1
1247    *       +-------------
1248    *       | 1  2  4  7
1249    * caps2 | 3  5  8 10
1250    *       | 6  9 11 12
1251    *
1252    * First we iterate over the caps1 structures (top line) intersecting
1253    * the structures diagonally down, then we iterate over the caps2
1254    * structures.
1255    */
1256   len1 = GST_CAPS_LEN (caps1);
1257   len2 = GST_CAPS_LEN (caps2);
1258   for (i = 0; i < len1 + len2 - 1; i++) {
1259     /* caps1 index goes from 0 to GST_CAPS_LEN (caps1)-1 */
1260     j = MIN (i, len1 - 1);
1261     /* caps2 index stays 0 until i reaches GST_CAPS_LEN (caps1), then it counts
1262      * up from 1 to GST_CAPS_LEN (caps2) - 1 */
1263     k = (i > j) ? (i - j) : 0;  /* MAX (0, i - j) */
1264
1265     /* now run the diagonal line, end condition is the left or bottom
1266      * border */
1267     while (k < len2) {
1268       struct1 = gst_caps_get_structure_unchecked (caps1, j);
1269       struct2 = gst_caps_get_structure_unchecked (caps2, k);
1270
1271       istruct = gst_structure_intersect (struct1, struct2);
1272
1273       gst_caps_merge_structure (dest, istruct);
1274       /* move down left */
1275       k++;
1276       if (G_UNLIKELY (j == 0))
1277         break;                  /* so we don't roll back to G_MAXUINT */
1278       j--;
1279     }
1280   }
1281   return dest;
1282 }
1283
1284 /**
1285  * gst_caps_intersect_first:
1286  * @caps1: a #GstCaps to intersect
1287  * @caps2: a #GstCaps to intersect
1288  *
1289  * Creates a new #GstCaps that contains all the formats that are common
1290  * to both @caps1 and @caps2.
1291  *
1292  * Unlike @gst_caps_intersect, the returned caps will be ordered in a similar
1293  * fashion as @caps1.
1294  *
1295  * Returns: the new #GstCaps
1296  */
1297 static GstCaps *
1298 gst_caps_intersect_first (const GstCaps * caps1, const GstCaps * caps2)
1299 {
1300   guint i;
1301   guint j, len1, len2;
1302
1303   GstStructure *struct1;
1304   GstStructure *struct2;
1305   GstCaps *dest;
1306   GstStructure *istruct;
1307
1308   /* caps are exactly the same pointers, just copy one caps */
1309   if (G_UNLIKELY (caps1 == caps2))
1310     return gst_caps_copy (caps1);
1311
1312   /* empty caps on either side, return empty */
1313   if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
1314     return gst_caps_new_empty ();
1315
1316   /* one of the caps is any, just copy the other caps */
1317   if (G_UNLIKELY (CAPS_IS_ANY (caps1)))
1318     return gst_caps_copy (caps2);
1319   if (G_UNLIKELY (CAPS_IS_ANY (caps2)))
1320     return gst_caps_copy (caps1);
1321
1322   dest = gst_caps_new_empty ();
1323
1324   len1 = GST_CAPS_LEN (caps1);
1325   len2 = GST_CAPS_LEN (caps2);
1326   for (i = 0; i < len1; i++) {
1327     struct1 = gst_caps_get_structure_unchecked (caps1, i);
1328     for (j = 0; j < len2; j++) {
1329       struct2 = gst_caps_get_structure_unchecked (caps2, j);
1330       istruct = gst_structure_intersect (struct1, struct2);
1331       if (istruct)
1332         gst_caps_merge_structure (dest, istruct);
1333     }
1334   }
1335
1336   return dest;
1337 }
1338
1339 /**
1340  * gst_caps_intersect_full:
1341  * @caps1: a #GstCaps to intersect
1342  * @caps2: a #GstCaps to intersect
1343  * @mode: The intersection algorithm/mode to use
1344  *
1345  * Creates a new #GstCaps that contains all the formats that are common
1346  * to both @caps1 and @caps2, the order is defined by the #GstCapsIntersectMode
1347  * used.
1348  *
1349  * Returns: the new #GstCaps
1350  * Since: 0.10.33
1351  */
1352 GstCaps *
1353 gst_caps_intersect_full (const GstCaps * caps1, const GstCaps * caps2,
1354     GstCapsIntersectMode mode)
1355 {
1356   g_return_val_if_fail (GST_IS_CAPS (caps1), NULL);
1357   g_return_val_if_fail (GST_IS_CAPS (caps2), NULL);
1358
1359   switch (mode) {
1360     case GST_CAPS_INTERSECT_FIRST:
1361       return gst_caps_intersect_first (caps1, caps2);
1362     default:
1363       g_warning ("Unknown caps intersect mode: %d", mode);
1364       /* fallthrough */
1365     case GST_CAPS_INTERSECT_ZIG_ZAG:
1366       return gst_caps_intersect_zig_zag (caps1, caps2);
1367   }
1368 }
1369
1370 /**
1371  * gst_caps_intersect:
1372  * @caps1: a #GstCaps to intersect
1373  * @caps2: a #GstCaps to intersect
1374  *
1375  * Creates a new #GstCaps that contains all the formats that are common
1376  * to both @caps1 and @caps2. Defaults to %GST_CAPS_INTERSECT_ZIG_ZAG mode.
1377  *
1378  * Returns: the new #GstCaps
1379  */
1380 GstCaps *
1381 gst_caps_intersect (const GstCaps * caps1, const GstCaps * caps2)
1382 {
1383   return gst_caps_intersect_full (caps1, caps2, GST_CAPS_INTERSECT_ZIG_ZAG);
1384 }
1385
1386
1387 /* subtract operation */
1388
1389 typedef struct
1390 {
1391   const GstStructure *subtract_from;
1392   GSList *put_into;
1393 }
1394 SubtractionEntry;
1395
1396 static gboolean
1397 gst_caps_structure_subtract_field (GQuark field_id, const GValue * value,
1398     gpointer user_data)
1399 {
1400   SubtractionEntry *e = user_data;
1401   GValue subtraction = { 0, };
1402   const GValue *other;
1403   GstStructure *structure;
1404
1405   other = gst_structure_id_get_value (e->subtract_from, field_id);
1406   if (!other) {
1407     return FALSE;
1408   }
1409   if (!gst_value_subtract (&subtraction, other, value))
1410     return TRUE;
1411   if (gst_value_compare (&subtraction, other) == GST_VALUE_EQUAL) {
1412     g_value_unset (&subtraction);
1413     return FALSE;
1414   } else {
1415     structure = gst_structure_copy (e->subtract_from);
1416     gst_structure_id_set_value (structure, field_id, &subtraction);
1417     g_value_unset (&subtraction);
1418     e->put_into = g_slist_prepend (e->put_into, structure);
1419     return TRUE;
1420   }
1421 }
1422
1423 static gboolean
1424 gst_caps_structure_subtract (GSList ** into, const GstStructure * minuend,
1425     const GstStructure * subtrahend)
1426 {
1427   SubtractionEntry e;
1428   gboolean ret;
1429
1430   e.subtract_from = minuend;
1431   e.put_into = NULL;
1432
1433   ret = gst_structure_foreach ((GstStructure *) subtrahend,
1434       gst_caps_structure_subtract_field, &e);
1435   if (ret) {
1436     *into = e.put_into;
1437   } else {
1438     GSList *walk;
1439
1440     for (walk = e.put_into; walk; walk = g_slist_next (walk)) {
1441       gst_structure_free (walk->data);
1442     }
1443     g_slist_free (e.put_into);
1444   }
1445   return ret;
1446 }
1447
1448 /**
1449  * gst_caps_subtract:
1450  * @minuend: #GstCaps to subtract from
1451  * @subtrahend: #GstCaps to subtract
1452  *
1453  * Subtracts the @subtrahend from the @minuend.
1454  * <note>This function does not work reliably if optional properties for caps
1455  * are included on one caps and omitted on the other.</note>
1456  *
1457  * Returns: the resulting caps
1458  */
1459 GstCaps *
1460 gst_caps_subtract (const GstCaps * minuend, const GstCaps * subtrahend)
1461 {
1462   guint i, j, sublen;
1463   GstStructure *min;
1464   GstStructure *sub;
1465   GstCaps *dest = NULL, *src;
1466
1467   g_return_val_if_fail (minuend != NULL, NULL);
1468   g_return_val_if_fail (subtrahend != NULL, NULL);
1469
1470   if (CAPS_IS_EMPTY (minuend) || CAPS_IS_ANY (subtrahend)) {
1471     return gst_caps_new_empty ();
1472   }
1473   if (CAPS_IS_EMPTY_SIMPLE (subtrahend))
1474     return _gst_caps_copy (minuend);
1475
1476   /* FIXME: Do we want this here or above?
1477      The reason we need this is that there is no definition about what
1478      ANY means for specific types, so it's not possible to reduce ANY partially
1479      You can only remove everything or nothing and that is done above.
1480      Note: there's a test that checks this behaviour. */
1481   g_return_val_if_fail (!CAPS_IS_ANY (minuend), NULL);
1482   sublen = GST_CAPS_LEN (subtrahend);
1483   g_assert (sublen > 0);
1484
1485   src = _gst_caps_copy (minuend);
1486   for (i = 0; i < sublen; i++) {
1487     guint srclen;
1488
1489     sub = gst_caps_get_structure_unchecked (subtrahend, i);
1490     if (dest) {
1491       gst_caps_unref (src);
1492       src = dest;
1493     }
1494     dest = gst_caps_new_empty ();
1495     srclen = GST_CAPS_LEN (src);
1496     for (j = 0; j < srclen; j++) {
1497       min = gst_caps_get_structure_unchecked (src, j);
1498       if (gst_structure_get_name_id (min) == gst_structure_get_name_id (sub)) {
1499         GSList *list;
1500
1501         if (gst_caps_structure_subtract (&list, min, sub)) {
1502           GSList *walk;
1503
1504           for (walk = list; walk; walk = g_slist_next (walk)) {
1505             gst_caps_append_structure_unchecked (dest,
1506                 (GstStructure *) walk->data);
1507           }
1508           g_slist_free (list);
1509         } else {
1510           gst_caps_append_structure_unchecked (dest, gst_structure_copy (min));
1511         }
1512       } else {
1513         gst_caps_append_structure_unchecked (dest, gst_structure_copy (min));
1514       }
1515     }
1516     if (CAPS_IS_EMPTY_SIMPLE (dest)) {
1517       gst_caps_unref (src);
1518       return dest;
1519     }
1520   }
1521
1522   gst_caps_unref (src);
1523   gst_caps_do_simplify (dest);
1524   return dest;
1525 }
1526
1527 /* union operation */
1528
1529 #if 0
1530 static GstStructure *
1531 gst_caps_structure_union (const GstStructure * struct1,
1532     const GstStructure * struct2)
1533 {
1534   int i;
1535   GstStructure *dest;
1536   const GstStructureField *field1;
1537   const GstStructureField *field2;
1538   int ret;
1539
1540   /* FIXME this doesn't actually work */
1541
1542   if (struct1->name != struct2->name)
1543     return NULL;
1544
1545   dest = gst_structure_new_id_empty (struct1->name);
1546
1547   for (i = 0; i < struct1->fields->len; i++) {
1548     GValue dest_value = { 0 };
1549
1550     field1 = GST_STRUCTURE_FIELD (struct1, i);
1551     field2 = gst_structure_id_get_field (struct2, field1->name);
1552
1553     if (field2 == NULL) {
1554       continue;
1555     } else {
1556       if (gst_value_union (&dest_value, &field1->value, &field2->value)) {
1557         gst_structure_set_value (dest, g_quark_to_string (field1->name),
1558             &dest_value);
1559       } else {
1560         ret = gst_value_compare (&field1->value, &field2->value);
1561       }
1562     }
1563   }
1564
1565   return dest;
1566 }
1567 #endif
1568
1569 /**
1570  * gst_caps_union:
1571  * @caps1: a #GstCaps to union
1572  * @caps2: a #GstCaps to union
1573  *
1574  * Creates a new #GstCaps that contains all the formats that are in
1575  * either @caps1 and @caps2.
1576  *
1577  * Returns: the new #GstCaps
1578  */
1579 GstCaps *
1580 gst_caps_union (const GstCaps * caps1, const GstCaps * caps2)
1581 {
1582   GstCaps *dest1;
1583   GstCaps *dest2;
1584
1585   /* NULL pointers are no correct GstCaps */
1586   g_return_val_if_fail (caps1 != NULL, NULL);
1587   g_return_val_if_fail (caps2 != NULL, NULL);
1588
1589   if (CAPS_IS_EMPTY (caps1))
1590     return _gst_caps_copy (caps2);
1591
1592   if (CAPS_IS_EMPTY (caps2))
1593     return _gst_caps_copy (caps1);
1594
1595   if (CAPS_IS_ANY (caps1) || CAPS_IS_ANY (caps2))
1596     return gst_caps_new_any ();
1597
1598   dest1 = _gst_caps_copy (caps1);
1599   dest2 = _gst_caps_copy (caps2);
1600   gst_caps_append (dest1, dest2);
1601
1602   gst_caps_do_simplify (dest1);
1603   return dest1;
1604 }
1605
1606 /* normalize/simplify operations */
1607
1608 typedef struct _NormalizeForeach
1609 {
1610   GstCaps *caps;
1611   GstStructure *structure;
1612 }
1613 NormalizeForeach;
1614
1615 static gboolean
1616 gst_caps_normalize_foreach (GQuark field_id, const GValue * value, gpointer ptr)
1617 {
1618   NormalizeForeach *nf = (NormalizeForeach *) ptr;
1619   GValue val = { 0 };
1620   guint i;
1621
1622   if (G_VALUE_TYPE (value) == GST_TYPE_LIST) {
1623     guint len = gst_value_list_get_size (value);
1624     for (i = 1; i < len; i++) {
1625       const GValue *v = gst_value_list_get_value (value, i);
1626       GstStructure *structure = gst_structure_copy (nf->structure);
1627
1628       gst_structure_id_set_value (structure, field_id, v);
1629       gst_caps_append_structure_unchecked (nf->caps, structure);
1630     }
1631
1632     gst_value_init_and_copy (&val, gst_value_list_get_value (value, 0));
1633     gst_structure_id_set_value (nf->structure, field_id, &val);
1634     g_value_unset (&val);
1635
1636     return FALSE;
1637   }
1638   return TRUE;
1639 }
1640
1641 /**
1642  * gst_caps_normalize:
1643  * @caps: a #GstCaps to normalize
1644  *
1645  * Creates a new #GstCaps that represents the same set of formats as
1646  * @caps, but contains no lists.  Each list is expanded into separate
1647  * @GstStructures.
1648  *
1649  * Returns: the new #GstCaps
1650  */
1651 GstCaps *
1652 gst_caps_normalize (const GstCaps * caps)
1653 {
1654   NormalizeForeach nf;
1655   GstCaps *newcaps;
1656   guint i;
1657
1658   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
1659
1660   newcaps = _gst_caps_copy (caps);
1661   nf.caps = newcaps;
1662
1663   for (i = 0; i < gst_caps_get_size (newcaps); i++) {
1664     nf.structure = gst_caps_get_structure_unchecked (newcaps, i);
1665
1666     while (!gst_structure_foreach (nf.structure,
1667             gst_caps_normalize_foreach, &nf));
1668   }
1669
1670   return newcaps;
1671 }
1672
1673 static gint
1674 gst_caps_compare_structures (gconstpointer one, gconstpointer two)
1675 {
1676   gint ret;
1677   const GstStructure *struct1 = *((const GstStructure **) one);
1678   const GstStructure *struct2 = *((const GstStructure **) two);
1679
1680   /* FIXME: this orders alphabetically, but ordering the quarks might be faster
1681      So what's the best way? */
1682   ret = strcmp (gst_structure_get_name (struct1),
1683       gst_structure_get_name (struct2));
1684   if (ret)
1685     return ret;
1686
1687   return gst_structure_n_fields (struct2) - gst_structure_n_fields (struct1);
1688 }
1689
1690 typedef struct
1691 {
1692   GQuark name;
1693   GValue value;
1694   GstStructure *compare;
1695 }
1696 UnionField;
1697
1698 static gboolean
1699 gst_caps_structure_figure_out_union (GQuark field_id, const GValue * value,
1700     gpointer user_data)
1701 {
1702   UnionField *u = user_data;
1703   const GValue *val = gst_structure_id_get_value (u->compare, field_id);
1704
1705   if (!val) {
1706     if (u->name)
1707       g_value_unset (&u->value);
1708     return FALSE;
1709   }
1710   if (gst_value_compare (val, value) == GST_VALUE_EQUAL)
1711     return TRUE;
1712   if (u->name) {
1713     g_value_unset (&u->value);
1714     return FALSE;
1715   }
1716   u->name = field_id;
1717   gst_value_union (&u->value, val, value);
1718   return TRUE;
1719 }
1720
1721 static gboolean
1722 gst_caps_structure_simplify (GstStructure ** result,
1723     const GstStructure * simplify, GstStructure * compare)
1724 {
1725   GSList *list;
1726   UnionField field = { 0, {0,}, NULL };
1727
1728   /* try to subtract to get a real subset */
1729   if (gst_caps_structure_subtract (&list, simplify, compare)) {
1730     if (list == NULL) {         /* no result */
1731       *result = NULL;
1732       return TRUE;
1733     } else if (list->next == NULL) {    /* one result */
1734       *result = list->data;
1735       g_slist_free (list);
1736       return TRUE;
1737     } else {                    /* multiple results */
1738       g_slist_foreach (list, (GFunc) gst_structure_free, NULL);
1739       g_slist_free (list);
1740       list = NULL;
1741     }
1742   }
1743
1744   /* try to union both structs */
1745   field.compare = compare;
1746   if (gst_structure_foreach ((GstStructure *) simplify,
1747           gst_caps_structure_figure_out_union, &field)) {
1748     gboolean ret = FALSE;
1749
1750     /* now we know all of simplify's fields are the same in compare
1751      * but at most one field: field.name */
1752     if (G_IS_VALUE (&field.value)) {
1753       if (gst_structure_n_fields (simplify) == gst_structure_n_fields (compare)) {
1754         gst_structure_id_set_value (compare, field.name, &field.value);
1755         *result = NULL;
1756         ret = TRUE;
1757       }
1758       g_value_unset (&field.value);
1759     } else if (gst_structure_n_fields (simplify) <=
1760         gst_structure_n_fields (compare)) {
1761       /* compare is just more specific, will be optimized away later */
1762       /* FIXME: do this here? */
1763       GST_LOG ("found a case that will be optimized later.");
1764     } else {
1765       gchar *one = gst_structure_to_string (simplify);
1766       gchar *two = gst_structure_to_string (compare);
1767
1768       GST_ERROR
1769           ("caps mismatch: structures %s and %s claim to be possible to unify, but aren't",
1770           one, two);
1771       g_free (one);
1772       g_free (two);
1773     }
1774     return ret;
1775   }
1776
1777   return FALSE;
1778 }
1779
1780 static void
1781 gst_caps_switch_structures (GstCaps * caps, GstStructure * old,
1782     GstStructure * new, gint i)
1783 {
1784   gst_structure_set_parent_refcount (old, NULL);
1785   gst_structure_free (old);
1786   gst_structure_set_parent_refcount (new, &GST_CAPS_REFCOUNT (caps));
1787   g_ptr_array_index (GST_CAPS_ARRAY (caps), i) = new;
1788 }
1789
1790 /**
1791  * gst_caps_do_simplify:
1792  * @caps: a #GstCaps to simplify
1793  *
1794  * Modifies the given @caps inplace into a representation that represents the
1795  * same set of formats, but in a simpler form.  Component structures that are
1796  * identical are merged.  Component structures that have values that can be
1797  * merged are also merged.
1798  *
1799  * Returns: TRUE, if the caps could be simplified
1800  */
1801 gboolean
1802 gst_caps_do_simplify (GstCaps * caps)
1803 {
1804   GstStructure *simplify, *compare, *result = NULL;
1805   gint i, j, start;
1806   gboolean changed = FALSE;
1807
1808   g_return_val_if_fail (caps != NULL, FALSE);
1809   g_return_val_if_fail (IS_WRITABLE (caps), FALSE);
1810
1811   if (gst_caps_get_size (caps) < 2)
1812     return FALSE;
1813
1814   g_ptr_array_sort (GST_CAPS_ARRAY (caps), gst_caps_compare_structures);
1815
1816   start = GST_CAPS_LEN (caps) - 1;
1817   for (i = GST_CAPS_LEN (caps) - 1; i >= 0; i--) {
1818     simplify = gst_caps_get_structure_unchecked (caps, i);
1819     if (gst_structure_get_name_id (simplify) !=
1820         gst_structure_get_name_id (gst_caps_get_structure_unchecked (caps,
1821                 start)))
1822       start = i;
1823     for (j = start; j >= 0; j--) {
1824       if (j == i)
1825         continue;
1826       compare = gst_caps_get_structure_unchecked (caps, j);
1827       if (gst_structure_get_name_id (simplify) !=
1828           gst_structure_get_name_id (compare)) {
1829         break;
1830       }
1831       if (gst_caps_structure_simplify (&result, simplify, compare)) {
1832         if (result) {
1833           gst_caps_switch_structures (caps, simplify, result, i);
1834           simplify = result;
1835         } else {
1836           gst_caps_remove_structure (caps, i);
1837           start--;
1838           break;
1839         }
1840         changed = TRUE;
1841       }
1842     }
1843   }
1844
1845   if (!changed)
1846     return FALSE;
1847
1848   /* gst_caps_do_simplify (caps); */
1849   return TRUE;
1850 }
1851
1852 /**
1853  * gst_caps_fixate:
1854  * @caps: a #GstCaps to fixate
1855  *
1856  * Modifies the given @caps inplace into a representation with only fixed
1857  * values. First the caps will be truncated and then the first structure will be
1858  * fixated with gst_structure_fixate(). @caps should be writable.
1859  */
1860 void
1861 gst_caps_fixate (GstCaps * caps)
1862 {
1863   GstStructure *s;
1864
1865   g_return_if_fail (GST_IS_CAPS (caps));
1866   g_return_if_fail (IS_WRITABLE (caps));
1867
1868   /* default fixation */
1869   gst_caps_truncate (caps);
1870   s = gst_caps_get_structure (caps, 0);
1871   gst_structure_fixate (s);
1872 }
1873
1874 /* utility */
1875
1876 /**
1877  * gst_caps_to_string:
1878  * @caps: a #GstCaps
1879  *
1880  * Converts @caps to a string representation.  This string representation
1881  * can be converted back to a #GstCaps by gst_caps_from_string().
1882  *
1883  * For debugging purposes its easier to do something like this:
1884  * |[
1885  * GST_LOG ("caps are %" GST_PTR_FORMAT, caps);
1886  * ]|
1887  * This prints the caps in human readble form.
1888  *
1889  * Returns: (transfer full): a newly allocated string representing @caps.
1890  */
1891 gchar *
1892 gst_caps_to_string (const GstCaps * caps)
1893 {
1894   guint i, slen, clen;
1895   GString *s;
1896
1897   /* NOTE:  This function is potentially called by the debug system,
1898    * so any calls to gst_log() (and GST_DEBUG(), GST_LOG(), etc.)
1899    * should be careful to avoid recursion.  This includes any functions
1900    * called by gst_caps_to_string.  In particular, calls should
1901    * not use the GST_PTR_FORMAT extension.  */
1902
1903   if (caps == NULL) {
1904     return g_strdup ("NULL");
1905   }
1906   if (CAPS_IS_ANY (caps)) {
1907     return g_strdup ("ANY");
1908   }
1909   if (CAPS_IS_EMPTY_SIMPLE (caps)) {
1910     return g_strdup ("EMPTY");
1911   }
1912
1913   /* estimate a rough string length to avoid unnecessary reallocs in GString */
1914   slen = 0;
1915   clen = GST_CAPS_LEN (caps);
1916   for (i = 0; i < clen; i++) {
1917     slen +=
1918         STRUCTURE_ESTIMATED_STRING_LEN (gst_caps_get_structure_unchecked (caps,
1919             i));
1920   }
1921
1922   s = g_string_sized_new (slen);
1923   for (i = 0; i < clen; i++) {
1924     GstStructure *structure;
1925
1926     if (i > 0) {
1927       /* ';' is now added by gst_structure_to_string */
1928       g_string_append_c (s, ' ');
1929     }
1930
1931     structure = gst_caps_get_structure_unchecked (caps, i);
1932     priv_gst_structure_append_to_gstring (structure, s);
1933   }
1934   if (s->len && s->str[s->len - 1] == ';') {
1935     /* remove latest ';' */
1936     s->str[--s->len] = '\0';
1937   }
1938   return g_string_free (s, FALSE);
1939 }
1940
1941 static gboolean
1942 gst_caps_from_string_inplace (GstCaps * caps, const gchar * string)
1943 {
1944   GstStructure *structure;
1945   gchar *s;
1946
1947   if (strcmp ("ANY", string) == 0) {
1948     GST_CAPS_FLAGS (caps) = GST_CAPS_FLAG_ANY;
1949     return TRUE;
1950   }
1951   if (strcmp ("EMPTY", string) == 0) {
1952     return TRUE;
1953   }
1954
1955   structure = gst_structure_from_string (string, &s);
1956   if (structure == NULL) {
1957     return FALSE;
1958   }
1959   gst_caps_append_structure_unchecked (caps, structure);
1960
1961   do {
1962
1963     while (g_ascii_isspace (*s))
1964       s++;
1965     if (*s == '\0') {
1966       break;
1967     }
1968     structure = gst_structure_from_string (s, &s);
1969     if (structure == NULL) {
1970       return FALSE;
1971     }
1972     gst_caps_append_structure_unchecked (caps, structure);
1973
1974   } while (TRUE);
1975
1976   return TRUE;
1977 }
1978
1979 /**
1980  * gst_caps_from_string:
1981  * @string: a string to convert to #GstCaps
1982  *
1983  * Converts @caps from a string representation.
1984  *
1985  * Returns: (transfer full): a newly allocated #GstCaps
1986  */
1987 GstCaps *
1988 gst_caps_from_string (const gchar * string)
1989 {
1990   GstCaps *caps;
1991
1992   g_return_val_if_fail (string, FALSE);
1993
1994   caps = gst_caps_new_empty ();
1995   if (gst_caps_from_string_inplace (caps, string)) {
1996     return caps;
1997   } else {
1998     gst_caps_unref (caps);
1999     return NULL;
2000   }
2001 }
2002
2003 static void
2004 gst_caps_transform_to_string (const GValue * src_value, GValue * dest_value)
2005 {
2006   g_return_if_fail (G_IS_VALUE (src_value));
2007   g_return_if_fail (G_IS_VALUE (dest_value));
2008   g_return_if_fail (G_VALUE_HOLDS (src_value, GST_TYPE_CAPS));
2009   g_return_if_fail (G_VALUE_HOLDS (dest_value, G_TYPE_STRING)
2010       || G_VALUE_HOLDS (dest_value, G_TYPE_POINTER));
2011
2012   g_value_take_string (dest_value,
2013       gst_caps_to_string (gst_value_get_caps (src_value)));
2014 }