SAVE

try last Ring, the one of Tree, very complicated
I think API should be different to be more readable
Split base removal and inheritance
Use as_shadow/as_drawable returning pointer
Finish insert_after in ring.hpp

5 files changed, 83 insertions, 67 deletions

diff --git a/server/display-channel-private.h b/server/display-channel-private.h
index 49edcfbf..279edada 100644
--- a/server/display-channel-private.h
+++ b/server/display-channel-private.h
@@ -45,7 +45,7 @@ struct RedSurface {
      * DrawItems, Containers, and Shadows. It is used to efficiently determine
      * which drawables overlap, and to exclude regions of drawables that are
      * obscured by other drawables */
-    Ring current;
+    TreeItemRing current;
     /* A ring of pending Drawables associated with this surface. This ring is
      * actually used for drawing. The ring is maintained in order of age, the
      * tail being the oldest drawable. */
diff --git a/server/display-channel.cpp b/server/display-channel.cpp
index 298474e3..cf07b4de 100644
--- a/server/display-channel.cpp
+++ b/server/display-channel.cpp
@@ -339,12 +339,12 @@ static void pipes_add_drawable_after(DisplayChannel *display,
 }
 
 static void current_add_drawable(DisplayChannel *display,
-                                 Drawable *drawable, RingItem *pos)
+                                 Drawable *drawable, TreeItemRing::iterator pos)
 {
     RedSurface *surface;
 
     surface = drawable->surface;
-    ring_add_after(&drawable->tree_item.siblings_link, pos);
+    surface->current.insert_after(pos, &drawable->tree_item);
     display->priv->current_list.push_front(drawable);
     surface->current_list.push_front(drawable);
     drawable->refs++;
@@ -357,7 +357,7 @@ static void current_remove_drawable(DisplayChannel *display, Drawable *item)
     /* todo: move all to unref? */
     video_stream_trace_add_drawable(display, item);
     draw_item_remove_shadow(&item->tree_item);
-    ring_remove(&item->tree_item.siblings_link);
+    TreeItemRing::remove(&item->tree_item);
     drawable_unref(item);
 }
 
@@ -373,19 +373,22 @@ static void drawable_remove_from_pipes(Drawable *drawable)
     }
 }
 
-/* This function should never be called for Shadow TreeItems */
+/**
+ * Remove an item from the tree and all its descendent.
+ * This function should never be called for Shadow TreeItems.
+ */
 static void current_remove(DisplayChannel *display, TreeItem *item)
 {
     TreeItem *now = item;
+    TreeItemRing::iterator now_it(item);
 
     /* depth-first tree traversal, TODO: do a to tree_foreach()? */
     for (;;) {
         Container *container_of_now = now->container;
-        RingItem *ring_item;
 
         if (now->type == TREE_ITEM_TYPE_DRAWABLE) {
             Drawable *drawable = SPICE_CONTAINEROF(static_cast<DrawItem*>(now), Drawable, tree_item);
-            ring_item = now->siblings_link.prev;
+            --now_it;
             drawable_remove_from_pipes(drawable);
             current_remove_drawable(display, drawable);
         } else {
@@ -393,16 +396,16 @@ static void current_remove(DisplayChannel *display, TreeItem *item)
 
             spice_assert(now->type == TREE_ITEM_TYPE_CONTAINER);
 
-            if ((ring_item = ring_get_head(&now_as_container->items))) {
+            if (!now_as_container->items.empty()) {
                 /* descend into the container's child ring and continue
                  * iterating and removing those children */
-                now = SPICE_CONTAINEROF(ring_item, TreeItem, siblings_link);
+                now_it = now_as_container->items.begin();
                 continue;
             }
             /* This item is a container but it has no children, so reset our
              * iterator to the item's previous sibling and free this empty
              * container */
-            ring_item = now->siblings_link.prev;
+            --now_it;
             container_free(now_as_container);
         }
         if (now == item) {
@@ -414,10 +417,11 @@ static void current_remove(DisplayChannel *display, TreeItem *item)
         }
 
         /* Increment the iterator to the next sibling. Note that if an item was
-         * removed above, ring_item will have been reset to the item before the
+         * removed above, now_it will have been reset to the item before the
          * item that was removed */
-        if ((ring_item = ring_next(&container_of_now->items, ring_item))) {
-            now = SPICE_CONTAINEROF(ring_item, TreeItem, siblings_link);
+        ++now_it;
+        if (now_it != container_of_now->items.end()) {
+            now = &*now_it;
         } else {
             /* there is no next sibling, so move one level up the tree */
             now = container_of_now;
@@ -427,11 +431,7 @@ static void current_remove(DisplayChannel *display, TreeItem *item)
 
 static void current_remove_all(DisplayChannel *display, RedSurface *surface)
 {
-    Ring *ring = &surface->current;
-    RingItem *ring_item;
-
-    while ((ring_item = ring_get_head(ring))) {
-        TreeItem *now = SPICE_CONTAINEROF(ring_item, TreeItem, siblings_link);
+    while (!surface->current.empty()) {
         /* NOTE: current_remove() should never be called on Shadow type items
          * or we will hit an assert. Fortunately, the 'current' ring is ordered
          * in such a way that a DrawItem will always be placed before its
@@ -439,7 +439,7 @@ static void current_remove_all(DisplayChannel *display, RedSurface *surface)
          * result in the associated Shadow item being removed from the tree,
          * this loop will never call current_remove() on a Shadow item unless
          * we change the order that items are inserted into the tree */
-        current_remove(display, now);
+        current_remove(display, &*surface->current.begin());
     }
 }
 
@@ -474,7 +474,7 @@ static bool current_add_equal(DisplayChannel *display, DrawItem *item, TreeItem
         int add_after = !!other_drawable->stream &&
                         is_drawable_independent_from_surfaces(drawable);
         video_stream_maintenance(display, drawable, other_drawable);
-        current_add_drawable(display, drawable, &other->siblings_link);
+        current_add_drawable(display, drawable, TreeItemRing::iterator(other));
         other_drawable->refs++;
         current_remove_drawable(display, other_drawable);
         if (add_after) {
@@ -517,7 +517,7 @@ static bool current_add_equal(DisplayChannel *display, DrawItem *item, TreeItem
         break;
     case QXL_EFFECT_OPAQUE_BRUSH:
         if (is_same_geometry(drawable, other_drawable)) {
-            current_add_drawable(display, drawable, &other->siblings_link);
+            current_add_drawable(display, drawable, TreeItemRing::iterator(other));
             drawable_remove_from_pipes(other_drawable);
             current_remove_drawable(display, other_drawable);
             pipes_add_drawable(display, drawable);
@@ -575,8 +575,9 @@ static bool current_add_equal(DisplayChannel *display, DrawItem *item, TreeItem
  * @top_ring: ???
  * @frame_candidate: ???
  */
-static void __exclude_region(DisplayChannel *display, Ring *ring, TreeItem *item, QRegion *rgn,
-                             Ring **top_ring, Drawable *frame_candidate)
+static void __exclude_region(DisplayChannel *display,
+                             TreeItemRing *ring, TreeItem *item, QRegion *rgn,
+                             TreeItemRing **top_ring, Drawable *frame_candidate)
 {
     QRegion and_rgn;
     stat_start(&display->priv->__exclude_stat, start_time);
@@ -699,25 +700,25 @@ static void __exclude_region(DisplayChannel *display, Ring *ring, TreeItem *item
  * @frame_candidate: usually callers pass NULL, sometimes it's the drawable
  *      that's being added to the 'current' ring. TODO: What is its purpose?
  */
-static void exclude_region(DisplayChannel *display, Ring *ring, RingItem *ring_item,
+static void exclude_region(DisplayChannel *display,
+                           TreeItemRing *ring, TreeItemRing::iterator item_it,
                            QRegion *rgn, TreeItem **last, Drawable *frame_candidate)
 {
-    Ring *top_ring;
     stat_start(&display->priv->exclude_stat, start_time);
 
-    if (!ring_item) {
+    if (item_it == ring->end()) {
         return;
     }
 
-    top_ring = ring;
+    auto top_ring = ring;
 
     for (;;) {
-        TreeItem *now = SPICE_CONTAINEROF(ring_item, TreeItem, siblings_link);
+        auto now = &*item_it;
         Container *container = now->container;
 
         spice_assert(!region_is_empty(&now->rgn));
 
-        /* check whether the ring_item item intersects the passed-in region */
+        /* check whether the item intersects the passed-in region */
         if (region_intersects(rgn, &now->rgn)) {
             /* remove the overlapping portions of region and now->rgn, among
              * other things. See documentation for __exclude_region() */
@@ -727,28 +728,29 @@ static void exclude_region(DisplayChannel *display, Ring *ring, RingItem *ring_i
                 /* __exclude_region() does not remove the region of shadow-type
                  * items */
                 spice_assert(now->type != TREE_ITEM_TYPE_SHADOW);
-                ring_item = now->siblings_link.prev;
+                --item_it;
                 /* if __exclude_region() removed the entire region for this
                  * sibling item, remove it from the 'current' tree */
                 current_remove(display, now);
                 if (last && *last == now) {
                     /* the caller wanted to stop at this item, but this item
                      * has been removed, so we set @last to the next item */
-                    SPICE_VERIFY(SPICE_OFFSETOF(TreeItem, siblings_link) == 0);
-                    *last = reinterpret_cast<TreeItem *>(ring_next(ring, ring_item));
+                    auto it = item_it;
+                    *last = &*++it;
                 }
             } else if (now->type == TREE_ITEM_TYPE_CONTAINER) {
                 /* if this sibling is a container type, descend into the
                  * container's child ring and continue iterating */
                 Container *now_container = CONTAINER(now);
-                if ((ring_item = ring_get_head(&now_container->items))) {
+                if (!now_container->items.empty()) {
                     ring = &now_container->items;
-                    spice_assert(SPICE_CONTAINEROF(ring_item, TreeItem, siblings_link)->container);
+                    // XXX what is this ??
+                    // spice_assert(SPICE_CONTAINEROF(ring_item, TreeItem, siblings_link)->container);
                     continue;
                 }
-                /* container had no children, so reset ring_item to the
+                /* container had no children, so reset item_it to the
                  * container itself */
-                ring_item = &now->siblings_link;
+                item_it = TreeItemRing::iterator(now);
             }
 
             if (region_is_empty(rgn)) {
@@ -759,11 +761,9 @@ static void exclude_region(DisplayChannel *display, Ring *ring, RingItem *ring_i
             }
         }
 
-        SPICE_VERIFY(SPICE_OFFSETOF(TreeItem, siblings_link) == 0);
         /* if this is the last item to check, or if the current ring is
          * completed, don't go any further */
-        while ((last && *last == reinterpret_cast<TreeItem *>(ring_item)) ||
-               !(ring_item = ring_next(ring, ring_item))) {
+        while ((last && *last == &*item_it) || ++item_it == ring->end()) {
             /* we're currently iterating the top ring, so we're done */
             if (ring == top_ring) {
                 stat_add(&display->priv->exclude_stat, start_time);
@@ -771,17 +771,19 @@ static void exclude_region(DisplayChannel *display, Ring *ring, RingItem *ring_i
             }
             /* we're iterating through a container child ring, so climb one
              * level up the heirarchy and continue iterating that ring */
-            ring_item = &container->siblings_link;
+            item_it = TreeItemRing::iterator(container);
             container = container->container;
-            ring = (container) ? &container->items : top_ring;
+            ring = container ? &container->items : top_ring;
         }
     }
 }
 
 /* Add a drawable @item (with a shadow) to the current ring.  The return value
  * indicates whether the new item should be added to the pipe */
-static bool current_add_with_shadow(DisplayChannel *display, Ring *ring, Drawable *item)
+static bool current_add_with_shadow(DisplayChannel *display, Drawable *item)
 {
+    auto ring = &item->surface->current;
+
     stat_start(&display->priv->add_stat, start_time);
 #ifdef RED_WORKER_STAT
     ++display->priv->add_with_shadow_count;
@@ -807,11 +809,12 @@ static bool current_add_with_shadow(DisplayChannel *display, Ring *ring, Drawabl
     }
 
     /* Prepend the shadow to the beginning of the current ring */
-    ring_add(ring, &shadow->siblings_link);
+    ring->push_front(shadow);
     /* Prepend the draw item to the beginning of the current ring. NOTE: this
      * means that the drawable is placed *before* its associated shadow in the
      * tree. Changing this order will violate several unstated assumptions */
-    current_add_drawable(display, item, ring);
+    // XXX --begin is lame
+    current_add_drawable(display, item, --ring->begin());
     if (item->tree_item.effect == QXL_EFFECT_OPAQUE) {
         QRegion exclude_rgn;
         region_clone(&exclude_rgn, &item->tree_item.rgn);
@@ -819,7 +822,8 @@ static bool current_add_with_shadow(DisplayChannel *display, Ring *ring, Drawabl
          * items already in the tree.  Start iterating through the tree
          * starting with the shadow item to avoid excluding the new item
          * itself */
-        exclude_region(display, ring, &shadow->siblings_link, &exclude_rgn, nullptr, nullptr);
+        exclude_region(display, ring, TreeItemRing::iterator(shadow),
+                       &exclude_rgn, nullptr, nullptr);
         region_destroy(&exclude_rgn);
         streams_update_visible_region(display, item);
     } else {
@@ -833,28 +837,31 @@ static bool current_add_with_shadow(DisplayChannel *display, Ring *ring, Drawabl
 
 /* Add a @drawable (without a shadow) to the current ring.
  * The return value indicates whether the new item should be added to the pipe */
-static bool current_add(DisplayChannel *display, Ring *ring, Drawable *drawable)
+static bool current_add(DisplayChannel *display, Drawable *drawable)
 {
+    auto &ring = drawable->surface->current;
     DrawItem *item = &drawable->tree_item;
-    RingItem *now;
+//    RingItem *now;
     QRegion exclude_rgn;
     RingItem *exclude_base = nullptr;
     stat_start(&display->priv->add_stat, start_time);
 
     spice_assert(!region_is_empty(&item->rgn));
     region_init(&exclude_rgn);
-    now = ring_next(ring, ring);
+
+    auto it = drawable->surface->current.begin();
+    const auto end = drawable->surface->current.end();
 
     /* check whether the new drawable region intersects any of the items
      * already in the 'current' ring */
-    while (now) {
-        TreeItem *sibling = SPICE_CONTAINEROF(now, TreeItem, siblings_link);
+    while (it != end) {
+        TreeItem *sibling = &*it;
         int test_res;
 
         if (!region_bounds_intersects(&item->rgn, &sibling->rgn)) {
             /* the bounds of the two items are totally disjoint, so no need to
              * check further. check the next item */
-            now = ring_next(ring, now);
+            ++it;
             continue;
         }
         /* bounds overlap, but check whether the regions actually overlap */
@@ -862,7 +869,7 @@ static bool current_add(DisplayChannel *display, Ring *ring, Drawable *drawable)
         if (!(test_res & REGION_TEST_SHARED)) {
             /* there's no overlap of the regions between these two items. Move
              * on to the next one. */
-            now = ring_next(ring, now);
+            ++it;
             continue;
         }
         if (sibling->type != TREE_ITEM_TYPE_SHADOW) {
@@ -885,7 +892,7 @@ static bool current_add(DisplayChannel *display, Ring *ring, Drawable *drawable)
             if (!(test_res & REGION_TEST_RIGHT_EXCLUSIVE) && item->effect == QXL_EFFECT_OPAQUE) {
                 /* the new drawable is opaque and entirely contains the sibling item */
                 Shadow *shadow;
-                int skip = now == exclude_base;
+                int skip = &*it == exclude_base;
 
                 if ((shadow = tree_item_find_shadow(sibling))) {
                     /* The sibling item was the destination of a COPY_BITS operation */
@@ -906,7 +913,7 @@ static bool current_add(DisplayChannel *display, Ring *ring, Drawable *drawable)
                          * item is obscured and has a shadow. -jjongsma
                          */
                         TreeItem *next = sibling;
-                        exclude_region(display, ring, exclude_base, &exclude_rgn, &next, nullptr);
+                        exclude_region(display, ring, TreeItemRing::iterator(exclude_base), &exclude_rgn, &next, nullptr);
                         if (next != sibling) {
                             /* the @next param is only changed if the given item
                              * was removed as a side-effect of calling
@@ -1330,13 +1337,12 @@ static void display_channel_add_drawable(DisplayChannel *display, Drawable *draw
         return;
     }
 
-    Ring *ring = &drawable->surface->current;
     int add_to_pipe;
     if (has_shadow(red_drawable)) {
-        add_to_pipe = current_add_with_shadow(display, ring, drawable);
+        add_to_pipe = current_add_with_shadow(display, drawable);
     } else {
         drawable->streamable = drawable_can_stream(display, drawable);
-        add_to_pipe = current_add(display, ring, drawable);
+        add_to_pipe = current_add(display, drawable);
     }
 
     if (add_to_pipe)
@@ -1542,7 +1548,6 @@ static Drawable *display_channel_drawable_try_new(DisplayChannel *display,
     drawable->display = display;
     drawable->refs = 1;
     drawable->creation_time = drawable->first_frame_time = spice_get_monotonic_time_ns();
-    ring_item_init(&drawable->tree_item.siblings_link);
     drawable->tree_item.type = TREE_ITEM_TYPE_DRAWABLE;
     region_init(&drawable->tree_item.rgn);
     glz_retention_init(&drawable->glz_retention);
@@ -2085,7 +2090,6 @@ display_channel_create_surface(DisplayChannel *display, uint32_t surface_id, uin
     }
 
     // finish initialization
-    ring_init(&surface->current);
     region_init(&surface->draw_dirty_region);
 
     if (display->priv->surfaces_[surface_id]) {
diff --git a/server/ring.hpp b/server/ring.hpp
index f2a3277a..aca5b9f8 100644
--- a/server/ring.hpp
+++ b/server/ring.hpp
@@ -84,6 +84,13 @@ struct Ring
 		pos->RingItem<T,n>::remove();
 		return iterator(next->to_contained());
 	}
+    /**
+     * Inserts an element after a given iterator
+     */
+    void insert_after(iterator it, T* item)
+    {
+        // XXX
+    }
 	static void remove(T *item)
 	{
 		item->RingItem<T,n>::remove();
diff --git a/server/tree.cpp b/server/tree.cpp
index b4ef75ca..6a8b8472 100644
--- a/server/tree.cpp
+++ b/server/tree.cpp
@@ -276,12 +276,12 @@ Shadow* tree_item_find_shadow(TreeItem *item)
 
 /* return the Ring containing siblings of item, falling back to @ring if @item
  * does not have a container */
-Ring *tree_item_container_items(TreeItem *item, Ring *ring)
+TreeItemRing* tree_item_container_items(TreeItem *item, TreeItemRing *ring)
 {
-    return (item->container) ? &item->container->items : ring;
+    return item->container ? &item->container->items : ring;
 }
 
-bool tree_item_contained_by(TreeItem *item, Ring *ring)
+bool tree_item_contained_by(TreeItem *item, TreeItemRing *ring)
 {
     spice_assert(item && ring);
     do {
diff --git a/server/tree.h b/server/tree.h
index 1b90a5ee..425d92eb 100644
--- a/server/tree.h
+++ b/server/tree.h
@@ -24,6 +24,7 @@
 #include <common/ring.h>
 
 #include "spice-bitmap-utils.h"
+#include "ring.hpp"
 
 #include "push-visibility.h"
 
@@ -38,8 +39,11 @@ enum {
 
 struct Container;
 
-struct TreeItem {
-    RingItem siblings_link;
+struct TreeItem:
+    public red::RingItem<TreeItem,0>
+{
+    SPICE_CXX_GLIB_ALLOCATOR
+
     uint32_t type;
     Container *container = nullptr;
     /* rgn holds the region of the item. As additional items get added to the
@@ -47,6 +51,7 @@ struct TreeItem {
      * that is obscured by other items */
     QRegion rgn;
 };
+using TreeItemRing = red::Ring<TreeItem,0>;
 
 /* A region "below" a copy, or the src region of the copy */
 struct Shadow: public TreeItem
@@ -62,7 +67,7 @@ struct Shadow: public TreeItem
 
 struct Container: public TreeItem
 {
-    Ring items;
+    TreeItemRing items;
 };
 
 #define IS_CONTAINER(item) ((item)->type == TREE_ITEM_TYPE_CONTAINER)
@@ -86,8 +91,8 @@ static inline int is_opaque_item(const TreeItem *item)
 
 void       tree_item_dump                           (TreeItem *item);
 Shadow*    tree_item_find_shadow                    (TreeItem *item);
-bool       tree_item_contained_by                   (TreeItem *item, Ring *ring);
-Ring*      tree_item_container_items                (TreeItem *item, Ring *ring);
+bool tree_item_contained_by(TreeItem *item, TreeItemRing *ring);
+TreeItemRing* tree_item_container_items(TreeItem *item, TreeItemRing *ring);
 
 void       draw_item_remove_shadow                  (DrawItem *item);
 Shadow*    shadow_new                               (DrawItem *item, const SpicePoint *delta);