Convert IdentifierHash to be template based

Make it a template based class, so we can store
more then just integers here and replace more
StringHash'es with it.

Change-Id: I21442d13c6260f184bc7b63a8a58e826699f0c83
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

3 files changed, 166 insertions, 106 deletions

diff --git a/src/qml/qml/v4/qv4identifier.cpp b/src/qml/qml/v4/qv4identifier.cpp
index af11d2db41..e2b9658d62 100644
--- a/src/qml/qml/v4/qv4identifier.cpp
+++ b/src/qml/qml/v4/qv4identifier.cpp
@@ -55,51 +55,24 @@ static inline int primeForNumBits(int numBits)
 }
 
 
-IdentifierIntHashData::IdentifierIntHashData(int numBits)
+IdentifierHashData::IdentifierHashData(int numBits)
     : refCount(Q_BASIC_ATOMIC_INITIALIZER(1))
     , numBits(numBits)
     , size(0)
 {
     alloc = primeForNumBits(numBits);
-    entries = (IdentifierIntHash::Entry *)malloc(alloc*sizeof(IdentifierIntHash::Entry));
-    memset(entries, 0, alloc*sizeof(IdentifierIntHash::Entry));
+    entries = (IdentifierHashEntry *)malloc(alloc*sizeof(IdentifierHashEntry));
+    memset(entries, 0, alloc*sizeof(IdentifierHashEntry));
 }
 
-IdentifierIntHash::IdentifierIntHash(ExecutionEngine *engine)
+IdentifierHashBase::IdentifierHashBase(ExecutionEngine *engine)
 {
-    d = new IdentifierIntHashData(3);
+    d = new IdentifierHashData(3);
     d->identifierTable = engine->identifierTable;
 }
 
-void IdentifierIntHash::add(const QString &str, int value)
-{
-    Identifier *i = d->identifierTable->identifier(str);
-    addEntry(i, value);
-}
-
-int IdentifierIntHash::value(const QString &str)
-{
-    return lookup(d->identifierTable->identifier(str));
-}
 
-int IdentifierIntHash::value(String *str)
-{
-    return lookup(d->identifierTable->identifier(str));
-}
-
-QString IdentifierIntHash::findId(int value) const
-{
-    Entry *e = d->entries;
-    Entry *end = e + d->alloc;
-    while (e < end) {
-        if (e->value == value)
-            return e->identifier->string;
-    }
-    return QString();
-}
-
-
-void IdentifierIntHash::addEntry(const Identifier *identifier, uint value)
+IdentifierHashEntry *IdentifierHashBase::addEntry(const Identifier *identifier)
 {
     // fill up to max 50%
     bool grow = (d->alloc <= d->size*2);
@@ -107,13 +80,13 @@ void IdentifierIntHash::addEntry(const Identifier *identifier, uint value)
     if (grow) {
         ++d->numBits;
         int newAlloc = primeForNumBits(d->numBits);
-        Entry *newEntries = (Entry *)malloc(newAlloc * sizeof(Entry));
-        memset(newEntries, 0, newAlloc*sizeof(Entry));
+        IdentifierHashEntry *newEntries = (IdentifierHashEntry *)malloc(newAlloc * sizeof(IdentifierHashEntry));
+        memset(newEntries, 0, newAlloc*sizeof(IdentifierHashEntry));
         for (uint i = 0; i < d->alloc; ++i) {
-            const Entry &e = d->entries[i];
+            const IdentifierHashEntry &e = d->entries[i];
             if (!e.identifier)
                 continue;
-            uint idx = hash(e.identifier) % newAlloc;
+            uint idx = Identifier::hash(e.identifier) % newAlloc;
             while (newEntries[idx].identifier) {
                 ++idx;
                 idx %= newAlloc;
@@ -125,32 +98,42 @@ void IdentifierIntHash::addEntry(const Identifier *identifier, uint value)
         d->alloc = newAlloc;
     }
 
-    uint idx = hash(identifier) % d->alloc;
+    uint idx = Identifier::hash(identifier) % d->alloc;
     while (d->entries[idx].identifier) {
         Q_ASSERT(d->entries[idx].identifier != identifier);
         ++idx;
         idx %= d->alloc;
     }
     d->entries[idx].identifier = identifier;
-    d->entries[idx].value = value;
     ++d->size;
+    return d->entries + idx;
 }
 
-int IdentifierIntHash::lookup(const Identifier *identifier) const
+const IdentifierHashEntry *IdentifierHashBase::lookup(const Identifier *identifier) const
 {
     assert(d->entries);
 
-    uint idx = hash(identifier) % d->alloc;
+    uint idx = Identifier::hash(identifier) % d->alloc;
     while (1) {
         if (d->entries[idx].identifier == identifier)
-            return d->entries[idx].value;
+            return d->entries + idx;
         if (!d->entries[idx].identifier)
-            return -1;
+            return 0;
         ++idx;
         idx %= d->alloc;
     }
 }
 
+const IdentifierHashEntry *IdentifierHashBase::lookup(const QString &str) const
+{
+    return lookup(d->identifierTable->identifier(str));
+}
+
+const IdentifierHashEntry *IdentifierHashBase::lookup(String *str) const
+{
+    return lookup(d->identifierTable->identifier(str));
+}
+
 
 
 IdentifierTable::IdentifierTable(ExecutionEngine *engine)
diff --git a/src/qml/qml/v4/qv4identifier_p.h b/src/qml/qml/v4/qv4identifier_p.h
index 40d5207d7b..8149d878d5 100644
--- a/src/qml/qml/v4/qv4identifier_p.h
+++ b/src/qml/qml/v4/qv4identifier_p.h
@@ -55,56 +55,64 @@ struct Identifier
 {
     QString string;
     uint hashValue;
+
+    static inline uint hash(const QV4::Identifier *id)
+    {
+        quintptr h = (quintptr)id;
+        if (sizeof(quintptr) == sizeof(uint))
+            return h ^ (h >> 8);
+        else
+            return (uint)(h ^ (h >> 8) ^ (h >> 32));
+    }
 };
 
-inline uint hash(const QV4::Identifier *id)
+struct IdentifierTable
 {
-    quintptr h = (quintptr)id;
-    if (sizeof(quintptr) == sizeof(uint))
-        return h ^ (h >> 8);
-    else
-        return (uint)(h ^ (h >> 8) ^ (h >> 32));
-}
+    ExecutionEngine *engine;
 
+    int alloc;
+    int size;
+    int numBits;
+    String **entries;
 
+    void addEntry(String *str);
 
-struct IdentifierIntHashData;
-struct IdentifierIntHash
-{
-    struct Entry {
-        const Identifier *identifier;
-        int value;
-    };
+public:
 
-    IdentifierIntHashData *d;
+    IdentifierTable(ExecutionEngine *engine);
+    ~IdentifierTable();
 
-    IdentifierIntHash() : d(0) {}
-    IdentifierIntHash(ExecutionEngine *engine);
-    inline IdentifierIntHash(const IdentifierIntHash &other);
-    inline ~IdentifierIntHash();
-    inline IdentifierIntHash &operator=(const IdentifierIntHash &other);
+    String *insertString(const QString &s);
 
-    bool isEmpty() const { return !d; }
-    // ###
-    void reserve(int) {}
+    Identifier *identifier(String *str);
+    Identifier *identifier(const QString &s);
+    Identifier *identifier(const char *s, int len);
+
+    void mark() {
+        for (int i = 0; i < alloc; ++i)
+            if (entries[i])
+                entries[i]->mark();
+    }
+};
 
-    inline int count() const;
-    void add(const QString &str, int value);
 
-    int value(const QString &);
-    int value(String *str);
 
-    QString findId(int value) const;
 
-private:
-    void addEntry(const Identifier *i, uint value);
-    int lookup(const Identifier *identifier) const;
+struct IdentifierHashEntry {
+    const Identifier *identifier;
+    union {
+        int value;
+        void *pointer;
+    };
+    int get(int *) const { return this ? value : -1; }
+    bool get(bool *) const { return this != 0; }
+    void *get(void **) const { return this ? pointer : 0; }
 };
 
-struct IdentifierIntHashData
+struct IdentifierHashData
 {
-    IdentifierIntHashData(int numBits);
-    ~IdentifierIntHashData() {
+    IdentifierHashData(int numBits);
+    ~IdentifierHashData() {
         free(entries);
     }
 
@@ -113,23 +121,73 @@ struct IdentifierIntHashData
     int size;
     int numBits;
     IdentifierTable *identifierTable;
-    IdentifierIntHash::Entry *entries;
+    IdentifierHashEntry *entries;
 };
 
-inline IdentifierIntHash::IdentifierIntHash(const IdentifierIntHash &other)
+struct IdentifierHashBase
+{
+
+    IdentifierHashData *d;
+
+    IdentifierHashBase() : d(0) {}
+    IdentifierHashBase(ExecutionEngine *engine);
+    inline IdentifierHashBase(const IdentifierHashBase &other);
+    inline ~IdentifierHashBase();
+    inline IdentifierHashBase &operator=(const IdentifierHashBase &other);
+
+    bool isEmpty() const { return !d; }
+    // ###
+    void reserve(int) {}
+
+    inline int count() const;
+    bool contains(const Identifier *i) const;
+    bool contains(const QString &str) const;
+    bool contains(String *str) const;
+
+protected:
+    IdentifierHashEntry *addEntry(const Identifier *i);
+    const IdentifierHashEntry *lookup(const Identifier *identifier) const;
+    const IdentifierHashEntry *lookup(const QString &str) const;
+    const IdentifierHashEntry *lookup(String *str) const;
+};
+
+
+template<typename T>
+struct IdentifierHash : public IdentifierHashBase
+{
+    IdentifierHash()
+        : IdentifierHashBase() {}
+    IdentifierHash(ExecutionEngine *engine)
+        : IdentifierHashBase(engine) {}
+    inline IdentifierHash(const IdentifierHash<T> &other)
+        : IdentifierHashBase(other) {}
+    inline ~IdentifierHash() {}
+    inline IdentifierHash &operator=(const IdentifierHash<T> &other) {
+        IdentifierHashBase::operator =(other);
+        return *this;
+    }
+
+    void add(const QString &str, const T &value);
+
+    inline T value(const QString &str) const;
+    inline T value(String *str) const;
+    QString findId(T value) const;
+};
+
+inline IdentifierHashBase::IdentifierHashBase(const IdentifierHashBase &other)
 {
     d = other.d;
     if (d)
         d->refCount.ref();
 }
 
-inline IdentifierIntHash::~IdentifierIntHash()
+inline IdentifierHashBase::~IdentifierHashBase()
 {
     if (d && !d->refCount.deref())
         delete d;
 }
 
-IdentifierIntHash &IdentifierIntHash::operator=(const IdentifierIntHash &other)
+IdentifierHashBase &IdentifierHashBase::operator=(const IdentifierHashBase &other)
 {
     if (other.d)
         other.d->refCount.ref();
@@ -139,40 +197,59 @@ IdentifierIntHash &IdentifierIntHash::operator=(const IdentifierIntHash &other)
     return *this;
 }
 
-inline int IdentifierIntHash::count() const
+inline int IdentifierHashBase::count() const
 {
     return d ? d->size : 0;
 }
 
-
-struct IdentifierTable
+inline bool IdentifierHashBase::contains(const Identifier *i) const
 {
-    ExecutionEngine *engine;
+    return lookup(i) != 0;
+}
 
-    int alloc;
-    int size;
-    int numBits;
-    String **entries;
+inline bool IdentifierHashBase::contains(const QString &str) const
+{
+    return lookup(str) != 0;
+}
 
-    void addEntry(String *str);
+inline bool IdentifierHashBase::contains(String *str) const
+{
+    return lookup(str) != 0;
+}
 
-public:
+template<typename T>
+void IdentifierHash<T>::add(const QString &str, const T &value)
+{
+    Identifier *i = d->identifierTable->identifier(str);
+    IdentifierHashEntry *e = addEntry(i);
+    e->value = value;
+}
 
-    IdentifierTable(ExecutionEngine *engine);
-    ~IdentifierTable();
+template<typename T>
+inline T IdentifierHash<T>::value(const QString &str) const
+{
+    return lookup(str)->get((T*)0);
+}
 
-    String *insertString(const QString &s);
+template<typename T>
+inline T IdentifierHash<T>::value(String *str) const
+{
+    return lookup(str)->get((T*)0);
+}
 
-    Identifier *identifier(String *str);
-    Identifier *identifier(const QString &s);
-    Identifier *identifier(const char *s, int len);
 
-    void mark() {
-        for (int i = 0; i < alloc; ++i)
-            if (entries[i])
-                entries[i]->mark();
+template<typename T>
+QString IdentifierHash<T>::findId(T value) const
+{
+    IdentifierHashEntry *e = d->entries;
+    IdentifierHashEntry *end = e + d->alloc;
+    while (e < end) {
+        if (e->get((T*)0) == value)
+            return e->identifier->string;
     }
-};
+    return QString();
+}
+
 
 }
 
diff --git a/src/qml/qml/v4/qv4internalclass.cpp b/src/qml/qml/v4/qv4internalclass.cpp
index 4e3e006a69..f7f898d9f1 100644
--- a/src/qml/qml/v4/qv4internalclass.cpp
+++ b/src/qml/qml/v4/qv4internalclass.cpp
@@ -50,7 +50,7 @@ QT_BEGIN_NAMESPACE
 
 uint QV4::qHash(const QV4::InternalClassTransition &t, uint)
 {
-    return hash(t.id) ^ t.flags;
+    return Identifier::hash(t.id) ^ t.flags;
 }
 
 using namespace QV4;
@@ -91,7 +91,7 @@ void PropertyHash::addEntry(const PropertyHash::Entry &entry, int classSize)
             const Entry &e = d->entries[i];
             if (!e.identifier || e.index >= classSize)
                 continue;
-            uint idx = hash(e.identifier) % dd->alloc;
+            uint idx = Identifier::hash(e.identifier) % dd->alloc;
             while (dd->entries[idx].identifier) {
                 ++idx;
                 idx %= dd->alloc;
@@ -104,7 +104,7 @@ void PropertyHash::addEntry(const PropertyHash::Entry &entry, int classSize)
         d = dd;
     }
 
-    uint idx = hash(entry.identifier) % d->alloc;
+    uint idx = Identifier::hash(entry.identifier) % d->alloc;
     while (d->entries[idx].identifier) {
         ++idx;
         idx %= d->alloc;
@@ -117,7 +117,7 @@ uint PropertyHash::lookup(const Identifier *identifier) const
 {
     assert(d->entries);
 
-    uint idx = hash(identifier) % d->alloc;
+    uint idx = Identifier::hash(identifier) % d->alloc;
     while (1) {
         if (d->entries[idx].identifier == identifier)
             return d->entries[idx].index;