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., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19
  20 /**
  21  * SECTION:gstcaps
  22  * @short_description: Structure describing sets of media formats
  23  * @see_also: #GstStructure
  24  *
  25  * Caps (capabilities) are lighweight 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_get_caps() pad
  33  * function. This function describes the possible types that the pad can
  34  * handle or produce at runtime.
  35  *
  36  * Caps are also attached to buffers to describe to content of the data
  37  * pointed to by the buffer with gst_buffer_set_caps(). Caps attached to
  38  * a #GstBuffer allow for format negotiation upstream and downstream.
  39  *
  40  * A #GstCaps can be constructed with the following code fragment:
  41  *
  42  * <example>
  43  *  <title>Creating caps</title>
  44  *  <programlisting>
  45  *  GstCaps *caps;
  46  *  caps = gst_caps_new_simple ("video/x-raw-yuv",
  47  *       "format", GST_TYPE_FOURCC, GST_MAKE_FOURCC ('I', '4', '2', '0'),
  48  *       "framerate", GST_TYPE_FRACTION, 25, 1,
  49  *       "pixel-aspect-ratio", GST_TYPE_FRACTION, 1, 1,
  50  *       "width", G_TYPE_INT, 320,
  51  *       "height", G_TYPE_INT, 240,
  52  *       NULL);
  53  *  </programlisting>
  54  * </example>
  55  *
  56  * A #GstCaps is fixed when it has no properties with ranges or lists. Use
  57  * gst_caps_is_fixed() to test for fixed caps. Only fixed caps can be
  58  * set on a #GstPad or #GstBuffer.
  59  *
  60  * Various methods exist to work with the media types such as subtracting
  61  * or intersecting.
  62  *
  63  * Last reviewed on 2007-02-13 (0.10.10)
  64  */
  65
  66 #ifdef HAVE_CONFIG_H
  67 #include "config.h"
  68 #endif
  69 #include <string.h>
  70 #include <signal.h>
  71
  72 #include "gst_private.h"
  73 #include <gst/gst.h>
  74 #include <gobject/gvaluecollector.h>
  75
  76 #define DEBUG_REFCOUNT
  77
  78 #define IS_WRITABLE(caps) \
  79   (GST_CAPS_REFCOUNT_VALUE (caps) == 1)
  80
  81 /* same as gst_caps_is_any () */
  82 #define CAPS_IS_ANY(caps)                               \
  83   (GST_CAPS_FLAGS(caps) & GST_CAPS_FLAGS_ANY)
  84
  85 /* same as gst_caps_is_empty () */
  86 #define CAPS_IS_EMPTY(caps)                             \
  87   (!CAPS_IS_ANY(caps) && CAPS_IS_EMPTY_SIMPLE(caps))
  88
  89 #define CAPS_IS_EMPTY_SIMPLE(caps)                                      \
  90   (((caps)->structs == NULL) || ((caps)->structs->len == 0))
  91
  92 /* quick way to get a caps structure at an index without doing a type or array
  93  * length check */
  94 #define gst_caps_get_structure_unchecked(caps, index) \
  95      ((GstStructure *)g_ptr_array_index ((caps)->structs, (index)))
  96 /* quick way to append a structure without checking the args */
  97 #define gst_caps_append_structure_unchecked(caps, structure) G_STMT_START{\
  98   GstStructure *__s=structure;                                      \
  99   if (gst_structure_set_parent_refcount (__s, &GST_MINI_OBJECT_REFCOUNT(caps)))         \
 100     g_ptr_array_add (caps->structs, __s);                             \
 101 }G_STMT_END
 102
 103 /* lock to protect multiple invocations of static caps to caps conversion */
 104 G_LOCK_DEFINE_STATIC (static_caps_lock);
 105
 106 static void gst_caps_transform_to_string (const GValue * src_value,
 107     GValue * dest_value);
 108 static gboolean gst_caps_from_string_inplace (GstCaps * caps,
 109     const gchar * string);
 110
 111 GType _gst_caps_type = 0;
 112
 113 void
 114 _gst_caps_initialize (void)
 115 {
 116   _gst_caps_type = gst_mini_object_register ("GstCaps");
 117
 118   g_value_register_transform_func (_gst_caps_type,
 119       G_TYPE_STRING, gst_caps_transform_to_string);
 120 }
 121
 122 static GstCaps *
 123 _gst_caps_copy (const GstCaps * caps)
 124 {
 125   GstCaps *newcaps;
 126   GstStructure *structure;
 127   guint i, n;
 128
 129   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 130
 131   newcaps = gst_caps_new_empty ();
 132   GST_CAPS_FLAGS (newcaps) = GST_CAPS_FLAGS (caps);
 133   n = caps->structs->len;
 134
 135   for (i = 0; i < n; i++) {
 136     structure = gst_caps_get_structure_unchecked (caps, i);
 137     gst_caps_append_structure (newcaps, gst_structure_copy (structure));
 138   }
 139
 140   return newcaps;
 141 }
 142
 143 /* creation/deletion */
 144 static void
 145 _gst_caps_free (GstCaps * caps)
 146 {
 147   GstStructure *structure;
 148   guint i, len;
 149
 150   /* The refcount must be 0, but since we're only called by gst_caps_unref,
 151    * don't bother testing. */
 152   len = caps->structs->len;
 153   /* This can be used to get statistics about caps sizes */
 154   /*GST_CAT_INFO (GST_CAT_CAPS, "caps size: %d", len); */
 155   for (i = 0; i < len; i++) {
 156     structure = (GstStructure *) gst_caps_get_structure_unchecked (caps, i);
 157     gst_structure_set_parent_refcount (structure, NULL);
 158     gst_structure_free (structure);
 159   }
 160   g_ptr_array_free (caps->structs, TRUE);
 161
 162 #ifdef DEBUG_REFCOUNT
 163   GST_CAT_LOG (GST_CAT_CAPS, "freeing caps %p", caps);
 164 #endif
 165   g_slice_free1 (GST_MINI_OBJECT_SIZE (caps), caps);
 166 }
 167
 168 static void
 169 gst_caps_init (GstCaps * caps, gsize size)
 170 {
 171   gst_mini_object_init (GST_MINI_OBJECT_CAST (caps), _gst_caps_type, size);
 172
 173   caps->mini_object.copy = (GstMiniObjectCopyFunction) _gst_caps_copy;
 174   caps->mini_object.dispose = NULL;
 175   caps->mini_object.free = (GstMiniObjectFreeFunction) _gst_caps_free;
 176
 177   /* the 32 has been determined by logging caps sizes in _gst_caps_free
 178    * but g_ptr_array uses 16 anyway if it expands once, so this does not help
 179    * in practise
 180    * caps->structs = g_ptr_array_sized_new (32);
 181    */
 182   caps->structs = g_ptr_array_new ();
 183 }
 184
 185 /**
 186  * gst_caps_new_empty:
 187  *
 188  * Creates a new #GstCaps that is empty.  That is, the returned
 189  * #GstCaps contains no media formats.
 190  * Caller is responsible for unreffing the returned caps.
 191  *
 192  * Returns: (transfer full): the new #GstCaps
 193  */
 194 GstCaps *
 195 gst_caps_new_empty (void)
 196 {
 197   GstCaps *caps;
 198
 199   caps = g_slice_new (GstCaps);
 200
 201   gst_caps_init (caps, sizeof (GstCaps));
 202
 203 #ifdef DEBUG_REFCOUNT
 204   GST_CAT_LOG (GST_CAT_CAPS, "created caps %p", caps);
 205 #endif
 206
 207   return caps;
 208 }
 209
 210 /**
 211  * gst_caps_new_any:
 212  *
 213  * Creates a new #GstCaps that indicates that it is compatible with
 214  * any media format.
 215  *
 216  * Returns: (transfer full): the new #GstCaps
 217  */
 218 GstCaps *
 219 gst_caps_new_any (void)
 220 {
 221   GstCaps *caps = gst_caps_new_empty ();
 222
 223   GST_CAPS_FLAG_SET (caps, GST_CAPS_FLAGS_ANY);
 224
 225   return caps;
 226 }
 227
 228 /**
 229  * gst_caps_new_simple:
 230  * @media_type: the media type of the structure
 231  * @fieldname: first field to set
 232  * @...: additional arguments
 233  *
 234  * Creates a new #GstCaps that contains one #GstStructure.  The
 235  * structure is defined by the arguments, which have the same format
 236  * as gst_structure_new().
 237  * Caller is responsible for unreffing the returned caps.
 238  *
 239  * Returns: (transfer full): the new #GstCaps
 240  */
 241 GstCaps *
 242 gst_caps_new_simple (const char *media_type, const char *fieldname, ...)
 243 {
 244   GstCaps *caps;
 245   GstStructure *structure;
 246   va_list var_args;
 247
 248   caps = gst_caps_new_empty ();
 249
 250   va_start (var_args, fieldname);
 251   structure = gst_structure_new_valist (media_type, fieldname, var_args);
 252   va_end (var_args);
 253
 254   if (structure)
 255     gst_caps_append_structure_unchecked (caps, structure);
 256   else
 257     gst_caps_replace (&caps, NULL);
 258
 259   return caps;
 260 }
 261
 262 /**
 263  * gst_caps_new_full:
 264  * @struct1: the first structure to add
 265  * @...: additional structures to add
 266  *
 267  * Creates a new #GstCaps and adds all the structures listed as
 268  * arguments.  The list must be NULL-terminated.  The structures
 269  * are not copied; the returned #GstCaps owns the structures.
 270  *
 271  * Returns: (transfer full): the new #GstCaps
 272  */
 273 GstCaps *
 274 gst_caps_new_full (GstStructure * struct1, ...)
 275 {
 276   GstCaps *caps;
 277   va_list var_args;
 278
 279   va_start (var_args, struct1);
 280   caps = gst_caps_new_full_valist (struct1, var_args);
 281   va_end (var_args);
 282
 283   return caps;
 284 }
 285
 286 /**
 287  * gst_caps_new_full_valist:
 288  * @structure: the first structure to add
 289  * @var_args: additional structures to add
 290  *
 291  * Creates a new #GstCaps and adds all the structures listed as
 292  * arguments.  The list must be NULL-terminated.  The structures
 293  * are not copied; the returned #GstCaps owns the structures.
 294  *
 295  * Returns: (transfer full): the new #GstCaps
 296  */
 297 GstCaps *
 298 gst_caps_new_full_valist (GstStructure * structure, va_list var_args)
 299 {
 300   GstCaps *caps;
 301
 302   caps = gst_caps_new_empty ();
 303
 304   while (structure) {
 305     gst_caps_append_structure_unchecked (caps, structure);
 306     structure = va_arg (var_args, GstStructure *);
 307   }
 308
 309   return caps;
 310 }
 311
 312 GType
 313 gst_static_caps_get_type (void)
 314 {
 315   static GType staticcaps_type = 0;
 316
 317   if (G_UNLIKELY (staticcaps_type == 0)) {
 318     staticcaps_type = g_pointer_type_register_static ("GstStaticCaps");
 319   }
 320   return staticcaps_type;
 321 }
 322
 323
 324 /**
 325  * gst_static_caps_get:
 326  * @static_caps: the #GstStaticCaps to convert
 327  *
 328  * Converts a #GstStaticCaps to a #GstCaps.
 329  *
 330  * Returns: (transfer full): a pointer to the #GstCaps. Unref after usage.
 331  *     Since the core holds an additional ref to the returned caps,
 332  *     use gst_caps_make_writable() on the returned caps to modify it.
 333  */
 334 GstCaps *
 335 gst_static_caps_get (GstStaticCaps * static_caps)
 336 {
 337   GstCaps *caps;
 338
 339   g_return_val_if_fail (static_caps != NULL, NULL);
 340
 341   caps = (GstCaps *) static_caps;
 342
 343   /* refcount is 0 when we need to convert */
 344   if (G_UNLIKELY (GST_CAPS_REFCOUNT_VALUE (caps) == 0)) {
 345     const char *string;
 346     GstCaps temp;
 347
 348     G_LOCK (static_caps_lock);
 349     /* check if other thread already updated */
 350     if (G_UNLIKELY (GST_CAPS_REFCOUNT_VALUE (caps) > 0))
 351       goto done;
 352
 353     string = static_caps->string;
 354
 355     if (G_UNLIKELY (string == NULL))
 356       goto no_string;
 357
 358     GST_CAT_LOG (GST_CAT_CAPS, "creating %p", static_caps);
 359
 360     /* we construct the caps on the stack, then copy over the struct into our
 361      * real caps, refcount last. We do this because we must leave the refcount
 362      * of the result caps to 0 so that other threads don't run away with the
 363      * caps while we are constructing it. */
 364     gst_caps_init (&temp, sizeof (GstCaps));
 365
 366     /* convert to string */
 367     if (G_UNLIKELY (!gst_caps_from_string_inplace (&temp, string)))
 368       g_critical ("Could not convert static caps \"%s\"", string);
 369
 370     gst_caps_init (caps, sizeof (GstCaps));
 371     /* now copy stuff over to the real caps. */
 372     GST_CAPS_FLAGS (caps) = GST_CAPS_FLAGS (&temp);
 373     caps->structs = temp.structs;
 374
 375     GST_CAT_LOG (GST_CAT_CAPS, "created %p", static_caps);
 376   done:
 377     G_UNLOCK (static_caps_lock);
 378   }
 379   /* ref the caps, makes it not writable */
 380   gst_caps_ref (caps);
 381
 382   return caps;
 383
 384   /* ERRORS */
 385 no_string:
 386   {
 387     G_UNLOCK (static_caps_lock);
 388     g_warning ("static caps %p string is NULL", static_caps);
 389     return NULL;
 390   }
 391 }
 392
 393 /* manipulation */
 394
 395 static GstStructure *
 396 gst_caps_remove_and_get_structure (GstCaps * caps, guint idx)
 397 {
 398   /* don't use index_fast, gst_caps_do_simplify relies on the order */
 399   GstStructure *s = g_ptr_array_remove_index (caps->structs, idx);
 400
 401   gst_structure_set_parent_refcount (s, NULL);
 402   return s;
 403 }
 404
 405 /**
 406  * gst_caps_steal_structure:
 407  * @caps: the #GstCaps to retrieve from
 408  * @index: Index of the structure to retrieve
 409  *
 410  * Retrieves the stucture with the given index from the list of structures
 411  * contained in @caps. The caller becomes the owner of the returned structure.
 412  *
 413  * Returns: (transfer full): a pointer to the #GstStructure corresponding
 414  *     to @index.
 415  *
 416  * Since: 0.10.30
 417  */
 418 GstStructure *
 419 gst_caps_steal_structure (GstCaps * caps, guint index)
 420 {
 421   g_return_val_if_fail (caps != NULL, NULL);
 422   g_return_val_if_fail (IS_WRITABLE (caps), NULL);
 423
 424   if (G_UNLIKELY (index >= caps->structs->len))
 425     return NULL;
 426
 427   return gst_caps_remove_and_get_structure (caps, index);
 428 }
 429
 430 /**
 431  * gst_caps_append:
 432  * @caps1: the #GstCaps that will be appended to
 433  * @caps2: (transfer full): the #GstCaps to append
 434  *
 435  * Appends the structures contained in @caps2 to @caps1. The structures in
 436  * @caps2 are not copied -- they are transferred to @caps1, and then @caps2 is
 437  * freed. If either caps is ANY, the resulting caps will be ANY.
 438  */
 439 void
 440 gst_caps_append (GstCaps * caps1, GstCaps * caps2)
 441 {
 442   GstStructure *structure;
 443   int i;
 444
 445   g_return_if_fail (GST_IS_CAPS (caps1));
 446   g_return_if_fail (GST_IS_CAPS (caps2));
 447   g_return_if_fail (IS_WRITABLE (caps1));
 448   g_return_if_fail (IS_WRITABLE (caps2));
 449
 450   if (G_UNLIKELY (CAPS_IS_ANY (caps1) || CAPS_IS_ANY (caps2))) {
 451     /* FIXME: this leaks */
 452     GST_CAPS_FLAGS (caps1) |= GST_CAPS_FLAGS_ANY;
 453     for (i = caps2->structs->len - 1; i >= 0; i--) {
 454       structure = gst_caps_remove_and_get_structure (caps2, i);
 455       gst_structure_free (structure);
 456     }
 457   } else {
 458     for (i = caps2->structs->len; i; i--) {
 459       structure = gst_caps_remove_and_get_structure (caps2, 0);
 460       gst_caps_append_structure_unchecked (caps1, structure);
 461     }
 462   }
 463   gst_caps_unref (caps2);       /* guaranteed to free it */
 464 }
 465
 466 /**
 467  * gst_caps_merge:
 468  * @caps1: the #GstCaps that will take the new entries
 469  * @caps2: (transfer full): the #GstCaps to merge in
 470  *
 471  * Appends the structures contained in @caps2 to @caps1 if they are not yet
 472  * expressed by @caps1. The structures in @caps2 are not copied -- they are
 473  * transferred to @caps1, and then @caps2 is freed.
 474  * If either caps is ANY, the resulting caps will be ANY.
 475  *
 476  * Since: 0.10.10
 477  */
 478 void
 479 gst_caps_merge (GstCaps * caps1, GstCaps * caps2)
 480 {
 481   GstStructure *structure;
 482   int i;
 483
 484   g_return_if_fail (GST_IS_CAPS (caps1));
 485   g_return_if_fail (GST_IS_CAPS (caps2));
 486   g_return_if_fail (IS_WRITABLE (caps1));
 487   g_return_if_fail (IS_WRITABLE (caps2));
 488
 489   if (G_UNLIKELY (CAPS_IS_ANY (caps1))) {
 490     for (i = caps2->structs->len - 1; i >= 0; i--) {
 491       structure = gst_caps_remove_and_get_structure (caps2, i);
 492       gst_structure_free (structure);
 493     }
 494   } else if (G_UNLIKELY (CAPS_IS_ANY (caps2))) {
 495     GST_CAPS_FLAGS (caps1) |= GST_CAPS_FLAGS_ANY;
 496     for (i = caps1->structs->len - 1; i >= 0; i--) {
 497       structure = gst_caps_remove_and_get_structure (caps1, i);
 498       gst_structure_free (structure);
 499     }
 500   } else {
 501     for (i = caps2->structs->len; i; i--) {
 502       structure = gst_caps_remove_and_get_structure (caps2, 0);
 503       gst_caps_merge_structure (caps1, structure);
 504     }
 505     /* this is too naive
 506        GstCaps *com = gst_caps_intersect (caps1, caps2);
 507        GstCaps *add = gst_caps_subtract (caps2, com);
 508
 509        GST_DEBUG ("common : %d", gst_caps_get_size (com));
 510        GST_DEBUG ("adding : %d", gst_caps_get_size (add));
 511        gst_caps_append (caps1, add);
 512        gst_caps_unref (com);
 513      */
 514   }
 515   gst_caps_unref (caps2);       /* guaranteed to free it */
 516 }
 517
 518 /**
 519  * gst_caps_append_structure:
 520  * @caps: the #GstCaps that will be appended to
 521  * @structure: (transfer full): the #GstStructure to append
 522  *
 523  * Appends @structure to @caps.  The structure is not copied; @caps
 524  * becomes the owner of @structure.
 525  */
 526 void
 527 gst_caps_append_structure (GstCaps * caps, GstStructure * structure)
 528 {
 529   g_return_if_fail (GST_IS_CAPS (caps));
 530   g_return_if_fail (IS_WRITABLE (caps));
 531
 532   if (G_LIKELY (structure)) {
 533     gst_caps_append_structure_unchecked (caps, structure);
 534   }
 535 }
 536
 537 /**
 538  * gst_caps_remove_structure:
 539  * @caps: the #GstCaps to remove from
 540  * @idx: Index of the structure to remove
 541  *
 542  * removes the stucture with the given index from the list of structures
 543  * contained in @caps.
 544  */
 545 void
 546 gst_caps_remove_structure (GstCaps * caps, guint idx)
 547 {
 548   GstStructure *structure;
 549
 550   g_return_if_fail (caps != NULL);
 551   g_return_if_fail (idx <= gst_caps_get_size (caps));
 552   g_return_if_fail (IS_WRITABLE (caps));
 553
 554   structure = gst_caps_remove_and_get_structure (caps, idx);
 555   gst_structure_free (structure);
 556 }
 557
 558 /**
 559  * gst_caps_merge_structure:
 560  * @caps: the #GstCaps that will the the new structure
 561  * @structure: (transfer full): the #GstStructure to merge
 562  *
 563  * Appends @structure to @caps if its not already expressed by @caps.  The
 564  * structure is not copied; @caps becomes the owner of @structure.
 565  */
 566 void
 567 gst_caps_merge_structure (GstCaps * caps, GstStructure * structure)
 568 {
 569   g_return_if_fail (GST_IS_CAPS (caps));
 570   g_return_if_fail (IS_WRITABLE (caps));
 571
 572   if (G_LIKELY (structure)) {
 573     GstStructure *structure1;
 574     int i;
 575     gboolean unique = TRUE;
 576
 577     /* check each structure */
 578     for (i = caps->structs->len - 1; i >= 0; i--) {
 579       structure1 = gst_caps_get_structure_unchecked (caps, i);
 580       /* if structure is a subset of structure1, then skip it */
 581       if (gst_structure_is_subset (structure, structure1)) {
 582         unique = FALSE;
 583         break;
 584       }
 585     }
 586     if (unique) {
 587       gst_caps_append_structure_unchecked (caps, structure);
 588     } else {
 589       gst_structure_free (structure);
 590     }
 591   }
 592 }
 593
 594 /**
 595  * gst_caps_get_size:
 596  * @caps: a #GstCaps
 597  *
 598  * Gets the number of structures contained in @caps.
 599  *
 600  * Returns: the number of structures that @caps contains
 601  */
 602 guint
 603 gst_caps_get_size (const GstCaps * caps)
 604 {
 605   g_return_val_if_fail (GST_IS_CAPS (caps), 0);
 606
 607   return caps->structs->len;
 608 }
 609
 610 /**
 611  * gst_caps_get_structure:
 612  * @caps: a #GstCaps
 613  * @index: the index of the structure
 614  *
 615  * Finds the structure in @caps that has the index @index, and
 616  * returns it.
 617  *
 618  * WARNING: This function takes a const GstCaps *, but returns a
 619  * non-const GstStructure *.  This is for programming convenience --
 620  * the caller should be aware that structures inside a constant
 621  * #GstCaps should not be modified. However, if you know the caps
 622  * are writable, either because you have just copied them or made
 623  * them writable with gst_caps_make_writable(), you may modify the
 624  * structure returned in the usual way, e.g. with functions like
 625  * gst_structure_set().
 626  *
 627  * You do not need to free or unref the structure returned, it
 628  * belongs to the #GstCaps.
 629  *
 630  * Returns: (transfer none): a pointer to the #GstStructure corresponding
 631  *     to @index
 632  */
 633 GstStructure *
 634 gst_caps_get_structure (const GstCaps * caps, guint index)
 635 {
 636   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 637   g_return_val_if_fail (index < caps->structs->len, NULL);
 638
 639   return gst_caps_get_structure_unchecked (caps, index);
 640 }
 641
 642 /**
 643  * gst_caps_copy_nth:
 644  * @caps: the #GstCaps to copy
 645  * @nth: the nth structure to copy
 646  *
 647  * Creates a new #GstCaps and appends a copy of the nth structure
 648  * contained in @caps.
 649  *
 650  * Returns: (transfer full): the new #GstCaps
 651  */
 652 GstCaps *
 653 gst_caps_copy_nth (const GstCaps * caps, guint nth)
 654 {
 655   GstCaps *newcaps;
 656   GstStructure *structure;
 657
 658   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
 659
 660   newcaps = gst_caps_new_empty ();
 661   GST_CAPS_FLAGS (newcaps) = GST_CAPS_FLAGS (caps);
 662
 663   if (G_LIKELY (caps->structs->len > nth)) {
 664     structure = gst_caps_get_structure_unchecked (caps, nth);
 665     gst_caps_append_structure_unchecked (newcaps,
 666         gst_structure_copy (structure));
 667   }
 668
 669   return newcaps;
 670 }
 671
 672 /**
 673  * gst_caps_truncate:
 674  * @caps: the #GstCaps to truncate
 675  *
 676  * Destructively discard all but the first structure from @caps. Useful when
 677  * fixating. @caps must be writable.
 678  */
 679 void
 680 gst_caps_truncate (GstCaps * caps)
 681 {
 682   gint i;
 683
 684   g_return_if_fail (GST_IS_CAPS (caps));
 685   g_return_if_fail (IS_WRITABLE (caps));
 686
 687   i = caps->structs->len - 1;
 688
 689   while (i > 0)
 690     gst_caps_remove_structure (caps, i--);
 691 }
 692
 693 /**
 694  * gst_caps_set_value:
 695  * @caps: a writable caps
 696  * @field: name of the field to set
 697  * @value: value to set the field to
 698  *
 699  * Sets the given @field on all structures of @caps to the given @value.
 700  * This is a convenience function for calling gst_structure_set_value() on
 701  * all structures of @caps.
 702  *
 703  * Since: 0.10.26
 704  **/
 705 void
 706 gst_caps_set_value (GstCaps * caps, const char *field, const GValue * value)
 707 {
 708   guint i, len;
 709
 710   g_return_if_fail (GST_IS_CAPS (caps));
 711   g_return_if_fail (IS_WRITABLE (caps));
 712   g_return_if_fail (field != NULL);
 713   g_return_if_fail (G_IS_VALUE (value));
 714
 715   len = caps->structs->len;
 716   for (i = 0; i < len; i++) {
 717     GstStructure *structure = gst_caps_get_structure_unchecked (caps, i);
 718     gst_structure_set_value (structure, field, value);
 719   }
 720 }
 721
 722 /**
 723  * gst_caps_set_simple_valist:
 724  * @caps: the #GstCaps to set
 725  * @field: first field to set
 726  * @varargs: additional parameters
 727  *
 728  * Sets fields in a #GstCaps.  The arguments must be passed in the same
 729  * manner as gst_structure_set(), and be NULL-terminated.
 730  * <note>Prior to GStreamer version 0.10.26, this function failed when
 731  * @caps was not simple. If your code needs to work with those versions
 732  * of GStreamer, you may only call this function when GST_CAPS_IS_SIMPLE()
 733  * is %TRUE for @caps.</note>
 734  */
 735 void
 736 gst_caps_set_simple_valist (GstCaps * caps, const char *field, va_list varargs)
 737 {
 738   GValue value = { 0, };
 739
 740   g_return_if_fail (GST_IS_CAPS (caps));
 741   g_return_if_fail (IS_WRITABLE (caps));
 742
 743   while (field) {
 744     GType type;
 745     char *err;
 746
 747     type = va_arg (varargs, GType);
 748
 749     if (G_UNLIKELY (type == G_TYPE_DATE)) {
 750       g_warning ("Don't use G_TYPE_DATE, use GST_TYPE_DATE instead\n");
 751       type = GST_TYPE_DATE;
 752     }
 753     G_VALUE_COLLECT_INIT (&value, type, varargs, 0, &err);
 754     if (G_UNLIKELY (err)) {
 755       g_critical ("%s", err);
 756       return;
 757     }
 758
 759     gst_caps_set_value (caps, field, &value);
 760
 761     g_value_unset (&value);
 762
 763     field = va_arg (varargs, const gchar *);
 764   }
 765 }
 766
 767 /**
 768  * gst_caps_set_simple:
 769  * @caps: the #GstCaps to set
 770  * @field: first field to set
 771  * @...: additional parameters
 772  *
 773  * Sets fields in a #GstCaps.  The arguments must be passed in the same
 774  * manner as gst_structure_set(), and be NULL-terminated.
 775  * <note>Prior to GStreamer version 0.10.26, this function failed when
 776  * @caps was not simple. If your code needs to work with those versions
 777  * of GStreamer, you may only call this function when GST_CAPS_IS_SIMPLE()
 778  * is %TRUE for @caps.</note>
 779  */
 780 void
 781 gst_caps_set_simple (GstCaps * caps, const char *field, ...)
 782 {
 783   va_list var_args;
 784
 785   g_return_if_fail (GST_IS_CAPS (caps));
 786   g_return_if_fail (IS_WRITABLE (caps));
 787
 788   va_start (var_args, field);
 789   gst_caps_set_simple_valist (caps, field, var_args);
 790   va_end (var_args);
 791 }
 792
 793 /* tests */
 794
 795 /**
 796  * gst_caps_is_any:
 797  * @caps: the #GstCaps to test
 798  *
 799  * Determines if @caps represents any media format.
 800  *
 801  * Returns: TRUE if @caps represents any format.
 802  */
 803 gboolean
 804 gst_caps_is_any (const GstCaps * caps)
 805 {
 806   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
 807
 808   return (CAPS_IS_ANY (caps));
 809 }
 810
 811 /**
 812  * gst_caps_is_empty:
 813  * @caps: the #GstCaps to test
 814  *
 815  * Determines if @caps represents no media formats.
 816  *
 817  * Returns: TRUE if @caps represents no formats.
 818  */
 819 gboolean
 820 gst_caps_is_empty (const GstCaps * caps)
 821 {
 822   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
 823
 824   if (CAPS_IS_ANY (caps))
 825     return FALSE;
 826
 827   return CAPS_IS_EMPTY_SIMPLE (caps);
 828 }
 829
 830 static gboolean
 831 gst_caps_is_fixed_foreach (GQuark field_id, const GValue * value,
 832     gpointer unused)
 833 {
 834   return gst_value_is_fixed (value);
 835 }
 836
 837 /**
 838  * gst_caps_is_fixed:
 839  * @caps: the #GstCaps to test
 840  *
 841  * Fixed #GstCaps describe exactly one format, that is, they have exactly
 842  * one structure, and each field in the structure describes a fixed type.
 843  * Examples of non-fixed types are GST_TYPE_INT_RANGE and GST_TYPE_LIST.
 844  *
 845  * Returns: TRUE if @caps is fixed
 846  */
 847 gboolean
 848 gst_caps_is_fixed (const GstCaps * caps)
 849 {
 850   GstStructure *structure;
 851
 852   g_return_val_if_fail (GST_IS_CAPS (caps), FALSE);
 853
 854   if (caps->structs->len != 1)
 855     return FALSE;
 856
 857   structure = gst_caps_get_structure_unchecked (caps, 0);
 858
 859   return gst_structure_foreach (structure, gst_caps_is_fixed_foreach, NULL);
 860 }
 861
 862 /**
 863  * gst_caps_is_equal_fixed:
 864  * @caps1: the #GstCaps to test
 865  * @caps2: the #GstCaps to test
 866  *
 867  * Tests if two #GstCaps are equal.  This function only works on fixed
 868  * #GstCaps.
 869  *
 870  * Returns: TRUE if the arguments represent the same format
 871  */
 872 gboolean
 873 gst_caps_is_equal_fixed (const GstCaps * caps1, const GstCaps * caps2)
 874 {
 875   GstStructure *struct1, *struct2;
 876
 877   g_return_val_if_fail (gst_caps_is_fixed (caps1), FALSE);
 878   g_return_val_if_fail (gst_caps_is_fixed (caps2), FALSE);
 879
 880   struct1 = gst_caps_get_structure_unchecked (caps1, 0);
 881   struct2 = gst_caps_get_structure_unchecked (caps2, 0);
 882
 883   return gst_structure_is_equal (struct1, struct2);
 884 }
 885
 886 /**
 887  * gst_caps_is_always_compatible:
 888  * @caps1: the #GstCaps to test
 889  * @caps2: the #GstCaps to test
 890  *
 891  * A given #GstCaps structure is always compatible with another if
 892  * every media format that is in the first is also contained in the
 893  * second.  That is, @caps1 is a subset of @caps2.
 894  *
 895  * Returns: TRUE if @caps1 is a subset of @caps2.
 896  */
 897 gboolean
 898 gst_caps_is_always_compatible (const GstCaps * caps1, const GstCaps * caps2)
 899 {
 900   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
 901   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
 902
 903   return gst_caps_is_subset (caps1, caps2);
 904 }
 905
 906 /**
 907  * gst_caps_is_subset:
 908  * @subset: a #GstCaps
 909  * @superset: a potentially greater #GstCaps
 910  *
 911  * Checks if all caps represented by @subset are also represented by @superset.
 912  * <note>This function does not work reliably if optional properties for caps
 913  * are included on one caps and omitted on the other.</note>
 914  *
 915  * Returns: %TRUE if @subset is a subset of @superset
 916  */
 917 gboolean
 918 gst_caps_is_subset (const GstCaps * subset, const GstCaps * superset)
 919 {
 920   GstStructure *s1, *s2;
 921   gboolean ret = TRUE;
 922   gint i, j;
 923
 924   g_return_val_if_fail (subset != NULL, FALSE);
 925   g_return_val_if_fail (superset != NULL, FALSE);
 926
 927   if (CAPS_IS_EMPTY (subset) || CAPS_IS_ANY (superset))
 928     return TRUE;
 929   if (CAPS_IS_ANY (subset) || CAPS_IS_EMPTY (superset))
 930     return FALSE;
 931
 932   for (i = subset->structs->len - 1; i >= 0; i--) {
 933     for (j = superset->structs->len - 1; j >= 0; j--) {
 934       s1 = gst_caps_get_structure_unchecked (subset, i);
 935       s2 = gst_caps_get_structure_unchecked (superset, j);
 936       if (gst_structure_is_subset (s1, s2)) {
 937         /* If we found a superset, continue with the next
 938          * subset structure */
 939         break;
 940       }
 941     }
 942     /* If we found no superset for this subset structure
 943      * we return FALSE immediately */
 944     if (j == -1) {
 945       ret = FALSE;
 946       break;
 947     }
 948   }
 949
 950   return ret;
 951 }
 952
 953 /**
 954  * gst_caps_is_subset_structure:
 955  * @caps: a #GstCaps
 956  * @structure: a potential #GstStructure subset of @caps
 957  *
 958  * Checks if @structure is a subset of @caps. See gst_caps_is_subset()
 959  * for more information.
 960  *
 961  * Returns: %TRUE if @structure is a subset of @caps
 962  *
 963  * Since: 0.10.35
 964  */
 965 gboolean
 966 gst_caps_is_subset_structure (const GstCaps * caps,
 967     const GstStructure * structure)
 968 {
 969   GstStructure *s;
 970   gint i;
 971
 972   g_return_val_if_fail (caps != NULL, FALSE);
 973   g_return_val_if_fail (structure != NULL, FALSE);
 974
 975   if (CAPS_IS_ANY (caps))
 976     return TRUE;
 977   if (CAPS_IS_EMPTY (caps))
 978     return FALSE;
 979
 980   for (i = caps->structs->len - 1; i >= 0; i--) {
 981     s = gst_caps_get_structure_unchecked (caps, i);
 982     if (gst_structure_is_subset (structure, s)) {
 983       /* If we found a superset return TRUE */
 984       return TRUE;
 985     }
 986   }
 987
 988   return FALSE;
 989 }
 990
 991 /**
 992  * gst_caps_is_equal:
 993  * @caps1: a #GstCaps
 994  * @caps2: another #GstCaps
 995  *
 996  * Checks if the given caps represent the same set of caps.
 997  * <note>This function does not work reliably if optional properties for caps
 998  * are included on one caps and omitted on the other.</note>
 999  *
1000  * This function deals correctly with passing NULL for any of the caps.
1001  *
1002  * Returns: TRUE if both caps are equal.
1003  */
1004 gboolean
1005 gst_caps_is_equal (const GstCaps * caps1, const GstCaps * caps2)
1006 {
1007   /* FIXME 0.11: NULL pointers are no valid Caps but indicate an error
1008    * So there should be an assertion that caps1 and caps2 != NULL */
1009
1010   /* NULL <-> NULL is allowed here */
1011   if (G_UNLIKELY (caps1 == caps2))
1012     return TRUE;
1013
1014   /* one of them NULL => they are different (can't be both NULL because
1015    * we checked that above) */
1016   if (G_UNLIKELY (caps1 == NULL || caps2 == NULL))
1017     return FALSE;
1018
1019   if (G_UNLIKELY (gst_caps_is_fixed (caps1) && gst_caps_is_fixed (caps2)))
1020     return gst_caps_is_equal_fixed (caps1, caps2);
1021
1022   return gst_caps_is_subset (caps1, caps2) && gst_caps_is_subset (caps2, caps1);
1023 }
1024
1025 /* intersect operation */
1026
1027 /**
1028  * gst_caps_can_intersect:
1029  * @caps1: a #GstCaps to intersect
1030  * @caps2: a #GstCaps to intersect
1031  *
1032  * Tries intersecting @caps1 and @caps2 and reports whether the result would not
1033  * be empty
1034  *
1035  * Returns: %TRUE if intersection would be not empty
1036  *
1037  * Since: 0.10.25
1038  */
1039 gboolean
1040 gst_caps_can_intersect (const GstCaps * caps1, const GstCaps * caps2)
1041 {
1042   guint64 i;                    /* index can be up to 2 * G_MAX_UINT */
1043   guint j, k, len1, len2;
1044   GstStructure *struct1;
1045   GstStructure *struct2;
1046
1047   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
1048   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
1049
1050   /* caps are exactly the same pointers */
1051   if (G_UNLIKELY (caps1 == caps2))
1052     return TRUE;
1053
1054   /* empty caps on either side, return empty */
1055   if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
1056     return FALSE;
1057
1058   /* one of the caps is any */
1059   if (G_UNLIKELY (CAPS_IS_ANY (caps1) || CAPS_IS_ANY (caps2)))
1060     return TRUE;
1061
1062   /* run zigzag on top line then right line, this preserves the caps order
1063    * much better than a simple loop.
1064    *
1065    * This algorithm zigzags over the caps structures as demonstrated in
1066    * the folowing matrix:
1067    *
1068    *          caps1                              0  1  2  3
1069    *       +-------------     total distance:  +-------------
1070    *       | 1  2  4  7                      0 | 0  1  2  3
1071    * caps2 | 3  5  8 10                      1 | 1  2  3  4
1072    *       | 6  9 11 12                      2 | 2  3  4  5
1073    *
1074    * First we iterate over the caps1 structures (top line) intersecting
1075    * the structures diagonally down, then we iterate over the caps2
1076    * structures. The result is that the intersections are ordered based on the
1077    * sum of the indexes in the list.
1078    */
1079   len1 = caps1->structs->len;
1080   len2 = caps2->structs->len;
1081   for (i = 0; i < len1 + len2 - 1; i++) {
1082     /* superset index goes from 0 to sgst_caps_structure_intersectuperset->structs->len-1 */
1083     j = MIN (i, len1 - 1);
1084     /* subset index stays 0 until i reaches superset->structs->len, then it
1085      * counts up from 1 to subset->structs->len - 1 */
1086     k = MAX (0, i - j);
1087
1088     /* now run the diagonal line, end condition is the left or bottom
1089      * border */
1090     while (k < len2) {
1091       struct1 = gst_caps_get_structure_unchecked (caps1, j);
1092       struct2 = gst_caps_get_structure_unchecked (caps2, k);
1093
1094       if (gst_structure_can_intersect (struct1, struct2)) {
1095         return TRUE;
1096       }
1097       /* move down left */
1098       k++;
1099       if (G_UNLIKELY (j == 0))
1100         break;                  /* so we don't roll back to G_MAXUINT */
1101       j--;
1102     }
1103   }
1104   return FALSE;
1105 }
1106
1107 static GstCaps *
1108 gst_caps_intersect_zig_zag (const GstCaps * caps1, const GstCaps * caps2)
1109 {
1110   guint64 i;                    /* index can be up to 2 * G_MAX_UINT */
1111   guint j, k, len1, len2;
1112
1113   GstStructure *struct1;
1114   GstStructure *struct2;
1115   GstCaps *dest;
1116   GstStructure *istruct;
1117
1118   /* caps are exactly the same pointers, just copy one caps */
1119   if (G_UNLIKELY (caps1 == caps2))
1120     return _gst_caps_copy (caps1);
1121
1122   /* empty caps on either side, return empty */
1123   if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
1124     return gst_caps_new_empty ();
1125
1126   /* one of the caps is any, just copy the other caps */
1127   if (G_UNLIKELY (CAPS_IS_ANY (caps1)))
1128     return _gst_caps_copy (caps2);
1129   if (G_UNLIKELY (CAPS_IS_ANY (caps2)))
1130     return _gst_caps_copy (caps1);
1131
1132   dest = gst_caps_new_empty ();
1133
1134   /* run zigzag on top line then right line, this preserves the caps order
1135    * much better than a simple loop.
1136    *
1137    * This algorithm zigzags over the caps structures as demonstrated in
1138    * the folowing matrix:
1139    *
1140    *          caps1
1141    *       +-------------
1142    *       | 1  2  4  7
1143    * caps2 | 3  5  8 10
1144    *       | 6  9 11 12
1145    *
1146    * First we iterate over the caps1 structures (top line) intersecting
1147    * the structures diagonally down, then we iterate over the caps2
1148    * structures.
1149    */
1150   len1 = caps1->structs->len;
1151   len2 = caps2->structs->len;
1152   for (i = 0; i < len1 + len2 - 1; i++) {
1153     /* caps1 index goes from 0 to caps1->structs->len-1 */
1154     j = MIN (i, len1 - 1);
1155     /* caps2 index stays 0 until i reaches caps1->structs->len, then it counts
1156      * up from 1 to caps2->structs->len - 1 */
1157     k = MAX (0, i - j);
1158
1159     /* now run the diagonal line, end condition is the left or bottom
1160      * border */
1161     while (k < len2) {
1162       struct1 = gst_caps_get_structure_unchecked (caps1, j);
1163       struct2 = gst_caps_get_structure_unchecked (caps2, k);
1164
1165       istruct = gst_structure_intersect (struct1, struct2);
1166
1167       gst_caps_merge_structure (dest, istruct);
1168       /* move down left */
1169       k++;
1170       if (G_UNLIKELY (j == 0))
1171         break;                  /* so we don't roll back to G_MAXUINT */
1172       j--;
1173     }
1174   }
1175   return dest;
1176 }
1177
1178 /**
1179  * gst_caps_intersect_first:
1180  * @caps1: a #GstCaps to intersect
1181  * @caps2: a #GstCaps to intersect
1182  *
1183  * Creates a new #GstCaps that contains all the formats that are common
1184  * to both @caps1 and @caps2.
1185  *
1186  * Unlike @gst_caps_intersect, the returned caps will be ordered in a similar
1187  * fashion as @caps1.
1188  *
1189  * Returns: the new #GstCaps
1190  */
1191 static GstCaps *
1192 gst_caps_intersect_first (const GstCaps * caps1, const GstCaps * caps2)
1193 {
1194   guint64 i;                    /* index can be up to 2 * G_MAX_UINT */
1195   guint j, len1, len2;
1196
1197   GstStructure *struct1;
1198   GstStructure *struct2;
1199   GstCaps *dest;
1200   GstStructure *istruct;
1201
1202   /* caps are exactly the same pointers, just copy one caps */
1203   if (G_UNLIKELY (caps1 == caps2))
1204     return gst_caps_copy (caps1);
1205
1206   /* empty caps on either side, return empty */
1207   if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
1208     return gst_caps_new_empty ();
1209
1210   /* one of the caps is any, just copy the other caps */
1211   if (G_UNLIKELY (CAPS_IS_ANY (caps1)))
1212     return gst_caps_copy (caps2);
1213   if (G_UNLIKELY (CAPS_IS_ANY (caps2)))
1214     return gst_caps_copy (caps1);
1215
1216   dest = gst_caps_new_empty ();
1217
1218   len1 = caps1->structs->len;
1219   len2 = caps2->structs->len;
1220   for (i = 0; i < len1; i++) {
1221     struct1 = gst_caps_get_structure_unchecked (caps1, i);
1222     for (j = 0; j < len2; j++) {
1223       struct2 = gst_caps_get_structure_unchecked (caps2, j);
1224       istruct = gst_structure_intersect (struct1, struct2);
1225       if (istruct)
1226         gst_caps_merge_structure (dest, istruct);
1227     }
1228   }
1229
1230   return dest;
1231 }
1232
1233 /**
1234  * gst_caps_intersect_full:
1235  * @caps1: a #GstCaps to intersect
1236  * @caps2: a #GstCaps to intersect
1237  * @mode: The intersection algorithm/mode to use
1238  *
1239  * Creates a new #GstCaps that contains all the formats that are common
1240  * to both @caps1 and @caps2, the order is defined by the #GstCapsIntersectMode
1241  * used.
1242  *
1243  * Returns: the new #GstCaps
1244  * Since: 0.10.33
1245  */
1246 GstCaps *
1247 gst_caps_intersect_full (const GstCaps * caps1, const GstCaps * caps2,
1248     GstCapsIntersectMode mode)
1249 {
1250   g_return_val_if_fail (GST_IS_CAPS (caps1), NULL);
1251   g_return_val_if_fail (GST_IS_CAPS (caps2), NULL);
1252
1253   switch (mode) {
1254     case GST_CAPS_INTERSECT_FIRST:
1255       return gst_caps_intersect_first (caps1, caps2);
1256     default:
1257       g_warning ("Unknown caps intersect mode: %d", mode);
1258       /* fallthrough */
1259     case GST_CAPS_INTERSECT_ZIG_ZAG:
1260       return gst_caps_intersect_zig_zag (caps1, caps2);
1261   }
1262 }
1263
1264 /**
1265  * gst_caps_intersect:
1266  * @caps1: a #GstCaps to intersect
1267  * @caps2: a #GstCaps to intersect
1268  *
1269  * Creates a new #GstCaps that contains all the formats that are common
1270  * to both @caps1 and @caps2. Defaults to %GST_CAPS_INTERSECT_ZIG_ZAG mode.
1271  *
1272  * Returns: the new #GstCaps
1273  */
1274 GstCaps *
1275 gst_caps_intersect (const GstCaps * caps1, const GstCaps * caps2)
1276 {
1277   return gst_caps_intersect_full (caps1, caps2, GST_CAPS_INTERSECT_ZIG_ZAG);
1278 }
1279
1280
1281 /* subtract operation */
1282
1283 typedef struct
1284 {
1285   const GstStructure *subtract_from;
1286   GSList *put_into;
1287 }
1288 SubtractionEntry;
1289
1290 static gboolean
1291 gst_caps_structure_subtract_field (GQuark field_id, const GValue * value,
1292     gpointer user_data)
1293 {
1294   SubtractionEntry *e = user_data;
1295   GValue subtraction = { 0, };
1296   const GValue *other;
1297   GstStructure *structure;
1298
1299   other = gst_structure_id_get_value (e->subtract_from, field_id);
1300   if (!other) {
1301     return FALSE;
1302   }
1303   if (!gst_value_subtract (&subtraction, other, value))
1304     return TRUE;
1305   if (gst_value_compare (&subtraction, other) == GST_VALUE_EQUAL) {
1306     g_value_unset (&subtraction);
1307     return FALSE;
1308   } else {
1309     structure = gst_structure_copy (e->subtract_from);
1310     gst_structure_id_set_value (structure, field_id, &subtraction);
1311     g_value_unset (&subtraction);
1312     e->put_into = g_slist_prepend (e->put_into, structure);
1313     return TRUE;
1314   }
1315 }
1316
1317 static gboolean
1318 gst_caps_structure_subtract (GSList ** into, const GstStructure * minuend,
1319     const GstStructure * subtrahend)
1320 {
1321   SubtractionEntry e;
1322   gboolean ret;
1323
1324   e.subtract_from = minuend;
1325   e.put_into = NULL;
1326
1327   ret = gst_structure_foreach ((GstStructure *) subtrahend,
1328       gst_caps_structure_subtract_field, &e);
1329   if (ret) {
1330     *into = e.put_into;
1331   } else {
1332     GSList *walk;
1333
1334     for (walk = e.put_into; walk; walk = g_slist_next (walk)) {
1335       gst_structure_free (walk->data);
1336     }
1337     g_slist_free (e.put_into);
1338   }
1339   return ret;
1340 }
1341
1342 /**
1343  * gst_caps_subtract:
1344  * @minuend: #GstCaps to substract from
1345  * @subtrahend: #GstCaps to substract
1346  *
1347  * Subtracts the @subtrahend from the @minuend.
1348  * <note>This function does not work reliably if optional properties for caps
1349  * are included on one caps and omitted on the other.</note>
1350  *
1351  * Returns: the resulting caps
1352  */
1353 GstCaps *
1354 gst_caps_subtract (const GstCaps * minuend, const GstCaps * subtrahend)
1355 {
1356   guint i, j, sublen;
1357   GstStructure *min;
1358   GstStructure *sub;
1359   GstCaps *dest = NULL, *src;
1360
1361   g_return_val_if_fail (minuend != NULL, NULL);
1362   g_return_val_if_fail (subtrahend != NULL, NULL);
1363
1364   if (CAPS_IS_EMPTY (minuend) || CAPS_IS_ANY (subtrahend)) {
1365     return gst_caps_new_empty ();
1366   }
1367   if (CAPS_IS_EMPTY_SIMPLE (subtrahend))
1368     return _gst_caps_copy (minuend);
1369
1370   /* FIXME: Do we want this here or above?
1371      The reason we need this is that there is no definition about what
1372      ANY means for specific types, so it's not possible to reduce ANY partially
1373      You can only remove everything or nothing and that is done above.
1374      Note: there's a test that checks this behaviour. */
1375   g_return_val_if_fail (!CAPS_IS_ANY (minuend), NULL);
1376   sublen = subtrahend->structs->len;
1377   g_assert (sublen > 0);
1378
1379   src = _gst_caps_copy (minuend);
1380   for (i = 0; i < sublen; i++) {
1381     guint srclen;
1382
1383     sub = gst_caps_get_structure_unchecked (subtrahend, i);
1384     if (dest) {
1385       gst_caps_unref (src);
1386       src = dest;
1387     }
1388     dest = gst_caps_new_empty ();
1389     srclen = src->structs->len;
1390     for (j = 0; j < srclen; j++) {
1391       min = gst_caps_get_structure_unchecked (src, j);
1392       if (gst_structure_get_name_id (min) == gst_structure_get_name_id (sub)) {
1393         GSList *list;
1394
1395         if (gst_caps_structure_subtract (&list, min, sub)) {
1396           GSList *walk;
1397
1398           for (walk = list; walk; walk = g_slist_next (walk)) {
1399             gst_caps_append_structure_unchecked (dest,
1400                 (GstStructure *) walk->data);
1401           }
1402           g_slist_free (list);
1403         } else {
1404           gst_caps_append_structure_unchecked (dest, gst_structure_copy (min));
1405         }
1406       } else {
1407         gst_caps_append_structure_unchecked (dest, gst_structure_copy (min));
1408       }
1409     }
1410     if (CAPS_IS_EMPTY_SIMPLE (dest)) {
1411       gst_caps_unref (src);
1412       return dest;
1413     }
1414   }
1415
1416   gst_caps_unref (src);
1417   gst_caps_do_simplify (dest);
1418   return dest;
1419 }
1420
1421 /* union operation */
1422
1423 #if 0
1424 static GstStructure *
1425 gst_caps_structure_union (const GstStructure * struct1,
1426     const GstStructure * struct2)
1427 {
1428   int i;
1429   GstStructure *dest;
1430   const GstStructureField *field1;
1431   const GstStructureField *field2;
1432   int ret;
1433
1434   /* FIXME this doesn't actually work */
1435
1436   if (struct1->name != struct2->name)
1437     return NULL;
1438
1439   dest = gst_structure_id_empty_new (struct1->name);
1440
1441   for (i = 0; i < struct1->fields->len; i++) {
1442     GValue dest_value = { 0 };
1443
1444     field1 = GST_STRUCTURE_FIELD (struct1, i);
1445     field2 = gst_structure_id_get_field (struct2, field1->name);
1446
1447     if (field2 == NULL) {
1448       continue;
1449     } else {
1450       if (gst_value_union (&dest_value, &field1->value, &field2->value)) {
1451         gst_structure_set_value (dest, g_quark_to_string (field1->name),
1452             &dest_value);
1453       } else {
1454         ret = gst_value_compare (&field1->value, &field2->value);
1455       }
1456     }
1457   }
1458
1459   return dest;
1460 }
1461 #endif
1462
1463 /**
1464  * gst_caps_union:
1465  * @caps1: a #GstCaps to union
1466  * @caps2: a #GstCaps to union
1467  *
1468  * Creates a new #GstCaps that contains all the formats that are in
1469  * either @caps1 and @caps2.
1470  *
1471  * Returns: the new #GstCaps
1472  */
1473 GstCaps *
1474 gst_caps_union (const GstCaps * caps1, const GstCaps * caps2)
1475 {
1476   GstCaps *dest1;
1477   GstCaps *dest2;
1478
1479   /* NULL pointers are no correct GstCaps */
1480   g_return_val_if_fail (caps1 != NULL, NULL);
1481   g_return_val_if_fail (caps2 != NULL, NULL);
1482
1483   if (CAPS_IS_EMPTY (caps1))
1484     return _gst_caps_copy (caps2);
1485
1486   if (CAPS_IS_EMPTY (caps2))
1487     return _gst_caps_copy (caps1);
1488
1489   if (CAPS_IS_ANY (caps1) || CAPS_IS_ANY (caps2))
1490     return gst_caps_new_any ();
1491
1492   dest1 = _gst_caps_copy (caps1);
1493   dest2 = _gst_caps_copy (caps2);
1494   gst_caps_append (dest1, dest2);
1495
1496   gst_caps_do_simplify (dest1);
1497   return dest1;
1498 }
1499
1500 /* normalize/simplify operations */
1501
1502 typedef struct _NormalizeForeach
1503 {
1504   GstCaps *caps;
1505   GstStructure *structure;
1506 }
1507 NormalizeForeach;
1508
1509 static gboolean
1510 gst_caps_normalize_foreach (GQuark field_id, const GValue * value, gpointer ptr)
1511 {
1512   NormalizeForeach *nf = (NormalizeForeach *) ptr;
1513   GValue val = { 0 };
1514   guint i;
1515
1516   if (G_VALUE_TYPE (value) == GST_TYPE_LIST) {
1517     guint len = gst_value_list_get_size (value);
1518     for (i = 1; i < len; i++) {
1519       const GValue *v = gst_value_list_get_value (value, i);
1520       GstStructure *structure = gst_structure_copy (nf->structure);
1521
1522       gst_structure_id_set_value (structure, field_id, v);
1523       gst_caps_append_structure_unchecked (nf->caps, structure);
1524     }
1525
1526     gst_value_init_and_copy (&val, gst_value_list_get_value (value, 0));
1527     gst_structure_id_set_value (nf->structure, field_id, &val);
1528     g_value_unset (&val);
1529
1530     return FALSE;
1531   }
1532   return TRUE;
1533 }
1534
1535 /**
1536  * gst_caps_normalize:
1537  * @caps: a #GstCaps to normalize
1538  *
1539  * Creates a new #GstCaps that represents the same set of formats as
1540  * @caps, but contains no lists.  Each list is expanded into separate
1541  * @GstStructures.
1542  *
1543  * Returns: the new #GstCaps
1544  */
1545 GstCaps *
1546 gst_caps_normalize (const GstCaps * caps)
1547 {
1548   NormalizeForeach nf;
1549   GstCaps *newcaps;
1550   guint i;
1551
1552   g_return_val_if_fail (GST_IS_CAPS (caps), NULL);
1553
1554   newcaps = _gst_caps_copy (caps);
1555   nf.caps = newcaps;
1556
1557   for (i = 0; i < gst_caps_get_size (newcaps); i++) {
1558     nf.structure = gst_caps_get_structure_unchecked (newcaps, i);
1559
1560     while (!gst_structure_foreach (nf.structure,
1561             gst_caps_normalize_foreach, &nf));
1562   }
1563
1564   return newcaps;
1565 }
1566
1567 static gint
1568 gst_caps_compare_structures (gconstpointer one, gconstpointer two)
1569 {
1570   gint ret;
1571   const GstStructure *struct1 = *((const GstStructure **) one);
1572   const GstStructure *struct2 = *((const GstStructure **) two);
1573
1574   /* FIXME: this orders alphabetically, but ordering the quarks might be faster
1575      So what's the best way? */
1576   ret = strcmp (gst_structure_get_name (struct1),
1577       gst_structure_get_name (struct2));
1578   if (ret)
1579     return ret;
1580
1581   return gst_structure_n_fields (struct2) - gst_structure_n_fields (struct1);
1582 }
1583
1584 typedef struct
1585 {
1586   GQuark name;
1587   GValue value;
1588   GstStructure *compare;
1589 }
1590 UnionField;
1591
1592 static gboolean
1593 gst_caps_structure_figure_out_union (GQuark field_id, const GValue * value,
1594     gpointer user_data)
1595 {
1596   UnionField *u = user_data;
1597   const GValue *val = gst_structure_id_get_value (u->compare, field_id);
1598
1599   if (!val) {
1600     if (u->name)
1601       g_value_unset (&u->value);
1602     return FALSE;
1603   }
1604   if (gst_value_compare (val, value) == GST_VALUE_EQUAL)
1605     return TRUE;
1606   if (u->name) {
1607     g_value_unset (&u->value);
1608     return FALSE;
1609   }
1610   u->name = field_id;
1611   gst_value_union (&u->value, val, value);
1612   return TRUE;
1613 }
1614
1615 static gboolean
1616 gst_caps_structure_simplify (GstStructure ** result,
1617     const GstStructure * simplify, GstStructure * compare)
1618 {
1619   GSList *list;
1620   UnionField field = { 0, {0,}, NULL };
1621
1622   /* try to subtract to get a real subset */
1623   if (gst_caps_structure_subtract (&list, simplify, compare)) {
1624     if (list == NULL) {         /* no result */
1625       *result = NULL;
1626       return TRUE;
1627     } else if (list->next == NULL) {    /* one result */
1628       *result = list->data;
1629       g_slist_free (list);
1630       return TRUE;
1631     } else {                    /* multiple results */
1632       g_slist_foreach (list, (GFunc) gst_structure_free, NULL);
1633       g_slist_free (list);
1634       list = NULL;
1635     }
1636   }
1637
1638   /* try to union both structs */
1639   field.compare = compare;
1640   if (gst_structure_foreach ((GstStructure *) simplify,
1641           gst_caps_structure_figure_out_union, &field)) {
1642     gboolean ret = FALSE;
1643
1644     /* now we know all of simplify's fields are the same in compare
1645      * but at most one field: field.name */
1646     if (G_IS_VALUE (&field.value)) {
1647       if (gst_structure_n_fields (simplify) == gst_structure_n_fields (compare)) {
1648         gst_structure_id_set_value (compare, field.name, &field.value);
1649         *result = NULL;
1650         ret = TRUE;
1651       }
1652       g_value_unset (&field.value);
1653     } else if (gst_structure_n_fields (simplify) <=
1654         gst_structure_n_fields (compare)) {
1655       /* compare is just more specific, will be optimized away later */
1656       /* FIXME: do this here? */
1657       GST_LOG ("found a case that will be optimized later.");
1658     } else {
1659       gchar *one = gst_structure_to_string (simplify);
1660       gchar *two = gst_structure_to_string (compare);
1661
1662       GST_ERROR
1663           ("caps mismatch: structures %s and %s claim to be possible to unify, but aren't",
1664           one, two);
1665       g_free (one);
1666       g_free (two);
1667     }
1668     return ret;
1669   }
1670
1671   return FALSE;
1672 }
1673
1674 static void
1675 gst_caps_switch_structures (GstCaps * caps, GstStructure * old,
1676     GstStructure * new, gint i)
1677 {
1678   gst_structure_set_parent_refcount (old, NULL);
1679   gst_structure_free (old);
1680   gst_structure_set_parent_refcount (new, &GST_CAPS_REFCOUNT (caps));
1681   g_ptr_array_index (caps->structs, i) = new;
1682 }
1683
1684 /**
1685  * gst_caps_do_simplify:
1686  * @caps: a #GstCaps to simplify
1687  *
1688  * Modifies the given @caps inplace into a representation that represents the
1689  * same set of formats, but in a simpler form.  Component structures that are
1690  * identical are merged.  Component structures that have values that can be
1691  * merged are also merged.
1692  *
1693  * Returns: TRUE, if the caps could be simplified
1694  */
1695 gboolean
1696 gst_caps_do_simplify (GstCaps * caps)
1697 {
1698   GstStructure *simplify, *compare, *result = NULL;
1699   gint i, j, start;
1700   gboolean changed = FALSE;
1701
1702   g_return_val_if_fail (caps != NULL, FALSE);
1703   g_return_val_if_fail (IS_WRITABLE (caps), FALSE);
1704
1705   if (gst_caps_get_size (caps) < 2)
1706     return FALSE;
1707
1708   g_ptr_array_sort (caps->structs, gst_caps_compare_structures);
1709
1710   start = caps->structs->len - 1;
1711   for (i = caps->structs->len - 1; i >= 0; i--) {
1712     simplify = gst_caps_get_structure_unchecked (caps, i);
1713     if (gst_structure_get_name_id (simplify) !=
1714         gst_structure_get_name_id (gst_caps_get_structure_unchecked (caps,
1715                 start)))
1716       start = i;
1717     for (j = start; j >= 0; j--) {
1718       if (j == i)
1719         continue;
1720       compare = gst_caps_get_structure_unchecked (caps, j);
1721       if (gst_structure_get_name_id (simplify) !=
1722           gst_structure_get_name_id (compare)) {
1723         break;
1724       }
1725       if (gst_caps_structure_simplify (&result, simplify, compare)) {
1726         if (result) {
1727           gst_caps_switch_structures (caps, simplify, result, i);
1728           simplify = result;
1729         } else {
1730           gst_caps_remove_structure (caps, i);
1731           start--;
1732           break;
1733         }
1734         changed = TRUE;
1735       }
1736     }
1737   }
1738
1739   if (!changed)
1740     return FALSE;
1741
1742   /* gst_caps_do_simplify (caps); */
1743   return TRUE;
1744 }
1745
1746 /* utility */
1747
1748 /**
1749  * gst_caps_to_string:
1750  * @caps: a #GstCaps
1751  *
1752  * Converts @caps to a string representation.  This string representation
1753  * can be converted back to a #GstCaps by gst_caps_from_string().
1754  *
1755  * For debugging purposes its easier to do something like this:
1756  * |[
1757  * GST_LOG ("caps are %" GST_PTR_FORMAT, caps);
1758  * ]|
1759  * This prints the caps in human readble form.
1760  *
1761  * Returns: (transfer full): a newly allocated string representing @caps.
1762  */
1763 gchar *
1764 gst_caps_to_string (const GstCaps * caps)
1765 {
1766   guint i, slen, clen;
1767   GString *s;
1768
1769   /* NOTE:  This function is potentially called by the debug system,
1770    * so any calls to gst_log() (and GST_DEBUG(), GST_LOG(), etc.)
1771    * should be careful to avoid recursion.  This includes any functions
1772    * called by gst_caps_to_string.  In particular, calls should
1773    * not use the GST_PTR_FORMAT extension.  */
1774
1775   if (caps == NULL) {
1776     return g_strdup ("NULL");
1777   }
1778   if (CAPS_IS_ANY (caps)) {
1779     return g_strdup ("ANY");
1780   }
1781   if (CAPS_IS_EMPTY_SIMPLE (caps)) {
1782     return g_strdup ("EMPTY");
1783   }
1784
1785   /* estimate a rough string length to avoid unnecessary reallocs in GString */
1786   slen = 0;
1787   clen = caps->structs->len;
1788   for (i = 0; i < clen; i++) {
1789     slen +=
1790         STRUCTURE_ESTIMATED_STRING_LEN (gst_caps_get_structure_unchecked (caps,
1791             i));
1792   }
1793
1794   s = g_string_sized_new (slen);
1795   for (i = 0; i < clen; i++) {
1796     GstStructure *structure;
1797
1798     if (i > 0) {
1799       /* ';' is now added by gst_structure_to_string */
1800       g_string_append_c (s, ' ');
1801     }
1802
1803     structure = gst_caps_get_structure_unchecked (caps, i);
1804     priv_gst_structure_append_to_gstring (structure, s);
1805   }
1806   if (s->len && s->str[s->len - 1] == ';') {
1807     /* remove latest ';' */
1808     s->str[--s->len] = '\0';
1809   }
1810   return g_string_free (s, FALSE);
1811 }
1812
1813 static gboolean
1814 gst_caps_from_string_inplace (GstCaps * caps, const gchar * string)
1815 {
1816   GstStructure *structure;
1817   gchar *s;
1818
1819   if (strcmp ("ANY", string) == 0) {
1820     GST_CAPS_FLAGS (caps) = GST_CAPS_FLAGS_ANY;
1821     return TRUE;
1822   }
1823   if (strcmp ("EMPTY", string) == 0) {
1824     return TRUE;
1825   }
1826
1827   structure = gst_structure_from_string (string, &s);
1828   if (structure == NULL) {
1829     return FALSE;
1830   }
1831   gst_caps_append_structure_unchecked (caps, structure);
1832
1833   do {
1834
1835     while (g_ascii_isspace (*s))
1836       s++;
1837     if (*s == '\0') {
1838       break;
1839     }
1840     structure = gst_structure_from_string (s, &s);
1841     if (structure == NULL) {
1842       return FALSE;
1843     }
1844     gst_caps_append_structure_unchecked (caps, structure);
1845
1846   } while (TRUE);
1847
1848   return TRUE;
1849 }
1850
1851 /**
1852  * gst_caps_from_string:
1853  * @string: a string to convert to #GstCaps
1854  *
1855  * Converts @caps from a string representation.
1856  *
1857  * Returns: (transfer full): a newly allocated #GstCaps
1858  */
1859 GstCaps *
1860 gst_caps_from_string (const gchar * string)
1861 {
1862   GstCaps *caps;
1863
1864   g_return_val_if_fail (string, FALSE);
1865
1866   caps = gst_caps_new_empty ();
1867   if (gst_caps_from_string_inplace (caps, string)) {
1868     return caps;
1869   } else {
1870     gst_caps_unref (caps);
1871     return NULL;
1872   }
1873 }
1874
1875 static void
1876 gst_caps_transform_to_string (const GValue * src_value, GValue * dest_value)
1877 {
1878   g_return_if_fail (G_IS_VALUE (src_value));
1879   g_return_if_fail (G_IS_VALUE (dest_value));
1880   g_return_if_fail (G_VALUE_HOLDS (src_value, GST_TYPE_CAPS));
1881   g_return_if_fail (G_VALUE_HOLDS (dest_value, G_TYPE_STRING)
1882       || G_VALUE_HOLDS (dest_value, G_TYPE_POINTER));
1883
1884   dest_value->data[0].v_pointer =
1885       gst_caps_to_string (src_value->data[0].v_pointer);
1886 }