diff options
author | RĂ¼diger Timm <rt@openoffice.org> | 2008-04-10 17:06:39 +0000 |
---|---|---|
committer | RĂ¼diger Timm <rt@openoffice.org> | 2008-04-10 17:06:39 +0000 |
commit | ff4544764ca6d2b592d572c352ce6df3e54e1eb5 (patch) | |
tree | 732fadfdfad6d5642ff4e909e60b30cf1f3abec0 /soltools | |
parent | INTEGRATION: CWS changefileheader (1.19.2); FILE MERGED (diff) | |
download | core-ff4544764ca6d2b592d572c352ce6df3e54e1eb5.tar.gz core-ff4544764ca6d2b592d572c352ce6df3e54e1eb5.zip |
INTEGRATION: CWS changefileheader (1.3.70); FILE MERGED
2008/04/01 09:43:44 thb 1.3.70.1: #i73081# Improve mkdepends runtime complexity by using better data structures (fix from kendy, merged from incguards01)
Diffstat (limited to 'soltools')
-rw-r--r-- | soltools/mkdepend/parse.c | 415 | ||||
-rw-r--r-- | soltools/mkdepend/pr.c | 5 |
2 files changed, 226 insertions, 194 deletions
diff --git a/soltools/mkdepend/parse.c b/soltools/mkdepend/parse.c index 307ba07d0b30..58ceadab0387 100644 --- a/soltools/mkdepend/parse.c +++ b/soltools/mkdepend/parse.c @@ -27,35 +27,35 @@ in this Software without prior written authorization from the X Consortium. */ #include "def.h" -void define( char *def, struct inclist *file ); -void define2(char * name, char * val, struct inclist * file); -void undefine( char *symbol, register struct inclist *file ); +char *hash_lookup( char *symbol, struct symhash *symbols ); +void hash_undefine( char *symbol, struct symhash *symbols ); extern char *directives[]; -extern struct inclist maininclist; +extern struct symhash *maininclist; -int find_includes(filep, file, file_red, recursion, failOK, incCollection) +int find_includes(filep, file, file_red, recursion, failOK, incCollection, symbols) struct filepointer *filep; struct inclist *file, *file_red; int recursion; boolean failOK; struct IncludesCollection* incCollection; + struct symhash *symbols; { register char *line; register int type; boolean recfailOK; while ((line = getline(filep))) { - switch(type = deftype(line, filep, file_red, file, TRUE)) { + switch(type = deftype(line, filep, file_red, file, TRUE, symbols)) { case IF: doif: type = find_includes(filep, file, - file_red, recursion+1, failOK, incCollection); + file_red, recursion+1, failOK, incCollection, symbols); while ((type == ELIF) || (type == ELIFFALSE) || (type == ELIFGUESSFALSE)) - type = gobble(filep, file, file_red); + type = gobble(filep, file, file_red, symbols); if (type == ELSE) - gobble(filep, file, file_red); + gobble(filep, file, file_red, symbols); break; case IFFALSE: case IFGUESSFALSE: @@ -64,10 +64,10 @@ int find_includes(filep, file, file_red, recursion, failOK, incCollection) recfailOK = TRUE; else recfailOK = failOK; - type = gobble(filep, file, file_red); + type = gobble(filep, file, file_red, symbols); if (type == ELSE) find_includes(filep, file, - file_red, recursion+1, recfailOK, incCollection); + file_red, recursion+1, recfailOK, incCollection, symbols); else if (type == ELIF) goto doif; @@ -77,28 +77,28 @@ int find_includes(filep, file, file_red, recursion, failOK, incCollection) break; case IFDEF: case IFNDEF: - if ((type == IFDEF && isdefined(line, file_red, NULL)) - || (type == IFNDEF && !isdefined(line, file_red, NULL))) { + if ((type == IFDEF && hash_lookup(line, symbols)) + || (type == IFNDEF && !hash_lookup(line, symbols))) { debug(1,(type == IFNDEF ? "line %d: %s !def'd in %s via %s%s\n" : "", filep->f_line, line, file->i_file, file_red->i_file, ": doit")); type = find_includes(filep, file, - file_red, recursion+1, failOK, incCollection); + file_red, recursion+1, failOK, incCollection, symbols); while (type == ELIF || type == ELIFFALSE || type == ELIFGUESSFALSE) - type = gobble(filep, file, file_red); + type = gobble(filep, file, file_red, symbols); if (type == ELSE) - gobble(filep, file, file_red); + gobble(filep, file, file_red, symbols); } else { debug(1,(type == IFDEF ? "line %d: %s !def'd in %s via %s%s\n" : "", filep->f_line, line, file->i_file, file_red->i_file, ": gobble")); - type = gobble(filep, file, file_red); + type = gobble(filep, file, file_red, symbols); if (type == ELSE) find_includes(filep, file, - file_red, recursion + 1, failOK, incCollection); + file_red, recursion + 1, failOK, incCollection, symbols); else if (type == ELIF) goto doif; else if (type == ELIFFALSE || type == ELIFGUESSFALSE) @@ -110,12 +110,12 @@ int find_includes(filep, file, file_red, recursion, failOK, incCollection) case ELIFGUESSFALSE: case ELIF: if (!recursion) - gobble(filep, file, file_red); + gobble(filep, file, file_red, symbols); case ENDIF: if (recursion) return(type); case DEFINE: - define(line, file); + define(line, &symbols); break; case UNDEF: if (!*line) { @@ -123,13 +123,13 @@ int find_includes(filep, file, file_red, recursion, failOK, incCollection) file_red->i_file, filep->f_line, line); break; } - undefine(line, file_red); + hash_undefine(line, symbols); break; case INCLUDE: - add_include(filep, file, file_red, line, FALSE, failOK, incCollection); + add_include(filep, file, file_red, line, FALSE, failOK, incCollection, symbols); break; case INCLUDEDOT: - add_include(filep, file, file_red, line, TRUE, failOK, incCollection); + add_include(filep, file, file_red, line, TRUE, failOK, incCollection, symbols); break; case ERROR: warning("%s: %d: %s\n", file_red->i_file, @@ -160,26 +160,27 @@ int find_includes(filep, file, file_red, recursion, failOK, incCollection) return(-1); } -int gobble(filep, file, file_red) +int gobble(filep, file, file_red, symbols) register struct filepointer *filep; struct inclist *file, *file_red; + struct symhash *symbols; { register char *line; register int type; while ((line = getline(filep))) { - switch(type = deftype(line, filep, file_red, file, FALSE)) { + switch(type = deftype(line, filep, file_red, file, FALSE, symbols)) { case IF: case IFFALSE: case IFGUESSFALSE: case IFDEF: case IFNDEF: - type = gobble(filep, file, file_red); + type = gobble(filep, file, file_red, symbols); while ((type == ELIF) || (type == ELIFFALSE) || (type == ELIFGUESSFALSE)) - type = gobble(filep, file, file_red); + type = gobble(filep, file, file_red, symbols); if (type == ELSE) - (void)gobble(filep, file, file_red); + (void)gobble(filep, file, file_red, symbols); break; case ELSE: case ENDIF: @@ -213,11 +214,12 @@ int gobble(filep, file, file_red) /* * Decide what type of # directive this line is. */ -int deftype (line, filep, file_red, file, parse_it) +int deftype (line, filep, file_red, file, parse_it, symbols) register char *line; register struct filepointer *filep; register struct inclist *file_red, *file; int parse_it; + struct symhash *symbols; { register char *p; char *directive, savechar; @@ -253,7 +255,7 @@ int deftype (line, filep, file_red, file, parse_it) */ debug(0,("%s, line %d: #elif %s ", file->i_file, filep->f_line, p)); - ret = zero_value(p, filep, file_red); + ret = zero_value(p, filep, file_red, symbols); if (ret != IF) { debug(0,("false...\n")); @@ -282,7 +284,7 @@ int deftype (line, filep, file_red, file, parse_it) /* * parse an expression. */ - ret = zero_value(p, filep, file_red); + ret = zero_value(p, filep, file_red, symbols); debug(0,("%s, line %d: %s #if %s\n", file->i_file, filep->f_line, ret?"false":"true", p)); break; @@ -304,16 +306,16 @@ int deftype (line, filep, file_red, file, parse_it) /* Support ANSI macro substitution */ { - struct symtab *sym = isdefined(p, file_red, NULL); - while (sym) { - p = sym->s_value; - debug(3,("%s : #includes SYMBOL %s = %s\n", - file->i_incstring, - sym -> s_name, - sym -> s_value)); - /* mark file as having included a 'soft include' */ - file->i_included_sym = TRUE; - sym = isdefined(p, file_red, NULL); + char *sym = hash_lookup(p, symbols); + while (sym) + { + p = sym; + debug(3,("%s : #includes SYMBOL %s\n", + file->i_incstring, + sym)); + /* mark file as having included a 'soft include' */ + file->i_included_sym = TRUE; + sym = hash_lookup(p, symbols); } } @@ -357,76 +359,37 @@ int deftype (line, filep, file_red, file, parse_it) return(ret); } -struct symtab *isdefined(symbol, file, srcfile) - register char *symbol; - struct inclist *file; - struct inclist **srcfile; -{ - register struct symtab *val; - - val = slookup(symbol, &maininclist); - if (val) { - debug(1,("%s defined on command line\n", symbol)); - if (srcfile != NULL) *srcfile = &maininclist; - return(val); - } - val = fdefined(symbol, file, srcfile); - if (val) - return(val); - debug(1,("%s not defined in %s\n", symbol, file->i_file)); - return(NULL); -} +/* + * HACK! - so that we do not have to introduce 'symbols' in each cppsetup.c + * function... It's safe, functions from cppsetup.c don't return here. + */ +struct symhash *global_symbols = NULL; -struct symtab *fdefined(symbol, file, srcfile) - register char *symbol; - struct inclist *file; - struct inclist **srcfile; +char * isdefined( symbol ) + register char *symbol; { - register struct inclist **ip; - register struct symtab *val; - register int i; - static int recurse_lvl = 0; - - if (file->i_defchecked) - return(NULL); - file->i_defchecked = TRUE; - val = slookup(symbol, file); - if (val) - debug(1,("%s defined in %s as %s\n", symbol, file->i_file, val->s_value)); - if (val == NULL && file->i_list) - { - for (ip = file->i_list, i=0; i < file->i_listlen; i++, ip++) - { - val = fdefined(symbol, *ip, srcfile); - if (val) { - break; - } - } - } - else if (val != NULL && srcfile != NULL) *srcfile = file; - recurse_lvl--; - file->i_defchecked = FALSE; - - return(val); + return hash_lookup( symbol, global_symbols ); } /* * Return type based on if the #if expression evaluates to 0 */ -int zero_value(exp, filep, file_red) +int zero_value(exp, filep, file_red, symbols) register char *exp; register struct filepointer *filep; register struct inclist *file_red; + register struct symhash *symbols; { + global_symbols = symbols; /* HACK! see above */ if (cppsetup(exp, filep, file_red)) return(IFFALSE); else return(IF); } -void define(def, file) - char *def; - struct inclist *file; +void define( def, symbols ) + char *def; + struct symhash **symbols; { char *val; @@ -441,137 +404,205 @@ void define(def, file) if (!*val) val = "1"; - define2(def, val, file); + hash_define( def, val, symbols ); } -void define2(name, val, file) - char *name, *val; - struct inclist *file; +static int hash( str ) + register char *str; { - int first, last, below; - register struct symtab *sp = NULL, *dest; + /* Hash (Kernighan and Ritchie) */ + register unsigned int hashval = 0; + register unsigned int i = 0; + char *s = str; - /* Make space if it's needed */ - if (file->i_defs == NULL) + for ( ; *str; str++ ) { - file->i_defs = (struct symtab *) - malloc(sizeof (struct symtab) * SYMTABINC); - file->i_deflen = SYMTABINC; - file->i_ndefs = 0; + hashval = ( hashval * SYMHASHSEED ) + ( *str ); } - else if (file->i_ndefs == file->i_deflen) - file->i_defs = (struct symtab *) - realloc(file->i_defs, - sizeof(struct symtab)*(file->i_deflen+=SYMTABINC)); - if (file->i_defs == NULL) - fatalerr("malloc()/realloc() failure in insert_defn()\n"); + //fprintf( stderr, "hash: %s, %d\n", s, hashval & ( SYMHASHMEMBERS - 1 ) ); + return hashval & ( SYMHASHMEMBERS - 1 ); +} + +struct symhash *hash_copy( symbols ) + struct symhash *symbols; +{ + int i; + struct symhash *newsym; + if ( !symbols ) + return NULL; + + newsym = (struct symhash *) malloc( sizeof( struct symhash ) ); - below = first = 0; - last = file->i_ndefs - 1; - while (last >= first) + for ( i = 0; i < SYMHASHMEMBERS; ++i ) { - /* Fast inline binary search */ - register char *s1; - register char *s2; - register int middle = (first + last) / 2; - - /* Fast inline strchr() */ - s1 = name; - s2 = file->i_defs[middle].s_name; - while (*s1++ == *s2++) - if (s2[-1] == '\0') break; - - /* If exact match, set sp and break */ - if (*--s1 == *--s2) + if ( !symbols->s_pairs[ i ] ) + newsym->s_pairs[ i ] = NULL; + else + { + struct pair *it = symbols->s_pairs[ i ]; + struct pair *nw = newsym->s_pairs[ i ] = (struct pair*) malloc( sizeof( struct pair ) ); + nw->p_name = it->p_name; + nw->p_value = it->p_value; + nw->p_next = NULL; + + while ( it->p_next ) + { + nw->p_next = (struct pair*) malloc( sizeof( struct pair ) ); + it = it->p_next; + nw = nw->p_next; + nw->p_name = it->p_name; + nw->p_value = it->p_value; + nw->p_next = NULL; + } + } + } + return newsym; +} + +void hash_free( symbols ) + struct symhash *symbols; +{ + int i; + + if ( !symbols ) + return; + + for ( i = 0; i < SYMHASHMEMBERS; ++i ) { - sp = file->i_defs + middle; - break; + struct pair *it = symbols->s_pairs[ i ]; + struct pair *next; + while ( it ) + { + next = it->p_next; + free( it ); + it = next; + } } + free( symbols->s_pairs ); +} + +void hash_define( name, val, symbols ) + char *name, *val; + struct symhash **symbols; +{ + int hashval; + struct pair *it; + + if ( !symbols ) + return; - /* If name > i_defs[middle] ... */ - if (*s1 > *s2) + /* Make space if it's needed */ + if ( *symbols == NULL ) { - below = first; - first = middle + 1; + int i; + + *symbols = (struct symhash *) malloc( sizeof( struct symhash ) ); + if ( *symbols == NULL ) + fatalerr( "malloc()/realloc() failure in insert_defn()\n" ); + + for ( i = 0; i < SYMHASHMEMBERS; ++i ) + (*symbols)->s_pairs[i] = NULL; } - /* else ... */ - else + + hashval = hash( name ); + it = (*symbols)->s_pairs[ hashval ]; + + /* Replace/insert the symbol */ + if ( it == NULL ) { - below = last = middle - 1; + it = (*symbols)->s_pairs[ hashval ] = (struct pair*) malloc( sizeof( struct pair ) ); + it->p_name = copy( name ); + it->p_value = copy( val ); + it->p_next = NULL; } + else if ( strcmp( it->p_name, name ) == 0 ) + { + it->p_value = copy( val ); } - - /* Search is done. If we found an exact match to the symbol name, - just replace its s_value */ - if (sp != NULL) + else { - free(sp->s_value); - sp->s_value = copy(val); - return; + while ( it->p_next && ( strcmp( it->p_next->p_name, name ) != 0 ) ) + { + it = it->p_next; + } + if ( it->p_next ) + it->p_next->p_name = copy( name ); + else + { + it->p_next = (struct pair*) malloc( sizeof( struct pair ) ); + it->p_next->p_name = copy( name ); + it->p_next->p_value = copy( val ); + it->p_next->p_next = NULL; + } } +} + +char *hash_lookup( symbol, symbols ) + char *symbol; + struct symhash *symbols; +{ + struct pair *it; - sp = file->i_defs + file->i_ndefs++; - dest = file->i_defs + below + 1; - while (sp > dest) + if ( !symbols ) + return NULL; + + it = symbols->s_pairs[ hash( symbol ) ]; + + while ( it && ( strcmp( it->p_name, symbol ) != 0 ) ) { - *sp = sp[-1]; - sp--; + it = it->p_next; } - sp->s_name = copy(name); - sp->s_value = copy(val); + if ( it ) + return it->p_value; + + return NULL; } -struct symtab *slookup(symbol, file) - register char *symbol; - register struct inclist *file; +void hash_undefine( symbol, symbols ) + char *symbol; + struct symhash *symbols; { - register int first = 0; - register int last = file->i_ndefs - 1; + int hashval; + struct pair *it; - if (file) while (last >= first) - { - /* Fast inline binary search */ - register char *s1; - register char *s2; - register int middle = (first + last) / 2; - - /* Fast inline strchr() */ - s1 = symbol; - s2 = file->i_defs[middle].s_name; - while (*s1++ == *s2++) - if (s2[-1] == '\0') break; - - /* If exact match, we're done */ - if (*--s1 == *--s2) - { - return file->i_defs + middle; - } + if ( !symbols ) + return; - /* If symbol > i_defs[middle] ... */ - if (*s1 > *s2) + hashval = hash( symbol ); + it = symbols->s_pairs[ hashval ]; + + /* Replace/insert the symbol */ + if ( it == NULL ) + return; + else if ( strcmp( it->p_name, symbol ) == 0 ) + { + if ( it->p_next ) { - first = middle + 1; + struct pair *tmp; + it->p_name = it->p_next->p_name; + it->p_value = it->p_next->p_value; + tmp = it->p_next->p_next; + free( it->p_next ); + it->p_next = tmp; } - /* else ... */ else { - last = middle - 1; + free( it ); + symbols->s_pairs[ hashval ] = NULL; } } - return(NULL); -} - -void undefine(symbol, file) - char *symbol; - register struct inclist *file; -{ - register struct symtab *ptr; - struct inclist *srcfile; - while ((ptr = isdefined(symbol, file, &srcfile)) != NULL) + else { - srcfile->i_ndefs--; - for (; ptr < srcfile->i_defs + srcfile->i_ndefs; ptr++) - *ptr = ptr[1]; + while ( it->p_next && ( strcmp( it->p_next->p_name, symbol ) != 0 ) ) + { + it = it->p_next; + } + if ( it->p_next ) + { + struct pair *tmp = it->p_next; + it->p_next = it->p_next->p_next; + free( tmp ); + } } } diff --git a/soltools/mkdepend/pr.c b/soltools/mkdepend/pr.c index 0a1d1a954b39..78b56e23b313 100644 --- a/soltools/mkdepend/pr.c +++ b/soltools/mkdepend/pr.c @@ -39,12 +39,13 @@ extern boolean printed; extern boolean verbose; extern boolean show_where_not; -void add_include(filep, file, file_red, include, dot, failOK, incCollection) +void add_include(filep, file, file_red, include, dot, failOK, incCollection, symbols) struct filepointer *filep; struct inclist *file, *file_red; char *include; boolean dot; struct IncludesCollection* incCollection; + struct symhash *symbols; { register struct inclist *newfile; register struct filepointer *content; @@ -77,7 +78,7 @@ void add_include(filep, file, file_red, include, dot, failOK, incCollection) if (!newfile->i_searched) { newfile->i_searched = TRUE; content = getfile(newfile->i_file); - find_includes(content, newfile, file_red, 0, failOK, incCollection); + find_includes(content, newfile, file_red, 0, failOK, incCollection, symbols); freefile(content); } } |