[akhaldi] 59593: [RSYM] * Speedup FindOrAddString(). Brought to you by Art Yerkes (arty).

Author: akhaldi
Date: Sun Jul 28 20:37:51 2013
New Revision: 59593
URL: http://svn.reactos.org/svn/reactos?rev=59593&view=rev
Log:
[RSYM]
* Speedup FindOrAddString(). Brought to you by Art Yerkes (arty).
Modified:
    trunk/reactos/tools/rsym/rsym.c
Modified: trunk/reactos/tools/rsym/rsym.c
URL:
http://svn.reactos.org/svn/reactos/trunk/reactos/tools/rsym/rsym.c?rev=5959…
==============================================================================
--- trunk/reactos/tools/rsym/rsym.c     [iso-8859-1] (original)
+++ trunk/reactos/tools/rsym/rsym.c     [iso-8859-1] Sun Jul 28 20:37:51 2013
@@ -33,6 +33,83 @@
 #define MAX_PATH 260
 #define MAX_SYM_NAME 2000
+struct StringEntry
+{
+    struct StringEntry *Next;
+    ULONG Offset;
+    char *String;
+};
+
+struct StringHashTable
+{
+    ULONG TableSize;
+    struct StringEntry **Table;
+};
+
+/* This is the famous DJB hash */
+static unsigned int
+ComputeDJBHash(const char *name)
+{
+    unsigned int val = 5381;
+    int i = 0;
+
+    for (i = 0; name[i]; i++)
+    {
+        val = (33 * val) + name[i];
+    }
+
+    return val;
+}
+
+static void
+AddStringToHash(struct StringHashTable *StringTable,
+                unsigned int hash,
+                ULONG Offset,
+                char *StringPtr)
+{
+    struct StringEntry *entry = calloc(1, sizeof(struct StringEntry));
+    entry->Offset = Offset;
+    entry->String = StringPtr;
+    entry->Next = StringTable->Table[hash];
+    StringTable->Table[hash] = entry;
+}
+
+static void
+StringHashTableInit(struct StringHashTable *StringTable,
+                    ULONG StringsLength,
+                    char *StringsBase)
+{
+    char *Start = StringsBase;
+    char *End = StringsBase + StringsLength;
+    StringTable->TableSize = 1024;
+    StringTable->Table = calloc(1024, sizeof(struct StringEntry *));
+    while (Start < End)
+    {
+        AddStringToHash(StringTable,
+                        ComputeDJBHash(Start) % StringTable->TableSize,
+                        Start - StringsBase,
+                        Start);
+        Start += strlen(Start) + 1;
+    }
+}
+
+static void
+StringHashTableFree(struct StringHashTable *StringTable)
+{
+    int i;
+    struct StringEntry *entry;
+    for (i = 0; i < StringTable->TableSize; i++)
+    {
+        while ((entry = StringTable->Table[i]))
+        {
+            entry = entry->Next;
+            free(StringTable->Table[i]);
+            StringTable->Table[i] = entry;
+        }
+    }
+    free(StringTable->Table);
+}
+
 static int
 CompareSymEntry(const PROSSYM_ENTRY SymEntry1, const PROSSYM_ENTRY SymEntry2)
 {
@@ -112,26 +189,32 @@
 }
 static ULONG
-FindOrAddString(char *StringToFind, ULONG *StringsLength, void *StringsBase)
-{
-    char *Search, *End;
-
-    Search = (char *)StringsBase;
-    End = Search + *StringsLength;
-
-    while (Search < End)
-    {
-        if (strcmp(Search, StringToFind) == 0)
-        {
-            return Search - (char *)StringsBase;
-        }
-        Search += strlen(Search) + 1;
-    }
-
-    strcpy(Search, StringToFind);
-    *StringsLength += strlen(StringToFind) + 1;
-
-    return Search - (char *)StringsBase;
+FindOrAddString(struct StringHashTable *StringTable,
+                char *StringToFind,
+                ULONG *StringsLength,
+                void *StringsBase)
+{
+    unsigned int hash = ComputeDJBHash(StringToFind) % StringTable->TableSize;
+    struct StringEntry *entry = StringTable->Table[hash];
+
+    while (entry && strcmp(entry->String, StringToFind))
+        entry = entry->Next;
+
+    if (entry)
+    {
+        return entry->Offset;
+    }
+    else
+    {
+        char *End = (char *)StringsBase + *StringsLength;
+
+        strcpy(End, StringToFind);
+        *StringsLength += strlen(StringToFind) + 1;
+
+        AddStringToHash(StringTable, hash, End - (char *)StringsBase, End);
+
+        return End - (char *)StringsBase;
+    }
 }
 static int
@@ -150,6 +233,7 @@
     ULONG NameLen;
     char FuncName[256];
     PROSSYM_ENTRY Current;
+    struct StringHashTable StringHash;
     StabEntry = StabSymbolsBase;
     Count = StabSymbolsLength / sizeof(STAB_ENTRY);
@@ -170,6 +254,8 @@
     }
     Current = *SymbolsBase;
     memset(Current, 0, sizeof(*Current));
+
+    StringHashTableInit(&StringHash, *StringsLength, (char *)StringsBase);
     LastFunctionAddress = 0;
     for (i = 0; i < Count; i++)
@@ -206,8 +292,8 @@
                         First = 0;
                     Current->Address = Address;
                 }
-                Current->FileOffset = FindOrAddString((char *)StabStringsBase
-                                                      + StabEntry[i].n_strx,
+                Current->FileOffset = FindOrAddString(&StringHash,
+                                                      (char *)StabStringsBase +
StabEntry[i].n_strx,
                                                       StringsLength,
                                                       StringsBase);
                 break;
@@ -236,7 +322,8 @@
                 }
                 memcpy(FuncName, Name, NameLen);
                 FuncName[NameLen] = '\0';
-                Current->FunctionOffset = FindOrAddString(FuncName,
+                Current->FunctionOffset = FindOrAddString(&StringHash,
+                                                          FuncName,
                                                           StringsLength,
                                                           StringsBase);
                 Current->SourceLine = 0;
@@ -265,6 +352,8 @@
     qsort(*SymbolsBase, *SymbolsCount, sizeof(ROSSYM_ENTRY), (int (*)(const void *, const
void *)) CompareSymEntry);
+    StringHashTableFree(&StringHash);
+
     return 0;
 }
@@ -281,6 +370,7 @@
     char FuncName[256], FileName[1024];
     char *p;
     PROSSYM_ENTRY Current;
+    struct StringHashTable StringHash;
     CoffEntry = (PCOFF_SYMENT) CoffSymbolsBase;
     Count = CoffSymbolsLength / sizeof(COFF_SYMENT);
@@ -293,6 +383,8 @@
     }
     *SymbolsCount = 0;
     Current = *SymbolsBase;
+
+    StringHashTableInit(&StringHash, *StringsLength, (char*)StringsBase);
     for (i = 0; i < Count; i++)
     {
@@ -319,6 +411,7 @@
                 {
                     free(*SymbolsBase);
                     fprintf(stderr, "Function name too long\n");
+                    StringHashTableFree(&StringHash);
                     return 1;
                 }
                 strcpy(FuncName, (char *) CoffStringsBase + CoffEntry[i].e.e.e_offset);
@@ -336,7 +429,8 @@
                 *p = '\0';
             }
             p = ('_' == FuncName[0] || '@' == FuncName[0] ? FuncName + 1
: FuncName);
-            Current->FunctionOffset = FindOrAddString(p,
+            Current->FunctionOffset = FindOrAddString(&StringHash,
+                                                      p,
                                                       StringsLength,
                                                       StringsBase);
             Current->SourceLine = 0;
@@ -348,6 +442,8 @@
     *SymbolsCount = (Current - *SymbolsBase + 1);
     qsort(*SymbolsBase, *SymbolsCount, sizeof(ROSSYM_ENTRY), (int (*)(const void *, const
void *)) CompareSymEntry);
+
+    StringHashTableFree(&StringHash);
     return 0;
 }
@@ -370,21 +466,6 @@
   DWORD module_base;
   struct DbgHelpLineEntry *lastLineEntry;
 };
-
-/* This is the famous DJB hash */
-static unsigned int
-ComputeDJBHash(const char *name)
-{
-    unsigned int val = 5381;
-    int i = 0;
-
-    for (i = 0; name[i]; i++)
-    {
-        val = (33 * val) + name[i];
-    }
-
-    return val;
-}
 static struct DbgHelpLineEntry*
 DbgHelpAddLineEntry(struct DbgHelpStringTab *tab)