-/* Possible improvements:
- + look for strings matching trailing substrings of other strings
- + better data structures? balanced trees?
- + smaller per-string or per-symbol data? re-use some of the symbol's
- data fields?
- + also look at reducing memory use elsewhere -- maybe if we didn't have to
- construct the entire symbol table at once, we could get by with smaller
- amounts of VM? (What effect does that have on the string table
- reductions?)
- + rip this out of here, put it into its own file in bfd or libiberty, so
- coff and elf can use it too. I'll work on this soon, but have more
- pressing tasks right now.
-
- A hash table might(?) be more efficient for handling exactly the cases that
- are handled now, but for trailing substring matches, I think we want to
- examine the `nearest' values (reverse-)lexically, not merely impose a strict
- order, nor look only for exact-match or not-match. I don't think a hash
- table would be very useful for that, and I don't feel like fleshing out two
- completely different implementations. [raeburn:930419.0331EDT] */
-
-struct stringtab_entry {
- /* Hash value for this string. Only useful so long as we aren't doing
- substring matches. */
- unsigned int hash;
-
- /* Next node to look at, depending on whether the hash value of the string
- being searched for is less than or greater than the hash value of the
- current node. For now, `equal to' is lumped in with `greater than', for
- space efficiency. It's not a common enough case to warrant another field
- to be used for all nodes. */
- struct stringtab_entry *less;
- struct stringtab_entry *greater;
-
- /* The string itself. */
- CONST char *string;
-
- /* The index allocated for this string. */
- bfd_size_type index;
-
-#ifdef GATHER_STATISTICS
- /* How many references have there been to this string? (Not currently used;
- could be dumped out for anaylsis, if anyone's interested.) */
- unsigned long count;
-#endif
-
- /* Next node in linked list, in suggested output order. */
- struct stringtab_entry *next_to_output;
-};
-
-struct stringtab_data {
- /* Tree of string table entries. */
- struct stringtab_entry *strings;
-
- /* Fudge factor used to center top node of tree. */
- int hash_zero;
-
- /* Next index value to issue. */
- bfd_size_type index;
-
- /* Index used for empty strings. Cached here because checking for them
- is really easy, and we can avoid searching the tree. */
- bfd_size_type empty_string_index;
-
- /* These fields indicate the two ends of a singly-linked list that indicates
- the order strings should be written out in. Use this order, and no
- seeking will need to be done, so output efficiency should be maximized. */
- struct stringtab_entry **end;
- struct stringtab_entry *output_order;
-
-#ifdef GATHER_STATISTICS
- /* Number of strings which duplicate strings already in the table. */
- unsigned long duplicates;
-
- /* Number of bytes saved by not having to write all the duplicate strings. */
- unsigned long bytes_saved;
-
- /* Number of zero-length strings. Currently, these all turn into
- references to the null byte at the end of the first string. In some
- cases (possibly not all? explore this...), it should be possible to
- simply write out a zero index value. */
- unsigned long empty_strings;
-
- /* Number of times the hash values matched but the strings were different.
- Note that this includes the number of times the other string(s) occurs, so
- there may only be two strings hashing to the same value, even if this
- number is very large. */
- unsigned long bad_hash_matches;
-
- /* Null strings aren't counted in this one.
- This will probably only be nonzero if we've got an input file
- which was produced by `ld -r' (i.e., it's already been processed
- through this code). Under some operating systems, native tools
- may make all empty strings have the same index; but the pointer
- check won't catch those, because to get to that stage we'd already
- have to compute the checksum, which requires reading the string,
- so we short-circuit that case with empty_string_index above. */
- unsigned long pointer_matches;
-
- /* Number of comparisons done. I figure with the algorithms in use below,
- the average number of comparisons done (per symbol) should be roughly
- log-base-2 of the number of unique strings. */
- unsigned long n_compares;
-#endif
-};
-
-/* Some utility functions for the string table code. */
-
-/* For speed, only hash on the first this many bytes of strings.
- This number was chosen by profiling ld linking itself, with -g. */
-#define HASHMAXLEN 25