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_copy_nth:
 937  * @caps: the #GstCaps to copy
 938  * @nth: the nth structure to copy
 939  *
 940  * Creates a new #GstCaps and appends a copy of the nth structure
 941  * contained in @caps.
 942  *
 943  * Returns: (transfer full): the new #GstCaps
 944  */
 945 GstCaps *
 946 gst_caps_copy_nth (const GstCaps * caps, guint nth)
 947 {
 948   GstCaps *newcaps;
 949   GstStructure *structure;
 950   GstCapsFeatures *features;
 951
 952   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 953
 954   newcaps = gst_caps_new_empty ();
 955   GST_CAPS_FLAGS (newcaps) = GST_CAPS_FLAGS (caps);
 956
 957   if (G_LIKELY (GST_CAPS_LEN (caps) > nth)) {
 958     structure = gst_caps_get_structure_unchecked (caps, nth);
 959     features = gst_caps_get_features_unchecked (caps, nth);
 960     gst_caps_append_structure_unchecked (newcaps,
 961         gst_structure_copy (structure),
 962         gst_caps_features_copy_conditional (features));
 963   }
 964
 965   return newcaps;
 966 }
 967
 968 /**
 969  * gst_caps_truncate:
 970  * @caps: (transfer full): the #GstCaps to truncate
 971  *
 972  * Discard all but the first structure from @caps. Useful when
 973  * fixating.
 974  *
 975  * This function takes ownership of @caps and will call gst_caps_make_writable()
 976  * on it if necessary, so you must not use @caps afterwards unless you keep an
 977  * additional reference to it with gst_caps_ref().
 978  *
 979  * Returns: (transfer full): truncated caps
 980  */
 981 GstCaps *
 982 gst_caps_truncate (GstCaps * caps)
 983 {
 984   gint i;
 985
 986   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 987
 988   i = GST_CAPS_LEN (caps) - 1;
 989   if (i == 0)
 990     return caps;
 991
 992   caps = gst_caps_make_writable (caps);
 993   while (i > 0)
 994     gst_caps_remove_structure (caps, i--);
 995
 996   return caps;
 997 }
 998
 999 /**
1000  * gst_caps_set_value:
1001  * @caps: a writable caps
1002  * @field: name of the field to set
1003  * @value: value to set the field to
1004  *
1005  * Sets the given @field on all structures of @caps to the given @value.
1006  * This is a convenience function for calling gst_structure_set_value() on
1007  * all structures of @caps.
1008  **/
1009 void
1010 gst_caps_set_value (GstCaps * caps, const char *field, const GValue * value)
1011 {
1012   guint i, len;
1013
1014   g_return_if_fail (GST_IS_CAPS (caps));
1015   g_return_if_fail (IS_WRITABLE (caps));
1016   g_return_if_fail (field != NULL);
1017   g_return_if_fail (G_IS_VALUE (value));
1018
1019   len = GST_CAPS_LEN (caps);
1020   for (i = 0; i < len; i++) {
1021     GstStructure *structure = gst_caps_get_structure_unchecked (caps, i);
1022     gst_structure_set_value (structure, field, value);
1023   }
1024 }
1025
1026 /**
1027  * gst_caps_set_simple_valist:
1028  * @caps: the #GstCaps to set
1029  * @field: first field to set
1030  * @varargs: additional parameters
1031  *
1032  * Sets fields in a #GstCaps.  The arguments must be passed in the same
1033  * manner as gst_structure_set(), and be %NULL-terminated.
1034  */
1035 void
1036 gst_caps_set_simple_valist (GstCaps * caps, const char *field, va_list varargs)
1037 {
1038   GValue value = { 0, };
1039
1040   g_return_if_fail (GST_IS_CAPS (caps));
1041   g_return_if_fail (IS_WRITABLE (caps));
1042
1043   while (field) {
1044     GType type;
1045     char *err;
1046
1047     type = va_arg (varargs, GType);
1048
1049     G_VALUE_COLLECT_INIT (&value, type, varargs, 0, &err);
1050     if (G_UNLIKELY (err)) {
1051       g_critical ("%s", err);
1052       g_free (err);
1053       return;
1054     }
1055
1056     gst_caps_set_value (caps, field, &value);
1057
1058     g_value_unset (&value);
1059
1060     field = va_arg (varargs, const gchar *);
1061   }
1062 }
1063
1064 /**
1065  * gst_caps_set_simple:
1066  * @caps: the #GstCaps to set
1067  * @field: first field to set
1068  * @...: additional parameters
1069  *
1070  * Sets fields in a #GstCaps.  The arguments must be passed in the same
1071  * manner as gst_structure_set(), and be %NULL-terminated.
1072  */
1073 void
1074 gst_caps_set_simple (GstCaps * caps, const char *field, ...)
1075 {
1076   va_list var_args;
1077
1078   g_return_if_fail (GST_IS_CAPS (caps));
1079   g_return_if_fail (IS_WRITABLE (caps));
1080
1081   va_start (var_args, field);
1082   gst_caps_set_simple_valist (caps, field, var_args);
1083   va_end (var_args);
1084 }
1085
1086 /* tests */
1087
1088 /**
1089  * gst_caps_is_any:
1090  * @caps: the #GstCaps to test
1091  *
1092  * Determines if @caps represents any media format.
1093  *
1094  * Returns: %TRUE if @caps represents any format.
1095  */
1096 gboolean
1097 gst_caps_is_any (const GstCaps * caps)
1098 {
1099   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
1100
1101   return (CAPS_IS_ANY (caps));
1102 }
1103
1104 /**
1105  * gst_caps_is_empty:
1106  * @caps: the #GstCaps to test
1107  *
1108  * Determines if @caps represents no media formats.
1109  *
1110  * Returns: %TRUE if @caps represents no formats.
1111  */
1112 gboolean
1113 gst_caps_is_empty (const GstCaps * caps)
1114 {
1115   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
1116
1117   if (CAPS_IS_ANY (caps))
1118     return FALSE;
1119
1120   return CAPS_IS_EMPTY_SIMPLE (caps);
1121 }
1122
1123 static gboolean
1124 gst_caps_is_fixed_foreach (GQuark field_id, const GValue * value,
1125     gpointer unused)
1126 {
1127   return gst_value_is_fixed (value);
1128 }
1129
1130 /**
1131  * gst_caps_is_fixed:
1132  * @caps: the #GstCaps to test
1133  *
1134  * Fixed #GstCaps describe exactly one format, that is, they have exactly
1135  * one structure, and each field in the structure describes a fixed type.
1136  * Examples of non-fixed types are GST_TYPE_INT_RANGE and GST_TYPE_LIST.
1137  *
1138  * Returns: %TRUE if @caps is fixed
1139  */
1140 gboolean
1141 gst_caps_is_fixed (const GstCaps * caps)
1142 {
1143   GstStructure *structure;
1144   GstCapsFeatures *features;
1145
1146   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
1147
1148   if (GST_CAPS_LEN (caps) != 1)
1149     return FALSE;
1150
1151   features = gst_caps_get_features_unchecked (caps, 0);
1152   if (features && gst_caps_features_is_any (features))
1153     return FALSE;
1154
1155   structure = gst_caps_get_structure_unchecked (caps, 0);
1156
1157   return gst_structure_foreach (structure, gst_caps_is_fixed_foreach, NULL);
1158 }
1159
1160 /**
1161  * gst_caps_is_equal_fixed:
1162  * @caps1: the #GstCaps to test
1163  * @caps2: the #GstCaps to test
1164  *
1165  * Tests if two #GstCaps are equal.  This function only works on fixed
1166  * #GstCaps.
1167  *
1168  * Returns: %TRUE if the arguments represent the same format
1169  */
1170 gboolean
1171 gst_caps_is_equal_fixed (const GstCaps * caps1, const GstCaps * caps2)
1172 {
1173   GstStructure *struct1, *struct2;
1174   GstCapsFeatures *features1, *features2;
1175
1176   g_return_val_if_fail (gst_caps_is_fixed (caps1), FALSE);
1177   g_return_val_if_fail (gst_caps_is_fixed (caps2), FALSE);
1178
1179   struct1 = gst_caps_get_structure_unchecked (caps1, 0);
1180   features1 = gst_caps_get_features_unchecked (caps1, 0);
1181   if (!features1)
1182     features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1183   struct2 = gst_caps_get_structure_unchecked (caps2, 0);
1184   features2 = gst_caps_get_features_unchecked (caps2, 0);
1185   if (!features2)
1186     features2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1187
1188   return gst_structure_is_equal (struct1, struct2) &&
1189       gst_caps_features_is_equal (features1, features2);
1190 }
1191
1192 /**
1193  * gst_caps_is_always_compatible:
1194  * @caps1: the #GstCaps to test
1195  * @caps2: the #GstCaps to test
1196  *
1197  * A given #GstCaps structure is always compatible with another if
1198  * every media format that is in the first is also contained in the
1199  * second.  That is, @caps1 is a subset of @caps2.
1200  *
1201  * Returns: %TRUE if @caps1 is a subset of @caps2.
1202  */
1203 gboolean
1204 gst_caps_is_always_compatible (const GstCaps * caps1, const GstCaps * caps2)
1205 {
1206   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
1207   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
1208
1209   return gst_caps_is_subset (caps1, caps2);
1210 }
1211
1212 /**
1213  * gst_caps_is_subset:
1214  * @subset: a #GstCaps
1215  * @superset: a potentially greater #GstCaps
1216  *
1217  * Checks if all caps represented by @subset are also represented by @superset.
1218  *
1219  * Returns: %TRUE if @subset is a subset of @superset
1220  */
1221 gboolean
1222 gst_caps_is_subset (const GstCaps * subset, const GstCaps * superset)
1223 {
1224   GstStructure *s1, *s2;
1225   GstCapsFeatures *f1, *f2;
1226   gboolean ret = TRUE;
1227   gint i, j;
1228
1229   g_return_val_if_fail (subset != NULL, FALSE);
1230   g_return_val_if_fail (superset != NULL, FALSE);
1231
1232   if (CAPS_IS_EMPTY (subset) || CAPS_IS_ANY (superset))
1233     return TRUE;
1234   if (CAPS_IS_ANY (subset) || CAPS_IS_EMPTY (superset))
1235     return FALSE;
1236
1237   for (i = GST_CAPS_LEN (subset) - 1; i >= 0; i--) {
1238     for (j = GST_CAPS_LEN (superset) - 1; j >= 0; j--) {
1239       s1 = gst_caps_get_structure_unchecked (subset, i);
1240       f1 = gst_caps_get_features_unchecked (subset, i);
1241       if (!f1)
1242         f1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1243       s2 = gst_caps_get_structure_unchecked (superset, j);
1244       f2 = gst_caps_get_features_unchecked (superset, j);
1245       if (!f2)
1246         f2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1247       if ((!gst_caps_features_is_any (f1) || gst_caps_features_is_any (f2)) &&
1248           gst_caps_features_is_equal (f1, f2)
1249           && gst_structure_is_subset (s1, s2)) {
1250         /* If we found a superset, continue with the next
1251          * subset structure */
1252         break;
1253       }
1254     }
1255     /* If we found no superset for this subset structure
1256      * we return FALSE immediately */
1257     if (j == -1) {
1258       ret = FALSE;
1259       break;
1260     }
1261   }
1262
1263   return ret;
1264 }
1265
1266 /**
1267  * gst_caps_is_subset_structure:
1268  * @caps: a #GstCaps
1269  * @structure: a potential #GstStructure subset of @caps
1270  *
1271  * Checks if @structure is a subset of @caps. See gst_caps_is_subset()
1272  * for more information.
1273  *
1274  * Returns: %TRUE if @structure is a subset of @caps
1275  */
1276 gboolean
1277 gst_caps_is_subset_structure (const GstCaps * caps,
1278     const GstStructure * structure)
1279 {
1280   GstStructure *s;
1281   gint i;
1282
1283   g_return_val_if_fail (caps != NULL, FALSE);
1284   g_return_val_if_fail (structure != NULL, FALSE);
1285
1286   if (CAPS_IS_ANY (caps))
1287     return TRUE;
1288   if (CAPS_IS_EMPTY (caps))
1289     return FALSE;
1290
1291   for (i = GST_CAPS_LEN (caps) - 1; i >= 0; i--) {
1292     s = gst_caps_get_structure_unchecked (caps, i);
1293     if (gst_structure_is_subset (structure, s)) {
1294       /* If we found a superset return TRUE */
1295       return TRUE;
1296     }
1297   }
1298
1299   return FALSE;
1300 }
1301
1302 /**
1303  * gst_caps_is_subset_structure_full:
1304  * @caps: a #GstCaps
1305  * @structure: a potential #GstStructure subset of @caps
1306  * @features: (allow-none): a #GstCapsFeatures for @structure
1307  *
1308  * Checks if @structure is a subset of @caps. See gst_caps_is_subset()
1309  * for more information.
1310  *
1311  * Returns: %TRUE if @structure is a subset of @caps
1312  *
1313  * Since: 1.2
1314  */
1315 gboolean
1316 gst_caps_is_subset_structure_full (const GstCaps * caps,
1317     const GstStructure * structure, const GstCapsFeatures * features)
1318 {
1319   GstStructure *s;
1320   GstCapsFeatures *f;
1321   gint i;
1322
1323   g_return_val_if_fail (caps != NULL, FALSE);
1324   g_return_val_if_fail (structure != NULL, FALSE);
1325
1326   if (CAPS_IS_ANY (caps))
1327     return TRUE;
1328   if (CAPS_IS_EMPTY (caps))
1329     return FALSE;
1330
1331   if (!features)
1332     features = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1333
1334   for (i = GST_CAPS_LEN (caps) - 1; i >= 0; i--) {
1335     s = gst_caps_get_structure_unchecked (caps, i);
1336     f = gst_caps_get_features_unchecked (caps, i);
1337     if (!f)
1338       f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1339     if ((!gst_caps_features_is_any (features) || gst_caps_features_is_any (f))
1340         && gst_caps_features_is_equal (features, f)
1341         && gst_structure_is_subset (structure, s)) {
1342       /* If we found a superset return TRUE */
1343       return TRUE;
1344     }
1345   }
1346
1347   return FALSE;
1348 }
1349
1350 /**
1351  * gst_caps_is_equal:
1352  * @caps1: a #GstCaps
1353  * @caps2: another #GstCaps
1354  *
1355  * Checks if the given caps represent the same set of caps.
1356  *
1357  * Returns: %TRUE if both caps are equal.
1358  */
1359 gboolean
1360 gst_caps_is_equal (const GstCaps * caps1, const GstCaps * caps2)
1361 {
1362   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
1363   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
1364
1365   if (G_UNLIKELY (caps1 == caps2))
1366     return TRUE;
1367
1368   if (G_UNLIKELY (gst_caps_is_fixed (caps1) && gst_caps_is_fixed (caps2)))
1369     return gst_caps_is_equal_fixed (caps1, caps2);
1370
1371   return gst_caps_is_subset (caps1, caps2) && gst_caps_is_subset (caps2, caps1);
1372 }
1373
1374 /**
1375  * gst_caps_is_strictly_equal:
1376  * @caps1: a #GstCaps
1377  * @caps2: another #GstCaps
1378  *
1379  * Checks if the given caps are exactly the same set of caps.
1380  *
1381  * Returns: %TRUE if both caps are strictly equal.
1382  */
1383 gboolean
1384 gst_caps_is_strictly_equal (const GstCaps * caps1, const GstCaps * caps2)
1385 {
1386   int i;
1387   GstStructure *s1, *s2;
1388   GstCapsFeatures *f1, *f2;
1389
1390   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
1391   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
1392
1393   if (G_UNLIKELY (caps1 == caps2))
1394     return TRUE;
1395
1396   if (GST_CAPS_LEN (caps1) != GST_CAPS_LEN (caps2))
1397     return FALSE;
1398
1399   for (i = 0; i < GST_CAPS_LEN (caps1); i++) {
1400     s1 = gst_caps_get_structure_unchecked (caps1, i);
1401     f1 = gst_caps_get_features_unchecked (caps1, i);
1402     if (!f1)
1403       f1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1404     s2 = gst_caps_get_structure_unchecked (caps2, i);
1405     f2 = gst_caps_get_features_unchecked (caps2, i);
1406     if (!f2)
1407       f2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1408
1409     if (gst_caps_features_is_any (f1) != gst_caps_features_is_any (f2) ||
1410         !gst_caps_features_is_equal (f1, f2) ||
1411         !gst_structure_is_equal (s1, s2))
1412       return FALSE;
1413   }
1414
1415   return TRUE;
1416 }
1417
1418 /* intersect operation */
1419
1420 /**
1421  * gst_caps_can_intersect:
1422  * @caps1: a #GstCaps to intersect
1423  * @caps2: a #GstCaps to intersect
1424  *
1425  * Tries intersecting @caps1 and @caps2 and reports whether the result would not
1426  * be empty
1427  *
1428  * Returns: %TRUE if intersection would be not empty
1429  */
1430 gboolean
1431 gst_caps_can_intersect (const GstCaps * caps1, const GstCaps * caps2)
1432 {
1433   guint64 i;                    /* index can be up to 2 * G_MAX_UINT */
1434   guint j, k, len1, len2;
1435   GstStructure *struct1;
1436   GstStructure *struct2;
1437   GstCapsFeatures *features1;
1438   GstCapsFeatures *features2;
1439
1440   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
1441   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
1442
1443   /* caps are exactly the same pointers */
1444   if (G_UNLIKELY (caps1 == caps2))
1445     return TRUE;
1446
1447   /* empty caps on either side, return empty */
1448   if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
1449     return FALSE;
1450
1451   /* one of the caps is any */
1452   if (G_UNLIKELY (CAPS_IS_ANY (caps1) || CAPS_IS_ANY (caps2)))
1453     return TRUE;
1454
1455   /* run zigzag on top line then right line, this preserves the caps order
1456    * much better than a simple loop.
1457    *
1458    * This algorithm zigzags over the caps structures as demonstrated in
1459    * the following matrix:
1460    *
1461    *          caps1                              0  1  2  3
1462    *       +-------------     total distance:  +-------------
1463    *       | 1  2  4  7                      0 | 0  1  2  3
1464    * caps2 | 3  5  8 10                      1 | 1  2  3  4
1465    *       | 6  9 11 12                      2 | 2  3  4  5
1466    *
1467    * First we iterate over the caps1 structures (top line) intersecting
1468    * the structures diagonally down, then we iterate over the caps2
1469    * structures. The result is that the intersections are ordered based on the
1470    * sum of the indexes in the list.
1471    */
1472   len1 = GST_CAPS_LEN (caps1);
1473   len2 = GST_CAPS_LEN (caps2);
1474   for (i = 0; i < len1 + len2 - 1; i++) {
1475     /* superset index goes from 0 to superset->structs->len-1 */
1476     j = MIN (i, len1 - 1);
1477     /* subset index stays 0 until i reaches superset->structs->len, then it
1478      * counts up from 1 to subset->structs->len - 1 */
1479     k = (i > j) ? (i - j) : 0;  /* MAX (0, i - j) */
1480     /* now run the diagonal line, end condition is the left or bottom
1481      * border */
1482     while (k < len2) {
1483       struct1 = gst_caps_get_structure_unchecked (caps1, j);
1484       features1 = gst_caps_get_features_unchecked (caps1, j);
1485       if (!features1)
1486         features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1487       struct2 = gst_caps_get_structure_unchecked (caps2, k);
1488       features2 = gst_caps_get_features_unchecked (caps2, k);
1489       if (!features2)
1490         features2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1491       if (gst_caps_features_is_equal (features1, features2) &&
1492           gst_structure_can_intersect (struct1, struct2)) {
1493         return TRUE;
1494       }
1495       /* move down left */
1496       k++;
1497       if (G_UNLIKELY (j == 0))
1498         break;                  /* so we don't roll back to G_MAXUINT */
1499       j--;
1500     }
1501   }
1502
1503   return FALSE;
1504 }
1505
1506 static GstCaps *
1507 gst_caps_intersect_zig_zag (GstCaps * caps1, GstCaps * caps2)
1508 {
1509   guint64 i;                    /* index can be up to 2 * G_MAX_UINT */
1510   guint j, k, len1, len2;
1511   GstStructure *struct1;
1512   GstStructure *struct2;
1513   GstCapsFeatures *features1;
1514   GstCapsFeatures *features2;
1515   GstCaps *dest;
1516   GstStructure *istruct;
1517
1518   /* caps are exactly the same pointers, just copy one caps */
1519   if (G_UNLIKELY (caps1 == caps2))
1520     return gst_caps_ref (caps1);
1521
1522   /* empty caps on either side, return empty */
1523   if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
1524     return gst_caps_ref (GST_CAPS_NONE);
1525
1526   /* one of the caps is any, just copy the other caps */
1527   if (G_UNLIKELY (CAPS_IS_ANY (caps1)))
1528     return gst_caps_ref (caps2);
1529
1530   if (G_UNLIKELY (CAPS_IS_ANY (caps2)))
1531     return gst_caps_ref (caps1);
1532
1533   dest = gst_caps_new_empty ();
1534   /* run zigzag on top line then right line, this preserves the caps order
1535    * much better than a simple loop.
1536    *
1537    * This algorithm zigzags over the caps structures as demonstrated in
1538    * the following matrix:
1539    *
1540    *          caps1
1541    *       +-------------
1542    *       | 1  2  4  7
1543    * caps2 | 3  5  8 10
1544    *       | 6  9 11 12
1545    *
1546    * First we iterate over the caps1 structures (top line) intersecting
1547    * the structures diagonally down, then we iterate over the caps2
1548    * structures.
1549    */
1550   len1 = GST_CAPS_LEN (caps1);
1551   len2 = GST_CAPS_LEN (caps2);
1552   for (i = 0; i < len1 + len2 - 1; i++) {
1553     /* caps1 index goes from 0 to GST_CAPS_LEN (caps1)-1 */
1554     j = MIN (i, len1 - 1);
1555     /* caps2 index stays 0 until i reaches GST_CAPS_LEN (caps1), then it counts
1556      * up from 1 to GST_CAPS_LEN (caps2) - 1 */
1557     k = (i > j) ? (i - j) : 0;  /* MAX (0, i - j) */
1558     /* now run the diagonal line, end condition is the left or bottom
1559      * border */
1560     while (k < len2) {
1561       struct1 = gst_caps_get_structure_unchecked (caps1, j);
1562       features1 = gst_caps_get_features_unchecked (caps1, j);
1563       if (!features1)
1564         features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1565       struct2 = gst_caps_get_structure_unchecked (caps2, k);
1566       features2 = gst_caps_get_features_unchecked (caps2, k);
1567       if (!features2)
1568         features2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1569       if (gst_caps_features_is_equal (features1, features2)) {
1570         istruct = gst_structure_intersect (struct1, struct2);
1571         if (istruct) {
1572           if (gst_caps_features_is_any (features1))
1573             dest =
1574                 gst_caps_merge_structure_full (dest, istruct,
1575                 gst_caps_features_copy_conditional (features2));
1576           else
1577             dest =
1578                 gst_caps_merge_structure_full (dest, istruct,
1579                 gst_caps_features_copy_conditional (features1));
1580         }
1581       }
1582       /* move down left */
1583       k++;
1584       if (G_UNLIKELY (j == 0))
1585         break;                  /* so we don't roll back to G_MAXUINT */
1586       j--;
1587     }
1588   }
1589   return dest;
1590 }
1591
1592 /**
1593  * gst_caps_intersect_first:
1594  * @caps1: a #GstCaps to intersect
1595  * @caps2: a #GstCaps to intersect
1596  *
1597  * Creates a new #GstCaps that contains all the formats that are common
1598  * to both @caps1 and @caps2.
1599  *
1600  * Unlike @gst_caps_intersect, the returned caps will be ordered in a similar
1601  * fashion as @caps1.
1602  *
1603  * Returns: (transfer full): the new #GstCaps
1604  */
1605 static GstCaps *
1606 gst_caps_intersect_first (GstCaps * caps1, GstCaps * caps2)
1607 {
1608   guint i;
1609   guint j, len1, len2;
1610   GstStructure *struct1;
1611   GstStructure *struct2;
1612   GstCapsFeatures *features1;
1613   GstCapsFeatures *features2;
1614   GstCaps *dest;
1615   GstStructure *istruct;
1616
1617   /* caps are exactly the same pointers, just copy one caps */
1618   if (G_UNLIKELY (caps1 == caps2))
1619     return gst_caps_ref (caps1);
1620
1621   /* empty caps on either side, return empty */
1622   if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
1623     return gst_caps_ref (GST_CAPS_NONE);
1624
1625   /* one of the caps is any, just copy the other caps */
1626   if (G_UNLIKELY (CAPS_IS_ANY (caps1)))
1627     return gst_caps_ref (caps2);
1628
1629   if (G_UNLIKELY (CAPS_IS_ANY (caps2)))
1630     return gst_caps_ref (caps1);
1631
1632   dest = gst_caps_new_empty ();
1633   len1 = GST_CAPS_LEN (caps1);
1634   len2 = GST_CAPS_LEN (caps2);
1635   for (i = 0; i < len1; i++) {
1636     struct1 = gst_caps_get_structure_unchecked (caps1, i);
1637     features1 = gst_caps_get_features_unchecked (caps1, i);
1638     if (!features1)
1639       features1 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1640     for (j = 0; j < len2; j++) {
1641       struct2 = gst_caps_get_structure_unchecked (caps2, j);
1642       features2 = gst_caps_get_features_unchecked (caps2, j);
1643       if (!features2)
1644         features2 = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1645       if (gst_caps_features_is_equal (features1, features2)) {
1646         istruct = gst_structure_intersect (struct1, struct2);
1647         if (istruct) {
1648           if (gst_caps_features_is_any (features1))
1649             dest =
1650                 gst_caps_merge_structure_full (dest, istruct,
1651                 gst_caps_features_copy_conditional (features2));
1652           else
1653             dest =
1654                 gst_caps_merge_structure_full (dest, istruct,
1655                 gst_caps_features_copy_conditional (features1));
1656         }
1657       }
1658     }
1659   }
1660
1661   return dest;
1662 }
1663
1664 /**
1665  * gst_caps_intersect_full:
1666  * @caps1: a #GstCaps to intersect
1667  * @caps2: a #GstCaps to intersect
1668  * @mode: The intersection algorithm/mode to use
1669  *
1670  * Creates a new #GstCaps that contains all the formats that are common
1671  * to both @caps1 and @caps2, the order is defined by the #GstCapsIntersectMode
1672  * used.
1673  *
1674  * Returns: (transfer full): the new #GstCaps
1675  */
1676 GstCaps *
1677 gst_caps_intersect_full (GstCaps * caps1, GstCaps * caps2,
1678     GstCapsIntersectMode mode)
1679 {
1680   g_return_val_if_fail (GST_IS_CAPS (caps1), NULL);
1681   g_return_val_if_fail (GST_IS_CAPS (caps2), NULL);
1682
1683   switch (mode) {
1684     case GST_CAPS_INTERSECT_FIRST:
1685       return gst_caps_intersect_first (caps1, caps2);
1686     default:
1687       g_warning ("Unknown caps intersect mode: %d", mode);
1688       /* fallthrough */
1689     case GST_CAPS_INTERSECT_ZIG_ZAG:
1690       return gst_caps_intersect_zig_zag (caps1, caps2);
1691   }
1692 }
1693
1694 /**
1695  * gst_caps_intersect:
1696  * @caps1: a #GstCaps to intersect
1697  * @caps2: a #GstCaps to intersect
1698  *
1699  * Creates a new #GstCaps that contains all the formats that are common
1700  * to both @caps1 and @caps2. Defaults to %GST_CAPS_INTERSECT_ZIG_ZAG mode.
1701  *
1702  * Returns: (transfer full): the new #GstCaps
1703  */
1704 GstCaps *
1705 gst_caps_intersect (GstCaps * caps1, GstCaps * caps2)
1706 {
1707   return gst_caps_intersect_full (caps1, caps2, GST_CAPS_INTERSECT_ZIG_ZAG);
1708 }
1709
1710 /* subtract operation */
1711
1712 typedef struct
1713 {
1714   const GstStructure *subtract_from;
1715   GSList *put_into;
1716 } SubtractionEntry;
1717
1718 static gboolean
1719 gst_caps_structure_subtract_field (GQuark field_id, const GValue * value,
1720     gpointer user_data)
1721 {
1722   SubtractionEntry *e = user_data;
1723   GValue subtraction = { 0, };
1724   const GValue *other;
1725   GstStructure *structure;
1726
1727   other = gst_structure_id_get_value (e->subtract_from, field_id);
1728
1729   if (!other) {
1730     return FALSE;
1731   }
1732
1733   if (!gst_value_subtract (&subtraction, other, value))
1734     return TRUE;
1735
1736   if (gst_value_compare (&subtraction, other) == GST_VALUE_EQUAL) {
1737     g_value_unset (&subtraction);
1738     return FALSE;
1739   } else {
1740     structure = gst_structure_copy (e->subtract_from);
1741     gst_structure_id_take_value (structure, field_id, &subtraction);
1742     e->put_into = g_slist_prepend (e->put_into, structure);
1743     return TRUE;
1744   }
1745 }
1746
1747 static gboolean
1748 gst_caps_structure_subtract (GSList ** into, const GstStructure * minuend,
1749     const GstStructure * subtrahend)
1750 {
1751   SubtractionEntry e;
1752   gboolean ret;
1753
1754   e.subtract_from = minuend;
1755   e.put_into = NULL;
1756   ret = gst_structure_foreach ((GstStructure *) subtrahend,
1757       gst_caps_structure_subtract_field, &e);
1758
1759   if (ret) {
1760     *into = e.put_into;
1761   } else {
1762     GSList *walk;
1763
1764     for (walk = e.put_into; walk; walk = g_slist_next (walk)) {
1765       gst_structure_free (walk->data);
1766     }
1767     g_slist_free (e.put_into);
1768   }
1769
1770   return ret;
1771 }
1772
1773 /**
1774  * gst_caps_subtract:
1775  * @minuend: #GstCaps to subtract from
1776  * @subtrahend: #GstCaps to subtract
1777  *
1778  * Subtracts the @subtrahend from the @minuend.
1779  * > This function does not work reliably if optional properties for caps
1780  * > are included on one caps and omitted on the other.
1781  *
1782  * Returns: (transfer full): the resulting caps
1783  */
1784 GstCaps *
1785 gst_caps_subtract (GstCaps * minuend, GstCaps * subtrahend)
1786 {
1787   guint i, j, sublen;
1788   GstStructure *min;
1789   GstStructure *sub;
1790   GstCapsFeatures *min_f, *sub_f;
1791   GstCaps *dest = NULL, *src;
1792
1793   g_return_val_if_fail (minuend != NULL, NULL);
1794   g_return_val_if_fail (subtrahend != NULL, NULL);
1795
1796   if (CAPS_IS_EMPTY (minuend) || CAPS_IS_ANY (subtrahend)) {
1797     return gst_caps_new_empty ();
1798   }
1799
1800   if (CAPS_IS_EMPTY_SIMPLE (subtrahend))
1801     return gst_caps_ref (minuend);
1802
1803   /* FIXME: Do we want this here or above?
1804      The reason we need this is that there is no definition about what
1805      ANY means for specific types, so it's not possible to reduce ANY partially
1806      You can only remove everything or nothing and that is done above.
1807      Note: there's a test that checks this behaviour. */
1808
1809   g_return_val_if_fail (!CAPS_IS_ANY (minuend), NULL);
1810   sublen = GST_CAPS_LEN (subtrahend);
1811   g_assert (sublen > 0);
1812
1813   src = _gst_caps_copy (minuend);
1814   for (i = 0; i < sublen; i++) {
1815     guint srclen;
1816
1817     sub = gst_caps_get_structure_unchecked (subtrahend, i);
1818     sub_f = gst_caps_get_features_unchecked (subtrahend, i);
1819     if (!sub_f)
1820       sub_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1821     if (dest) {
1822       gst_caps_unref (src);
1823       src = dest;
1824     }
1825     dest = gst_caps_new_empty ();
1826     srclen = GST_CAPS_LEN (src);
1827     for (j = 0; j < srclen; j++) {
1828       min = gst_caps_get_structure_unchecked (src, j);
1829       min_f = gst_caps_get_features_unchecked (src, j);
1830       if (!min_f)
1831         min_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
1832
1833       /* Same reason as above for ANY caps */
1834       g_return_val_if_fail (!gst_caps_features_is_any (min_f), NULL);
1835
1836       if (gst_structure_get_name_id (min) == gst_structure_get_name_id (sub) &&
1837           gst_caps_features_is_equal (min_f, sub_f)) {
1838         GSList *list;
1839
1840         if (gst_caps_structure_subtract (&list, min, sub)) {
1841           GSList *walk;
1842
1843           for (walk = list; walk; walk = g_slist_next (walk)) {
1844             gst_caps_append_structure_unchecked (dest,
1845                 (GstStructure *) walk->data,
1846                 gst_caps_features_copy_conditional (min_f));
1847           }
1848           g_slist_free (list);
1849         } else {
1850           gst_caps_append_structure_unchecked (dest, gst_structure_copy (min),
1851               gst_caps_features_copy_conditional (min_f));
1852         }
1853       } else {
1854         gst_caps_append_structure_unchecked (dest, gst_structure_copy (min),
1855             gst_caps_features_copy_conditional (min_f));
1856       }
1857     }
1858
1859     if (CAPS_IS_EMPTY_SIMPLE (dest)) {
1860       gst_caps_unref (src);
1861       return dest;
1862     }
1863   }
1864
1865   gst_caps_unref (src);
1866   dest = gst_caps_simplify (dest);
1867
1868   return dest;
1869 }
1870
1871 /* normalize/simplify operations */
1872
1873 typedef struct _NormalizeForeach
1874 {
1875   GstCaps *caps;
1876   GstStructure *structure;
1877   GstCapsFeatures *features;
1878 } NormalizeForeach;
1879
1880 static gboolean
1881 gst_caps_normalize_foreach (GQuark field_id, const GValue * value, gpointer ptr)
1882 {
1883   NormalizeForeach *nf = (NormalizeForeach *) ptr;
1884   GValue val = { 0 };
1885   guint i;
1886
1887   if (G_VALUE_TYPE (value) == GST_TYPE_LIST) {
1888     guint len = gst_value_list_get_size (value);
1889
1890     for (i = 1; i < len; i++) {
1891       const GValue *v = gst_value_list_get_value (value, i);
1892       GstStructure *structure = gst_structure_copy (nf->structure);
1893
1894       gst_structure_id_set_value (structure, field_id, v);
1895       gst_caps_append_structure_unchecked (nf->caps, structure,
1896           gst_caps_features_copy_conditional (nf->features));
1897     }
1898
1899     gst_value_init_and_copy (&val, gst_value_list_get_value (value, 0));
1900     gst_structure_id_take_value (nf->structure, field_id, &val);
1901     return FALSE;
1902   }
1903
1904   return TRUE;
1905 }
1906
1907 /**
1908  * gst_caps_normalize:
1909  * @caps: (transfer full): a #GstCaps to normalize
1910  *
1911  * Returns a #GstCaps that represents the same set of formats as
1912  * @caps, but contains no lists.  Each list is expanded into separate
1913  * @GstStructures.
1914  *
1915  * This function takes ownership of @caps and will call gst_caps_make_writable()
1916  * on it so you must not use @caps afterwards unless you keep an additional
1917  * reference to it with gst_caps_ref().
1918  *
1919  * Returns: (transfer full): the normalized #GstCaps
1920  */
1921 GstCaps *
1922 gst_caps_normalize (GstCaps * caps)
1923 {
1924   NormalizeForeach nf;
1925   guint i;
1926
1927   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
1928
1929   caps = gst_caps_make_writable (caps);
1930   nf.caps = caps;
1931
1932   for (i = 0; i < gst_caps_get_size (nf.caps); i++) {
1933     nf.structure = gst_caps_get_structure_unchecked (nf.caps, i);
1934     nf.features = gst_caps_get_features_unchecked (nf.caps, i);
1935     while (!gst_structure_foreach (nf.structure,
1936             gst_caps_normalize_foreach, &nf));
1937   }
1938
1939   return nf.caps;
1940 }
1941
1942 static gint
1943 gst_caps_compare_structures (gconstpointer one, gconstpointer two)
1944 {
1945   gint ret;
1946   const GstStructure *struct1 = ((const GstCapsArrayElement *) one)->structure;
1947   const GstStructure *struct2 = ((const GstCapsArrayElement *) two)->structure;
1948
1949   /* FIXME: this orders alphabetically, but ordering the quarks might be faster
1950      So what's the best way? */
1951   ret = strcmp (gst_structure_get_name (struct1),
1952       gst_structure_get_name (struct2));
1953
1954   if (ret)
1955     return ret;
1956
1957   return gst_structure_n_fields (struct2) - gst_structure_n_fields (struct1);
1958 }
1959
1960 typedef struct
1961 {
1962   GQuark name;
1963   GValue value;
1964   GstStructure *compare;
1965 } UnionField;
1966
1967 static gboolean
1968 gst_caps_structure_figure_out_union (GQuark field_id, const GValue * value,
1969     gpointer user_data)
1970 {
1971   UnionField *u = user_data;
1972   const GValue *val = gst_structure_id_get_value (u->compare, field_id);
1973
1974   if (!val) {
1975     if (u->name)
1976       g_value_unset (&u->value);
1977     return FALSE;
1978   }
1979
1980   if (gst_value_compare (val, value) == GST_VALUE_EQUAL)
1981     return TRUE;
1982
1983   if (u->name) {
1984     g_value_unset (&u->value);
1985     return FALSE;
1986   }
1987
1988   u->name = field_id;
1989   gst_value_union (&u->value, val, value);
1990
1991   return TRUE;
1992 }
1993
1994 static gboolean
1995 gst_caps_structure_simplify (GstStructure ** result,
1996     GstStructure * simplify, GstStructure * compare)
1997 {
1998   GSList *list;
1999   UnionField field = { 0, {0,}, NULL };
2000
2001   /* try to subtract to get a real subset */
2002   if (gst_caps_structure_subtract (&list, simplify, compare)) {
2003     if (list == NULL) {         /* no result */
2004       *result = NULL;
2005       return TRUE;
2006     } else if (list->next == NULL) {    /* one result */
2007       *result = list->data;
2008       g_slist_free (list);
2009       return TRUE;
2010     } else {                    /* multiple results */
2011       g_slist_foreach (list, (GFunc) gst_structure_free, NULL);
2012       g_slist_free (list);
2013       list = NULL;
2014     }
2015   }
2016
2017   /* try to union both structs */
2018   field.compare = compare;
2019   if (gst_structure_foreach (simplify,
2020           gst_caps_structure_figure_out_union, &field)) {
2021     gboolean ret = FALSE;
2022
2023     /* now we know all of simplify's fields are the same in compare
2024      * but at most one field: field.name */
2025     if (G_IS_VALUE (&field.value)) {
2026       if (gst_structure_n_fields (simplify) == gst_structure_n_fields (compare)) {
2027         gst_structure_id_take_value (compare, field.name, &field.value);
2028         *result = NULL;
2029         ret = TRUE;
2030       } else {
2031         g_value_unset (&field.value);
2032       }
2033     } else
2034         if (gst_structure_n_fields (simplify) <=
2035         gst_structure_n_fields (compare)) {
2036       /* compare is just more specific, will be optimized away later */
2037       /* FIXME: do this here? */
2038       GST_LOG ("found a case that will be optimized later.");
2039     } else {
2040       gchar *one = gst_structure_to_string (simplify);
2041       gchar *two = gst_structure_to_string (compare);
2042
2043       GST_ERROR
2044           ("caps mismatch: structures %s and %s claim to be possible to unify, but aren't",
2045           one, two);
2046       g_free (one);
2047       g_free (two);
2048     }
2049     return ret;
2050   }
2051
2052   return FALSE;
2053 }
2054
2055 static void
2056 gst_caps_switch_structures (GstCaps * caps, GstStructure * old,
2057     GstStructure * new, gint i)
2058 {
2059   gst_structure_set_parent_refcount (old, NULL);
2060   gst_structure_free (old);
2061   gst_structure_set_parent_refcount (new, &GST_CAPS_REFCOUNT (caps));
2062   g_array_index (GST_CAPS_ARRAY (caps), GstCapsArrayElement, i).structure = new;
2063 }
2064
2065 /**
2066  * gst_caps_simplify:
2067  * @caps: (transfer full): a #GstCaps to simplify
2068  *
2069  * Converts the given @caps into a representation that represents the
2070  * same set of formats, but in a simpler form.  Component structures that are
2071  * identical are merged.  Component structures that have values that can be
2072  * merged are also merged.
2073  *
2074  * This function takes ownership of @caps and will call gst_caps_make_writable()
2075  * on it if necessary, so you must not use @caps afterwards unless you keep an
2076  * additional reference to it with gst_caps_ref().
2077  *
2078  * This method does not preserve the original order of @caps.
2079  *
2080  * Returns: (transfer full): The simplified caps.
2081  */
2082 GstCaps *
2083 gst_caps_simplify (GstCaps * caps)
2084 {
2085   GstStructure *simplify, *compare, *result = NULL;
2086   GstCapsFeatures *simplify_f, *compare_f;
2087   gint i, j, start;
2088
2089   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
2090
2091   start = GST_CAPS_LEN (caps) - 1;
2092   /* one caps, already as simple as can be */
2093   if (start == 0)
2094     return caps;
2095
2096   caps = gst_caps_make_writable (caps);
2097
2098   g_array_sort (GST_CAPS_ARRAY (caps), gst_caps_compare_structures);
2099
2100   for (i = start; i >= 0; i--) {
2101     simplify = gst_caps_get_structure_unchecked (caps, i);
2102     simplify_f = gst_caps_get_features_unchecked (caps, i);
2103     if (!simplify_f)
2104       simplify_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
2105     compare = gst_caps_get_structure_unchecked (caps, start);
2106     compare_f = gst_caps_get_features_unchecked (caps, start);
2107     if (!compare_f)
2108       compare_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
2109     if (gst_structure_get_name_id (simplify) !=
2110         gst_structure_get_name_id (compare) ||
2111         !gst_caps_features_is_equal (simplify_f, compare_f))
2112       start = i;
2113     for (j = start; j >= 0; j--) {
2114       if (j == i)
2115         continue;
2116       compare = gst_caps_get_structure_unchecked (caps, j);
2117       compare_f = gst_caps_get_features_unchecked (caps, j);
2118       if (!compare_f)
2119         compare_f = GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY;
2120       if (gst_structure_get_name_id (simplify) !=
2121           gst_structure_get_name_id (compare) ||
2122           !gst_caps_features_is_equal (simplify_f, compare_f)) {
2123         break;
2124       }
2125       if (gst_caps_structure_simplify (&result, simplify, compare)) {
2126         if (result) {
2127           gst_caps_switch_structures (caps, simplify, result, i);
2128           simplify = result;
2129         } else {
2130           gst_caps_remove_structure (caps, i);
2131           start--;
2132           break;
2133         }
2134       }
2135     }
2136   }
2137   return caps;
2138 }
2139
2140 /**
2141  * gst_caps_fixate:
2142  * @caps: (transfer full): a #GstCaps to fixate
2143  *
2144  * Modifies the given @caps into a representation with only fixed
2145  * values. First the caps will be truncated and then the first structure will be
2146  * fixated with gst_structure_fixate().
2147  *
2148  * This function takes ownership of @caps and will call gst_caps_make_writable()
2149  * on it so you must not use @caps afterwards unless you keep an additional
2150  * reference to it with gst_caps_ref().
2151  *
2152  * Returns: (transfer full): the fixated caps
2153  */
2154 GstCaps *
2155 gst_caps_fixate (GstCaps * caps)
2156 {
2157   GstStructure *s;
2158   GstCapsFeatures *f;
2159
2160   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
2161
2162   /* default fixation */
2163   caps = gst_caps_truncate (caps);
2164   caps = gst_caps_make_writable (caps);
2165   s = gst_caps_get_structure (caps, 0);
2166   gst_structure_fixate (s);
2167
2168   /* Set features to sysmem if they're still ANY */
2169   f = gst_caps_get_features_unchecked (caps, 0);
2170   if (f && gst_caps_features_is_any (f)) {
2171     f = gst_caps_features_new_empty ();
2172     gst_caps_set_features (caps, 0, f);
2173   }
2174
2175   return caps;
2176 }
2177
2178 /* utility */
2179
2180 /**
2181  * gst_caps_to_string:
2182  * @caps: a #GstCaps
2183  *
2184  * Converts @caps to a string representation.  This string representation
2185  * can be converted back to a #GstCaps by gst_caps_from_string().
2186  *
2187  * For debugging purposes its easier to do something like this:
2188  * |[<!-- language="C" -->
2189  * GST_LOG ("caps are %" GST_PTR_FORMAT, caps);
2190  * ]|
2191  * This prints the caps in human readable form.
2192  *
2193  * The current implementation of serialization will lead to unexpected results
2194  * when there are nested #GstCaps / #GstStructure deeper than one level.
2195  *
2196  * Returns: (transfer full): a newly allocated string representing @caps.
2197  */
2198 gchar *
2199 gst_caps_to_string (const GstCaps * caps)
2200 {
2201   guint i, slen, clen;
2202   GString *s;
2203
2204   /* NOTE:  This function is potentially called by the debug system,
2205    * so any calls to gst_log() (and GST_DEBUG(), GST_LOG(), etc.)
2206    * should be careful to avoid recursion.  This includes any functions
2207    * called by gst_caps_to_string.  In particular, calls should
2208    * not use the GST_PTR_FORMAT extension.  */
2209
2210   if (caps == NULL) {
2211     return g_strdup ("NULL");
2212   }
2213   if (CAPS_IS_ANY (caps)) {
2214     return g_strdup ("ANY");
2215   }
2216   if (CAPS_IS_EMPTY_SIMPLE (caps)) {
2217     return g_strdup ("EMPTY");
2218   }
2219
2220   /* estimate a rough string length to avoid unnecessary reallocs in GString */
2221   slen = 0;
2222   clen = GST_CAPS_LEN (caps);
2223   for (i = 0; i < clen; i++) {
2224     GstCapsFeatures *f;
2225
2226     slen +=
2227         STRUCTURE_ESTIMATED_STRING_LEN (gst_caps_get_structure_unchecked
2228         (caps, i));
2229     f = gst_caps_get_features_unchecked (caps, i);
2230     if (f)
2231       slen += FEATURES_ESTIMATED_STRING_LEN (f);
2232   }
2233
2234   s = g_string_sized_new (slen);
2235   for (i = 0; i < clen; i++) {
2236     GstStructure *structure;
2237     GstCapsFeatures *features;
2238
2239     if (i > 0) {
2240       /* ';' is now added by gst_structure_to_string */
2241       g_string_append_c (s, ' ');
2242     }
2243
2244     structure = gst_caps_get_structure_unchecked (caps, i);
2245     features = gst_caps_get_features_unchecked (caps, i);
2246
2247     g_string_append (s, gst_structure_get_name (structure));
2248     if (features && (gst_caps_features_is_any (features)
2249             || !gst_caps_features_is_equal (features,
2250                 GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY))) {
2251       g_string_append_c (s, '(');
2252       priv_gst_caps_features_append_to_gstring (features, s);
2253       g_string_append_c (s, ')');
2254     }
2255     priv_gst_structure_append_to_gstring (structure, s);
2256   }
2257   if (s->len && s->str[s->len - 1] == ';') {
2258     /* remove latest ';' */
2259     s->str[--s->len] = '\0';
2260   }
2261   return g_string_free (s, FALSE);
2262 }
2263
2264 static gboolean
2265 gst_caps_from_string_inplace (GstCaps * caps, const gchar * string)
2266 {
2267   GstStructure *structure;
2268   gchar *s, *copy, *end, *next, save;
2269
2270   if (strcmp ("ANY", string) == 0) {
2271     GST_CAPS_FLAGS (caps) = GST_CAPS_FLAG_ANY;
2272     return TRUE;
2273   }
2274
2275   if (strcmp ("EMPTY", string) == 0 || strcmp ("NONE", string) == 0) {
2276     return TRUE;
2277   }
2278
2279   copy = s = g_strdup (string);
2280   do {
2281     GstCapsFeatures *features = NULL;
2282
2283     while (g_ascii_isspace (*s))
2284       s++;
2285     if (*s == '\0') {
2286       break;
2287     }
2288
2289     if (!priv_gst_structure_parse_name (s, &s, &end, &next)) {
2290       g_free (copy);
2291       return FALSE;
2292     }
2293
2294     save = *end;
2295     *end = '\0';
2296     structure = gst_structure_new_empty (s);
2297     *end = save;
2298
2299     if (structure == NULL) {
2300       g_free (copy);
2301       return FALSE;
2302     }
2303
2304     s = next;
2305
2306     if (*s == '\0') {
2307       goto append;
2308     }
2309
2310     if (*s == '(') {
2311       s++;
2312       end = s;
2313
2314       while (TRUE) {
2315         if (*end == '\0') {
2316           break;
2317         } else if (*end == ')') {
2318           break;
2319         } else {
2320           end++;
2321         }
2322       }
2323
2324       save = *end;
2325       *end = '\0';
2326       features = gst_caps_features_from_string (s);
2327       if (!features) {
2328         gst_structure_free (structure);
2329         g_free (copy);
2330         return FALSE;
2331       }
2332       *end = save;
2333       s = end;
2334       if (save == ')')
2335         s++;
2336     }
2337
2338     if (*s == '\0') {
2339       goto append;
2340     }
2341
2342     if (!priv_gst_structure_parse_fields (s, &s, structure)) {
2343       gst_structure_free (structure);
2344       if (features)
2345         gst_caps_features_free (features);
2346       g_free (copy);
2347       return FALSE;
2348     }
2349
2350   append:
2351     gst_caps_append_structure_unchecked (caps, structure, features);
2352     features = NULL;
2353     if (*s == '\0')
2354       break;
2355   } while (TRUE);
2356
2357   g_free (copy);
2358
2359   return TRUE;
2360 }
2361
2362 /**
2363  * gst_caps_from_string:
2364  * @string: a string to convert to #GstCaps
2365  *
2366  * Converts @caps from a string representation.
2367  *
2368  * The current implementation of serialization will lead to unexpected results
2369  * when there are nested #GstCaps / #GstStructure deeper than one level.
2370  *
2371  * Returns: (transfer full) (nullable): a newly allocated #GstCaps
2372  */
2373 GstCaps *
2374 gst_caps_from_string (const gchar * string)
2375 {
2376   GstCaps *caps;
2377
2378   g_return_val_if_fail (string, FALSE);
2379
2380   caps = gst_caps_new_empty ();
2381   if (gst_caps_from_string_inplace (caps, string)) {
2382     return caps;
2383   } else {
2384     gst_caps_unref (caps);
2385     return NULL;
2386   }
2387 }
2388
2389 static void
2390 gst_caps_transform_to_string (const GValue * src_value, GValue * dest_value)
2391 {
2392   g_return_if_fail (G_IS_VALUE (src_value));
2393   g_return_if_fail (G_IS_VALUE (dest_value));
2394   g_return_if_fail (G_VALUE_HOLDS (src_value, GST_TYPE_CAPS));
2395   g_return_if_fail (G_VALUE_HOLDS (dest_value, G_TYPE_STRING)
2396       || G_VALUE_HOLDS (dest_value, G_TYPE_POINTER));
2397
2398   g_value_take_string (dest_value,
2399       gst_caps_to_string (gst_value_get_caps (src_value)));
2400 }
2401
2402 /**
2403  * gst_caps_foreach:
2404  * @caps: a #GstCaps
2405  * @func: (scope call): a function to call for each field
2406  * @user_data: (closure): private data
2407  *
2408  * Calls the provided function once for each structure and caps feature in the
2409  * #GstCaps. The function must not modify the fields.
2410  * Also see gst_caps_map_in_place() and gst_caps_filter_and_map_in_place().
2411  *
2412  * Returns: %TRUE if the supplied function returns %TRUE for each call,
2413  * %FALSE otherwise.
2414  *
2415  * Since: 1.6
2416  */
2417 gboolean
2418 gst_caps_foreach (const GstCaps * caps, GstCapsForeachFunc func,
2419     gpointer user_data)
2420 {
2421   guint i, n;
2422   GstCapsFeatures *features;
2423   GstStructure *structure;
2424   gboolean ret;
2425
2426   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
2427   g_return_val_if_fail (func != NULL, FALSE);
2428
2429   n = GST_CAPS_LEN (caps);
2430
2431   for (i = 0; i < n; i++) {
2432     features = gst_caps_get_features_unchecked (caps, i);
2433     structure = gst_caps_get_structure_unchecked (caps, i);
2434
2435     ret = func (features, structure, user_data);
2436     if (G_UNLIKELY (!ret))
2437       return FALSE;
2438   }
2439
2440   return TRUE;
2441 }
2442
2443 /**
2444  * gst_caps_map_in_place:
2445  * @caps: a #GstCaps
2446  * @func: (scope call): a function to call for each field
2447  * @user_data: (closure): private data
2448  *
2449  * Calls the provided function once for each structure and caps feature in the
2450  * #GstCaps. In contrast to gst_caps_foreach(), the function may modify but not
2451  * delete the structures and features. The caps must be mutable.
2452  *
2453  * Returns: %TRUE if the supplied function returns %TRUE for each call,
2454  * %FALSE otherwise.
2455  *
2456  * Since: 1.6
2457  */
2458 gboolean
2459 gst_caps_map_in_place (GstCaps * caps, GstCapsMapFunc func, gpointer user_data)
2460 {
2461   guint i, n;
2462   GstCapsFeatures *features;
2463   GstStructure *structure;
2464   gboolean ret;
2465
2466   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
2467   g_return_val_if_fail (gst_caps_is_writable (caps), FALSE);
2468   g_return_val_if_fail (func != NULL, FALSE);
2469
2470   n = GST_CAPS_LEN (caps);
2471
2472   for (i = 0; i < n; i++) {
2473     features = gst_caps_get_features_unchecked (caps, i);
2474     structure = gst_caps_get_structure_unchecked (caps, i);
2475
2476     /* Provide sysmem features if there are none yet */
2477     if (!features) {
2478       features =
2479           gst_caps_features_copy (GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY);
2480       gst_caps_set_features (caps, i, features);
2481     }
2482
2483     ret = func (features, structure, user_data);
2484     if (G_UNLIKELY (!ret))
2485       return FALSE;
2486   }
2487
2488   return TRUE;
2489 }
2490
2491 /**
2492  * gst_caps_filter_and_map_in_place:
2493  * @caps: a #GstCaps
2494  * @func: (scope call): a function to call for each field
2495  * @user_data: (closure): private data
2496  *
2497  * Calls the provided function once for each structure and caps feature in the
2498  * #GstCaps. In contrast to gst_caps_foreach(), the function may modify the
2499  * structure and features. In contrast to gst_caps_filter_and_map_in_place(),
2500  * the structure and features are removed from the caps if %FALSE is returned
2501  * from the function.
2502  * The caps must be mutable.
2503  *
2504  * Since: 1.6
2505  */
2506 void
2507 gst_caps_filter_and_map_in_place (GstCaps * caps, GstCapsFilterMapFunc func,
2508     gpointer user_data)
2509 {
2510   guint i, n;
2511   GstCapsFeatures *features;
2512   GstStructure *structure;
2513   gboolean ret;
2514
2515   g_return_if_fail (GST_IS_CAPS (caps));
2516   g_return_if_fail (gst_caps_is_writable (caps));
2517   g_return_if_fail (func != NULL);
2518
2519   n = GST_CAPS_LEN (caps);
2520
2521   for (i = 0; i < n;) {
2522     features = gst_caps_get_features_unchecked (caps, i);
2523     structure = gst_caps_get_structure_unchecked (caps, i);
2524
2525     /* Provide sysmem features if there are none yet */
2526     if (!features) {
2527       features =
2528           gst_caps_features_copy (GST_CAPS_FEATURES_MEMORY_SYSTEM_MEMORY);
2529       gst_caps_set_features (caps, i, features);
2530     }
2531
2532     ret = func (features, structure, user_data);
2533     if (!ret) {
2534       GST_CAPS_ARRAY (caps) = g_array_remove_index (GST_CAPS_ARRAY (caps), i);
2535
2536       gst_structure_set_parent_refcount (structure, NULL);
2537       gst_structure_free (structure);
2538       if (features) {
2539         gst_caps_features_set_parent_refcount (features, NULL);
2540         gst_caps_features_free (features);
2541       }
2542
2543       n = GST_CAPS_LEN (caps);
2544     } else {
2545       i++;
2546     }
2547   }
2548 }
2549
2550 /**
2551  * gst_caps_copy:
2552  * @caps: a #GstCaps.
2553  *
2554  * Creates a new #GstCaps as a copy of the old @caps. The new caps will have a
2555  * refcount of 1, owned by the caller. The structures are copied as well.
2556  *
2557  * Note that this function is the semantic equivalent of a gst_caps_ref()
2558  * followed by a gst_caps_make_writable(). If you only want to hold on to a
2559  * reference to the data, you should use gst_caps_ref().
2560  *
2561  * When you are finished with the caps, call gst_caps_unref() on it.
2562  *
2563  * Returns: the new #GstCaps
2564  */
2565 GstCaps *(gst_caps_copy) (const GstCaps * caps)
2566 {
2567   return GST_CAPS (gst_mini_object_copy (GST_MINI_OBJECT_CAST (caps)));
2568 }