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