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