cluster: STABLE2 - qdisk: optimize list append operations

[Fabio M. Di Nitto]

Gitweb:        http://git.fedorahosted.org/git/cluster.git?p=cluster.git;a=commitdiff;h=640bfefbe007b5ed601175145392b02d68adb722
Commit:        640bfefbe007b5ed601175145392b02d68adb722
Parent:        d623a0dd5badd8459f3e1a5b989bedbb08d1097f
Author:        Fabio M. Di Nitto <fdinitto@redhat.com>
AuthorDate:    Wed Feb 11 11:37:55 2009 +0100
Committer:     Fabio M. Di Nitto <fdinitto@redhat.com>
CommitterDate: Wed Feb 11 11:44:24 2009 +0100

qdisk: optimize list append operations

makes list insertion O(1) instead of O(n) - add 'tail' to the
structure

Signed-off-by: Lon Hohberger <lhh@redhat.com>
Signed-off-by: Fabio M. Di Nitto <fdinitto@redhat.com>
---
 cman/qdisk/scandisk.c |   23 +++++++++--------------
 cman/qdisk/scandisk.h |    3 ++-
 2 files changed, 11 insertions(+), 15 deletions(-)

diff --git a/cman/qdisk/scandisk.c b/cman/qdisk/scandisk.c
index 8851fe3..39acb31 100644
--- a/cman/qdisk/scandisk.c
+++ b/cman/qdisk/scandisk.c
@@ -97,7 +97,7 @@ static void flush_dev_cache(struct devlisthead *devlisthead)
 static struct devnode *alloc_list_obj(struct devlisthead *devlisthead, int maj,
 				      int min)
 {
-	struct devnode *nextnode, *startnode;
+	struct devnode *nextnode;
 
 	nextnode = malloc(sizeof(struct devnode));
 	if (!nextnode)
@@ -105,22 +105,17 @@ static struct devnode *alloc_list_obj(struct devlisthead *devlisthead, int maj,
 
 	memset(nextnode, 0, sizeof(struct devnode));
 
-	if (!devlisthead->devnode) {
-		devlisthead->devnode = startnode = nextnode;
-	} else {
-		startnode = devlisthead->devnode;
-		while (startnode->next)
-			startnode = startnode->next;
+	if (!devlisthead->devnode)
+		devlisthead->devnode = nextnode;
+	else
+		devlisthead->tail->next = nextnode;
 
-		/* always append what we find */
-		startnode->next = nextnode;
-		startnode = nextnode;
-	}
+	devlisthead->tail = nextnode;
 
-	startnode->maj = maj;
-	startnode->min = min;
+	nextnode->maj = maj;
+	nextnode->min = min;
 
-	return startnode;
+	return nextnode;
 }
 
 /* really annoying but we have no way to know upfront how
diff --git a/cman/qdisk/scandisk.h b/cman/qdisk/scandisk.h
index 6a8aa32..394d153 100644
--- a/cman/qdisk/scandisk.h
+++ b/cman/qdisk/scandisk.h
@@ -63,6 +63,8 @@ struct devnode {
 /* each entry can be 0 if we can't scan or < 0 if there are errors */
 
 struct devlisthead {
+	struct devnode *devnode;	/* points to the first entry */
+	struct devnode *tail;	/* last entry (for fast append) */
 	time_t cache_timestamp;	/* this cache timestamp */
 	int cache_timeout;	/* for how long this cache is valid */
 	int sysfs;		/* set to 1 if we were able to scan
@@ -74,7 +76,6 @@ struct devlisthead {
 				 * /proc/mdstat */
 	int mapper;		/* set to 1 if we were able to run
 				 * something against mapper */
-	struct devnode *devnode;	/* points to the first entry */
 };
 
 typedef void (*devfilter) (struct devnode * cur, void *arg);