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