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., 51 Franklin St, Fifth Floor,
  17  * Boston, MA 02110-1301, USA.
  18  */
  19
  20 /**
  21  * SECTION:gstcaps
  22  * @title: GstCaps
  23  * @short_description: Structure describing sets of media formats
  24  * @see_also: #GstStructure, #GstMiniObject
  25  *
  26  * Caps (capabilities) are lightweight refcounted objects describing media types.
  27  * They are composed of an array of #GstStructure.
  28  *
  29  * Caps are exposed on #GstPadTemplate to describe all possible types a
  30  * given pad can handle. They are also stored in the #GstRegistry along with
  31  * a description of the #GstElement.
  32  *
  33  * Caps are exposed on the element pads using the gst_pad_query_caps() pad
  34  * function. This function describes the possible types that the pad can
  35  * handle or produce at runtime.
  36  *
  37  * A #GstCaps can be constructed with the following code fragment:
  38  * |[<!-- language="C" -->
  39  *   GstCaps *caps = gst_caps_new_simple ("video/x-raw",
  40  *      "format", G_TYPE_STRING, "I420",
  41  *      "framerate", GST_TYPE_FRACTION, 25, 1,
  42  *      "pixel-aspect-ratio", GST_TYPE_FRACTION, 1, 1,
  43  *      "width", G_TYPE_INT, 320,
  44  *      "height", G_TYPE_INT, 240,
  45  *      NULL);
  46  * ]|
  47  *
  48  * A #GstCaps is fixed when it has no properties with ranges or lists. Use
  49  * gst_caps_is_fixed() to test for fixed caps. Fixed caps can be used in a
  50  * caps event to notify downstream elements of the current media type.
  51  *
  52  * Various methods exist to work with the media types such as subtracting
  53  * or intersecting.
  54  *
  55  * Be aware that the current #GstCaps / #GstStructure serialization into string
  56  * has limited support for nested #GstCaps / #GstStructure fields. It can only
  57  * support one level of nesting. Using more levels will lead to unexpected
  58  * behavior when using serialization features, such as gst_caps_to_string() or
  59  * gst_value_serialize() and their counterparts.
  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 _GstCapsArrayElement
  75 {
  76   GstStructure *structure;
  77   GstCapsFeatures *features;
  78 } GstCapsArrayElement;
  79
  80 typedef struct _GstCapsImpl
  81 {
  82   GstCaps caps;
  83
  84   GArray *array;
  85 } GstCapsImpl;
  86
  87 #define GST_CAPS_ARRAY(c) (((GstCapsImpl *)(c))->array)
  88
  89 #define GST_CAPS_LEN(c)   (GST_CAPS_ARRAY(c)->len)
  90
  91 #define IS_WRITABLE(caps) \
  92   (GST_CAPS_REFCOUNT_VALUE (caps) == 1)
  93
  94 /* same as gst_caps_is_any () */
  95 #define CAPS_IS_ANY(caps)                               \
  96   (!!(GST_CAPS_FLAGS(caps) & GST_CAPS_FLAG_ANY))
  97
  98 /* same as gst_caps_is_empty () */
  99 #define CAPS_IS_EMPTY(caps)                             \
 100   (!CAPS_IS_ANY(caps) && CAPS_IS_EMPTY_SIMPLE(caps))
 101
 102 #define CAPS_IS_EMPTY_SIMPLE(caps)                                      \
 103   ((GST_CAPS_ARRAY (caps) == NULL) || (GST_CAPS_LEN (caps) == 0))
 104
 105 #define gst_caps_features_copy_conditional(f) ((f && (gst_caps_features_is_any (f) || !gst_caps_features_is_equal (f, GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY))) ? gst_caps_features_copy (f) : NULL)
 106
 107 /* quick way to get a caps structure at an index without doing a type or array
 108  * length check */
 109 #define gst_caps_get_structure_unchecked(caps, index) \
 110      (g_array_index (GST_CAPS_ARRAY (caps), GstCapsArrayElement, (index)).structure)
 111 #define gst_caps_get_features_storage_unchecked(caps, index) \
 112      (&g_array_index (GST_CAPS_ARRAY (caps), GstCapsArrayElement, (index)).features)
 113 #define gst_caps_get_features_unchecked(caps, index) \
 114      (g_atomic_pointer_get (gst_caps_get_features_storage_unchecked (caps, index)))
 115 /* quick way to append a structure without checking the args */
 116 #define gst_caps_append_structure_unchecked(caps, s, f) G_STMT_START{\
 117   GstCapsArrayElement __e={s, f};                                      \
 118   if (gst_structure_set_parent_refcount (__e.structure, &GST_MINI_OBJECT_REFCOUNT(caps)) && \
 119       (!__e.features || gst_caps_features_set_parent_refcount (__e.features, &GST_MINI_OBJECT_REFCOUNT(caps))))         \
 120     g_array_append_val (GST_CAPS_ARRAY (caps), __e);                             \
 121 }G_STMT_END
 122
 123 /* lock to protect multiple invocations of static caps to caps conversion */
 124 G_LOCK_DEFINE_STATIC (static_caps_lock);
 125
 126 static void gst_caps_transform_to_string (const GValue * src_value,
 127     GValue * dest_value);
 128 static gboolean gst_caps_from_string_inplace (GstCaps * caps,
 129     const gchar * string);
 130
 131 GType _gst_caps_type = 0;
 132 GstCaps *_gst_caps_any;
 133 GstCaps *_gst_caps_none;
 134
 135 GST_DEFINE_MINI_OBJECT_TYPE (GstCaps, gst_caps);
 136
 137 void
 138 _priv_gst_caps_initialize (void)
 139 {
 140   _gst_caps_type = gst_caps_get_type ();
 141
 142   _gst_caps_any = gst_caps_new_any ();
 143   _gst_caps_none = gst_caps_new_empty ();
 144
 145   g_value_register_transform_func (_gst_caps_type,
 146       G_TYPE_STRING, gst_caps_transform_to_string);
 147 }
 148
 149 void
 150 _priv_gst_caps_cleanup (void)
 151 {
 152   gst_caps_unref (_gst_caps_any);
 153   _gst_caps_any = NULL;
 154   gst_caps_unref (_gst_caps_none);
 155   _gst_caps_none = NULL;
 156 }
 157
 158 GstCapsFeatures *
 159 __gst_caps_get_features_unchecked (const GstCaps * caps, guint idx)
 160 {
 161   return gst_caps_get_features_unchecked (caps, idx);
 162 }
 163
 164 static GstCaps *
 165 _gst_caps_copy (const GstCaps * caps)
 166 {
 167   GstCaps *newcaps;
 168   GstStructure *structure;
 169   GstCapsFeatures *features;
 170   guint i, n;
 171
 172   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 173
 174   newcaps = gst_caps_new_empty ();
 175   GST_CAPS_FLAGS (newcaps) = GST_CAPS_FLAGS (caps);
 176   n = GST_CAPS_LEN (caps);
 177
 178   GST_CAT_DEBUG_OBJECT (GST_CAT_PERFORMANCE, caps, "doing copy %p -> %p",
 179       caps, newcaps);
 180
 181   for (i = 0; i < n; i++) {
 182     structure = gst_caps_get_structure_unchecked (caps, i);
 183     features = gst_caps_get_features_unchecked (caps, i);
 184     gst_caps_append_structure_full (newcaps, gst_structure_copy (structure),
 185         gst_caps_features_copy_conditional (features));
 186   }
 187
 188   return newcaps;
 189 }
 190
 191 /* creation/deletion */
 192 static void
 193 _gst_caps_free (GstCaps * caps)
 194 {
 195   GstStructure *structure;
 196   GstCapsFeatures *features;
 197   guint i, len;
 198
 199   /* The refcount must be 0, but since we're only called by gst_caps_unref,
 200    * don't bother testing. */
 201   len = GST_CAPS_LEN (caps);
 202   /* This can be used to get statistics about caps sizes */
 203   /*GST_CAT_INFO (GST_CAT_CAPS, "caps size: %d", len); */
 204   for (i = 0; i < len; i++) {
 205     structure = gst_caps_get_structure_unchecked (caps, i);
 206     gst_structure_set_parent_refcount (structure, NULL);
 207     gst_structure_free (structure);
 208     features = gst_caps_get_features_unchecked (caps, i);
 209     if (features) {
 210       gst_caps_features_set_parent_refcount (features, NULL);
 211       gst_caps_features_free (features);
 212     }
 213   }
 214   g_array_free (GST_CAPS_ARRAY (caps), TRUE);
 215
 216 #ifdef DEBUG_REFCOUNT
 217   GST_CAT_TRACE (GST_CAT_CAPS, "freeing caps %p", caps);
 218 #endif
 219
 220 #ifdef USE_POISONING
 221   memset (caps, 0xff, sizeof (GstCapsImpl));
 222 #endif
 223
 224   g_slice_free1 (sizeof (GstCapsImpl), caps);
 225 }
 226
 227 static void
 228 gst_caps_init (GstCaps * caps)
 229 {
 230   gst_mini_object_init (GST_MINI_OBJECT_CAST (caps), 0, _gst_caps_type,
 231       (GstMiniObjectCopyFunction) _gst_caps_copy, NULL,
 232       (GstMiniObjectFreeFunction) _gst_caps_free);
 233
 234   /* the 32 has been determined by logging caps sizes in _gst_caps_free
 235    * but g_ptr_array uses 16 anyway if it expands once, so this does not help
 236    * in practice
 237    * GST_CAPS_ARRAY (caps) = g_ptr_array_sized_new (32);
 238    */
 239   GST_CAPS_ARRAY (caps) =
 240       g_array_new (FALSE, TRUE, sizeof (GstCapsArrayElement));
 241 }
 242
 243 /**
 244  * gst_caps_new_empty:
 245  *
 246  * Creates a new #GstCaps that is empty.  That is, the returned
 247  * #GstCaps contains no media formats.
 248  * The #GstCaps is guaranteed to be writable.
 249  * Caller is responsible for unreffing the returned caps.
 250  *
 251  * Returns: (transfer full): the new #GstCaps
 252  */
 253 GstCaps *
 254 gst_caps_new_empty (void)
 255 {
 256   GstCaps *caps;
 257
 258   caps = (GstCaps *) g_slice_new (GstCapsImpl);
 259
 260   gst_caps_init (caps);
 261
 262 #ifdef DEBUG_REFCOUNT
 263   GST_CAT_TRACE (GST_CAT_CAPS, "created caps %p", caps);
 264 #endif
 265
 266   return caps;
 267 }
 268
 269 /**
 270  * gst_caps_new_any:
 271  *
 272  * Creates a new #GstCaps that indicates that it is compatible with
 273  * any media format.
 274  *
 275  * Returns: (transfer full): the new #GstCaps
 276  */
 277 GstCaps *
 278 gst_caps_new_any (void)
 279 {
 280   GstCaps *caps = gst_caps_new_empty ();
 281
 282   GST_CAPS_FLAG_SET (caps, GST_CAPS_FLAG_ANY);
 283
 284   return caps;
 285 }
 286
 287 /**
 288  * gst_caps_new_empty_simple:
 289  * @media_type: the media type of the structure
 290  *
 291  * Creates a new #GstCaps that contains one #GstStructure with name
 292  * @media_type.
 293  * Caller is responsible for unreffing the returned caps.
 294  *
 295  * Returns: (transfer full): the new #GstCaps
 296  */
 297 GstCaps *
 298 gst_caps_new_empty_simple (const char *media_type)
 299 {
 300   GstCaps *caps;
 301   GstStructure *structure;
 302
 303   caps = gst_caps_new_empty ();
 304   structure = gst_structure_new_empty (media_type);
 305   if (structure)
 306     gst_caps_append_structure_unchecked (caps, structure, NULL);
 307
 308   return caps;
 309 }
 310
 311 /**
 312  * gst_caps_new_simple:
 313  * @media_type: the media type of the structure
 314  * @fieldname: first field to set
 315  * @...: additional arguments
 316  *
 317  * Creates a new #GstCaps that contains one #GstStructure.  The
 318  * structure is defined by the arguments, which have the same format
 319  * as gst_structure_new().
 320  * Caller is responsible for unreffing the returned caps.
 321  *
 322  * Returns: (transfer full): the new #GstCaps
 323  */
 324 GstCaps *
 325 gst_caps_new_simple (const char *media_type, const char *fieldname, ...)
 326 {
 327   GstCaps *caps;
 328   GstStructure *structure;
 329   va_list var_args;
 330
 331   caps = gst_caps_new_empty ();
 332
 333   va_start (var_args, fieldname);
 334   structure = gst_structure_new_valist (media_type, fieldname, var_args);
 335   va_end (var_args);
 336
 337   if (structure)
 338     gst_caps_append_structure_unchecked (caps, structure, NULL);
 339   else
 340     gst_caps_replace (&caps, NULL);
 341
 342   return caps;
 343 }
 344
 345 /**
 346  * gst_caps_new_full:
 347  * @struct1: the first structure to add
 348  * @...: additional structures to add
 349  *
 350  * Creates a new #GstCaps and adds all the structures listed as
 351  * arguments.  The list must be %NULL-terminated.  The structures
 352  * are not copied; the returned #GstCaps owns the structures.
 353  *
 354  * Returns: (transfer full): the new #GstCaps
 355  */
 356 GstCaps *
 357 gst_caps_new_full (GstStructure * struct1, ...)
 358 {
 359   GstCaps *caps;
 360   va_list var_args;
 361
 362   va_start (var_args, struct1);
 363   caps = gst_caps_new_full_valist (struct1, var_args);
 364   va_end (var_args);
 365
 366   return caps;
 367 }
 368
 369 /**
 370  * gst_caps_new_full_valist:
 371  * @structure: the first structure to add
 372  * @var_args: additional structures to add
 373  *
 374  * Creates a new #GstCaps and adds all the structures listed as
 375  * arguments.  The list must be %NULL-terminated.  The structures
 376  * are not copied; the returned #GstCaps owns the structures.
 377  *
 378  * Returns: (transfer full): the new #GstCaps
 379  */
 380 GstCaps *
 381 gst_caps_new_full_valist (GstStructure * structure, va_list var_args)
 382 {
 383   GstCaps *caps;
 384
 385   caps = gst_caps_new_empty ();
 386
 387   while (structure) {
 388     gst_caps_append_structure_unchecked (caps, structure, NULL);
 389     structure = va_arg (var_args, GstStructure *);
 390   }
 391
 392   return caps;
 393 }
 394
 395 G_DEFINE_POINTER_TYPE (GstStaticCaps, gst_static_caps);
 396
 397 /**
 398  * gst_static_caps_get:
 399  * @static_caps: the #GstStaticCaps to convert
 400  *
 401  * Converts a #GstStaticCaps to a #GstCaps.
 402  *
 403  * Returns: (transfer full) (nullable): a pointer to the #GstCaps. Unref
 404  *     after usage. Since the core holds an additional ref to the
 405  *     returned caps, use gst_caps_make_writable() on the returned caps
 406  *     to modify it.
 407  */
 408 GstCaps *
 409 gst_static_caps_get (GstStaticCaps * static_caps)
 410 {
 411   GstCaps **caps;
 412
 413   g_return_val_if_fail (static_caps != NULL, NULL);
 414
 415   caps = &static_caps->caps;
 416
 417   /* refcount is 0 when we need to convert */
 418   if (G_UNLIKELY (*caps == NULL)) {
 419     const char *string;
 420
 421     G_LOCK (static_caps_lock);
 422     /* check if other thread already updated */
 423     if (G_UNLIKELY (*caps != NULL))
 424       goto done;
 425
 426     string = static_caps->string;
 427
 428     if (G_UNLIKELY (string == NULL))
 429       goto no_string;
 430
 431     *caps = gst_caps_from_string (string);
 432
 433     /* convert to string */
 434     if (G_UNLIKELY (*caps == NULL)) {
 435       g_critical ("Could not convert static caps \"%s\"", string);
 436       goto done;
 437     }
 438
 439     /* Caps generated from static caps are usually leaked */
 440     GST_MINI_OBJECT_FLAG_SET (*caps, GST_MINI_OBJECT_FLAG_MAY_BE_LEAKED);
 441
 442     GST_CAT_TRACE (GST_CAT_CAPS, "created %p from string %s", static_caps,
 443         string);
 444   done:
 445     G_UNLOCK (static_caps_lock);
 446   }
 447   /* ref the caps, makes it not writable */
 448   if (G_LIKELY (*caps != NULL))
 449     gst_caps_ref (*caps);
 450
 451   return *caps;
 452
 453   /* ERRORS */
 454 no_string:
 455   {
 456     G_UNLOCK (static_caps_lock);
 457     g_warning ("static caps %p string is NULL", static_caps);
 458     return NULL;
 459   }
 460 }
 461
 462 /**
 463  * gst_static_caps_cleanup:
 464  * @static_caps: the #GstStaticCaps to clean
 465  *
 466  * Clean up the cached caps contained in @static_caps.
 467  */
 468 void
 469 gst_static_caps_cleanup (GstStaticCaps * static_caps)
 470 {
 471   G_LOCK (static_caps_lock);
 472   gst_caps_replace (&static_caps->caps, NULL);
 473   G_UNLOCK (static_caps_lock);
 474 }
 475
 476 /* manipulation */
 477
 478 static void
 479 gst_caps_remove_and_get_structure_and_features (GstCaps * caps, guint idx,
 480     GstStructure ** s, GstCapsFeatures ** f)
 481 {
 482   GstStructure *s_;
 483   GstCapsFeatures *f_;
 484
 485   s_ = gst_caps_get_structure_unchecked (caps, idx);
 486   f_ = gst_caps_get_features_unchecked (caps, idx);
 487
 488   /* don't use index_fast, gst_caps_simplify relies on the order */
 489   g_array_remove_index (GST_CAPS_ARRAY (caps), idx);
 490
 491   gst_structure_set_parent_refcount (s_, NULL);
 492   if (f_) {
 493     gst_caps_features_set_parent_refcount (f_, NULL);
 494   }
 495
 496   *s = s_;
 497   *f = f_;
 498 }
 499
 500 static GstStructure *
 501 gst_caps_remove_and_get_structure (GstCaps * caps, guint idx)
 502 {
 503   GstStructure *s;
 504   GstCapsFeatures *f;
 505
 506   gst_caps_remove_and_get_structure_and_features (caps, idx, &s, &f);
 507
 508   if (f)
 509     gst_caps_features_free (f);
 510
 511   return s;
 512 }
 513
 514 /**
 515  * gst_caps_steal_structure:
 516  * @caps: the #GstCaps to retrieve from
 517  * @index: Index of the structure to retrieve
 518  *
 519  * Retrieves the structure with the given index from the list of structures
 520  * contained in @caps. The caller becomes the owner of the returned structure.
 521  *
 522  * Returns: (transfer full) (nullable): a pointer to the #GstStructure
 523  *     corresponding to @index.
 524  */
 525 GstStructure *
 526 gst_caps_steal_structure (GstCaps * caps, guint index)
 527 {
 528   g_return_val_if_fail (caps != NULL, NULL);
 529   g_return_val_if_fail (IS_WRITABLE (caps), NULL);
 530
 531   if (G_UNLIKELY (index >= GST_CAPS_LEN (caps)))
 532     return NULL;
 533
 534   return gst_caps_remove_and_get_structure (caps, index);
 535 }
 536
 537 /**
 538  * gst_caps_append:
 539  * @caps1: the #GstCaps that will be appended to
 540  * @caps2: (transfer full): the #GstCaps to append
 541  *
 542  * Appends the structures contained in @caps2 to @caps1. The structures in
 543  * @caps2 are not copied -- they are transferred to @caps1, and then @caps2 is
 544  * freed. If either caps is ANY, the resulting caps will be ANY.
 545  */
 546 void
 547 gst_caps_append (GstCaps * caps1, GstCaps * caps2)
 548 {
 549   GstStructure *structure;
 550   GstCapsFeatures *features;
 551   int i;
 552
 553   g_return_if_fail (GST_IS_CAPS (caps1));
 554   g_return_if_fail (GST_IS_CAPS (caps2));
 555   g_return_if_fail (IS_WRITABLE (caps1));
 556
 557   if (G_UNLIKELY (CAPS_IS_ANY (caps1) || CAPS_IS_ANY (caps2))) {
 558     GST_CAPS_FLAGS (caps1) |= GST_CAPS_FLAG_ANY;
 559     gst_caps_unref (caps2);
 560   } else {
 561     caps2 = gst_caps_make_writable (caps2);
 562
 563     for (i = GST_CAPS_LEN (caps2); i; i--) {
 564       gst_caps_remove_and_get_structure_and_features (caps2, 0, &structure,
 565           &features);
 566       gst_caps_append_structure_unchecked (caps1, structure, features);
 567     }
 568     gst_caps_unref (caps2);     /* guaranteed to free it */
 569   }
 570 }
 571
 572 /**
 573  * gst_caps_merge:
 574  * @caps1: (transfer full): the #GstCaps that will take the new entries
 575  * @caps2: (transfer full): the #GstCaps to merge in
 576  *
 577  * Appends the structures contained in @caps2 to @caps1 if they are not yet
 578  * expressed by @caps1. The structures in @caps2 are not copied -- they are
 579  * transferred to a writable copy of @caps1, and then @caps2 is freed.
 580  * If either caps is ANY, the resulting caps will be ANY.
 581  *
 582  * Returns: (transfer full): the merged caps.
 583  */
 584 GstCaps *
 585 gst_caps_merge (GstCaps * caps1, GstCaps * caps2)
 586 {
 587   GstStructure *structure;
 588   GstCapsFeatures *features;
 589   int i;
 590   GstCaps *result;
 591
 592   g_return_val_if_fail (GST_IS_CAPS (caps1), NULL);
 593   g_return_val_if_fail (GST_IS_CAPS (caps2), NULL);
 594
 595   if (G_UNLIKELY (CAPS_IS_ANY (caps1))) {
 596     gst_caps_unref (caps2);
 597     result = caps1;
 598   } else if (G_UNLIKELY (CAPS_IS_ANY (caps2))) {
 599     gst_caps_unref (caps1);
 600     result = caps2;
 601   } else {
 602     caps2 = gst_caps_make_writable (caps2);
 603
 604     for (i = GST_CAPS_LEN (caps2); i; i--) {
 605       gst_caps_remove_and_get_structure_and_features (caps2, 0, &structure,
 606           &features);
 607       caps1 = gst_caps_merge_structure_full (caps1, structure, features);
 608     }
 609     gst_caps_unref (caps2);
 610     result = caps1;
 611
 612     /* this is too naive
 613        GstCaps *com = gst_caps_intersect (caps1, caps2);
 614        GstCaps *add = gst_caps_subtract (caps2, com);
 615
 616        GST_DEBUG ("common : %d", gst_caps_get_size (com));
 617        GST_DEBUG ("adding : %d", gst_caps_get_size (add));
 618        gst_caps_append (caps1, add);
 619        gst_caps_unref (com);
 620      */
 621   }
 622
 623   return result;
 624 }
 625
 626 /**
 627  * gst_caps_append_structure:
 628  * @caps: the #GstCaps that will be appended to
 629  * @structure: (transfer full): the #GstStructure to append
 630  *
 631  * Appends @structure to @caps.  The structure is not copied; @caps
 632  * becomes the owner of @structure.
 633  */
 634 void
 635 gst_caps_append_structure (GstCaps * caps, GstStructure * structure)
 636 {
 637   g_return_if_fail (GST_IS_CAPS (caps));
 638   g_return_if_fail (IS_WRITABLE (caps));
 639
 640   if (G_LIKELY (structure)) {
 641     gst_caps_append_structure_unchecked (caps, structure, NULL);
 642   }
 643 }
 644
 645 /**
 646  * gst_caps_append_structure_full:
 647  * @caps: the #GstCaps that will be appended to
 648  * @structure: (transfer full): the #GstStructure to append
 649  * @features: (transfer full) (allow-none): the #GstCapsFeatures to append
 650  *
 651  * Appends @structure with @features to @caps.  The structure is not copied; @caps
 652  * becomes the owner of @structure.
 653  *
 654  * Since: 1.2
 655  */
 656 void
 657 gst_caps_append_structure_full (GstCaps * caps, GstStructure * structure,
 658     GstCapsFeatures * features)
 659 {
 660   g_return_if_fail (GST_IS_CAPS (caps));
 661   g_return_if_fail (IS_WRITABLE (caps));
 662
 663   if (G_LIKELY (structure)) {
 664     gst_caps_append_structure_unchecked (caps, structure, features);
 665   }
 666 }
 667
 668 /**
 669  * gst_caps_remove_structure:
 670  * @caps: the #GstCaps to remove from
 671  * @idx: Index of the structure to remove
 672  *
 673  * removes the structure with the given index from the list of structures
 674  * contained in @caps.
 675  */
 676 void
 677 gst_caps_remove_structure (GstCaps * caps, guint idx)
 678 {
 679   GstStructure *structure;
 680
 681   g_return_if_fail (caps != NULL);
 682   g_return_if_fail (idx <= gst_caps_get_size (caps));
 683   g_return_if_fail (IS_WRITABLE (caps));
 684
 685   structure = gst_caps_remove_and_get_structure (caps, idx);
 686   gst_structure_free (structure);
 687 }
 688
 689 /**
 690  * gst_caps_merge_structure:
 691  * @caps: (transfer full): the #GstCaps to merge into
 692  * @structure: (transfer full): the #GstStructure to merge
 693  *
 694  * Appends @structure to @caps if its not already expressed by @caps.
 695  *
 696  * Returns: (transfer full): the merged caps.
 697  */
 698 GstCaps *
 699 gst_caps_merge_structure (GstCaps * caps, GstStructure * structure)
 700 {
 701   GstStructure *structure1;
 702   GstCapsFeatures *features1;
 703   int i;
 704   gboolean unique = TRUE;
 705
 706   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 707
 708   if (G_UNLIKELY (structure == NULL))
 709     return caps;
 710
 711   /* check each structure */
 712   for (i = GST_CAPS_LEN (caps) - 1; i >= 0; i--) {
 713     structure1 = gst_caps_get_structure_unchecked (caps, i);
 714     features1 = gst_caps_get_features_unchecked (caps, i);
 715     if (!features1)
 716       features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
 717
 718     /* if structure is a subset of structure1 and the
 719      * there are no existing features, then skip it */
 720     if (gst_caps_features_is_equal (features1,
 721             GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY)
 722         && gst_structure_is_subset (structure, structure1)) {
 723       unique = FALSE;
 724       break;
 725     }
 726   }
 727   if (unique) {
 728     caps = gst_caps_make_writable (caps);
 729     gst_caps_append_structure_unchecked (caps, structure, NULL);
 730   } else {
 731     gst_structure_free (structure);
 732   }
 733   return caps;
 734 }
 735
 736 /**
 737  * gst_caps_merge_structure_full:
 738  * @caps: (transfer full): the #GstCaps to merge into
 739  * @structure: (transfer full): the #GstStructure to merge
 740  * @features: (transfer full) (allow-none): the #GstCapsFeatures to merge
 741  *
 742  * Appends @structure with @features to @caps if its not already expressed by @caps.
 743  *
 744  * Returns: (transfer full): the merged caps.
 745  *
 746  * Since: 1.2
 747  */
 748 GstCaps *
 749 gst_caps_merge_structure_full (GstCaps * caps, GstStructure * structure,
 750     GstCapsFeatures * features)
 751 {
 752   GstStructure *structure1;
 753   GstCapsFeatures *features1, *features_tmp;
 754   int i;
 755   gboolean unique = TRUE;
 756
 757   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 758
 759   if (G_UNLIKELY (structure == NULL))
 760     return caps;
 761
 762   /* To make comparisons easier below */
 763   features_tmp = features ? features : GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
 764
 765   /* check each structure */
 766   for (i = GST_CAPS_LEN (caps) - 1; i >= 0; i--) {
 767     structure1 = gst_caps_get_structure_unchecked (caps, i);
 768     features1 = gst_caps_get_features_unchecked (caps, i);
 769     if (!features1)
 770       features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
 771     /* if structure is a subset of structure1 and the
 772      * the features are a subset, then skip it */
 773     /* FIXME: We only skip if none of the features are
 774      * ANY and are still equal. That way all ANY structures
 775      * show up in the caps and no non-ANY structures are
 776      * swallowed by ANY structures
 777      */
 778     if (((!gst_caps_features_is_any (features_tmp)
 779                 || gst_caps_features_is_any (features1))
 780             && gst_caps_features_is_equal (features_tmp, features1))
 781         && gst_structure_is_subset (structure, structure1)) {
 782       unique = FALSE;
 783       break;
 784     }
 785   }
 786   if (unique) {
 787     caps = gst_caps_make_writable (caps);
 788     gst_caps_append_structure_unchecked (caps, structure, features);
 789   } else {
 790     gst_structure_free (structure);
 791     if (features)
 792       gst_caps_features_free (features);
 793   }
 794   return caps;
 795 }
 796
 797 /**
 798  * gst_caps_get_size:
 799  * @caps: a #GstCaps
 800  *
 801  * Gets the number of structures contained in @caps.
 802  *
 803  * Returns: the number of structures that @caps contains
 804  */
 805 guint
 806 gst_caps_get_size (const GstCaps * caps)
 807 {
 808   g_return_val_if_fail (GST_IS_CAPS (caps), 0);
 809
 810   return GST_CAPS_LEN (caps);
 811 }
 812
 813 /**
 814  * gst_caps_get_structure:
 815  * @caps: a #GstCaps
 816  * @index: the index of the structure
 817  *
 818  * Finds the structure in @caps that has the index @index, and
 819  * returns it.
 820  *
 821  * WARNING: This function takes a const GstCaps *, but returns a
 822  * non-const GstStructure *.  This is for programming convenience --
 823  * the caller should be aware that structures inside a constant
 824  * #GstCaps should not be modified. However, if you know the caps
 825  * are writable, either because you have just copied them or made
 826  * them writable with gst_caps_make_writable(), you may modify the
 827  * structure returned in the usual way, e.g. with functions like
 828  * gst_structure_set().
 829  *
 830  * You do not need to free or unref the structure returned, it
 831  * belongs to the #GstCaps.
 832  *
 833  * Returns: (transfer none): a pointer to the #GstStructure corresponding
 834  *     to @index
 835  */
 836 GstStructure *
 837 gst_caps_get_structure (const GstCaps * caps, guint index)
 838 {
 839   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 840   g_return_val_if_fail (index < GST_CAPS_LEN (caps), NULL);
 841
 842   return gst_caps_get_structure_unchecked (caps, index);
 843 }
 844
 845 /**
 846  * gst_caps_get_features:
 847  * @caps: a #GstCaps
 848  * @index: the index of the structure
 849  *
 850  * Finds the features in @caps that has the index @index, and
 851  * returns it.
 852  *
 853  * WARNING: This function takes a const GstCaps *, but returns a
 854  * non-const GstCapsFeatures *.  This is for programming convenience --
 855  * the caller should be aware that structures inside a constant
 856  * #GstCaps should not be modified. However, if you know the caps
 857  * are writable, either because you have just copied them or made
 858  * them writable with gst_caps_make_writable(), you may modify the
 859  * features returned in the usual way, e.g. with functions like
 860  * gst_caps_features_add().
 861  *
 862  * You do not need to free or unref the structure returned, it
 863  * belongs to the #GstCaps.
 864  *
 865  * Returns: (transfer none) (nullable): a pointer to the #GstCapsFeatures
 866  *     corresponding to @index
 867  *
 868  * Since: 1.2
 869  */
 870 GstCapsFeatures *
 871 gst_caps_get_features (const GstCaps * caps, guint index)
 872 {
 873   GstCapsFeatures *features;
 874
 875   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 876   g_return_val_if_fail (index < GST_CAPS_LEN (caps), NULL);
 877
 878   features = gst_caps_get_features_unchecked (caps, index);
 879   if (!features) {
 880     GstCapsFeatures **storage;
 881
 882     /* We have to do some atomic pointer magic here as the caps
 883      * might not be writable and someone else calls this function
 884      * at the very same time */
 885     features = gst_caps_features_copy (GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY);
 886     gst_caps_features_set_parent_refcount (features, &GST_CAPS_REFCOUNT (caps));
 887
 888     storage = gst_caps_get_features_storage_unchecked (caps, index);
 889     if (!g_atomic_pointer_compare_and_exchange (storage, NULL, features)) {
 890       /* Someone did the same we just tried in the meantime */
 891       gst_caps_features_set_parent_refcount (features, NULL);
 892       gst_caps_features_free (features);
 893
 894       features = gst_caps_get_features_unchecked (caps, index);
 895       g_assert (features != NULL);
 896     }
 897   }
 898
 899   return features;
 900 }
 901
 902 /**
 903  * gst_caps_set_features:
 904  * @caps: a #GstCaps
 905  * @index: the index of the structure
 906  * @features: (allow-none) (transfer full): the #GstCapsFeatures to set
 907  *
 908  * Sets the #GstCapsFeatures @features for the structure at @index.
 909  *
 910  * Since: 1.2
 911  */
 912 void
 913 gst_caps_set_features (GstCaps * caps, guint index, GstCapsFeatures * features)
 914 {
 915   GstCapsFeatures **storage, *old;
 916
 917   g_return_if_fail (caps != NULL);
 918   g_return_if_fail (index <= gst_caps_get_size (caps));
 919   g_return_if_fail (IS_WRITABLE (caps));
 920
 921   storage = gst_caps_get_features_storage_unchecked (caps, index);
 922   /* Not much problem here as caps are writable */
 923   old = g_atomic_pointer_get (storage);
 924   g_atomic_pointer_set (storage, features);
 925
 926   if (features)
 927     gst_caps_features_set_parent_refcount (features, &GST_CAPS_REFCOUNT (caps));
 928
 929   if (old) {
 930     gst_caps_features_set_parent_refcount (old, NULL);
 931     gst_caps_features_free (old);
 932   }
 933 }
 934
 935 /**
 936  * gst_caps_set_features_simple:
 937  * @caps: a #GstCaps
 938  * @features: (allow-none) (transfer full): the #GstCapsFeatures to set
 939  *
 940  * Sets the #GstCapsFeatures @features for all the structures of @caps.
 941  *
 942  * Since: 1.16
 943  */
 944 void
 945 gst_caps_set_features_simple (GstCaps * caps, GstCapsFeatures * features)
 946 {
 947   guint i;
 948   guint n;
 949
 950   g_return_if_fail (caps != NULL);
 951   g_return_if_fail (IS_WRITABLE (caps));
 952
 953   n = gst_caps_get_size (caps);
 954
 955   for (i = 0; i < n; i++) {
 956     GstCapsFeatures *f;
 957
 958     /* Transfer ownership of @features to the last structure */
 959     if (features && i < n - 1)
 960       f = gst_caps_features_copy (features);
 961     else
 962       f = features;
 963
 964     gst_caps_set_features (caps, i, f);
 965   }
 966 }
 967
 968 /**
 969  * gst_caps_copy_nth:
 970  * @caps: the #GstCaps to copy
 971  * @nth: the nth structure to copy
 972  *
 973  * Creates a new #GstCaps and appends a copy of the nth structure
 974  * contained in @caps.
 975  *
 976  * Returns: (transfer full): the new #GstCaps
 977  *
 978  * Since: 1.16
 979  */
 980 GstCaps *
 981 gst_caps_copy_nth (const GstCaps * caps, guint nth)
 982 {
 983   GstCaps *newcaps;
 984   GstStructure *structure;
 985   GstCapsFeatures *features;
 986
 987   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 988
 989   newcaps = gst_caps_new_empty ();
 990   GST_CAPS_FLAGS (newcaps) = GST_CAPS_FLAGS (caps);
 991
 992   if (G_LIKELY (GST_CAPS_LEN (caps) > nth)) {
 993     structure = gst_caps_get_structure_unchecked (caps, nth);
 994     features = gst_caps_get_features_unchecked (caps, nth);
 995     gst_caps_append_structure_unchecked (newcaps,
 996         gst_structure_copy (structure),
 997         gst_caps_features_copy_conditional (features));
 998   }
 999
1000   return newcaps;
1001 }
1002
1003 /**
1004  * gst_caps_truncate:
1005  * @caps: (transfer full): the #GstCaps to truncate
1006  *
1007  * Discard all but the first structure from @caps. Useful when
1008  * fixating.
1009  *
1010  * This function takes ownership of @caps and will call gst_caps_make_writable()
1011  * on it if necessary, so you must not use @caps afterwards unless you keep an
1012  * additional reference to it with gst_caps_ref().
1013  *
1014  * Returns: (transfer full): truncated caps
1015  */
1016 GstCaps *
1017 gst_caps_truncate (GstCaps * caps)
1018 {
1019   gint i;
1020
1021   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
1022
1023   i = GST_CAPS_LEN (caps) - 1;
1024   if (i == 0)
1025     return caps;
1026
1027   caps = gst_caps_make_writable (caps);
1028   while (i > 0)
1029     gst_caps_remove_structure (caps, i--);
1030
1031   return caps;
1032 }
1033
1034 /**
1035  * gst_caps_set_value:
1036  * @caps: a writable caps
1037  * @field: name of the field to set
1038  * @value: value to set the field to
1039  *
1040  * Sets the given @field on all structures of @caps to the given @value.
1041  * This is a convenience function for calling gst_structure_set_value() on
1042  * all structures of @caps.
1043  **/
1044 void
1045 gst_caps_set_value (GstCaps * caps, const char *field, const GValue * value)
1046 {
1047   guint i, len;
1048
1049   g_return_if_fail (GST_IS_CAPS (caps));
1050   g_return_if_fail (IS_WRITABLE (caps));
1051   g_return_if_fail (field != NULL);
1052   g_return_if_fail (G_IS_VALUE (value));
1053
1054   len = GST_CAPS_LEN (caps);
1055   for (i = 0; i < len; i++) {
1056     GstStructure *structure = gst_caps_get_structure_unchecked (caps, i);
1057     gst_structure_set_value (structure, field, value);
1058   }
1059 }
1060
1061 /**
1062  * gst_caps_set_simple_valist:
1063  * @caps: the #GstCaps to set
1064  * @field: first field to set
1065  * @varargs: additional parameters
1066  *
1067  * Sets fields in a #GstCaps.  The arguments must be passed in the same
1068  * manner as gst_structure_set(), and be %NULL-terminated.
1069  */
1070 void
1071 gst_caps_set_simple_valist (GstCaps * caps, const char *field, va_list varargs)
1072 {
1073   GValue value = { 0, };
1074
1075   g_return_if_fail (GST_IS_CAPS (caps));
1076   g_return_if_fail (IS_WRITABLE (caps));
1077
1078   while (field) {
1079     GType type;
1080     char *err;
1081
1082     type = va_arg (varargs, GType);
1083
1084     G_VALUE_COLLECT_INIT (&value, type, varargs, 0, &err);
1085     if (G_UNLIKELY (err)) {
1086       g_critical ("%s", err);
1087       g_free (err);
1088       return;
1089     }
1090
1091     gst_caps_set_value (caps, field, &value);
1092
1093     g_value_unset (&value);
1094
1095     field = va_arg (varargs, const gchar *);
1096   }
1097 }
1098
1099 /**
1100  * gst_caps_set_simple:
1101  * @caps: the #GstCaps to set
1102  * @field: first field to set
1103  * @...: additional parameters
1104  *
1105  * Sets fields in a #GstCaps.  The arguments must be passed in the same
1106  * manner as gst_structure_set(), and be %NULL-terminated.
1107  */
1108 void
1109 gst_caps_set_simple (GstCaps * caps, const char *field, ...)
1110 {
1111   va_list var_args;
1112
1113   g_return_if_fail (GST_IS_CAPS (caps));
1114   g_return_if_fail (IS_WRITABLE (caps));
1115
1116   va_start (var_args, field);
1117   gst_caps_set_simple_valist (caps, field, var_args);
1118   va_end (var_args);
1119 }
1120
1121 /* tests */
1122
1123 /**
1124  * gst_caps_is_any:
1125  * @caps: the #GstCaps to test
1126  *
1127  * Determines if @caps represents any media format.
1128  *
1129  * Returns: %TRUE if @caps represents any format.
1130  */
1131 gboolean
1132 gst_caps_is_any (const GstCaps * caps)
1133 {
1134   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
1135
1136   return (CAPS_IS_ANY (caps));
1137 }
1138
1139 /**
1140  * gst_caps_is_empty:
1141  * @caps: the #GstCaps to test
1142  *
1143  * Determines if @caps represents no media formats.
1144  *
1145  * Returns: %TRUE if @caps represents no formats.
1146  */
1147 gboolean
1148 gst_caps_is_empty (const GstCaps * caps)
1149 {
1150   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
1151
1152   if (CAPS_IS_ANY (caps))
1153     return FALSE;
1154
1155   return CAPS_IS_EMPTY_SIMPLE (caps);
1156 }
1157
1158 static gboolean
1159 gst_caps_is_fixed_foreach (GQuark field_id, const GValue * value,
1160     gpointer unused)
1161 {
1162   return gst_value_is_fixed (value);
1163 }
1164
1165 /**
1166  * gst_caps_is_fixed:
1167  * @caps: the #GstCaps to test
1168  *
1169  * Fixed #GstCaps describe exactly one format, that is, they have exactly
1170  * one structure, and each field in the structure describes a fixed type.
1171  * Examples of non-fixed types are GST_TYPE_INT_RANGE and GST_TYPE_LIST.
1172  *
1173  * Returns: %TRUE if @caps is fixed
1174  */
1175 gboolean
1176 gst_caps_is_fixed (const GstCaps * caps)
1177 {
1178   GstStructure *structure;
1179   GstCapsFeatures *features;
1180
1181   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
1182
1183   if (GST_CAPS_LEN (caps) != 1)
1184     return FALSE;
1185
1186   features = gst_caps_get_features_unchecked (caps, 0);
1187   if (features && gst_caps_features_is_any (features))
1188     return FALSE;
1189
1190   structure = gst_caps_get_structure_unchecked (caps, 0);
1191
1192   return gst_structure_foreach (structure, gst_caps_is_fixed_foreach, NULL);
1193 }
1194
1195 /**
1196  * gst_caps_is_equal_fixed:
1197  * @caps1: the #GstCaps to test
1198  * @caps2: the #GstCaps to test
1199  *
1200  * Tests if two #GstCaps are equal.  This function only works on fixed
1201  * #GstCaps.
1202  *
1203  * Returns: %TRUE if the arguments represent the same format
1204  */
1205 gboolean
1206 gst_caps_is_equal_fixed (const GstCaps * caps1, const GstCaps * caps2)
1207 {
1208   GstStructure *struct1, *struct2;
1209   GstCapsFeatures *features1, *features2;
1210
1211   g_return_val_if_fail (gst_caps_is_fixed (caps1), FALSE);
1212   g_return_val_if_fail (gst_caps_is_fixed (caps2), FALSE);
1213
1214   struct1 = gst_caps_get_structure_unchecked (caps1, 0);
1215   features1 = gst_caps_get_features_unchecked (caps1, 0);
1216   if (!features1)
1217     features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1218   struct2 = gst_caps_get_structure_unchecked (caps2, 0);
1219   features2 = gst_caps_get_features_unchecked (caps2, 0);
1220   if (!features2)
1221     features2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1222
1223   return gst_structure_is_equal (struct1, struct2) &&
1224       gst_caps_features_is_equal (features1, features2);
1225 }
1226
1227 /**
1228  * gst_caps_is_always_compatible:
1229  * @caps1: the #GstCaps to test
1230  * @caps2: the #GstCaps to test
1231  *
1232  * A given #GstCaps structure is always compatible with another if
1233  * every media format that is in the first is also contained in the
1234  * second.  That is, @caps1 is a subset of @caps2.
1235  *
1236  * Returns: %TRUE if @caps1 is a subset of @caps2.
1237  */
1238 gboolean
1239 gst_caps_is_always_compatible (const GstCaps * caps1, const GstCaps * caps2)
1240 {
1241   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
1242   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
1243
1244   return gst_caps_is_subset (caps1, caps2);
1245 }
1246
1247 /**
1248  * gst_caps_is_subset:
1249  * @subset: a #GstCaps
1250  * @superset: a potentially greater #GstCaps
1251  *
1252  * Checks if all caps represented by @subset are also represented by @superset.
1253  *
1254  * Returns: %TRUE if @subset is a subset of @superset
1255  */
1256 gboolean
1257 gst_caps_is_subset (const GstCaps * subset, const GstCaps * superset)
1258 {
1259   GstStructure *s1, *s2;
1260   GstCapsFeatures *f1, *f2;
1261   gboolean ret = TRUE;
1262   gint i, j;
1263
1264   g_return_val_if_fail (subset != NULL, FALSE);
1265   g_return_val_if_fail (superset != NULL, FALSE);
1266
1267   if (CAPS_IS_EMPTY (subset) || CAPS_IS_ANY (superset))
1268     return TRUE;
1269   if (CAPS_IS_ANY (subset) || CAPS_IS_EMPTY (superset))
1270     return FALSE;
1271
1272   for (i = GST_CAPS_LEN (subset) - 1; i >= 0; i--) {
1273     for (j = GST_CAPS_LEN (superset) - 1; j >= 0; j--) {
1274       s1 = gst_caps_get_structure_unchecked (subset, i);
1275       f1 = gst_caps_get_features_unchecked (subset, i);
1276       if (!f1)
1277         f1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1278       s2 = gst_caps_get_structure_unchecked (superset, j);
1279       f2 = gst_caps_get_features_unchecked (superset, j);
1280       if (!f2)
1281         f2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1282       if ((!gst_caps_features_is_any (f1) || gst_caps_features_is_any (f2)) &&
1283           gst_caps_features_is_equal (f1, f2)
1284           && gst_structure_is_subset (s1, s2)) {
1285         /* If we found a superset, continue with the next
1286          * subset structure */
1287         break;
1288       }
1289     }
1290     /* If we found no superset for this subset structure
1291      * we return FALSE immediately */
1292     if (j == -1) {
1293       ret = FALSE;
1294       break;
1295     }
1296   }
1297
1298   return ret;
1299 }
1300
1301 /**
1302  * gst_caps_is_subset_structure:
1303  * @caps: a #GstCaps
1304  * @structure: a potential #GstStructure subset of @caps
1305  *
1306  * Checks if @structure is a subset of @caps. See gst_caps_is_subset()
1307  * for more information.
1308  *
1309  * Returns: %TRUE if @structure is a subset of @caps
1310  */
1311 gboolean
1312 gst_caps_is_subset_structure (const GstCaps * caps,
1313     const GstStructure * structure)
1314 {
1315   GstStructure *s;
1316   gint i;
1317
1318   g_return_val_if_fail (caps != NULL, FALSE);
1319   g_return_val_if_fail (structure != NULL, FALSE);
1320
1321   if (CAPS_IS_ANY (caps))
1322     return TRUE;
1323   if (CAPS_IS_EMPTY (caps))
1324     return FALSE;
1325
1326   for (i = GST_CAPS_LEN (caps) - 1; i >= 0; i--) {
1327     s = gst_caps_get_structure_unchecked (caps, i);
1328     if (gst_structure_is_subset (structure, s)) {
1329       /* If we found a superset return TRUE */
1330       return TRUE;
1331     }
1332   }
1333
1334   return FALSE;
1335 }
1336
1337 /**
1338  * gst_caps_is_subset_structure_full:
1339  * @caps: a #GstCaps
1340  * @structure: a potential #GstStructure subset of @caps
1341  * @features: (allow-none): a #GstCapsFeatures for @structure
1342  *
1343  * Checks if @structure is a subset of @caps. See gst_caps_is_subset()
1344  * for more information.
1345  *
1346  * Returns: %TRUE if @structure is a subset of @caps
1347  *
1348  * Since: 1.2
1349  */
1350 gboolean
1351 gst_caps_is_subset_structure_full (const GstCaps * caps,
1352     const GstStructure * structure, const GstCapsFeatures * features)
1353 {
1354   GstStructure *s;
1355   GstCapsFeatures *f;
1356   gint i;
1357
1358   g_return_val_if_fail (caps != NULL, FALSE);
1359   g_return_val_if_fail (structure != NULL, FALSE);
1360
1361   if (CAPS_IS_ANY (caps))
1362     return TRUE;
1363   if (CAPS_IS_EMPTY (caps))
1364     return FALSE;
1365
1366   if (!features)
1367     features = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1368
1369   for (i = GST_CAPS_LEN (caps) - 1; i >= 0; i--) {
1370     s = gst_caps_get_structure_unchecked (caps, i);
1371     f = gst_caps_get_features_unchecked (caps, i);
1372     if (!f)
1373       f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1374     if ((!gst_caps_features_is_any (features) || gst_caps_features_is_any (f))
1375         && gst_caps_features_is_equal (features, f)
1376         && gst_structure_is_subset (structure, s)) {
1377       /* If we found a superset return TRUE */
1378       return TRUE;
1379     }
1380   }
1381
1382   return FALSE;
1383 }
1384
1385 /**
1386  * gst_caps_is_equal:
1387  * @caps1: a #GstCaps
1388  * @caps2: another #GstCaps
1389  *
1390  * Checks if the given caps represent the same set of caps.
1391  *
1392  * Returns: %TRUE if both caps are equal.
1393  */
1394 gboolean
1395 gst_caps_is_equal (const GstCaps * caps1, const GstCaps * caps2)
1396 {
1397   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
1398   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
1399
1400   if (G_UNLIKELY (caps1 == caps2))
1401     return TRUE;
1402
1403   if (G_UNLIKELY (gst_caps_is_fixed (caps1) && gst_caps_is_fixed (caps2)))
1404     return gst_caps_is_equal_fixed (caps1, caps2);
1405
1406   return gst_caps_is_subset (caps1, caps2) && gst_caps_is_subset (caps2, caps1);
1407 }
1408
1409 /**
1410  * gst_caps_is_strictly_equal:
1411  * @caps1: a #GstCaps
1412  * @caps2: another #GstCaps
1413  *
1414  * Checks if the given caps are exactly the same set of caps.
1415  *
1416  * Returns: %TRUE if both caps are strictly equal.
1417  */
1418 gboolean
1419 gst_caps_is_strictly_equal (const GstCaps * caps1, const GstCaps * caps2)
1420 {
1421   int i;
1422   GstStructure *s1, *s2;
1423   GstCapsFeatures *f1, *f2;
1424
1425   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
1426   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
1427
1428   if (G_UNLIKELY (caps1 == caps2))
1429     return TRUE;
1430
1431   if (GST_CAPS_LEN (caps1) != GST_CAPS_LEN (caps2))
1432     return FALSE;
1433
1434   for (i = 0; i < GST_CAPS_LEN (caps1); i++) {
1435     s1 = gst_caps_get_structure_unchecked (caps1, i);
1436     f1 = gst_caps_get_features_unchecked (caps1, i);
1437     if (!f1)
1438       f1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1439     s2 = gst_caps_get_structure_unchecked (caps2, i);
1440     f2 = gst_caps_get_features_unchecked (caps2, i);
1441     if (!f2)
1442       f2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1443
1444     if (gst_caps_features_is_any (f1) != gst_caps_features_is_any (f2) ||
1445         !gst_caps_features_is_equal (f1, f2) ||
1446         !gst_structure_is_equal (s1, s2))
1447       return FALSE;
1448   }
1449
1450   return TRUE;
1451 }
1452
1453 /* intersect operation */
1454
1455 /**
1456  * gst_caps_can_intersect:
1457  * @caps1: a #GstCaps to intersect
1458  * @caps2: a #GstCaps to intersect
1459  *
1460  * Tries intersecting @caps1 and @caps2 and reports whether the result would not
1461  * be empty
1462  *
1463  * Returns: %TRUE if intersection would be not empty
1464  */
1465 gboolean
1466 gst_caps_can_intersect (const GstCaps * caps1, const GstCaps * caps2)
1467 {
1468   guint64 i;                    /* index can be up to 2 * G_MAX_UINT */
1469   guint j, k, len1, len2;
1470   GstStructure *struct1;
1471   GstStructure *struct2;
1472   GstCapsFeatures *features1;
1473   GstCapsFeatures *features2;
1474
1475   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
1476   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
1477
1478   /* caps are exactly the same pointers */
1479   if (G_UNLIKELY (caps1 == caps2))
1480     return TRUE;
1481
1482   /* empty caps on either side, return empty */
1483   if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
1484     return FALSE;
1485
1486   /* one of the caps is any */
1487   if (G_UNLIKELY (CAPS_IS_ANY (caps1) || CAPS_IS_ANY (caps2)))
1488     return TRUE;
1489
1490   /* run zigzag on top line then right line, this preserves the caps order
1491    * much better than a simple loop.
1492    *
1493    * This algorithm zigzags over the caps structures as demonstrated in
1494    * the following matrix:
1495    *
1496    *          caps1                              0  1  2  3
1497    *       +-------------     total distance:  +-------------
1498    *       | 1  2  4  7                      0 | 0  1  2  3
1499    * caps2 | 3  5  8 10                      1 | 1  2  3  4
1500    *       | 6  9 11 12                      2 | 2  3  4  5
1501    *
1502    * First we iterate over the caps1 structures (top line) intersecting
1503    * the structures diagonally down, then we iterate over the caps2
1504    * structures. The result is that the intersections are ordered based on the
1505    * sum of the indexes in the list.
1506    */
1507   len1 = GST_CAPS_LEN (caps1);
1508   len2 = GST_CAPS_LEN (caps2);
1509   for (i = 0; i < len1 + len2 - 1; i++) {
1510     /* superset index goes from 0 to superset->structs->len-1 */
1511     j = MIN (i, len1 - 1);
1512     /* subset index stays 0 until i reaches superset->structs->len, then it
1513      * counts up from 1 to subset->structs->len - 1 */
1514     k = (i > j) ? (i - j) : 0;  /* MAX (0, i - j) */
1515     /* now run the diagonal line, end condition is the left or bottom
1516      * border */
1517     while (k < len2) {
1518       struct1 = gst_caps_get_structure_unchecked (caps1, j);
1519       features1 = gst_caps_get_features_unchecked (caps1, j);
1520       if (!features1)
1521         features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1522       struct2 = gst_caps_get_structure_unchecked (caps2, k);
1523       features2 = gst_caps_get_features_unchecked (caps2, k);
1524       if (!features2)
1525         features2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1526       if (gst_caps_features_is_equal (features1, features2) &&
1527           gst_structure_can_intersect (struct1, struct2)) {
1528         return TRUE;
1529       }
1530       /* move down left */
1531       k++;
1532       if (G_UNLIKELY (j == 0))
1533         break;                  /* so we don't roll back to G_MAXUINT */
1534       j--;
1535     }
1536   }
1537
1538   return FALSE;
1539 }
1540
1541 static GstCaps *
1542 gst_caps_intersect_zig_zag (GstCaps * caps1, GstCaps * caps2)
1543 {
1544   guint64 i;                    /* index can be up to 2 * G_MAX_UINT */
1545   guint j, k, len1, len2;
1546   GstStructure *struct1;
1547   GstStructure *struct2;
1548   GstCapsFeatures *features1;
1549   GstCapsFeatures *features2;
1550   GstCaps *dest;
1551   GstStructure *istruct;
1552
1553   /* caps are exactly the same pointers, just copy one caps */
1554   if (G_UNLIKELY (caps1 == caps2))
1555     return gst_caps_ref (caps1);
1556
1557   /* empty caps on either side, return empty */
1558   if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
1559     return gst_caps_ref (GST_CAPS_NONE);
1560
1561   /* one of the caps is any, just copy the other caps */
1562   if (G_UNLIKELY (CAPS_IS_ANY (caps1)))
1563     return gst_caps_ref (caps2);
1564
1565   if (G_UNLIKELY (CAPS_IS_ANY (caps2)))
1566     return gst_caps_ref (caps1);
1567
1568   dest = gst_caps_new_empty ();
1569   /* run zigzag on top line then right line, this preserves the caps order
1570    * much better than a simple loop.
1571    *
1572    * This algorithm zigzags over the caps structures as demonstrated in
1573    * the following matrix:
1574    *
1575    *          caps1
1576    *       +-------------
1577    *       | 1  2  4  7
1578    * caps2 | 3  5  8 10
1579    *       | 6  9 11 12
1580    *
1581    * First we iterate over the caps1 structures (top line) intersecting
1582    * the structures diagonally down, then we iterate over the caps2
1583    * structures.
1584    */
1585   len1 = GST_CAPS_LEN (caps1);
1586   len2 = GST_CAPS_LEN (caps2);
1587   for (i = 0; i < len1 + len2 - 1; i++) {
1588     /* caps1 index goes from 0 to GST_CAPS_LEN (caps1)-1 */
1589     j = MIN (i, len1 - 1);
1590     /* caps2 index stays 0 until i reaches GST_CAPS_LEN (caps1), then it counts
1591      * up from 1 to GST_CAPS_LEN (caps2) - 1 */
1592     k = (i > j) ? (i - j) : 0;  /* MAX (0, i - j) */
1593     /* now run the diagonal line, end condition is the left or bottom
1594      * border */
1595     while (k < len2) {
1596       struct1 = gst_caps_get_structure_unchecked (caps1, j);
1597       features1 = gst_caps_get_features_unchecked (caps1, j);
1598       if (!features1)
1599         features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1600       struct2 = gst_caps_get_structure_unchecked (caps2, k);
1601       features2 = gst_caps_get_features_unchecked (caps2, k);
1602       if (!features2)
1603         features2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1604       if (gst_caps_features_is_equal (features1, features2)) {
1605         istruct = gst_structure_intersect (struct1, struct2);
1606         if (istruct) {
1607           if (gst_caps_features_is_any (features1))
1608             dest =
1609                 gst_caps_merge_structure_full (dest, istruct,
1610                 gst_caps_features_copy_conditional (features2));
1611           else
1612             dest =
1613                 gst_caps_merge_structure_full (dest, istruct,
1614                 gst_caps_features_copy_conditional (features1));
1615         }
1616       }
1617       /* move down left */
1618       k++;
1619       if (G_UNLIKELY (j == 0))
1620         break;                  /* so we don't roll back to G_MAXUINT */
1621       j--;
1622     }
1623   }
1624   return dest;
1625 }
1626
1627 /**
1628  * gst_caps_intersect_first:
1629  * @caps1: a #GstCaps to intersect
1630  * @caps2: a #GstCaps to intersect
1631  *
1632  * Creates a new #GstCaps that contains all the formats that are common
1633  * to both @caps1 and @caps2.
1634  *
1635  * Unlike @gst_caps_intersect, the returned caps will be ordered in a similar
1636  * fashion as @caps1.
1637  *
1638  * Returns: (transfer full): the new #GstCaps
1639  */
1640 static GstCaps *
1641 gst_caps_intersect_first (GstCaps * caps1, GstCaps * caps2)
1642 {
1643   guint i;
1644   guint j, len1, len2;
1645   GstStructure *struct1;
1646   GstStructure *struct2;
1647   GstCapsFeatures *features1;
1648   GstCapsFeatures *features2;
1649   GstCaps *dest;
1650   GstStructure *istruct;
1651
1652   /* caps are exactly the same pointers, just copy one caps */
1653   if (G_UNLIKELY (caps1 == caps2))
1654     return gst_caps_ref (caps1);
1655
1656   /* empty caps on either side, return empty */
1657   if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
1658     return gst_caps_ref (GST_CAPS_NONE);
1659
1660   /* one of the caps is any, just copy the other caps */
1661   if (G_UNLIKELY (CAPS_IS_ANY (caps1)))
1662     return gst_caps_ref (caps2);
1663
1664   if (G_UNLIKELY (CAPS_IS_ANY (caps2)))
1665     return gst_caps_ref (caps1);
1666
1667   dest = gst_caps_new_empty ();
1668   len1 = GST_CAPS_LEN (caps1);
1669   len2 = GST_CAPS_LEN (caps2);
1670   for (i = 0; i < len1; i++) {
1671     struct1 = gst_caps_get_structure_unchecked (caps1, i);
1672     features1 = gst_caps_get_features_unchecked (caps1, i);
1673     if (!features1)
1674       features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1675     for (j = 0; j < len2; j++) {
1676       struct2 = gst_caps_get_structure_unchecked (caps2, j);
1677       features2 = gst_caps_get_features_unchecked (caps2, j);
1678       if (!features2)
1679         features2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1680       if (gst_caps_features_is_equal (features1, features2)) {
1681         istruct = gst_structure_intersect (struct1, struct2);
1682         if (istruct) {
1683           if (gst_caps_features_is_any (features1))
1684             dest =
1685                 gst_caps_merge_structure_full (dest, istruct,
1686                 gst_caps_features_copy_conditional (features2));
1687           else
1688             dest =
1689                 gst_caps_merge_structure_full (dest, istruct,
1690                 gst_caps_features_copy_conditional (features1));
1691         }
1692       }
1693     }
1694   }
1695
1696   return dest;
1697 }
1698
1699 /**
1700  * gst_caps_intersect_full:
1701  * @caps1: a #GstCaps to intersect
1702  * @caps2: a #GstCaps to intersect
1703  * @mode: The intersection algorithm/mode to use
1704  *
1705  * Creates a new #GstCaps that contains all the formats that are common
1706  * to both @caps1 and @caps2, the order is defined by the #GstCapsIntersectMode
1707  * used.
1708  *
1709  * Returns: (transfer full): the new #GstCaps
1710  */
1711 GstCaps *
1712 gst_caps_intersect_full (GstCaps * caps1, GstCaps * caps2,
1713     GstCapsIntersectMode mode)
1714 {
1715   g_return_val_if_fail (GST_IS_CAPS (caps1), NULL);
1716   g_return_val_if_fail (GST_IS_CAPS (caps2), NULL);
1717
1718   switch (mode) {
1719     case GST_CAPS_INTERSECT_FIRST:
1720       return gst_caps_intersect_first (caps1, caps2);
1721     default:
1722       g_warning ("Unknown caps intersect mode: %d", mode);
1723       /* fallthrough */
1724     case GST_CAPS_INTERSECT_ZIG_ZAG:
1725       return gst_caps_intersect_zig_zag (caps1, caps2);
1726   }
1727 }
1728
1729 /**
1730  * gst_caps_intersect:
1731  * @caps1: a #GstCaps to intersect
1732  * @caps2: a #GstCaps to intersect
1733  *
1734  * Creates a new #GstCaps that contains all the formats that are common
1735  * to both @caps1 and @caps2. Defaults to %GST_CAPS_INTERSECT_ZIG_ZAG mode.
1736  *
1737  * Returns: (transfer full): the new #GstCaps
1738  */
1739 GstCaps *
1740 gst_caps_intersect (GstCaps * caps1, GstCaps * caps2)
1741 {
1742   return gst_caps_intersect_full (caps1, caps2, GST_CAPS_INTERSECT_ZIG_ZAG);
1743 }
1744
1745 /* subtract operation */
1746
1747 typedef struct
1748 {
1749   const GstStructure *subtract_from;
1750   GSList *put_into;
1751 } SubtractionEntry;
1752
1753 static gboolean
1754 gst_caps_structure_subtract_field (GQuark field_id, const GValue * value,
1755     gpointer user_data)
1756 {
1757   SubtractionEntry *e = user_data;
1758   GValue subtraction = { 0, };
1759   const GValue *other;
1760   GstStructure *structure;
1761
1762   other = gst_structure_id_get_value (e->subtract_from, field_id);
1763
1764   if (!other) {
1765     return FALSE;
1766   }
1767
1768   if (!gst_value_subtract (&subtraction, other, value))
1769     return TRUE;
1770
1771   if (gst_value_compare (&subtraction, other) == GST_VALUE_EQUAL) {
1772     g_value_unset (&subtraction);
1773     return FALSE;
1774   } else {
1775     structure = gst_structure_copy (e->subtract_from);
1776     gst_structure_id_take_value (structure, field_id, &subtraction);
1777     e->put_into = g_slist_prepend (e->put_into, structure);
1778     return TRUE;
1779   }
1780 }
1781
1782 static gboolean
1783 gst_caps_structure_subtract (GSList ** into, const GstStructure * minuend,
1784     const GstStructure * subtrahend)
1785 {
1786   SubtractionEntry e;
1787   gboolean ret;
1788
1789   e.subtract_from = minuend;
1790   e.put_into = NULL;
1791   ret = gst_structure_foreach ((GstStructure *) subtrahend,
1792       gst_caps_structure_subtract_field, &e);
1793
1794   if (ret) {
1795     *into = e.put_into;
1796   } else {
1797     GSList *walk;
1798
1799     for (walk = e.put_into; walk; walk = g_slist_next (walk)) {
1800       gst_structure_free (walk->data);
1801     }
1802     g_slist_free (e.put_into);
1803   }
1804
1805   return ret;
1806 }
1807
1808 /**
1809  * gst_caps_subtract:
1810  * @minuend: #GstCaps to subtract from
1811  * @subtrahend: #GstCaps to subtract
1812  *
1813  * Subtracts the @subtrahend from the @minuend.
1814  * > This function does not work reliably if optional properties for caps
1815  * > are included on one caps and omitted on the other.
1816  *
1817  * Returns: (transfer full): the resulting caps
1818  */
1819 GstCaps *
1820 gst_caps_subtract (GstCaps * minuend, GstCaps * subtrahend)
1821 {
1822   guint i, j, sublen;
1823   GstStructure *min;
1824   GstStructure *sub;
1825   GstCapsFeatures *min_f, *sub_f;
1826   GstCaps *dest = NULL, *src;
1827
1828   g_return_val_if_fail (minuend != NULL, NULL);
1829   g_return_val_if_fail (subtrahend != NULL, NULL);
1830
1831   if (CAPS_IS_EMPTY (minuend) || CAPS_IS_ANY (subtrahend)) {
1832     return gst_caps_new_empty ();
1833   }
1834
1835   if (CAPS_IS_EMPTY_SIMPLE (subtrahend))
1836     return gst_caps_ref (minuend);
1837
1838   /* FIXME: Do we want this here or above?
1839      The reason we need this is that there is no definition about what
1840      ANY means for specific types, so it's not possible to reduce ANY partially
1841      You can only remove everything or nothing and that is done above.
1842      Note: there's a test that checks this behaviour. */
1843
1844   g_return_val_if_fail (!CAPS_IS_ANY (minuend), NULL);
1845   sublen = GST_CAPS_LEN (subtrahend);
1846   g_assert (sublen > 0);
1847
1848   src = _gst_caps_copy (minuend);
1849   for (i = 0; i < sublen; i++) {
1850     guint srclen;
1851
1852     sub = gst_caps_get_structure_unchecked (subtrahend, i);
1853     sub_f = gst_caps_get_features_unchecked (subtrahend, i);
1854     if (!sub_f)
1855       sub_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1856     if (dest) {
1857       gst_caps_unref (src);
1858       src = dest;
1859     }
1860     dest = gst_caps_new_empty ();
1861     srclen = GST_CAPS_LEN (src);
1862     for (j = 0; j < srclen; j++) {
1863       min = gst_caps_get_structure_unchecked (src, j);
1864       min_f = gst_caps_get_features_unchecked (src, j);
1865       if (!min_f)
1866         min_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1867
1868       /* Same reason as above for ANY caps */
1869       g_return_val_if_fail (!gst_caps_features_is_any (min_f), NULL);
1870
1871       if (gst_structure_get_name_id (min) == gst_structure_get_name_id (sub) &&
1872           gst_caps_features_is_equal (min_f, sub_f)) {
1873         GSList *list;
1874
1875         if (gst_caps_structure_subtract (&list, min, sub)) {
1876           GSList *walk;
1877
1878           for (walk = list; walk; walk = g_slist_next (walk)) {
1879             gst_caps_append_structure_unchecked (dest,
1880                 (GstStructure *) walk->data,
1881                 gst_caps_features_copy_conditional (min_f));
1882           }
1883           g_slist_free (list);
1884         } else {
1885           gst_caps_append_structure_unchecked (dest, gst_structure_copy (min),
1886               gst_caps_features_copy_conditional (min_f));
1887         }
1888       } else {
1889         gst_caps_append_structure_unchecked (dest, gst_structure_copy (min),
1890             gst_caps_features_copy_conditional (min_f));
1891       }
1892     }
1893
1894     if (CAPS_IS_EMPTY_SIMPLE (dest)) {
1895       gst_caps_unref (src);
1896       return dest;
1897     }
1898   }
1899
1900   gst_caps_unref (src);
1901   dest = gst_caps_simplify (dest);
1902
1903   return dest;
1904 }
1905
1906 /* normalize/simplify operations */
1907
1908 typedef struct _NormalizeForeach
1909 {
1910   GstCaps *caps;
1911   GstStructure *structure;
1912   GstCapsFeatures *features;
1913 } NormalizeForeach;
1914
1915 static gboolean
1916 gst_caps_normalize_foreach (GQuark field_id, const GValue * value, gpointer ptr)
1917 {
1918   NormalizeForeach *nf = (NormalizeForeach *) ptr;
1919   GValue val = { 0 };
1920   guint i;
1921
1922   if (G_VALUE_TYPE (value) == GST_TYPE_LIST) {
1923     guint len = gst_value_list_get_size (value);
1924
1925     for (i = 1; i < len; i++) {
1926       const GValue *v = gst_value_list_get_value (value, i);
1927       GstStructure *structure = gst_structure_copy (nf->structure);
1928
1929       gst_structure_id_set_value (structure, field_id, v);
1930       gst_caps_append_structure_unchecked (nf->caps, structure,
1931           gst_caps_features_copy_conditional (nf->features));
1932     }
1933
1934     gst_value_init_and_copy (&val, gst_value_list_get_value (value, 0));
1935     gst_structure_id_take_value (nf->structure, field_id, &val);
1936     return FALSE;
1937   }
1938
1939   return TRUE;
1940 }
1941
1942 /**
1943  * gst_caps_normalize:
1944  * @caps: (transfer full): a #GstCaps to normalize
1945  *
1946  * Returns a #GstCaps that represents the same set of formats as
1947  * @caps, but contains no lists.  Each list is expanded into separate
1948  * @GstStructures.
1949  *
1950  * This function takes ownership of @caps and will call gst_caps_make_writable()
1951  * on it so you must not use @caps afterwards unless you keep an additional
1952  * reference to it with gst_caps_ref().
1953  *
1954  * Returns: (transfer full): the normalized #GstCaps
1955  */
1956 GstCaps *
1957 gst_caps_normalize (GstCaps * caps)
1958 {
1959   NormalizeForeach nf;
1960   guint i;
1961
1962   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
1963
1964   caps = gst_caps_make_writable (caps);
1965   nf.caps = caps;
1966
1967   for (i = 0; i < gst_caps_get_size (nf.caps); i++) {
1968     nf.structure = gst_caps_get_structure_unchecked (nf.caps, i);
1969     nf.features = gst_caps_get_features_unchecked (nf.caps, i);
1970     while (!gst_structure_foreach (nf.structure,
1971             gst_caps_normalize_foreach, &nf));
1972   }
1973
1974   return nf.caps;
1975 }
1976
1977 static gint
1978 gst_caps_compare_structures (gconstpointer one, gconstpointer two)
1979 {
1980   gint ret;
1981   const GstStructure *struct1 = ((const GstCapsArrayElement *) one)->structure;
1982   const GstStructure *struct2 = ((const GstCapsArrayElement *) two)->structure;
1983
1984   /* FIXME: this orders alphabetically, but ordering the quarks might be faster
1985      So what's the best way? */
1986   ret = strcmp (gst_structure_get_name (struct1),
1987       gst_structure_get_name (struct2));
1988
1989   if (ret)
1990     return ret;
1991
1992   return gst_structure_n_fields (struct2) - gst_structure_n_fields (struct1);
1993 }
1994
1995 typedef struct
1996 {
1997   GQuark name;
1998   GValue value;
1999   GstStructure *compare;
2000 } UnionField;
2001
2002 static gboolean
2003 gst_caps_structure_figure_out_union (GQuark field_id, const GValue * value,
2004     gpointer user_data)
2005 {
2006   UnionField *u = user_data;
2007   const GValue *val = gst_structure_id_get_value (u->compare, field_id);
2008
2009   if (!val) {
2010     if (u->name)
2011       g_value_unset (&u->value);
2012     return FALSE;
2013   }
2014
2015   if (gst_value_compare (val, value) == GST_VALUE_EQUAL)
2016     return TRUE;
2017
2018   if (u->name) {
2019     g_value_unset (&u->value);
2020     return FALSE;
2021   }
2022
2023   u->name = field_id;
2024   gst_value_union (&u->value, val, value);
2025
2026   return TRUE;
2027 }
2028
2029 static gboolean
2030 gst_caps_structure_simplify (GstStructure ** result,
2031     GstStructure * simplify, GstStructure * compare)
2032 {
2033   GSList *list;
2034   UnionField field = { 0, {0,}, NULL };
2035
2036   /* try to subtract to get a real subset */
2037   if (gst_caps_structure_subtract (&list, simplify, compare)) {
2038     if (list == NULL) {         /* no result */
2039       *result = NULL;
2040       return TRUE;
2041     } else if (list->next == NULL) {    /* one result */
2042       *result = list->data;
2043       g_slist_free (list);
2044       return TRUE;
2045     } else {                    /* multiple results */
2046       g_slist_foreach (list, (GFunc) gst_structure_free, NULL);
2047       g_slist_free (list);
2048       list = NULL;
2049     }
2050   }
2051
2052   /* try to union both structs */
2053   field.compare = compare;
2054   if (gst_structure_foreach (simplify,
2055           gst_caps_structure_figure_out_union, &field)) {
2056     gboolean ret = FALSE;
2057
2058     /* now we know all of simplify's fields are the same in compare
2059      * but at most one field: field.name */
2060     if (G_IS_VALUE (&field.value)) {
2061       if (gst_structure_n_fields (simplify) == gst_structure_n_fields (compare)) {
2062         gst_structure_id_take_value (compare, field.name, &field.value);
2063         *result = NULL;
2064         ret = TRUE;
2065       } else {
2066         g_value_unset (&field.value);
2067       }
2068     } else
2069         if (gst_structure_n_fields (simplify) <=
2070         gst_structure_n_fields (compare)) {
2071       /* compare is just more specific, will be optimized away later */
2072       /* FIXME: do this here? */
2073       GST_LOG ("found a case that will be optimized later.");
2074     } else {
2075       gchar *one = gst_structure_to_string (simplify);
2076       gchar *two = gst_structure_to_string (compare);
2077
2078       GST_ERROR
2079           ("caps mismatch: structures %s and %s claim to be possible to unify, but aren't",
2080           one, two);
2081       g_free (one);
2082       g_free (two);
2083     }
2084     return ret;
2085   }
2086
2087   return FALSE;
2088 }
2089
2090 static void
2091 gst_caps_switch_structures (GstCaps * caps, GstStructure * old,
2092     GstStructure * new, gint i)
2093 {
2094   gst_structure_set_parent_refcount (old, NULL);
2095   gst_structure_free (old);
2096   gst_structure_set_parent_refcount (new, &GST_CAPS_REFCOUNT (caps));
2097   g_array_index (GST_CAPS_ARRAY (caps), GstCapsArrayElement, i).structure = new;
2098 }
2099
2100 /**
2101  * gst_caps_simplify:
2102  * @caps: (transfer full): a #GstCaps to simplify
2103  *
2104  * Converts the given @caps into a representation that represents the
2105  * same set of formats, but in a simpler form.  Component structures that are
2106  * identical are merged.  Component structures that have values that can be
2107  * merged are also merged.
2108  *
2109  * This function takes ownership of @caps and will call gst_caps_make_writable()
2110  * on it if necessary, so you must not use @caps afterwards unless you keep an
2111  * additional reference to it with gst_caps_ref().
2112  *
2113  * This method does not preserve the original order of @caps.
2114  *
2115  * Returns: (transfer full): The simplified caps.
2116  */
2117 GstCaps *
2118 gst_caps_simplify (GstCaps * caps)
2119 {
2120   GstStructure *simplify, *compare, *result = NULL;
2121   GstCapsFeatures *simplify_f, *compare_f;
2122   gint i, j, start;
2123
2124   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
2125
2126   start = GST_CAPS_LEN (caps) - 1;
2127   /* one caps, already as simple as can be */
2128   if (start == 0)
2129     return caps;
2130
2131   caps = gst_caps_make_writable (caps);
2132
2133   g_array_sort (GST_CAPS_ARRAY (caps), gst_caps_compare_structures);
2134
2135   for (i = start; i >= 0; i--) {
2136     simplify = gst_caps_get_structure_unchecked (caps, i);
2137     simplify_f = gst_caps_get_features_unchecked (caps, i);
2138     if (!simplify_f)
2139       simplify_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
2140     compare = gst_caps_get_structure_unchecked (caps, start);
2141     compare_f = gst_caps_get_features_unchecked (caps, start);
2142     if (!compare_f)
2143       compare_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
2144     if (gst_structure_get_name_id (simplify) !=
2145         gst_structure_get_name_id (compare) ||
2146         !gst_caps_features_is_equal (simplify_f, compare_f))
2147       start = i;
2148     for (j = start; j >= 0; j--) {
2149       if (j == i)
2150         continue;
2151       compare = gst_caps_get_structure_unchecked (caps, j);
2152       compare_f = gst_caps_get_features_unchecked (caps, j);
2153       if (!compare_f)
2154         compare_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
2155       if (gst_structure_get_name_id (simplify) !=
2156           gst_structure_get_name_id (compare) ||
2157           !gst_caps_features_is_equal (simplify_f, compare_f)) {
2158         break;
2159       }
2160       if (gst_caps_structure_simplify (&result, simplify, compare)) {
2161         if (result) {
2162           gst_caps_switch_structures (caps, simplify, result, i);
2163           simplify = result;
2164         } else {
2165           gst_caps_remove_structure (caps, i);
2166           start--;
2167           break;
2168         }
2169       }
2170     }
2171   }
2172   return caps;
2173 }
2174
2175 /**
2176  * gst_caps_fixate:
2177  * @caps: (transfer full): a #GstCaps to fixate
2178  *
2179  * Modifies the given @caps into a representation with only fixed
2180  * values. First the caps will be truncated and then the first structure will be
2181  * fixated with gst_structure_fixate().
2182  *
2183  * This function takes ownership of @caps and will call gst_caps_make_writable()
2184  * on it so you must not use @caps afterwards unless you keep an additional
2185  * reference to it with gst_caps_ref().
2186  *
2187  * Returns: (transfer full): the fixated caps
2188  */
2189 GstCaps *
2190 gst_caps_fixate (GstCaps * caps)
2191 {
2192   GstStructure *s;
2193   GstCapsFeatures *f;
2194
2195   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
2196
2197   /* default fixation */
2198   caps = gst_caps_truncate (caps);
2199   caps = gst_caps_make_writable (caps);
2200   s = gst_caps_get_structure (caps, 0);
2201   gst_structure_fixate (s);
2202
2203   /* Set features to sysmem if they're still ANY */
2204   f = gst_caps_get_features_unchecked (caps, 0);
2205   if (f && gst_caps_features_is_any (f)) {
2206     f = gst_caps_features_new_empty ();
2207     gst_caps_set_features (caps, 0, f);
2208   }
2209
2210   return caps;
2211 }
2212
2213 /* utility */
2214
2215 /**
2216  * gst_caps_to_string:
2217  * @caps: a #GstCaps
2218  *
2219  * Converts @caps to a string representation.  This string representation
2220  * can be converted back to a #GstCaps by gst_caps_from_string().
2221  *
2222  * For debugging purposes its easier to do something like this:
2223  * |[<!-- language="C" -->
2224  * GST_LOG ("caps are %" GST_PTR_FORMAT, caps);
2225  * ]|
2226  * This prints the caps in human readable form.
2227  *
2228  * The current implementation of serialization will lead to unexpected results
2229  * when there are nested #GstCaps / #GstStructure deeper than one level.
2230  *
2231  * Returns: (transfer full): a newly allocated string representing @caps.
2232  */
2233 gchar *
2234 gst_caps_to_string (const GstCaps * caps)
2235 {
2236   guint i, slen, clen;
2237   GString *s;
2238
2239   /* NOTE:  This function is potentially called by the debug system,
2240    * so any calls to gst_log() (and GST_DEBUG(), GST_LOG(), etc.)
2241    * should be careful to avoid recursion.  This includes any functions
2242    * called by gst_caps_to_string.  In particular, calls should
2243    * not use the GST_PTR_FORMAT extension.  */
2244
2245   if (caps == NULL) {
2246     return g_strdup ("NULL");
2247   }
2248   if (CAPS_IS_ANY (caps)) {
2249     return g_strdup ("ANY");
2250   }
2251   if (CAPS_IS_EMPTY_SIMPLE (caps)) {
2252     return g_strdup ("EMPTY");
2253   }
2254
2255   /* estimate a rough string length to avoid unnecessary reallocs in GString */
2256   slen = 0;
2257   clen = GST_CAPS_LEN (caps);
2258   for (i = 0; i < clen; i++) {
2259     GstCapsFeatures *f;
2260
2261     slen +=
2262         STRUCTURE_ESTIMATED_STRING_LEN (gst_caps_get_structure_unchecked
2263         (caps, i));
2264     f = gst_caps_get_features_unchecked (caps, i);
2265     if (f)
2266       slen += FEATURES_ESTIMATED_STRING_LEN (f);
2267   }
2268
2269   s = g_string_sized_new (slen);
2270   for (i = 0; i < clen; i++) {
2271     GstStructure *structure;
2272     GstCapsFeatures *features;
2273
2274     if (i > 0) {
2275       /* ';' is now added by gst_structure_to_string */
2276       g_string_append_c (s, ' ');
2277     }
2278
2279     structure = gst_caps_get_structure_unchecked (caps, i);
2280     features = gst_caps_get_features_unchecked (caps, i);
2281
2282     g_string_append (s, gst_structure_get_name (structure));
2283     if (features && (gst_caps_features_is_any (features)
2284             || !gst_caps_features_is_equal (features,
2285                 GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY))) {
2286       g_string_append_c (s, '(');
2287       priv_gst_caps_features_append_to_gstring (features, s);
2288       g_string_append_c (s, ')');
2289     }
2290     priv_gst_structure_append_to_gstring (structure, s);
2291   }
2292   if (s->len && s->str[s->len - 1] == ';') {
2293     /* remove latest ';' */
2294     s->str[--s->len] = '\0';
2295   }
2296   return g_string_free (s, FALSE);
2297 }
2298
2299 static gboolean
2300 gst_caps_from_string_inplace (GstCaps * caps, const gchar * string)
2301 {
2302   GstStructure *structure;
2303   gchar *s, *copy, *end, *next, save;
2304
2305   if (strcmp ("ANY", string) == 0) {
2306     GST_CAPS_FLAGS (caps) = GST_CAPS_FLAG_ANY;
2307     return TRUE;
2308   }
2309
2310   if (strcmp ("EMPTY", string) == 0 || strcmp ("NONE", string) == 0) {
2311     return TRUE;
2312   }
2313
2314   copy = s = g_strdup (string);
2315   do {
2316     GstCapsFeatures *features = NULL;
2317
2318     while (g_ascii_isspace (*s))
2319       s++;
2320     if (*s == '\0') {
2321       break;
2322     }
2323
2324     if (!priv_gst_structure_parse_name (s, &s, &end, &next)) {
2325       g_free (copy);
2326       return FALSE;
2327     }
2328
2329     save = *end;
2330     *end = '\0';
2331     structure = gst_structure_new_empty (s);
2332     *end = save;
2333
2334     if (structure == NULL) {
2335       g_free (copy);
2336       return FALSE;
2337     }
2338
2339     s = next;
2340
2341     if (*s == '\0') {
2342       goto append;
2343     }
2344
2345     if (*s == '(') {
2346       s++;
2347       end = s;
2348
2349       while (TRUE) {
2350         if (*end == '\0') {
2351           break;
2352         } else if (*end == ')') {
2353           break;
2354         } else {
2355           end++;
2356         }
2357       }
2358
2359       save = *end;
2360       *end = '\0';
2361       features = gst_caps_features_from_string (s);
2362       if (!features) {
2363         gst_structure_free (structure);
2364         g_free (copy);
2365         return FALSE;
2366       }
2367       *end = save;
2368       s = end;
2369       if (save == ')')
2370         s++;
2371     }
2372
2373     if (*s == '\0') {
2374       goto append;
2375     }
2376
2377     if (!priv_gst_structure_parse_fields (s, &s, structure)) {
2378       gst_structure_free (structure);
2379       if (features)
2380         gst_caps_features_free (features);
2381       g_free (copy);
2382       return FALSE;
2383     }
2384
2385   append:
2386     gst_caps_append_structure_unchecked (caps, structure, features);
2387     features = NULL;
2388     if (*s == '\0')
2389       break;
2390   } while (TRUE);
2391
2392   g_free (copy);
2393
2394   return TRUE;
2395 }
2396
2397 /**
2398  * gst_caps_from_string:
2399  * @string: a string to convert to #GstCaps
2400  *
2401  * Converts @caps from a string representation.
2402  *
2403  * The current implementation of serialization will lead to unexpected results
2404  * when there are nested #GstCaps / #GstStructure deeper than one level.
2405  *
2406  * Returns: (transfer full) (nullable): a newly allocated #GstCaps
2407  */
2408 GstCaps *
2409 gst_caps_from_string (const gchar * string)
2410 {
2411   GstCaps *caps;
2412
2413   g_return_val_if_fail (string, FALSE);
2414
2415   caps = gst_caps_new_empty ();
2416   if (gst_caps_from_string_inplace (caps, string)) {
2417     return caps;
2418   } else {
2419     gst_caps_unref (caps);
2420     return NULL;
2421   }
2422 }
2423
2424 static void
2425 gst_caps_transform_to_string (const GValue * src_value, GValue * dest_value)
2426 {
2427   g_return_if_fail (G_IS_VALUE (src_value));
2428   g_return_if_fail (G_IS_VALUE (dest_value));
2429   g_return_if_fail (G_VALUE_HOLDS (src_value, GST_TYPE_CAPS));
2430   g_return_if_fail (G_VALUE_HOLDS (dest_value, G_TYPE_STRING)
2431       || G_VALUE_HOLDS (dest_value, G_TYPE_POINTER));
2432
2433   g_value_take_string (dest_value,
2434       gst_caps_to_string (gst_value_get_caps (src_value)));
2435 }
2436
2437 /**
2438  * gst_caps_foreach:
2439  * @caps: a #GstCaps
2440  * @func: (scope call): a function to call for each field
2441  * @user_data: (closure): private data
2442  *
2443  * Calls the provided function once for each structure and caps feature in the
2444  * #GstCaps. The function must not modify the fields.
2445  * Also see gst_caps_map_in_place() and gst_caps_filter_and_map_in_place().
2446  *
2447  * Returns: %TRUE if the supplied function returns %TRUE for each call,
2448  * %FALSE otherwise.
2449  *
2450  * Since: 1.6
2451  */
2452 gboolean
2453 gst_caps_foreach (const GstCaps * caps, GstCapsForeachFunc func,
2454     gpointer user_data)
2455 {
2456   guint i, n;
2457   GstCapsFeatures *features;
2458   GstStructure *structure;
2459   gboolean ret;
2460
2461   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
2462   g_return_val_if_fail (func != NULL, FALSE);
2463
2464   n = GST_CAPS_LEN (caps);
2465
2466   for (i = 0; i < n; i++) {
2467     features = gst_caps_get_features_unchecked (caps, i);
2468     structure = gst_caps_get_structure_unchecked (caps, i);
2469
2470     ret = func (features, structure, user_data);
2471     if (G_UNLIKELY (!ret))
2472       return FALSE;
2473   }
2474
2475   return TRUE;
2476 }
2477
2478 /**
2479  * gst_caps_map_in_place:
2480  * @caps: a #GstCaps
2481  * @func: (scope call): a function to call for each field
2482  * @user_data: (closure): private data
2483  *
2484  * Calls the provided function once for each structure and caps feature in the
2485  * #GstCaps. In contrast to gst_caps_foreach(), the function may modify but not
2486  * delete the structures and features. The caps must be mutable.
2487  *
2488  * Returns: %TRUE if the supplied function returns %TRUE for each call,
2489  * %FALSE otherwise.
2490  *
2491  * Since: 1.6
2492  */
2493 gboolean
2494 gst_caps_map_in_place (GstCaps * caps, GstCapsMapFunc func, gpointer user_data)
2495 {
2496   guint i, n;
2497   GstCapsFeatures *features;
2498   GstStructure *structure;
2499   gboolean ret;
2500
2501   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
2502   g_return_val_if_fail (gst_caps_is_writable (caps), FALSE);
2503   g_return_val_if_fail (func != NULL, FALSE);
2504
2505   n = GST_CAPS_LEN (caps);
2506
2507   for (i = 0; i < n; i++) {
2508     features = gst_caps_get_features_unchecked (caps, i);
2509     structure = gst_caps_get_structure_unchecked (caps, i);
2510
2511     /* Provide sysmem features if there are none yet */
2512     if (!features) {
2513       features =
2514           gst_caps_features_copy (GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY);
2515       gst_caps_set_features (caps, i, features);
2516     }
2517
2518     ret = func (features, structure, user_data);
2519     if (G_UNLIKELY (!ret))
2520       return FALSE;
2521   }
2522
2523   return TRUE;
2524 }
2525
2526 /**
2527  * gst_caps_filter_and_map_in_place:
2528  * @caps: a #GstCaps
2529  * @func: (scope call): a function to call for each field
2530  * @user_data: (closure): private data
2531  *
2532  * Calls the provided function once for each structure and caps feature in the
2533  * #GstCaps. In contrast to gst_caps_foreach(), the function may modify the
2534  * structure and features. In contrast to gst_caps_filter_and_map_in_place(),
2535  * the structure and features are removed from the caps if %FALSE is returned
2536  * from the function.
2537  * The caps must be mutable.
2538  *
2539  * Since: 1.6
2540  */
2541 void
2542 gst_caps_filter_and_map_in_place (GstCaps * caps, GstCapsFilterMapFunc func,
2543     gpointer user_data)
2544 {
2545   guint i, n;
2546   GstCapsFeatures *features;
2547   GstStructure *structure;
2548   gboolean ret;
2549
2550   g_return_if_fail (GST_IS_CAPS (caps));
2551   g_return_if_fail (gst_caps_is_writable (caps));
2552   g_return_if_fail (func != NULL);
2553
2554   n = GST_CAPS_LEN (caps);
2555
2556   for (i = 0; i < n;) {
2557     features = gst_caps_get_features_unchecked (caps, i);
2558     structure = gst_caps_get_structure_unchecked (caps, i);
2559
2560     /* Provide sysmem features if there are none yet */
2561     if (!features) {
2562       features =
2563           gst_caps_features_copy (GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY);
2564       gst_caps_set_features (caps, i, features);
2565     }
2566
2567     ret = func (features, structure, user_data);
2568     if (!ret) {
2569       GST_CAPS_ARRAY (caps) = g_array_remove_index (GST_CAPS_ARRAY (caps), i);
2570
2571       gst_structure_set_parent_refcount (structure, NULL);
2572       gst_structure_free (structure);
2573       if (features) {
2574         gst_caps_features_set_parent_refcount (features, NULL);
2575         gst_caps_features_free (features);
2576       }
2577
2578       n = GST_CAPS_LEN (caps);
2579     } else {
2580       i++;
2581     }
2582   }
2583 }
2584
2585 /**
2586  * gst_caps_copy:
2587  * @caps: a #GstCaps.
2588  *
2589  * Creates a new #GstCaps as a copy of the old @caps. The new caps will have a
2590  * refcount of 1, owned by the caller. The structures are copied as well.
2591  *
2592  * Note that this function is the semantic equivalent of a gst_caps_ref()
2593  * followed by a gst_caps_make_writable(). If you only want to hold on to a
2594  * reference to the data, you should use gst_caps_ref().
2595  *
2596  * When you are finished with the caps, call gst_caps_unref() on it.
2597  *
2598  * Returns: the new #GstCaps
2599  */
2600 GstCaps *(gst_caps_copy) (const GstCaps * caps)
2601 {
2602   return GST_CAPS (gst_mini_object_copy (GST_MINI_OBJECT_CAST (caps)));
2603 }