From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 32427 invoked by alias); 11 Feb 2009 10:39:19 -0000 Received: (qmail 32420 invoked by alias); 11 Feb 2009 10:39:19 -0000 X-SWARE-Spam-Status: No, hits=-1.3 required=5.0 tests=AWL,BAYES_00,J_CHICKENPOX_66,SPF_HELO_PASS X-Spam-Status: No, hits=-1.3 required=5.0 tests=AWL,BAYES_00,J_CHICKENPOX_66,SPF_HELO_PASS X-Spam-Check-By: sourceware.org X-Spam-Checker-Version: SpamAssassin 3.2.5 (2008-06-10) on bastion.fedora.phx.redhat.com Subject: cluster: STABLE3 - qdisk: optimize list append operations To: cluster-cvs-relay@redhat.com X-Project: Cluster Project X-Git-Module: cluster.git X-Git-Refname: refs/heads/STABLE3 X-Git-Reftype: branch X-Git-Oldrev: eadf95f2a6e0ee01af107921ab7c3b306df32fb9 X-Git-Newrev: 1bd2905ffd9b6d414b88c2d0200067292f83ca33 From: "Fabio M. Di Nitto" Message-Id: <20090211103859.B6568120198@lists.fedorahosted.org> Date: Wed, 11 Feb 2009 10:39:00 -0000 X-Scanned-By: MIMEDefang 2.58 on 172.16.52.254 Mailing-List: contact cluster-cvs-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Post: List-Help: , Sender: cluster-cvs-owner@sourceware.org X-SW-Source: 2009-q1/txt/msg00422.txt.bz2 Gitweb: http://git.fedorahosted.org/git/cluster.git?p=cluster.git;a=commitdiff;h=1bd2905ffd9b6d414b88c2d0200067292f83ca33 Commit: 1bd2905ffd9b6d414b88c2d0200067292f83ca33 Parent: eadf95f2a6e0ee01af107921ab7c3b306df32fb9 Author: Fabio M. Di Nitto AuthorDate: Wed Feb 11 11:37:55 2009 +0100 Committer: Fabio M. Di Nitto CommitterDate: Wed Feb 11 11:37:55 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 Signed-off-by: Fabio M. Di Nitto --- 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);