aboutsummaryrefslogtreecommitdiff
path: root/gold/stringpool.h
diff options
context:
space:
mode:
authorIan Lance Taylor <iant@google.com>2007-12-05 22:56:51 +0000
committerIan Lance Taylor <iant@google.com>2007-12-05 22:56:51 +0000
commit987cc25110bd87a1657ff6555c3e8a479fd3daaa (patch)
tree4a5dd6076b8682e8406c4af30a155e2179f315d7 /gold/stringpool.h
parentd688b66ee1470fe1c6a1eec2869f6f324ecd1ac3 (diff)
downloadgdb-987cc25110bd87a1657ff6555c3e8a479fd3daaa.zip
gdb-987cc25110bd87a1657ff6555c3e8a479fd3daaa.tar.gz
gdb-987cc25110bd87a1657ff6555c3e8a479fd3daaa.tar.bz2
Rework Stringpool to not compute the hash code twice when adding a new
string.
Diffstat (limited to 'gold/stringpool.h')
-rw-r--r--gold/stringpool.h90
1 files changed, 57 insertions, 33 deletions
diff --git a/gold/stringpool.h b/gold/stringpool.h
index c5a3baf..929b4d1 100644
--- a/gold/stringpool.h
+++ b/gold/stringpool.h
@@ -161,6 +161,15 @@ class Stringpool_template
static size_t
string_length(const Stringpool_char*);
+ // Return whether two strings are equal.
+ static bool
+ string_equal(const Stringpool_char*, const Stringpool_char*);
+
+ // Compute a hash code for a string. LENGTH is the length of the
+ // string in characters.
+ static size_t
+ string_hash(const Stringpool_char*, size_t length);
+
// We store the actual data in a list of these buffers.
struct Stringdata
{
@@ -176,55 +185,70 @@ class Stringpool_template
// Copy a string into the buffers, returning a canonical string.
const Stringpool_char*
- add_string(const Stringpool_char*, Key*);
+ add_string(const Stringpool_char*, size_t, Key*);
+
+ // Return whether s1 is a suffix of s2.
+ static bool
+ is_suffix(const Stringpool_char* s1, size_t len1,
+ const Stringpool_char* s2, size_t len2);
+
+ // The hash table key includes the string, the length of the string,
+ // and the hash code for the string. We put the hash code
+ // explicitly into the key so that we can do a find()/insert()
+ // sequence without having to recompute the hash. Computing the
+ // hash code is a significant user of CPU time in the linker.
+ struct Hashkey
+ {
+ const Stringpool_char* string;
+ // Length is in characters, not bytes.
+ size_t length;
+ size_t hash_code;
+
+ // This goes in an STL container, so we need a default
+ // constructor.
+ Hashkey()
+ : string(NULL), length(0), hash_code(0)
+ { }
+
+ // Note that these constructors are relatively expensive, because
+ // they compute the hash code.
+ Hashkey(const Stringpool_char* s)
+ : string(s), length(string_length(s)), hash_code(string_hash(s, length))
+ { }
+
+ Hashkey(const Stringpool_char* s, size_t len)
+ : string(s), length(len), hash_code(string_hash(s, len))
+ { }
+ };
- // Hash function.
+ // Hash function. This is trivial, since we have already computed
+ // the hash.
struct Stringpool_hash
{
size_t
- operator()(const Stringpool_char*) const;
+ operator()(const Hashkey& hk) const
+ { return hk.hash_code; }
};
// Equality comparison function for hash table.
struct Stringpool_eq
{
bool
- operator()(const Stringpool_char* p1, const Stringpool_char* p2) const;
+ operator()(const Hashkey&, const Hashkey&) const;
};
- // Return whether s1 is a suffix of s2.
- static bool
- is_suffix(const Stringpool_char* s1, size_t len1,
- const Stringpool_char* s2, size_t len2);
-
- // The hash table is a map from string names to a pair of Key and
- // string table offsets. We only use the offsets if we turn this
- // into an string table section.
+ // The hash table is a map from strings to a pair of Key and string
+ // table offsets. We only use the offsets if we turn this into an
+ // string table section.
- typedef std::pair<Key, off_t> Val;
+ typedef std::pair<Key, off_t> Hashval;
-#ifdef HAVE_TR1_UNORDERED_SET
- typedef Unordered_map<const Stringpool_char*, Val, Stringpool_hash,
- Stringpool_eq,
- std::allocator<std::pair<const Stringpool_char* const,
- Val> >,
- true> String_set_type;
-#else
- typedef Unordered_map<const Stringpool_char*, Val, Stringpool_hash,
+ typedef Unordered_map<Hashkey, Hashval, Stringpool_hash,
Stringpool_eq> String_set_type;
-#endif
- // Comparison routine used when sorting into a string table. We
- // store string-sizes in the sort-vector so we don't have to
- // recompute them log(n) times as we sort.
- struct Stringpool_sort_info
- {
- typename String_set_type::iterator it;
- size_t string_length;
- Stringpool_sort_info(typename String_set_type::iterator i, size_t s)
- : it(i), string_length(s)
- { }
- };
+ // Comparison routine used when sorting into a string table.
+
+ typedef typename String_set_type::iterator Stringpool_sort_info;
struct Stringpool_sort_comparison
{