From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 25817 invoked by alias); 18 Sep 2002 22:16:05 -0000 Mailing-List: contact gdb-patches-help@sources.redhat.com; run by ezmlm Precedence: bulk List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sources.redhat.com Received: (qmail 25469 invoked from network); 18 Sep 2002 22:15:42 -0000 Received: from unknown (HELO jackfruit.Stanford.EDU) (171.64.38.136) by sources.redhat.com with SMTP; 18 Sep 2002 22:15:42 -0000 Received: (from carlton@localhost) by jackfruit.Stanford.EDU (8.11.6/8.11.6) id g8IMFfX02156; Wed, 18 Sep 2002 15:15:41 -0700 X-Authentication-Warning: jackfruit.Stanford.EDU: carlton set sender to carlton@math.stanford.edu using -f To: gdb-patches@sources.redhat.com Subject: [RFA] delete BLOCK_SHOULD_SORT Cc: Aidan Skinner , Jim Blandy , Elena Zannoni From: David Carlton Date: Wed, 18 Sep 2002 15:16:00 -0000 Message-ID: User-Agent: Gnus/5.0808 (Gnus v5.8.8) XEmacs/21.4 (Common Lisp) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-SW-Source: 2002-09/txt/msg00433.txt.bz2 I'd like to delete all occurences of BLOCK_SHOULD_SORT from GDB; it's really no longer necessary, and will get in the way of my dictionary work. The history, as I understand it, is that formerly symbols in blocks were always stored linearly; but, for blocks where the order didn't matter, the symbols were sorted to improve search time. Then blocks using hashtables were introduced; these are now used almost everywhere that sorted linear blocks had been previously used. In particular, blocks produced by buildsym.c, which is the vast majority of blocks, will never satisfy BLOCK_SHOULD_SORT. Right now, I believe that there are only two situations where blocks satisfying BLOCK_SHOULD_SORT can be produced: * jv-lang.c builds one such block. However, despite its satisfying the BLOCK_SHOULD_SORT predicate, the block in question _isn't_ sorted, leading to a special case in lookup_block_symbol(). * mdebugread.c hasn't been converted over to use the buildsym.c mechanisms, so it's still producing sorted blocks in some situations. So, basically, making this change will get rid of some cruft, make an unnoticeable speed improvement to symbol manipulation stuff for normal usage, and when debugging ECOFF files, symbol table lookup will be a bit slower. (But it will still be correct: this is removing an optimization, but the unoptimized behavior will still work.) If anybody out there actually uses ECOFF and is bothered by this, clearly the best thing would be for that person to convert mdebugread.c to use the mechanisms in buildsym.c just like every other debugging format reader. I think the changes are pretty straightforward, though I'd appreciate it if somebody more conversant with ada-lang.c than I am could make sure I'm not missing anything with my change there. David Carlton carlton@math.stanford.edu 2002-09-18 David Carlton * symtab.h: Delete BLOCK_SHOULD_SORT. * symtab.c (lookup_block_symbol): Assume non-hashed blocks aren't sorted. * ada-lang.c (ada_add_block_symbols): Ditto. * symfile.h: Delete prototypes for sort_block_syms and sort_symtab_syms. * symfile.c: Delete functions sort_block_syms and sort_symtab_syms. * coffread.c (coff_symfile_read): Remove call to sort_symtab_syms. * xcoffread.c (xcoff_psymtab_to_symtab_1): Ditto. * mdebugread.c (psymtab_to_symtab_1): Ditto. * hpread.c (hpread_psymtab_to_symtab_1): Ditto. * dwarfread.c (psymtab_to_symtab_1): Ditto. * dwarf2read.c (psymtab_to_symtab_1): Ditto. * dbxread.c (dbx_psymtab_to_symtab_1): Ditto. Index: symtab.h =================================================================== RCS file: /cvs/src/src/gdb/symtab.h,v retrieving revision 1.39 diff -u -p -r1.39 symtab.h --- symtab.h 12 Sep 2002 19:19:37 -0000 1.39 +++ symtab.h 18 Sep 2002 20:56:48 -0000 @@ -441,13 +441,6 @@ struct block for ((sym) = BLOCK_BUCKET ((bl), (i)); (sym); \ (sym) = (sym)->hash_next) -/* Nonzero if symbols of block BL should be sorted alphabetically. - Don't sort a block which corresponds to a function. If we did the - sorting would have to preserve the order of the symbols for the - arguments. Also don't sort any block that we chose to hash. */ - -#define BLOCK_SHOULD_SORT(bl) (! BLOCK_HASHTABLE (bl) \ - && BLOCK_FUNCTION (bl) == NULL) /* Represent one symbol name; a variable, constant, function or typedef. */ Index: symtab.c =================================================================== RCS file: /cvs/src/src/gdb/symtab.c,v retrieving revision 1.69 diff -u -p -r1.69 symtab.c --- symtab.c 30 Aug 2002 03:24:00 -0000 1.69 +++ symtab.c 18 Sep 2002 20:56:53 -0000 @@ -1334,10 +1334,9 @@ lookup_block_symbol (register const stru const char *mangled_name, const namespace_enum namespace) { - register int bot, top, inc; + register int bot, top; register struct symbol *sym; register struct symbol *sym_found = NULL; - register int do_linear_search = 1; if (BLOCK_HASHTABLE (block)) { @@ -1354,103 +1353,27 @@ lookup_block_symbol (register const stru } return NULL; } - - /* If the blocks's symbols were sorted, start with a binary search. */ - - if (BLOCK_SHOULD_SORT (block)) - { - /* Reset the linear search flag so if the binary search fails, we - won't do the linear search once unless we find some reason to - do so */ - - do_linear_search = 0; - top = BLOCK_NSYMS (block); - bot = 0; - - /* Advance BOT to not far before the first symbol whose name is NAME. */ - - while (1) - { - inc = (top - bot + 1); - /* No need to keep binary searching for the last few bits worth. */ - if (inc < 4) - { - break; - } - inc = (inc >> 1) + bot; - sym = BLOCK_SYM (block, inc); - if (!do_linear_search && (SYMBOL_LANGUAGE (sym) == language_java)) - { - do_linear_search = 1; - } - if (SYMBOL_SOURCE_NAME (sym)[0] < name[0]) - { - bot = inc; - } - else if (SYMBOL_SOURCE_NAME (sym)[0] > name[0]) - { - top = inc; - } - else if (strcmp (SYMBOL_SOURCE_NAME (sym), name) < 0) - { - bot = inc; - } - else - { - top = inc; - } - } - - /* Now scan forward until we run out of symbols, find one whose - name is greater than NAME, or find one we want. If there is - more than one symbol with the right name and namespace, we - return the first one; I believe it is now impossible for us - to encounter two symbols with the same name and namespace - here, because blocks containing argument symbols are no - longer sorted. The exception is for C++, where multiple functions - (cloned constructors / destructors, in particular) can have - the same demangled name. So if we have a particular - mangled name to match, try to do so. */ - - top = BLOCK_NSYMS (block); - while (bot < top) - { - sym = BLOCK_SYM (block, bot); - if (SYMBOL_NAMESPACE (sym) == namespace - && (mangled_name - ? strcmp (SYMBOL_NAME (sym), mangled_name) == 0 - : SYMBOL_MATCHES_NAME (sym, name))) - { - return sym; - } - if (SYMBOL_SOURCE_NAME (sym)[0] > name[0]) - { - break; - } - bot++; - } - } - - /* Here if block isn't sorted, or we fail to find a match during the - binary search above. If during the binary search above, we find a - symbol which is a Java symbol, then we have re-enabled the linear - search flag which was reset when starting the binary search. - - This loop is equivalent to the loop above, but hacked greatly for speed. - - Note that parameter symbols do not always show up last in the - list; this loop makes sure to take anything else other than - parameter symbols first; it only uses parameter symbols as a - last resort. Note that this only takes up extra computation - time on a match. */ - - if (do_linear_search) + else { + /* Note that parameter symbols do not always show up last in the + list. This loop makes sure to take anything else other than + parameter symbols first; it only uses parameter symbols as a + last resort. Note that this only takes up extra computation + time on a match. */ top = BLOCK_NSYMS (block); bot = 0; while (bot < top) { sym = BLOCK_SYM (block, bot); + /* If there is more than one symbol with the right name and + namespace, we return the first one; I believe it is now + impossible for us to encounter two symbols with the same + name and namespace here, because blocks containing + argument symbols are no longer sorted. The exception is + for C++, where multiple functions (cloned constructors / + destructors, in particular) can have the same demangled + name. So if we have a particular mangled name to match, + try to do so. */ if (SYMBOL_NAMESPACE (sym) == namespace && (mangled_name ? strcmp (SYMBOL_NAME (sym), mangled_name) == 0 @@ -1492,8 +1415,8 @@ lookup_block_symbol (register const stru } bot++; } + return (sym_found); /* Will be NULL if not found. */ } - return (sym_found); /* Will be NULL if not found. */ } /* Given a main symbol SYM and ADDR, search through the alias Index: ada-lang.c =================================================================== RCS file: /cvs/src/src/gdb/ada-lang.c,v retrieving revision 1.9 diff -u -p -r1.9 ada-lang.c --- ada-lang.c 8 Sep 2002 17:43:26 -0000 1.9 +++ ada-lang.c 18 Sep 2002 20:53:52 -0000 @@ -3949,7 +3949,6 @@ ada_add_block_symbols (struct block *blo struct symbol *arg_sym; /* Set true when we find a matching non-argument symbol */ int found_sym; - int is_sorted = BLOCK_SHOULD_SORT (block); struct symbol *sym; arg_sym = NULL; @@ -3985,45 +3984,14 @@ ada_add_block_symbols (struct block *blo } else { - if (is_sorted) - { - int U; - i = 0; - U = BLOCK_NSYMS (block) - 1; - while (U - i > 4) - { - int M = (U + i) >> 1; - struct symbol *sym = BLOCK_SYM (block, M); - if (SYMBOL_NAME (sym)[0] < name[0]) - i = M + 1; - else if (SYMBOL_NAME (sym)[0] > name[0]) - U = M - 1; - else if (strcmp (SYMBOL_NAME (sym), name) < 0) - i = M + 1; - else - U = M; - } - } - else - i = 0; - - for (; i < BLOCK_BUCKETS (block); i += 1) - for (sym = BLOCK_BUCKET (block, i); sym != NULL; sym = sym->hash_next) + ALL_BLOCK_SYMBOLS (block, i, sym) { if (SYMBOL_NAMESPACE (sym) == namespace) { int cmp = strncmp (name, SYMBOL_NAME (sym), name_len); - if (cmp < 0) - { - if (is_sorted) - { - i = BLOCK_BUCKETS (block); - break; - } - } - else if (cmp == 0 - && is_name_suffix (SYMBOL_NAME (sym) + name_len)) + if (cmp == 0 + && is_name_suffix (SYMBOL_NAME (sym) + name_len)) { switch (SYMBOL_CLASS (sym)) { @@ -4059,30 +4027,8 @@ ada_add_block_symbols (struct block *blo { arg_sym = NULL; found_sym = 0; - if (is_sorted) - { - int U; - i = 0; - U = BLOCK_NSYMS (block) - 1; - while (U - i > 4) - { - int M = (U + i) >> 1; - struct symbol *sym = BLOCK_SYM (block, M); - if (SYMBOL_NAME (sym)[0] < '_') - i = M + 1; - else if (SYMBOL_NAME (sym)[0] > '_') - U = M - 1; - else if (strcmp (SYMBOL_NAME (sym), "_ada_") < 0) - i = M + 1; - else - U = M; - } - } - else - i = 0; - for (; i < BLOCK_BUCKETS (block); i += 1) - for (sym = BLOCK_BUCKET (block, i); sym != NULL; sym = sym->hash_next) + ALL_BLOCK_SYMBOLS (block, i, sym) { struct symbol *sym = BLOCK_SYM (block, i); @@ -4098,16 +4044,8 @@ ada_add_block_symbols (struct block *blo cmp = strncmp (name, SYMBOL_NAME (sym) + 5, name_len); } - if (cmp < 0) - { - if (is_sorted) - { - i = BLOCK_BUCKETS (block); - break; - } - } - else if (cmp == 0 - && is_name_suffix (SYMBOL_NAME (sym) + name_len + 5)) + if (cmp == 0 + && is_name_suffix (SYMBOL_NAME (sym) + name_len + 5)) { switch (SYMBOL_CLASS (sym)) { Index: symfile.h =================================================================== RCS file: /cvs/src/src/gdb/symfile.h,v retrieving revision 1.13 diff -u -p -r1.13 symfile.h --- symfile.h 22 Apr 2002 10:19:04 -0000 1.13 +++ symfile.h 18 Sep 2002 20:56:41 -0000 @@ -198,12 +198,6 @@ extern struct partial_symtab *start_psym struct partial_symbol **, struct partial_symbol **); -/* Sorting your symbols for fast lookup or alphabetical printing. */ - -extern void sort_block_syms (struct block *); - -extern void sort_symtab_syms (struct symtab *); - /* Make a copy of the string at PTR with SIZE characters in the symbol obstack (and add a null character at the end in the copy). Returns the address of the copy. */ Index: symfile.c =================================================================== RCS file: /cvs/src/src/gdb/symfile.c,v retrieving revision 1.65 diff -u -p -r1.65 symfile.c --- symfile.c 1 Aug 2002 17:18:32 -0000 1.65 +++ symfile.c 18 Sep 2002 20:56:34 -0000 @@ -275,38 +275,6 @@ sort_pst_symbols (struct partial_symtab compare_psymbols); } -/* Call sort_block_syms to sort alphabetically the symbols of one block. */ - -void -sort_block_syms (register struct block *b) -{ - qsort (&BLOCK_SYM (b, 0), BLOCK_NSYMS (b), - sizeof (struct symbol *), compare_symbols); -} - -/* Call sort_symtab_syms to sort alphabetically - the symbols of each block of one symtab. */ - -void -sort_symtab_syms (register struct symtab *s) -{ - register struct blockvector *bv; - int nbl; - int i; - register struct block *b; - - if (s == 0) - return; - bv = BLOCKVECTOR (s); - nbl = BLOCKVECTOR_NBLOCKS (bv); - for (i = 0; i < nbl; i++) - { - b = BLOCKVECTOR_BLOCK (bv, i); - if (BLOCK_SHOULD_SORT (b)) - sort_block_syms (b); - } -} - /* Make a null terminated copy of the string at PTR with SIZE characters in the obstack pointed to by OBSTACKP . Returns the address of the copy. Note that the string at PTR does not have to be null terminated, I.E. it Index: coffread.c =================================================================== RCS file: /cvs/src/src/gdb/coffread.c,v retrieving revision 1.29 diff -u -p -r1.29 coffread.c --- coffread.c 22 Aug 2002 05:50:11 -0000 1.29 +++ coffread.c 18 Sep 2002 20:55:11 -0000 @@ -637,15 +637,6 @@ coff_symfile_read (struct objfile *objfi coff_symtab_read ((long) symtab_offset, num_symbols, objfile); - /* Sort symbols alphabetically within each block. */ - - { - struct symtab *s; - - for (s = objfile->symtabs; s != NULL; s = s->next) - sort_symtab_syms (s); - } - /* Install any minimal symbols that have been collected as the current minimal symbols for this objfile. */ Index: xcoffread.c =================================================================== RCS file: /cvs/src/src/gdb/xcoffread.c,v retrieving revision 1.20 diff -u -p -r1.20 xcoffread.c --- xcoffread.c 12 Jul 2002 18:30:15 -0000 1.20 +++ xcoffread.c 18 Sep 2002 20:56:59 -0000 @@ -1768,7 +1768,6 @@ xcoff_psymtab_to_symtab_1 (struct partia old_chain = make_cleanup (really_free_pendings, 0); read_xcoff_symtab (pst); - sort_symtab_syms (pst->symtab); do_cleanups (old_chain); } Index: mdebugread.c =================================================================== RCS file: /cvs/src/src/gdb/mdebugread.c,v retrieving revision 1.28 diff -u -p -r1.28 mdebugread.c --- mdebugread.c 29 Jul 2002 22:55:26 -0000 1.28 +++ mdebugread.c 18 Sep 2002 20:56:25 -0000 @@ -3981,10 +3981,6 @@ psymtab_to_symtab_1 (struct partial_symt end_stabs (); } - /* Sort the symbol table now, we are done adding symbols to it. - We must do this before parse_procedure calls lookup_symbol. */ - sort_symtab_syms (st); - /* There used to be a call to sort_blocks here, but this should not be necessary for stabs symtabs. And as sort_blocks modifies the start address of the GLOBAL_BLOCK to the FIRST_LOCAL_BLOCK, @@ -4178,9 +4174,6 @@ psymtab_to_symtab_1 (struct partial_symt pop_parse_stack (); st->primary = 1; - - /* Sort the symbol table now, we are done adding symbols to it. */ - sort_symtab_syms (st); sort_blocks (st); } Index: hpread.c =================================================================== RCS file: /cvs/src/src/gdb/hpread.c,v retrieving revision 1.22 diff -u -p -r1.22 hpread.c --- hpread.c 4 Aug 2002 19:11:12 -0000 1.22 +++ hpread.c 18 Sep 2002 20:56:18 -0000 @@ -2729,7 +2729,6 @@ hpread_psymtab_to_symtab_1 (struct parti hpread_expand_symtab (pst->objfile, LDSYMOFF (pst), LDSYMLEN (pst), pst->textlow, pst->texthigh - pst->textlow, pst->section_offsets, pst->filename); - sort_symtab_syms (pst->symtab); do_cleanups (old_chain); } Index: dwarfread.c =================================================================== RCS file: /cvs/src/src/gdb/dwarfread.c,v retrieving revision 1.14 diff -u -p -r1.14 dwarfread.c --- dwarfread.c 1 Aug 2002 17:18:32 -0000 1.14 +++ dwarfread.c 18 Sep 2002 20:58:30 -0000 @@ -2364,7 +2364,6 @@ psymtab_to_symtab_1 (struct partial_symt wrap_here (""); gdb_flush (gdb_stdout); } - sort_symtab_syms (pst->symtab); do_cleanups (old_chain); } pst->readin = 1; Index: dwarf2read.c =================================================================== RCS file: /cvs/src/src/gdb/dwarf2read.c,v retrieving revision 1.66 diff -u -p -r1.66 dwarf2read.c --- dwarf2read.c 3 Sep 2002 17:32:11 -0000 1.66 +++ dwarf2read.c 18 Sep 2002 20:56:12 -0000 @@ -1606,7 +1606,6 @@ psymtab_to_symtab_1 (struct partial_symt } pst->symtab = symtab; pst->readin = 1; - sort_symtab_syms (pst->symtab); do_cleanups (back_to); } Index: dbxread.c =================================================================== RCS file: /cvs/src/src/gdb/dbxread.c,v retrieving revision 1.34 diff -u -p -r1.34 dbxread.c --- dbxread.c 29 Jul 2002 22:55:26 -0000 1.34 +++ dbxread.c 18 Sep 2002 20:55:59 -0000 @@ -2477,7 +2477,6 @@ dbx_psymtab_to_symtab_1 (struct partial_ /* Read in this file's symbols */ bfd_seek (pst->objfile->obfd, SYMBOL_OFFSET (pst), SEEK_SET); read_ofile_symtab (pst); - sort_symtab_syms (pst->symtab); do_cleanups (old_chain); }