From ec1991ba992640171eabe2f5d1029a2836624c58 Mon Sep 17 00:00:00 2001
From: Robin Haberkorn <robin.haberkorn@googlemail.com>
Date: Thu, 27 Sep 2012 03:00:09 +0200
Subject: make layer list double-linked

 * does not in any way affect rendering performance
 * inserting is a bit more complex, but still O(1)
 * deleting is a lot faster (O(1)) since we do not have to search by name
---
 layer.cpp      | 32 ++++++++++++++------------------
 layer.h        |  8 ++++----
 osc_server.cpp |  4 +---
 3 files changed, 19 insertions(+), 25 deletions(-)

diff --git a/layer.cpp b/layer.cpp
index 6dbfa71..fdb3a3d 100644
--- a/layer.cpp
+++ b/layer.cpp
@@ -16,37 +16,33 @@ Layer::Layer(const char *_name) : mutex(SDL_CreateMutex()), name(strdup(_name))
 void
 LayerList::insert(int pos, Layer *layer)
 {
-	Layer *cur, **prev;
+	Layer *cur, *prev = NULL;
 
 	lock();
 
-	SLIST_FOREACH_PREVPTR(cur, prev, &head, layers)
+	LIST_FOREACH(cur, &head, layers) {
 		if (!pos--)
 			break;
+		prev = cur;
+	}
 
-	SLIST_NEXT(layer, layers) = cur;
-	*prev = layer;
+	if (prev)
+		LIST_INSERT_AFTER(prev, layer, layers);
+	else
+		LIST_INSERT_HEAD(&head, layer, layers);
 
 	unlock();
 }
 
-bool
-LayerList::delete_by_name(const char *name)
+void
+LayerList::delete_layer(Layer *layer)
 {
-	Layer *cur, **prev;
-
 	lock();
-
-	SLIST_FOREACH_PREVPTR(cur, prev, &head, layers)
-		if (!strcmp(cur->name, name)) {
-			*prev = SLIST_NEXT(cur, layers);
-			delete cur;
-			break;
-		}
-
+	LIST_REMOVE(layer, layers);
 	unlock();
 
-	return cur == NULL;
+	/* layer is guaranteed not to be rendered */
+	delete layer;
 }
 
 void
@@ -57,7 +53,7 @@ LayerList::render(SDL_Surface *target)
 	lock();
 
 	Layer *cur;
-	SLIST_FOREACH(cur, &head, layers) {
+	LIST_FOREACH(cur, &head, layers) {
 		cur->lock();
 		cur->frame(target);
 		cur->unlock();
diff --git a/layer.h b/layer.h
index d06707c..21fab50 100644
--- a/layer.h
+++ b/layer.h
@@ -27,7 +27,7 @@ public:
 		const char *types;
 	};
 
-	SLIST_ENTRY(Layer) layers;
+	LIST_ENTRY(Layer) layers;
 
 	char *name;
 
@@ -92,7 +92,7 @@ private:
 };
 
 class LayerList {
-	SLIST_HEAD(layers_head, Layer) head;
+	LIST_HEAD(layers_head, Layer) head;
 
 	SDL_mutex *mutex;
 
@@ -110,7 +110,7 @@ class LayerList {
 public:
 	LayerList() : mutex(SDL_CreateMutex())
 	{
-		SLIST_INIT(&head);
+		LIST_INIT(&head);
 	}
 	~LayerList()
 	{
@@ -118,7 +118,7 @@ public:
 	}
 
 	void insert(int pos, Layer *layer);
-	bool delete_by_name(const char *name);
+	void delete_layer(Layer *layer);
 	void render(SDL_Surface *target);
 };
 
diff --git a/osc_server.cpp b/osc_server.cpp
index 2178303..c3eb328 100644
--- a/osc_server.cpp
+++ b/osc_server.cpp
@@ -107,9 +107,7 @@ dtor_generic_handler(const char *path,
 {
 	Layer *layer = (Layer *)user_data;
 
-	/* FIXME: double-linked list allows more effecient layer delete */
-	layers.delete_by_name(layer->name);
-
+	layers.delete_layer(layer);
 	osc_server.del_method("", "%s", path);
 
 	return 0;
-- 
cgit v1.2.3