Index: cvs/src/rcs.c diff -c cvs/src/rcs.c:1.1.1.1 cvs/src/rcs.c:1.3 *** cvs/src/rcs.c:1.1.1.1 Tue Jun 22 15:36:02 2004 --- cvs/src/rcs.c Tue Jul 6 10:03:42 2004 *************** *** 88,94 **** static void rcsbuf_cache_close PROTO ((void)); static void rcsbuf_cache_open PROTO ((RCSNode *, long, FILE **, struct rcsbuffer *)); ! static int checkmagic_proc PROTO((Node *p, void *closure)); static void do_branches PROTO((List * list, char *val)); static void do_symbols PROTO((List * list, char *val)); static void do_locks PROTO((List * list, char *val)); --- 88,95 ---- static void rcsbuf_cache_close PROTO ((void)); static void rcsbuf_cache_open PROTO ((RCSNode *, long, FILE **, struct rcsbuffer *)); ! /*static int checkmagic_proc PROTO((Node *p, void *closure));*/ ! static int checkmagic_proc PROTO((Node *p)); static void do_branches PROTO((List * list, char *val)); static void do_symbols PROTO((List * list, char *val)); static void do_locks PROTO((List * list, char *val)); *************** *** 2495,2500 **** --- 2496,2527 ---- * * Note: We assume that REV is an RCS revision and not a branch number. */ + + /* ---------------- ajw --------------------- + + The version of this as distributed is highly inefficient if there + are many branch symbols. Something like 98% of the time in long + tag -b operations is spent here, and in the checkmagic_proc (strcmp) + that it calls. + + It has an n**2 scan, from rev 2 onwards, comparing all symbols + against magic rev 2, then all symbols against magic rev 4 and + so on. Because they use their list walking proc which applies the + given proc to *every* element of the list, they compare against + all symbols in each case, even if they should fail on the first. + + We have two enhancements here which give us substantial performance + improvement. + + (1) Inline the 'walklist' call, and the strcomp proc. This + is quicker anyway, but gives us the control to terminate early. + + (2) We do an initial scan at 500 revision intervals for the highest + numbered n*500 rev that is already allocated, and start from there, + rather than 2. + + ------------ end ajw ---------------------*/ + static char *check_rev; char * RCS_magicrev (rcs, rev) *************** *** 2502,2516 **** char *rev; { int rev_num; ! char *xrev, *test_branch; ! xrev = xmalloc (strlen (rev) + 14); /* enough for .0.number */ check_rev = xrev; /* only look at even numbered branches */ ! for (rev_num = 2; ; rev_num += 2) { ! /* see if the physical branch exists */ (void) sprintf (xrev, "%s.%d", rev, rev_num); test_branch = RCS_getbranch (rcs, xrev, 1); if (test_branch != NULL) /* it did, so keep looking */ --- 2529,2586 ---- char *rev; { int rev_num; ! char *xrev, *test_branch,*s,*t; ! Node *head, *p; ! int found = 0; ! int initial; ! int start_pt; ! int valid_start; ! ! valid_start = 0; ! ! /* ------------ find a good rev number to start from ------------*/ ! xrev = xmalloc (strlen (rev) + 14); /* enough for .0.number */ check_rev = xrev; + /* if 500, 1000, 1500, exist, start there.*/ + for (start_pt=5000;!valid_start && start_pt>0;start_pt-=500) + { + /* already exists as a real branch?*/ + (void) sprintf(xrev,"%s.%d",rev, rev_num); + test_branch = RCS_getbranch(rcs,xrev,1); + if(test_branch != NULL) + { + free(test_branch); + valid_start=start_pt; + break; + } + + /* already exists as a magic branch?*/ + (void) sprintf(xrev,"%s.%d.%d", rev, RCS_MAGIC_BRANCH, start_pt); + if(RCS_symbols(rcs)==NULL) continue; + head = (RCS_symbols(rcs))->list; + found = 0; + for(p=head->next; p!=head; p=p->next) + { + if(checkmagic_proc(p)){ /* true if match*/ + valid_start=start_pt; + break; + } + } + } + + if(! valid_start) + { + valid_start=2; + } + + /* -------------- now go from valid start-------------*/ + /* only look at even numbered branches */ ! for (rev_num = valid_start; ; rev_num += 2) { ! /* see if the physical branch exists */ (void) sprintf (xrev, "%s.%d", rev, rev_num); test_branch = RCS_getbranch (rcs, xrev, 1); if (test_branch != NULL) /* it did, so keep looking */ *************** *** 2522,2531 **** /* now, create a "magic" revision */ (void) sprintf (xrev, "%s.%d.%d", rev, RCS_MAGIC_BRANCH, rev_num); /* walk the symbols list to see if a magic one already exists */ - if (walklist (RCS_symbols(rcs), checkmagic_proc, NULL) != 0) - continue; /* we found a free magic branch. Claim it as ours */ return (xrev); } --- 2592,2640 ---- /* now, create a "magic" revision */ (void) sprintf (xrev, "%s.%d.%d", rev, RCS_MAGIC_BRANCH, rev_num); + /* ---------------------- ajw ----------------------*/ + + /* if (walklist (RCS_symbols(rcs), checkmagic_proc, NULL) != 0) */ + /* continue; */ + /* with an inlining of walklist/checkmagic_proc, and optimise */ + /* walk the symbols list to see if a magic one already exists */ + /* Branches are created by tagging with symbols, so every branch + *will* have a symbol. The hope is that there are fewer symbols + than revision numbers so its quicker than walking the version + numbers. However in Transitive's case this is probably the wrong way + around. + */ + + /* no symbols - so our new one is ok */ + if(RCS_symbols(rcs)==NULL) return(xrev); + + /* existing symbols - is our candidate one of them? */ + head = (RCS_symbols(rcs))->list; + found = 0; + for(p=head->next; p!=head; p=p->next) + { + /* inlined checkmagic_proc (strcmp) */ + s=check_rev; + t=p->data; + /* stcmp(s,t) : err=>different */ + while(*s==*t) + { + if(*s!=*t) break; /*differ*/ + if(*s=='\0'){ + /* same */ + found++; + break; + } + s++; + t++; + } + if(found) break; + } + + /* symbol exists , so try next */ + if (found)continue; /* we found a free magic branch. Claim it as ours */ return (xrev); } *************** *** 2536,2552 **** * Returns 0 if the symbol does not match, 1 if it does. */ static int ! checkmagic_proc (p, closure) Node *p; - void *closure; { ! if (STREQ (check_rev, p->data)) return (1); else ! return (0); } /* * Given an RCSNode, returns non-zero if the specified revision number * or symbolic tag resolves to a "branch" within the rcs file. * --- 2645,2682 ---- * Returns 0 if the symbol does not match, 1 if it does. */ static int ! checkmagic_proc (p) Node *p; { ! if (STREQ (check_rev, p->data)) return (1); else ! return (0); } /* + * walk a list with a specific proc + */ + /* int */ + /* walklist_local (list, proc, closure) */ + /* List *list; */ + /* int (*proc) PROTO ((Node *, void *)); */ + /* void *closure; */ + /* { */ + /* Node *head, *p; */ + /* int err = 0; */ + + /* if (list == NULL) */ + /* return (0); */ + + /* head = list->list; */ + /* for (p = head->next; p != head; p = p->next) */ + /* err += proc (p, closure); */ + /* return (err); */ + /* } */ + + + /* * Given an RCSNode, returns non-zero if the specified revision number * or symbolic tag resolves to a "branch" within the rcs file. *