caps: implement lazy caps for intersections

Implement lazy caps for gst_caps_intersect(). Fix gst_caps_can_intersect() to
not require knowing the size of caps.

1 files changed, 304 insertions, 77 deletions

diff --git a/gst/gstcaps.c b/gst/gstcaps.c
index f426fc176..1c6796343 100644
--- a/gst/gstcaps.c
+++ b/gst/gstcaps.c
@@ -1528,25 +1528,40 @@ gst_caps_structure_can_intersect (const GstStructure * struct1,
 gboolean
 gst_caps_can_intersect (const GstCaps * caps1, const GstCaps * caps2)
 {
-  guint64 i;                    /* index can be up to 2 * G_MAX_UINT */
-  guint j, k, len1, len2;
-  GstStructure *struct1;
-  GstStructure *struct2;
+#define LEN1 caps1->structs->len
+#define LEN2 caps2->structs->len
+#define DONE1 !CAPS_IS_LAZY (caps1)
+#define DONE2 !CAPS_IS_LAZY (caps2)
+  guint64 i = G_GUINT64_CONSTANT (0);   /* index can be up to 2 * G_MAXUINT */
+  guint j = 0, k = 0;
+  GstStructure *s1;
+  GstStructure *s2;
 
   g_return_val_if_fail (GST_IS_CAPS (caps1), FALSE);
   g_return_val_if_fail (GST_IS_CAPS (caps2), FALSE);
 
+  GST_INFO ("caps1=%p: caps2=%p", caps1, caps2);
+
   /* caps are exactly the same pointers */
-  if (G_UNLIKELY (caps1 == caps2))
+  if (G_UNLIKELY (caps1 == caps2)) {
+    GST_INFO ("caps are same pointers");
     return TRUE;
+  }
 
   /* empty caps on either side, return empty */
-  if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
+  if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2))) {
+    GST_INFO ("some caps are empty");
     return FALSE;
+  }
 
   /* one of the caps is any */
-  if (G_UNLIKELY (CAPS_IS_ANY (caps1) || CAPS_IS_ANY (caps2)))
+  if (G_UNLIKELY (CAPS_IS_ANY (caps1) || CAPS_IS_ANY (caps2))) {
+    GST_INFO ("some caps are any");
     return TRUE;
+  }
+
+  GST_INFO ("caps1=%p: cur-size=%d, lazy-done=%d", caps1, LEN1, DONE1);
+  GST_INFO ("caps2=%p: cur-size=%d, lazy-done=%d", caps2, LEN2, DONE2);
 
   /* run zigzag on top line then right line, this preserves the caps order
    * much better than a simple loop.
@@ -1564,32 +1579,256 @@ gst_caps_can_intersect (const GstCaps * caps1, const GstCaps * caps2)
    * the structures diagonally down, then we iterate over the caps2
    * structures.
    */
-  len1 = caps1->structs->len;
-  len2 = caps2->structs->len;
-  for (i = 0; i < len1 + len2 - 1; i++) {
-    /* superset index goes from 0 to sgst_caps_structure_intersectuperset->structs->len-1 */
-    j = MIN (i, len1 - 1);
-    /* subset index stays 0 until i reaches superset->structs->len, then it
-     * counts up from 1 to subset->structs->len - 1 */
-    k = MAX (0, i - j);
+  while (TRUE) {
+    if (G_UNLIKELY (DONE1 && DONE2 && (i >= LEN1 + LEN2 - 1))) {
+      GST_DEBUG ("can_intersect done: FALSE");
+      return FALSE;
+    }
 
-    /* now run the diagonal line, end condition is the left or bottom
-     * border */
-    while (k < len2) {
-      struct1 = gst_caps_get_structure_unchecked (caps1, j);
-      struct2 = gst_caps_get_structure_unchecked (caps2, k);
+    GST_LOG ("intersecting: %" G_GUINT64_FORMAT "(%d+%d), %d, %d [%d,%d]",
+        i, LEN1, LEN2, j, k, DONE1, DONE2);
 
-      if (gst_caps_structure_can_intersect (struct1, struct2)) {
-        return TRUE;
+    if (!DONE1 && (j >= LEN1)) {
+      if (!(s1 = gst_caps_get_structure (caps1, j)))
+        goto wrap;
+    } else {
+      s1 = gst_caps_get_structure_unchecked (caps1, j);
+    }
+
+    if (!DONE2 && (k >= LEN2)) {
+      if (!(s2 = gst_caps_get_structure (caps2, k))) {
+        /* start a new diagonal */
+        i++;
+        goto wrap;
       }
-      /* move down left */
-      k++;
-      if (G_UNLIKELY (j == 0))
-        break;                  /* so we don't roll back to G_MAXUINT */
+    } else {
+      s2 = gst_caps_get_structure_unchecked (caps2, k);
+    }
+
+    if (G_UNLIKELY (DONE1 && DONE2 && (i >= LEN1 + LEN2 - 1))) {
+      GST_DEBUG ("can_intersect done: FALSE");
+      return FALSE;
+    }
+
+    GST_LOG ("intersecting: %" G_GUINT64_FORMAT "(%d+%d), %d, %d", i,
+        LEN1, LEN2, j, k);
+    GST_LOG ("intersecting: %" GST_PTR_FORMAT " and %" GST_PTR_FORMAT, s1, s2);
+
+    if (gst_caps_structure_can_intersect (s1, s2)) {
+      GST_DEBUG ("can_intersect done: TRUE");
+      return TRUE;
+    }
+
+    /* move down left */
+    if (j == 0) {
+      /* start a new diagonal */
+      i++;
+      goto wrap;
+    } else {
       j--;
+      if (DONE2 && k >= (LEN2 - 1)) {
+        /* start a new diagonal */
+        i++;
+        goto wrap;
+      } else {
+        k++;
+      }
+      continue;
     }
+  wrap:
+    /* caps1 index goes from 0 to caps1_len-1 */
+    if (DONE1)
+      j = MIN (i, LEN1 - 1);
+    else
+      j = i;
+    /* caps2 index stays 0 until i reaches caps1_len, then it counts
+     * up from 1 to caps2_len-1 */
+    k = MAX (0, i - j);
   }
-  return FALSE;
+#undef LEN1
+#undef LEN2
+#undef DONE1
+#undef DONE2
+}
+
+typedef struct _GstCapsIntersectionIterator
+{
+  GstIterator it;
+  const GstCaps *caps1, *caps2;
+  guint j, k;
+  guint64 i;
+} GstCapsIntersectionIterator;
+
+/*
+ * when caps1 aka j overruns, we just clamp:
+ * - if caps1.len=10 and j=11, then we continue at j,k=10,1, instead of j,k=11,0
+ *   for j=12, we continue at j,k=10,2
+ * when caps2 aka k overruns, we start a new diagonal i
+ */
+static void
+gst_caps_intersection_iterator_wrap_seq (GstCapsIntersectionIterator * it)
+{
+  /* caps1 index goes from 0 to caps1_len-1 */
+  if (!CAPS_IS_LAZY (it->caps1))
+    it->j = MIN (it->i, it->caps1->structs->len - 1);
+  else
+    it->j = it->i;
+  /* caps2 index stays 0 until i reaches caps1_len, then it counts
+   * up from 1 to caps2_len-1 */
+  it->k = MAX (0, it->i - it->j);
+}
+
+static GstIteratorResult
+gst_caps_intersection_iterator_next (GstCapsIntersectionIterator * it,
+    gpointer * result)
+{
+#define LEN1 it->caps1->structs->len
+#define LEN2 it->caps2->structs->len
+#define DONE1 !CAPS_IS_LAZY (it->caps1)
+#define DONE2 !CAPS_IS_LAZY (it->caps2)
+  GstStructure *s1 = NULL, *s2 = NULL, *si;
+
+restart:
+  if (G_UNLIKELY (DONE1 && DONE2 && (it->i >= LEN1 + LEN2 - 1))) {
+    GST_INFO ("intersecting done");
+    return GST_ITERATOR_DONE;
+  }
+
+  GST_LOG ("intersecting: %" G_GUINT64_FORMAT "(%d+%d), %d, %d [%d,%d]",
+      it->i, LEN1, LEN2, it->j, it->k, DONE1, DONE2);
+  if (!DONE1 && (it->j >= LEN1)) {
+    if (!(s1 = gst_caps_get_structure (it->caps1, it->j))) {
+      /* we reached the end, recalculated the position */
+      gst_caps_intersection_iterator_wrap_seq (it);
+      goto restart;
+    }
+  } else {
+    s1 = gst_caps_get_structure_unchecked (it->caps1, it->j);
+  }
+
+  if (!DONE2 && (it->k >= LEN2)) {
+    if (!(s2 = gst_caps_get_structure (it->caps2, it->k))) {
+      /* we reached the end, start a new diagonal */
+      it->i++;
+      gst_caps_intersection_iterator_wrap_seq (it);
+      goto restart;
+    }
+  } else {
+    s2 = gst_caps_get_structure_unchecked (it->caps2, it->k);
+  }
+
+  if (G_UNLIKELY (DONE1 && DONE2 && (it->i >= LEN1 + LEN2 - 1))) {
+    GST_DEBUG ("intersecting done");
+    return GST_ITERATOR_DONE;
+  }
+
+  GST_LOG ("intersecting: %" G_GUINT64_FORMAT "(%d+%d), %d, %d [%p,%p]",
+      it->i, LEN1, LEN2, it->j, it->k, s1, s2);
+  GST_LOG ("intersecting: %" GST_PTR_FORMAT " and %" GST_PTR_FORMAT, s1, s2);
+
+  si = gst_caps_structure_intersect (s1, s2);
+
+  /* move down left */
+  if (it->j == 0) {
+    /* start a new diagonal */
+    it->i++;
+    gst_caps_intersection_iterator_wrap_seq (it);
+  } else {
+    it->j--;
+    if (DONE2 && it->k >= (LEN2 - 1)) {
+      /* start a new diagonal */
+      it->i++;
+      gst_caps_intersection_iterator_wrap_seq (it);
+    } else {
+      it->k++;
+    }
+  }
+
+  if (!si)
+    goto restart;
+
+  *result = si;
+  return GST_ITERATOR_OK;
+#undef LEN1
+#undef LEN2
+#undef DONE1
+#undef DONE2
+}
+
+static void
+gst_caps_intersection_iterator_resync (GstCapsIntersectionIterator * it)
+{
+  it->j = it->k = 0;
+  it->i = G_GUINT64_CONSTANT (0);
+
+  GST_INFO ("caps1=%p: cur-size=%d, lazy-done=%d", it->caps1,
+      it->caps1->structs->len, !CAPS_IS_LAZY (it->caps1));
+  GST_INFO ("caps2=%p: cur-size=%d, lazy-done=%d", it->caps2,
+      it->caps2->structs->len, !CAPS_IS_LAZY (it->caps2));
+}
+
+static void
+gst_caps_intersection_iterator_free (GstCapsIntersectionIterator * it)
+{
+  gst_caps_unref ((GstCaps *) it->caps1);
+  gst_caps_unref ((GstCaps *) it->caps2);
+  g_free (it);
+}
+
+static GstStructure *
+gst_caps_intersection_eval_structure (GstCaps * caps, guint index,
+    gpointer user_data)
+{
+  GstIterator *it = (GstIterator *) user_data;
+  GstIteratorResult res;
+  gpointer item;
+  GstStructure *s = NULL;
+
+  res = gst_iterator_next (it, &item);
+  switch (res) {
+    case GST_ITERATOR_OK:
+      s = (GstStructure *) item;
+      break;
+    default:
+      break;
+  }
+  return s;
+}
+
+static void
+gst_caps_intersection_free (const GstCaps * caps, gpointer user_data)
+{
+  gst_iterator_free ((GstIterator *) user_data);
+}
+
+static GstCaps *
+gst_caps_intersection_copy (const GstCaps * caps, gpointer user_data)
+{
+  GstCapsIntersectionIterator *new_it;
+  GstCapsIntersectionIterator *old_it = (GstCapsIntersectionIterator *)
+      user_data;
+  static guint32 cookie_hack = 0;
+
+  GST_INFO ("copy lazy caps=%p: cur-size=%d", caps, caps->structs->len);
+
+  new_it = (GstCapsIntersectionIterator *)
+      gst_iterator_new (sizeof (GstCapsIntersectionIterator),
+      GST_TYPE_STRUCTURE,
+      /*GST_OBJECT_GET_LOCK (XXX) */ NULL,
+      &cookie_hack,
+      (GstIteratorNextFunction) gst_caps_intersection_iterator_next,
+      (GstIteratorItemFunction) NULL,
+      (GstIteratorResyncFunction) gst_caps_intersection_iterator_resync,
+      (GstIteratorFreeFunction) gst_caps_intersection_iterator_free);
+
+  new_it->i = old_it->i;
+  new_it->caps1 = gst_caps_ref ((GstCaps *) old_it->caps1);
+  new_it->j = old_it->j;
+  new_it->caps2 = gst_caps_ref ((GstCaps *) old_it->caps2);
+  new_it->k = old_it->k;
+
+  return gst_caps_new_lazy (gst_caps_intersection_eval_structure,
+      gst_caps_intersection_free, gst_caps_intersection_copy, new_it);
 }
 
 /**
@@ -1605,75 +1844,63 @@ gst_caps_can_intersect (const GstCaps * caps1, const GstCaps * caps2)
 GstCaps *
 gst_caps_intersect (const GstCaps * caps1, const GstCaps * caps2)
 {
-  guint64 i;                    /* index can be up to 2 * G_MAX_UINT */
-  guint j, k, len1, len2;
-
-  GstStructure *struct1;
-  GstStructure *struct2;
-  GstCaps *dest;
-  GstStructure *istruct;
+  GstCapsIntersectionIterator *it;
+  GstCaps *result;
+  static guint32 cookie_hack = 0;
 
   g_return_val_if_fail (GST_IS_CAPS (caps1), NULL);
   g_return_val_if_fail (GST_IS_CAPS (caps2), NULL);
 
   /* caps are exactly the same pointers, just copy one caps */
-  if (G_UNLIKELY (caps1 == caps2))
+  if (G_UNLIKELY (caps1 == caps2)) {
+    GST_INFO ("caps are same pointers");
     return gst_caps_copy (caps1);
+  }
 
   /* empty caps on either side, return empty */
-  if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2)))
+  if (G_UNLIKELY (CAPS_IS_EMPTY (caps1) || CAPS_IS_EMPTY (caps2))) {
+    GST_INFO ("some caps are empty");
     return gst_caps_new_empty ();
+  }
 
   /* one of the caps is any, just copy the other caps */
-  if (G_UNLIKELY (CAPS_IS_ANY (caps1)))
+  if (G_UNLIKELY (CAPS_IS_ANY (caps1))) {
+    GST_INFO ("caps1 in any");
     return gst_caps_copy (caps2);
-  if (G_UNLIKELY (CAPS_IS_ANY (caps2)))
+  }
+  if (G_UNLIKELY (CAPS_IS_ANY (caps2))) {
+    GST_INFO ("caps2 in any");
     return gst_caps_copy (caps1);
+  }
 
-  dest = gst_caps_new_empty ();
+  GST_INFO ("intersect caps1=%p: cur-size=%d, caps2=%p: cur-size=%d",
+      caps1, caps1->structs->len, caps2, caps2->structs->len);
+  GST_LOG ("caps1=%" GST_PTR_FORMAT, caps1);
+  GST_LOG ("caps2=%" GST_PTR_FORMAT, caps2);
 
-  /* run zigzag on top line then right line, this preserves the caps order
-   * much better than a simple loop.
-   *
-   * This algorithm zigzags over the caps structures as demonstrated in
-   * the folowing matrix:
-   *
-   *          caps1
-   *       +-------------
-   *       | 1  2  4  7
-   * caps2 | 3  5  8 10
-   *       | 6  9 11 12
-   *
-   * First we iterate over the caps1 structures (top line) intersecting
-   * the structures diagonally down, then we iterate over the caps2
-   * structures.
+  /* - we don't need an ItemFunction because we create new items in _next
+   * - we ref the caps and thus they can't change, we still need a dummy cookie
+   * - we have no lock
    */
-  len1 = caps1->structs->len;
-  len2 = caps2->structs->len;
-  for (i = 0; i < len1 + len2 - 1; i++) {
-    /* caps1 index goes from 0 to caps1->structs->len-1 */
-    j = MIN (i, len1 - 1);
-    /* caps2 index stays 0 until i reaches caps1->structs->len, then it counts
-     * up from 1 to caps2->structs->len - 1 */
-    k = MAX (0, i - j);
+  it = (GstCapsIntersectionIterator *)
+      gst_iterator_new (sizeof (GstCapsIntersectionIterator),
+      GST_TYPE_STRUCTURE,
+      /*GST_OBJECT_GET_LOCK (XXX) */ NULL,
+      &cookie_hack,
+      (GstIteratorNextFunction) gst_caps_intersection_iterator_next,
+      (GstIteratorItemFunction) NULL,
+      (GstIteratorResyncFunction) gst_caps_intersection_iterator_resync,
+      (GstIteratorFreeFunction) gst_caps_intersection_iterator_free);
 
-    /* now run the diagonal line, end condition is the left or bottom
-     * border */
-    while (k < len2) {
-      struct1 = gst_caps_get_structure_unchecked (caps1, j);
-      struct2 = gst_caps_get_structure_unchecked (caps2, k);
+  it->caps1 = gst_caps_ref ((GstCaps *) caps1);
+  it->caps2 = gst_caps_ref ((GstCaps *) caps2);
 
-      istruct = gst_caps_structure_intersect (struct1, struct2);
+  gst_caps_intersection_iterator_resync (it);
 
-      gst_caps_append_structure (dest, istruct);
-      /* move down left */
-      k++;
-      if (G_UNLIKELY (j == 0))
-        break;                  /* so we don't roll back to G_MAXUINT */
-      j--;
-    }
-  }
-  return dest;
+  result = gst_caps_new_lazy (gst_caps_intersection_eval_structure,
+      gst_caps_intersection_free, gst_caps_intersection_copy, it);
+
+  return result;
 }
 
 /* subtract operation */