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