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