[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
Re: Proposed branch tag performance patch for feature,
Mark D. Baushke <=