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