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