[src/trunk]: src/usr.sbin/mtree Fix the "mtree -M" problem reported in PR 420...

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

details:   https://anonhg.NetBSD.org/src/rev/abd4d4a4bfbe
branches:  trunk
changeset: 747544:abd4d4a4bfbe
user:      apb <apb%NetBSD.org@localhost>
date:      Sat Sep 19 20:42:06 2009 +0000

description:
Fix the "mtree -M" problem reported in PR 42031 by Geoff Wing.
The cause of the problem was that part of the code assumed that
nodecmp() on two nodes with the same name would return 0, but in
fact nodecmp() would return -1 or +1 if one of the nodes was a
directory and the other was not.  The fix is to separate the notion
of whether or not a duplicate name was found from the notion of
where the new node should appear in the list.

diffstat:

 usr.sbin/mtree/spec.c |  129 ++++++++++++++++++++++++++++++++++++-------------
 1 files changed, 93 insertions(+), 36 deletions(-)

diffs (170 lines):

diff -r 20546a943ffd -r abd4d4a4bfbe usr.sbin/mtree/spec.c
--- a/usr.sbin/mtree/spec.c     Sat Sep 19 20:37:05 2009 +0000
+++ b/usr.sbin/mtree/spec.c     Sat Sep 19 20:42:06 2009 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: spec.c,v 1.75 2009/04/11 14:32:51 apb Exp $    */
+/*     $NetBSD: spec.c,v 1.76 2009/09/19 20:42:06 apb Exp $    */
 
 /*-
  * Copyright (c) 1989, 1993
@@ -67,13 +67,14 @@
 #if 0
 static char sccsid[] = "@(#)spec.c     8.2 (Berkeley) 4/28/95";
 #else
-__RCSID("$NetBSD: spec.c,v 1.75 2009/04/11 14:32:51 apb Exp $");
+__RCSID("$NetBSD: spec.c,v 1.76 2009/09/19 20:42:06 apb Exp $");
 #endif
 #endif /* not lint */
 
 #include <sys/param.h>
 #include <sys/stat.h>
 
+#include <assert.h>
 #include <ctype.h>
 #include <errno.h>
 #include <grp.h>
@@ -670,9 +671,18 @@
 static void
 addchild(NODE *pathparent, NODE *centry)
 {
-       NODE *cur, *insertpos;
+       NODE *samename;      /* node with the same name as centry */
+       NODE *replacepos;    /* if non-NULL, centry should replace this node */
+       NODE *insertpos;     /* if non-NULL, centry should be inserted
+                             * after this node */
+       NODE *cur;           /* for stepping through the list */
+       NODE *last;          /* the last node in the list */
        int cmp;
 
+       samename = NULL;
+       replacepos = NULL;
+       insertpos = NULL;
+       last = NULL;
        cur = pathparent->child;
        if (cur == NULL) {
                /* centry is pathparent's first and only child node so far */
@@ -684,44 +694,91 @@
         * pathparent already has at least one other child, so add the
         * centry node to the list.
         *
-        * To keep the list sorted, the new centry node will be
-        * inserted just after the existing insertpos node, if any;
-        * otherwise it will be inserted at the start of the list.
+        * We first scan through the list looking for an existing node
+        * with the same name (setting samename), and also looking
+        * for the correct position to replace or insert the new node
+        * (setting replacepos and/or insertpos).
         */
-       insertpos = NULL;
-       for (; cur != NULL; cur = cur->next) {
-               cmp = nodecmp(centry, cur);
-               if (cmp == 0) {
-                       /* existing entry; replace */
-                       replacenode(cur, centry);
-                       break;
-               } else if (cmp > 0) {
-                       /* centry appears after cur in sort order */
-                       insertpos = cur;
+       for (; cur != NULL; last = cur, cur = cur->next) {
+               if (strcmp(centry->name, cur->name) == 0) {
+                       samename = cur;
+               }
+               if (mtree_Sflag) {
+                       cmp = nodecmp(centry, cur);
+                       if (cmp == 0) {
+                               replacepos = cur;
+                       } else if (cmp > 0) {
+                               insertpos = cur;
+                       }
                }
-               if ((mtree_Sflag && cmp < 0) || cur->next == NULL) {
+       }
+       if (! mtree_Sflag) {
+               if (samename != NULL) {
+                       /* replace node with same name */
+                       replacepos = samename;
+               } else {
+                       /* add new node at end of list */
+                       insertpos = last;
+               }
+       }
+
+       if (samename != NULL) {
+               /*
+                * We found a node with the same name above.  Call
+                * replacenode(), which will either exit with an error,
+                * or replace the information in the samename node and
+                * free the information in the centry node.
+                */
+               replacenode(samename, centry);
+               if (samename == replacepos) {
+                       /* The just-replaced node was in the correct position */
+                       return;
+               }
+               if (samename == insertpos || samename->prev == insertpos) {
                        /*
-                        * centry appears before cur in sort order,
-                        * or we reached the end of the list; insert
-                        * centry either just after insertpos, or at the
-                        * beginning of the list.  If we are not sorting,
-                        * then always append to the list.
+                        * We thought the new node should be just before
+                        * or just after the replaced node, but that would
+                        * be equivalent to just retaining the replaced node.
                         */
-                       if (!mtree_Sflag)
-                               insertpos = cur;
-                       if (insertpos) {
-                               centry->next = insertpos->next;
-                               insertpos->next = centry;
-                               centry->prev = insertpos;
-                               if (centry->next)
-                                       centry->next->prev = centry;
-                       } else {
-                               pathparent->child->prev = centry;
-                               centry->next = pathparent->child;
-                               pathparent->child = centry;
-                       }
-                       break;
+                       return;
+               }
+
+               /*
+                * The just-replaced node is in the wrong position in
+                * the list.  This can happen if sort order depends on
+                * criteria other than the node name.
+                *
+                * Make centry point to the just-replaced node.  Unlink
+                * the just-replaced node from the list, and allow it to
+                * be insterted in the correct position later.
+                */
+               centry = samename;
+               if (centry->prev)
+                       centry->prev->next = centry->next;
+               else {
+                       /* centry->next is the new head of the list */
+                       pathparent->child = centry->next;
+                       assert(centry->next != NULL);
                }
+               if (centry->next)
+                       centry->next->prev = centry->prev;
+               centry->prev = NULL;
+               centry->next = NULL;
+       }
+
+       if (insertpos == NULL) {
+               /* insert centry at the beginning of the list */
+               pathparent->child->prev = centry;
+               centry->next = pathparent->child;
+               centry->prev = NULL;
+               pathparent->child = centry;
+       } else {
+               /* insert centry into the list just after insertpos */
+               centry->next = insertpos->next;
+               insertpos->next = centry;
+               centry->prev = insertpos;
+               if (centry->next)
+                       centry->next->prev = centry;
        }
        return;
 }