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