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