[src/trunk]: src/sys/kern change cache_purgevfs() from O(N^2) to O(N).

[chs <chs%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/3e977459ab93
branches:  trunk
changeset: 499582:3e977459ab93
user:      chs <chs%NetBSD.org@localhost>
date:      Fri Nov 24 05:02:23 2000 +0000

description:
change cache_purgevfs() from O(N^2) to O(N).
use queue.h macros where possible.

diffstat:

 sys/kern/vfs_cache.c |  24 +++++++++---------------
 1 files changed, 9 insertions(+), 15 deletions(-)

diffs (82 lines):

diff -r 242499010223 -r 3e977459ab93 sys/kern/vfs_cache.c
--- a/sys/kern/vfs_cache.c      Fri Nov 24 03:59:07 2000 +0000
+++ b/sys/kern/vfs_cache.c      Fri Nov 24 05:02:23 2000 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: vfs_cache.c,v 1.26 2000/11/08 14:28:13 ad Exp $        */
+/*     $NetBSD: vfs_cache.c,v 1.27 2000/11/24 05:02:23 chs Exp $       */
 
 /*
  * Copyright (c) 1989, 1993
@@ -122,7 +122,7 @@
                return (-1);
        }
        ncpp = &nchashtbl[(cnp->cn_hash ^ dvp->v_id) & nchash];
-       for (ncp = ncpp->lh_first; ncp != 0; ncp = ncp->nc_hash.le_next) {
+       LIST_FOREACH(ncp, ncpp, nc_hash) {
                if (ncp->nc_dvp == dvp &&
                    ncp->nc_dvpid == dvp->v_id &&
                    ncp->nc_nlen == cnp->cn_namelen &&
@@ -271,7 +271,7 @@
 
        nvcpp = &ncvhashtbl[(vp->v_id & ncvhash)];
 
-       for (ncp = nvcpp->lh_first; ncp != 0; ncp = ncp->nc_vhash.le_next) {
+       LIST_FOREACH(ncp, nvcpp, nc_vhash) {
                if ((ncp->nc_vp == vp) &&
                    (ncp->nc_vpid == vp->v_id) &&
                    ((dvp = ncp->nc_dvp) != 0) &&
@@ -338,9 +338,9 @@
         */
        if (numcache < numvnodes) {
                ncp = pool_get(&namecache_pool, PR_WAITOK);
-               memset((char *)ncp, 0, sizeof(*ncp));
+               memset(ncp, 0, sizeof(*ncp));
                numcache++;
-       } else if ((ncp = nclruhead.tqh_first) != NULL) {
+       } else if ((ncp = TAILQ_FIRST(&nclruhead)) != NULL) {
                TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
                if (ncp->nc_hash.le_prev != 0) {
                        LIST_REMOVE(ncp, nc_hash);
@@ -424,7 +424,7 @@
        if (nextvnodeid != 0)
                return;
        for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
-               for (ncp = ncpp->lh_first; ncp != 0; ncp = ncp->nc_hash.le_next) {
+               LIST_FOREACH(ncp, ncpp, nc_hash) {
                        ncp->nc_vpid = 0;
                        ncp->nc_dvpid = 0;
                }
@@ -434,11 +434,7 @@
 
 /*
  * Cache flush, a whole filesystem; called when filesys is umounted to
- * remove entries that would now be invalid
- *
- * The line "nxtcp = nclruhead.tqh_first" near the end is to avoid potential
- * problems if the cache lru chain is modified while we are dumping the inode.
- * This makes the algorithm O(n^2), but do you think I care?
+ * remove entries that would now be invalid.
  */
 void
 cache_purgevfs(mp)
@@ -446,9 +442,9 @@
 {
        struct namecache *ncp, *nxtcp;
 
-       for (ncp = nclruhead.tqh_first; ncp != 0; ncp = nxtcp) {
+       for (ncp = TAILQ_FIRST(&nclruhead); ncp != NULL; ncp = nxtcp) {
+               nxtcp = TAILQ_NEXT(ncp, nc_lru);
                if (ncp->nc_dvp == NULL || ncp->nc_dvp->v_mount != mp) {
-                       nxtcp = ncp->nc_lru.tqe_next;
                        continue;
                }
                /* free the resources we had */
@@ -463,8 +459,6 @@
                        LIST_REMOVE(ncp, nc_vhash);
                        ncp->nc_vhash.le_prev = 0;
                }
-               /* cause rescan of list, it may have altered */
-               nxtcp = nclruhead.tqh_first;
                TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru);
        }
 }