gst/gstcaps.c

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