bug-cvs
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Proposed branch tag performance patch for feature


From: Mark D. Baushke
Subject: Re: Proposed branch tag performance patch for feature
Date: Wed, 03 Jan 2007 22:23:15 -0800

Hi Kelly,

I believe I have ported your changes to the FEATURE branch.
To get your own copy of the sources I am using do the following:

  cvs -d :pserver:anonymous@cvs.savannah.nongnu.org:/cvsroot/cvs co ccvs
  patch -p0 < this-message

I have just kicked off a 'make check' to test everything, but the
branches5 test (a ported version of your branches3 test) passed unit
test for each of these:

  sh sanity.sh `pwd`/cvs branches5
  sh sanity.sh -r `pwd`/cvs branches5
  sh sanity.sh -p `pwd`/cvs branches5
  sh sanity.sh -B `pwd`/cvs branches5
  sh sanity.sh -Br `pwd`/cvs branches5
  sh sanity.sh -Bp `pwd`/cvs branches5

So, it is probably as good as I can get for now.

As I said, if it passes all of these tests, I'll do my best to commit
it.

It would help if you would verify the performance improvement on a copy
of your own worst-case repository and point out any errors in
transcription that I may have made by accident.

        Thanks,
        -- Mark

Here is the patch...

Index: src/ChangeLog
===================================================================
RCS file: /cvsroot/cvs/ccvs/src/ChangeLog,v
retrieving revision 1.3502
diff -u -p -r1.3502 ChangeLog
--- src/ChangeLog       19 Dec 2006 04:24:03 -0000      1.3502
+++ src/ChangeLog       4 Jan 2007 06:13:52 -0000
@@ -1,3 +1,14 @@
+2007-01-03  Mark D. Baushke  <mdb@gnu.org>
+
+       * rcs.c (findnextmagicrev_proc): New function to find the
+       all rev numbers with the required number of dots and matching
+       initial substring.
+       (findnextmagicrev): New function to walk the symbolic tag list
+       calling findnextmagicrev_proc() to get a list of used rev numbers
+       and choose the highest suitable one.
+       (RCS_magicrev): Use findnextmagicrev().
+       (Based on a patch provided by Kelly F. Hickel <kfh@mqsoftware.com>)
+ 
 2006-12-18  Mark D. Baushke  <mdb@gnu.org>
 
        * cvs.h (checksum_t): New typedef union for md5 checksum
Index: src/rcs.c
===================================================================
RCS file: /cvsroot/cvs/ccvs/src/rcs.c,v
retrieving revision 1.382
diff -u -p -r1.382 rcs.c
--- src/rcs.c   7 Sep 2006 19:47:14 -0000       1.382
+++ src/rcs.c   4 Jan 2007 06:13:52 -0000
@@ -143,6 +143,8 @@ static void putdeltatext (FILE *, Deltat
 static FILE *rcs_internal_lockfile (char *);
 static void rcs_internal_unlockfile (FILE *, char *);
 static char *rcs_lockfilename (const char *);
+static int findnextmagicrev (RCSNode *rcs, char *rev, int default_rv);
+static int findnextmagicrev_proc (Node *p, void *closure);
 
 /* The RCS file reading functions are called a lot, and they do some
    string comparisons.  This macro speeds things up a bit by skipping
@@ -2499,17 +2501,27 @@ RCS_magicrev (RCSNode *rcs, char *rev)
     xrev = xmalloc (strlen (rev) + 14); /* enough for .0.number */
     check_rev = xrev;
 
-    local_branch_num = getenv("CVS_LOCAL_BRANCH_NUM");
+    local_branch_num = getenv ("CVS_LOCAL_BRANCH_NUM");
     if (local_branch_num)
     {
-      rev_num = atoi(local_branch_num);
+      rev_num = atoi (local_branch_num);
       if (rev_num < 2)
        rev_num = 2;
       else
        rev_num &= ~1;
+
+      /* Find the next unused magic rev,
+       * if none are found, it should return 2.
+       */
+      rev_num = findnextmagicrev (rcs, rev, rev_num);
     }
     else
-      rev_num = 2;
+    {
+       /* Find the next unused magic rev,
+        * if none are found, it should return 2.
+        */
+       rev_num = findnextmagicrev (rcs, rev, 2);
+    }
 
     /* only look at even numbered branches */
     for ( ; ; rev_num += 2)
@@ -9369,3 +9381,188 @@ getfullCVSname(char *CVSname, char **pat
     }
     return CVSname;
 }
+
+/* closure structure to communicate through walklist */
+struct findnextmagicrev_info
+{
+    char *target_rev;
+    int target_rev_dots;
+    int target_rev_len;
+    List *rev_list;
+};
+
+/* sort a list assuming that the data members are integers */
+static int
+findnextmagicrev_sortfunc (const Node *p, const Node *q)
+{
+    /* We want the highest value sorted first, to make it easy to find */
+    return ((int)q->data - (int)p->data);
+}
+
+/* free a list node where the data member is an integer */
+static void
+findnextmagicrev_delproc (Node *p)
+{
+    /* Do nothing, it's not a pointer */
+    p->data = 0;
+}
+
+/*
+ * Go through the symbolic tag list, find the next unused magic
+ * branch revision.
+ *
+ * Returns defaultrv if it can't figure anything out, then the caller
+ * will end up doing a linear search.
+ */
+static int
+findnextmagicrev (RCSNode *rcs, char *rev, int defaultrv)
+{
+    int rv = defaultrv;
+    struct findnextmagicrev_info info;
+  
+    /* Tell the walklist proc how many dots we're looking for,
+     * which is the number of dots in the existing rev, plus
+     * 2.  one for RCS_MAGIC_BRANCH and one for the new rev number.
+     */
+    info.target_rev = rev;
+    info.target_rev_dots = numdots (rev) + 2;
+    info.target_rev_len = strlen (rev);
+    info.rev_list = getlist ();
+  
+    /* walk the symbols list to find the highest revision. */
+    (void) walklist (RCS_symbols (rcs), findnextmagicrev_proc, &info);
+
+    if (! list_isempty (info.rev_list))
+    {
+       /* sort the list that came back */
+       sortlist(info.rev_list, findnextmagicrev_sortfunc);
+
+       /* Get the highest numeric value */
+       rv = (int)info.rev_list->list->next->data;  
+
+       /* adjust to next even number if we found something */
+       if (rv != defaultrv)
+       {
+           if ((rv % 2) != 0)
+               rv++;
+           else
+               rv += 2;
+       }
+    }
+
+    dellist (&(info.rev_list));
+    return rv;
+}
+
+/*
+ * walklist proc to find all "interesting" revs,
+ * and put them in a list for the caller to look through.
+ * Interesting is defined as having numdots+2 and same initial
+ * substring (up to the dot of numdots+1), or the second to last
+ * term indicates this is a magic branch.
+ */
+static int
+findnextmagicrev_proc (Node *p, void *closure)
+{
+    struct findnextmagicrev_info *pinfo = closure;
+    int sym_dots = numdots (p->data);
+
+    /*
+     * Quick first level screen, if the number of dots isn't right, then we
+     * don't care about this revision.
+     */
+    if (sym_dots == pinfo->target_rev_dots) 
+    {
+       /*
+        * We can't rely on being able to find the magic branch tag to
+        * find all existing branches, as that may have been deleted.
+        * So, here we're looking for revisions where the initial
+        * substring matches our target, and that have the same number
+        * of dots that revisions in the new branch will have in this
+        * case we record atoi of the second to last term in the list.
+        *
+        * We're also looking at revisions with RCS_MAGIC_BRANCH as
+        * the second to last term, for those, we record atoi of the
+        * last term in the list.
+        *
+        * Example:
+        * We're about to create a branch from 1.1, if we see
+        * revisions like 1.1.2.1, or 1.1.6.1, then we know we can't
+        * use either 2 or 6 as the new rev term, even if we don't see
+        * the symbols 1.1.0.2 and 1.1.0.6.
+        *
+        * If we see revisions like 1.1.0.8 or 1.1.0.12, we know that
+        * we can't use 8 or 12.
+        *
+        * Simply put, for revistions that have the same initial
+        * substring as our target, if the second to last term is
+        * RCS_MAGIC_BRANCH, take atoi of the last term and put it in
+        * the list, if not, take atoi of the second to last term, put
+        * it in the list.
+        */
+    
+       /*
+        * Second screen, make sure that target_rev is an initial substring
+        * of the rev we're considering.  This means doing a strncmp, then if
+        * it's the same, making sure that the one under consideration has a
+        * dot after the target rev.
+        *
+        * Check the dot first, since that's faster.
+        */
+       char *ver_str = p->data;
+       if ((ver_str[pinfo->target_rev_len] == '.') && 
+           (strncmp (pinfo->target_rev, p->data, pinfo->target_rev_len) == 0))
+       {
+           char *plast_dot = NULL;
+           char *psecond_to_last_dot = NULL;
+           int i = strlen (ver_str);
+
+           /* Get pointers in this revision to the last and second to
+            * last dots
+            */
+           while((i > 0) && ((plast_dot == 0) || (psecond_to_last_dot == 0)))
+           {
+               if (ver_str[i] == '.')
+               {
+                   if (plast_dot == 0)
+                       plast_dot = &(ver_str[i]);
+                   else
+                       psecond_to_last_dot = &(ver_str[i]);
+               }
+               i--;
+           }
+           if ((plast_dot != 0) && (psecond_to_last_dot != 0))
+           {
+               int term_to_add = 0;
+               int second_to_last_term = atoi (psecond_to_last_dot + 1);
+               if (second_to_last_term == RCS_MAGIC_BRANCH)
+               {
+                   /* We want to put the value of the last term into
+                    * the list
+                    */
+                   term_to_add = atoi (plast_dot + 1);
+               }
+               else
+               {
+                   /* We want to put the value of the second to last
+                    * term into the list
+                    */
+
+                   term_to_add = atoi (psecond_to_last_dot + 1);
+               }
+               if (term_to_add != 0)
+               {
+                   Node *n = getnode ();
+                   n->type = VARIABLE;
+                   n->key = 0;
+                   n->data = (void *)term_to_add;
+                   n->delproc = findnextmagicrev_delproc;
+
+                   /* dupe insert won't fail because we aren't using a hash */
+                   addnode (pinfo->rev_list, n); 
+               }
+           }
+       }
+    }
+    return 1;
+}
Index: src/sanity.sh
===================================================================
RCS file: /cvsroot/cvs/ccvs/src/sanity.sh,v
retrieving revision 1.1171
diff -u -p -r1.1171 sanity.sh
--- src/sanity.sh       14 Sep 2006 15:33:41 -0000      1.1171
+++ src/sanity.sh       4 Jan 2007 06:13:54 -0000
@@ -2068,7 +2068,7 @@ if test x"$*" = x; then
        tests="${tests} rdiff2 diff diffnl death death2 death-rtag"
        tests="${tests} rm-update-message rmadd rmadd2 rmadd3 resurrection"
        tests="${tests} dirs dirs2 branches branches2 branches3"
-       tests="${tests} branches4 tagc tagf tag-space"
+       tests="${tests} branches4 branches5 tagc tagf tag-space"
        tests="${tests} rcslib multibranch import importb importc importX"
        tests="$tests importX2 import-CVS import-quirks"
        tests="${tests} update-p import-after-initial branch-after-import"
@@ -8484,6 +8484,179 @@ ${SPROG} update: Updating versions"
 
 
 
+       branches5)
+         # test new faster branching code to make sure it doesn't
+         # reuse a previously used magic branch tag.
+          # Set up a repo, files, etc.
+         modify_repo mkdir $CVSROOT_DIRNAME/first-dir
+         mkdir branches5; cd branches5
+
+         dotest branches5-1 "${testcvs} -q co first-dir" ''
+         cd first-dir
+         echo 1:ancest >file1
+         echo 2:ancest >file2
+         dotest branches5-2 "${testcvs} add file1 file2" \
+"${SPROG} add: scheduling file .file1. for addition
+${SPROG} add: scheduling file .file2. for addition
+${SPROG} add: use .${SPROG} commit. to add these files permanently"
+         dotest branches5-3a "${testcvs} -q ci -m add-it" \
+"${CVSROOT_DIRNAME}/first-dir/file1,v  <--  file1
+initial revision: 1\.1
+${CVSROOT_DIRNAME}/first-dir/file2,v  <--  file2
+initial revision: 1\.1"
+
+         dotest branches5-3b "${testcvs} update -d " \
+"${SPROG} update: Updating \."
+
+         # First branch gets a commit, then the branch gets deleted.
+         # The purpose of this test is to make sure that even if the 
+          # magic branch tag is missing, we see the commits and don't
+          # consider the missing branch tag as eligible for reuse.
+         dotest branches5-4a "${testcvs} -q tag -b br3br1" \
+'T file1
+T file2'
+         dotest branches5-4b "${testcvs} -q update -r br3br1" \
+'[UP] file1
+[UP] file2'
+         echo 1:br3br1 >file1
+         dotest branches5-4c "${testcvs} -q ci -m modify" \
+"${CVSROOT_DIRNAME}/first-dir/file1,v  <--  file1
+new revision: 1\.1\.2\.1; previous revision: 1\.1"
+
+         dotest branches5-4d "${testcvs} tag -d -B br3br1 file1 file2" \
+'D file1
+D file2'
+
+
+         # Second branch gets no commits.
+         # The purpose of this test is to make sure we respect branches
+         # that don't (yet) have any changes on them.
+         dotest branches5-5a "${testcvs} -q update -r HEAD" \
+'[UP] file1
+[UP] file2'
+         echo "about to issue:${testcvs} -q tag -b br3br2" >>$LOGFILE
+         dotest branches5-5b "${testcvs} -q tag -b br3br2" \
+'T file1
+T file2'
+
+         # Third branch gets several commits so that the 4th 
+         # digit of it's revision number is 10 to test that
+         # we don't just consider the highest number in the 4th position.
+         dotest branches5-6a "${testcvs} -q update -r HEAD" ''
+         dotest branches5-6b "${testcvs} -q tag -b br3br3" \
+'T file1
+T file2'
+
+         dotest branches5-6c "${testcvs} -q update -r br3br3" \
+'[UP] file1
+[UP] file2'
+         echo 1:br3br3.1 >file1
+         dotest branches5-6d "${testcvs} -q ci -m modify" \
+"${CVSROOT_DIRNAME}/first-dir/file1,v  <--  file1
+new revision: 1\.1\.6\.1; previous revision: 1\.1"
+         echo 1:br3br3.2 >file1
+         dotest branches5-6e "${testcvs} -q ci -m modify" \
+"${CVSROOT_DIRNAME}/first-dir/file1,v  <--  file1
+new revision: 1\.1\.6\.2; previous revision: 1\.1\.6\.1"
+
+         echo 1:br3br3.3 >file1
+         dotest branches5-6f "${testcvs} -q ci -m modify" \
+"${CVSROOT_DIRNAME}/first-dir/file1,v  <--  file1
+new revision: 1\.1\.6\.3; previous revision: 1\.1\.6\.2"
+
+         echo 1:br3br3.4 >file1
+         dotest branches5-6g "${testcvs} -q ci -m modify" \
+"${CVSROOT_DIRNAME}/first-dir/file1,v  <--  file1
+new revision: 1\.1\.6\.4; previous revision: 1\.1\.6\.3"
+
+         echo 1:br3br3.5 >file1
+         dotest branches5-6h "${testcvs} -q ci -m modify" \
+"${CVSROOT_DIRNAME}/first-dir/file1,v  <--  file1
+new revision: 1\.1\.6\.5; previous revision: 1\.1\.6\.4"
+
+         echo 1:br3br3.6 >file1
+         dotest branches5-6i "${testcvs} -q ci -m modify" \
+"${CVSROOT_DIRNAME}/first-dir/file1,v  <--  file1
+new revision: 1\.1\.6\.6; previous revision: 1\.1\.6\.5"
+
+         echo 1:br3br3.7 >file1
+         dotest branches5-6i "${testcvs} -q ci -m modify" \
+"${CVSROOT_DIRNAME}/first-dir/file1,v  <--  file1
+new revision: 1\.1\.6\.7; previous revision: 1\.1\.6\.6"
+
+         echo 1:br3br3.8 >file1
+         dotest branches5-6k "${testcvs} -q ci -m modify" \
+"${CVSROOT_DIRNAME}/first-dir/file1,v  <--  file1
+new revision: 1\.1\.6\.8; previous revision: 1\.1\.6\.7"
+
+         echo 1:br3br3.9 >file1
+         dotest branches5-6l "${testcvs} -q ci -m modify" \
+"${CVSROOT_DIRNAME}/first-dir/file1,v  <--  file1
+new revision: 1\.1\.6\.9; previous revision: 1\.1\.6\.8"
+
+         echo 1:br3br3.10 >file1
+         dotest branches5-6m "${testcvs} -q ci -m modify" \
+"${CVSROOT_DIRNAME}/first-dir/file1,v  <--  file1
+new revision: 1\.1\.6\.10; previous revision: 1\.1\.6\.9"
+
+         # Create a tag on revision 1.1.6.10 so it shows up in RCS symbols
+         dotest branches5-6n "${testcvs} -q tag br3br3_rev_10" \
+'T file1
+T file2'
+
+         # Create the fourth branch, ensure that it gets the correct magic
+         # branch tag.
+         dotest branches5-7a "${testcvs} -q update -r HEAD" \
+'[UP] file1
+[UP] file2'
+         dotest branches5-7b "${testcvs} -q tag -b br3br4" \
+'T file1
+T file2'
+         dotest branches5-7c "${testcvs} -q update -r br3br4" \
+'[UP] file1
+[UP] file2'
+         echo 1:br3br4 >file1
+         dotest branches5-7d "${testcvs} -q ci -m modify" \
+"${CVSROOT_DIRNAME}/first-dir/file1,v  <--  file1
+new revision: 1\.1\.8\.1; previous revision: 1\.1"
+
+
+         # Make a commit on the trunk, then create the fifth branch,
+         # make sure we get the correct revision.
+         #
+         # The purpose of this test is to make sure that we're only
+         # looking at the revisions we should be. If we didn't, this
+         # branch would end up being 1.2.0.10 instead of 1.2.0.2
+         cd ..
+         rm -rf first-dir
+         dotest branches5-8a "${testcvs} -q co first-dir" \
+'U first-dir/file1
+U first-dir/file2'
+         cd first-dir
+         echo 1:HEAD.2 >file1
+         dotest branches5-8b "${testcvs} -q ci -m modify" \
+"${CVSROOT_DIRNAME}/first-dir/file1,v  <--  file1
+new revision: 1\.2; previous revision: 1\.1"
+
+         dotest branches5-8c "${testcvs} -q tag -b br3br5" \
+'T file1
+T file2'
+         dotest branches5-8d "${testcvs} -q update -r br3br5" \
+'[UP] file1
+[UP] file2'
+         echo 1:br3br5 >file1
+         dotest branches5-8e "${testcvs} -q ci -m modify" \
+"${CVSROOT_DIRNAME}/first-dir/file1,v  <--  file1
+new revision: 1\.2\.2\.1; previous revision: 1\.2"
+
+
+         dokeep
+         cd ../..
+         modify_repo rm -rf ${CVSROOT_DIRNAME}/first-dir
+         rm -rf branches5
+         ;;
+
+
        tagc)
          # Test the tag -c option.
          mkdir 1; cd 1





reply via email to

[Prev in Thread] Current Thread [Next in Thread]