Index: /trunk/src/lib/nt/kFsCache.c
===================================================================
--- /trunk/src/lib/nt/kFsCache.c	(revision 2929)
+++ /trunk/src/lib/nt/kFsCache.c	(revision 2930)
@@ -41,5 +41,7 @@
 #include <mbstring.h>
 #include <wchar.h>
-//#include <intrin.h>
+#ifdef _MSC_VER
+# include <intrin.h>
+#endif
 //#include <setjmp.h>
 //#include <ctype.h>
@@ -200,10 +202,10 @@
  * @param   cchString           The length of the substring.
  */
-static KU32 kFsCacheStrHashN(const char *pszString, KSIZE cchString)
+static KU32 kFsCacheStrHashN(const char *pchString, KSIZE cchString)
 {
     KU32 uHash = 0;
     while (cchString-- > 0)
     {
-        KU32 uChar = (unsigned char)*pszString++;
+        KU32 uChar = (unsigned char)*pchString++;
         uHash = uChar + (uHash << 6) + (uHash << 16) - uHash;
     }
@@ -588,4 +590,6 @@
         pObj->fFlags        = pParent->Obj.fFlags & KFSOBJ_F_INHERITED_MASK;
         pObj->pParent       = pParent;
+        pObj->uNameHash     = 0;
+        pObj->pNextNameHash = NULL;
         pObj->pUserDataHead = NULL;
 
@@ -637,5 +641,5 @@
 
         /*
-         * Type specific initilization.
+         * Type specific initialization.
          */
         if (fDirish)
@@ -645,6 +649,6 @@
             pDirObj->cChildrenAllocated = 0;
             pDirObj->papChildren        = NULL;
-            pDirObj->cHashTab           = 0;
-            pDirObj->paHashTab          = NULL;
+            pDirObj->fHashTabMask       = 0;
+            pDirObj->papHashTab         = NULL;
             pDirObj->hDir               = INVALID_HANDLE_VALUE;
             pDirObj->uDevNo             = pParent->uDevNo;
@@ -1516,4 +1520,21 @@
                                   pDir->Obj.pParent->Obj.pszName, pDir->Obj.pszName, pOldChild->pszName));
                     kHlpAssert(pOldChild->bObjType != KFSOBJ_TYPE_DIR);
+                    /* Remove from hash table. */
+                    if (pOldChild->uNameHash != 0)
+                    {
+                        KU32    idx = pOldChild->uNameHash & pDir->fHashTabMask;
+                        PKFSOBJ pPrev = pDir->papHashTab[idx];
+                        if (pPrev == pOldChild)
+                            pDir->papHashTab[idx] = pOldChild->pNextNameHash;
+                        else
+                        {
+                            while (pPrev && pPrev->pNextNameHash != pOldChild)
+                                pPrev = pPrev->pNextNameHash;
+                            kHlpAssert(pPrev);
+                            if (pPrev)
+                                pPrev->pNextNameHash = pOldChild->pNextNameHash;
+                        }
+                        pOldChild->uNameHash = 0;
+                    }
                 }
                 kFsCacheObjRelease(pCache, pOldChild);
@@ -1920,10 +1941,11 @@
  *                              failed.
  */
-static PKFSOBJ kFswCacheLookupDrive(PKFSCACHE pCache, char chLetter, KU32 fFlags, KFSLOOKUPERROR *penmError)
-{
-    KU32 const          uHash = chLetter - 'A';
+static PKFSOBJ kFsCacheLookupDrive(PKFSCACHE pCache, char chLetter, KU32 fFlags, KFSLOOKUPERROR *penmError)
+{
+    KU32 const          uNameHash = chLetter - 'A';
+    PKFSOBJ             pCur      = pCache->RootDir.papHashTab[uNameHash];
+
     KU32                cLeft;
     PKFSOBJ            *ppCur;
-
     MY_UNICODE_STRING   NtPath;
     wchar_t             wszTmp[8];
@@ -1933,11 +1955,24 @@
      * Custom drive letter hashing.
      */
-    if (pCache->RootDir.paHashTab)
-    {
-        /** @todo PKFSOBJHASH pHash = */
+    kHlpAssert((uNameHash & pCache->RootDir.fHashTabMask) == uNameHash);
+    while (pCur)
+    {
+        if (   pCur->uNameHash == uNameHash
+            && pCur->cchName == 2
+            && pCur->pszName[0] == chLetter
+            && pCur->pszName[1] == ':')
+        {
+            if (pCur->bObjType == KFSOBJ_TYPE_DIR)
+                return pCur;
+            if (   (fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH)
+                || kFsCacheRefreshMissingIntermediateDir(pCache, pCur, penmError))
+                return pCur;
+            return NULL;
+        }
+        pCur = pCur->pNextNameHash;
     }
 
     /*
-     * Special cased lookup.
+     * Make 100% sure it's not there.
      */
     cLeft = pCache->RootDir.cChildren;
@@ -1945,5 +1980,5 @@
     while (cLeft-- > 0)
     {
-        PKFSOBJ pCur = *ppCur++;
+        pCur = *ppCur++;
         if (   pCur->cchName == 2
             && pCur->pszName[0] == chLetter
@@ -2059,5 +2094,11 @@
                 fRc = kFsCacheDirAddChild(pCache, &pCache->RootDir, &pDir->Obj, penmError);
                 kFsCacheObjRelease(pCache, &pDir->Obj);
-                return fRc ? &pDir->Obj : NULL;
+                if (fRc)
+                {
+                    pDir->Obj.pNextNameHash = pCache->RootDir.papHashTab[uNameHash];
+                    pCache->RootDir.papHashTab[uNameHash] = &pDir->Obj;
+                    return &pDir->Obj;
+                }
+                return NULL;
             }
 
@@ -2110,4 +2151,80 @@
 
 /**
+ * Slow path that allocates the child hash table and enters the given one.
+ *
+ * Allocation fialures are ignored.
+ *
+ * @param   pCache              The cache (for stats).
+ * @param   pDir                The directory.
+ * @param   uNameHash           The name hash  to enter @a pChild under.
+ * @param   pChild              The child to enter into the hash table.
+ */
+static void kFsCacheDirAllocHashTabAndEnterChild(PKFSCACHE pCache, PKFSDIR pDir, KU32 uNameHash, PKFSOBJ pChild)
+{
+    if (uNameHash != 0) /* paranoia ^ 4! */
+    {
+        /*
+         * Double the current number of children and round up to a multiple of
+         * two so we can avoid division.
+         */
+        KU32 cbHashTab;
+        KU32 cEntries;
+        kHlpAssert(pDir->cChildren > 0);
+        if (pDir->cChildren <= KU32_MAX / 4)
+        {
+#if defined(_MSC_VER) && 1
+            KU32 cEntriesRaw = pDir->cChildren * 2;
+            KU32 cEntriesShift;
+            kHlpAssert(sizeof(cEntries) == (unsigned long));
+            if (_BitScanReverse(&cEntriesShift, cEntriesRaw))
+            {
+                if (   K_BIT32(cEntriesShift) < cEntriesRaw
+                    && cEntriesShift < 31U)
+                    cEntriesShift++;
+                cEntries = K_BIT32(cEntriesShift);
+            }
+            else
+            {
+                kHlpAssertFailed();
+                cEntries = KU32_MAX / 2 + 1;
+            }
+#else
+            cEntries = pDir->cChildren * 2 - 1;
+            cEntries |= cEntries >> 1;
+            cEntries |= cEntries >> 2;
+            cEntries |= cEntries >> 4;
+            cEntries |= cEntries >> 8;
+            cEntries |= cEntries >> 16;
+            cEntries++;
+#endif
+        }
+        else
+            cEntries = KU32_MAX / 2 + 1;
+        kHlpAssert((cEntries & (cEntries -  1)) == 0);
+
+        cbHashTab = cEntries * sizeof(pDir->papHashTab[0]);
+        pDir->papHashTab = (PKFSOBJ *)kHlpAllocZ(cbHashTab);
+        if (pDir->papHashTab)
+        {
+            KU32 idx;
+            pDir->fHashTabMask = cEntries - 1;
+            pCache->cbObjects += cbHashTab;
+            pCache->cChildHashTabs++;
+            pCache->cChildHashEntriesTotal += cEntries;
+
+            /*
+             * Insert it.
+             */
+            pChild->uNameHash     = uNameHash;
+            idx = uNameHash & (pDir->fHashTabMask);
+            pChild->pNextNameHash = pDir->papHashTab[idx];
+            pDir->papHashTab[idx] = pChild;
+            pCache->cChildHashed++;
+        }
+    }
+}
+
+
+/**
  * Look up a child node, ANSI version.
  *
@@ -2120,16 +2237,50 @@
 static PKFSOBJ kFsCacheFindChildA(PKFSCACHE pCache, PKFSDIR pParent, const char *pchName, KU32 cchName)
 {
-    /* Check for '.' first. */
+    /*
+     * Check for '.' first ('..' won't appear).
+     */
     if (cchName != 1 || *pchName != '.')
     {
+        PKFSOBJ    *ppCur;
         KU32        cLeft;
-        PKFSOBJ    *ppCur;
-
-        if (pParent->paHashTab != NULL)
-        {
-            /** @todo directory hash table lookup.   */
-        }
-
-        /* Linear search. */
+        KU32        uNameHash;
+
+        /*
+         * Do hash table lookup.
+         *
+         * This caches previous lookups, which should be useful when looking up
+         * intermediate directories at least.
+         */
+        if (pParent->papHashTab != NULL)
+        {
+            PKFSOBJ pCur;
+            uNameHash = kFsCacheStrHashN(pchName, cchName);
+            pCur = pParent->papHashTab[uNameHash & pParent->fHashTabMask];
+            while (pCur)
+            {
+                if (   pCur->uNameHash == uNameHash
+                    && (   (   pCur->cchName == cchName
+                            && _mbsnicmp(pCur->pszName, pchName, cchName) == 0)
+#ifdef KFSCACHE_CFG_SHORT_NAMES
+                        || (   pCur->cchShortName == cchName
+                            && pCur->pszShortName != pCur->pszName
+                            && _mbsnicmp(pCur->pszShortName, pchName, cchName) == 0)
+#endif
+                        )
+                   )
+                {
+                    pCache->cChildHashHits++;
+                    pCache->cChildSearches++;
+                    return pCur;
+                }
+                pCur = pCur->pNextNameHash;
+            }
+        }
+        else
+            uNameHash = 0;
+
+        /*
+         * Do linear search.
+         */
         cLeft = pParent->cChildren;
         ppCur = pParent->papChildren;
@@ -2145,6 +2296,35 @@
 #endif
                )
+            {
+                /*
+                 * Consider entering it into the parent hash table.
+                 * Note! We hash the input, not the name we found.
+                 */
+                if (   pCur->uNameHash == 0
+                    && pParent->cChildren >= 2)
+                {
+                    if (pParent->papHashTab)
+                    {
+                        if (uNameHash != 0)
+                        {
+                            KU32 idxNameHash = uNameHash & pParent->fHashTabMask;
+                            pCur->uNameHash     = uNameHash;
+                            pCur->pNextNameHash = pParent->papHashTab[idxNameHash];
+                            pParent->papHashTab[idxNameHash] = pCur;
+                            if (pCur->pNextNameHash)
+                                pCache->cChildHashCollisions++;
+                            pCache->cChildHashed++;
+                        }
+                    }
+                    else
+                        kFsCacheDirAllocHashTabAndEnterChild(pCache, pParent, kFsCacheStrHashN(pchName, cchName), pCur);
+                }
+
+                pCache->cChildSearches++;
                 return pCur;
-        }
+            }
+        }
+
+        pCache->cChildSearches++;
         return NULL;
     }
@@ -2164,16 +2344,50 @@
 static PKFSOBJ kFsCacheFindChildW(PKFSCACHE pCache, PKFSDIR pParent, const wchar_t *pwcName, KU32 cwcName)
 {
-    /* Check for '.' first. */
+    /*
+     * Check for '.' first ('..' won't appear).
+     */
     if (cwcName != 1 || *pwcName != '.')
     {
+        PKFSOBJ    *ppCur;
         KU32        cLeft;
-        PKFSOBJ    *ppCur;
-
-        if (pParent->paHashTab != NULL)
-        {
-            /** @todo directory hash table lookup.   */
-        }
-
-        /* Linear search. */
+        KU32        uNameHash;
+
+        /*
+         * Do hash table lookup.
+         *
+         * This caches previous lookups, which should be useful when looking up
+         * intermediate directories at least.
+         */
+        if (pParent->papHashTab != NULL)
+        {
+            PKFSOBJ pCur;
+            uNameHash = kFsCacheUtf16HashN(pwcName, cwcName);
+            pCur = pParent->papHashTab[uNameHash & pParent->fHashTabMask];
+            while (pCur)
+            {
+                if (   pCur->uNameHash == uNameHash
+                    && (   (   pCur->cwcName == cwcName
+                            && kFsCacheIAreEqualW(pCur->pwszName, pwcName, cwcName))
+#ifdef KFSCACHE_CFG_SHORT_NAMES
+                         || (   pCur->cwcShortName == cwcName
+                             && pCur->pwszShortName != pCur->pwszName
+                             && kFsCacheIAreEqualW(pCur->pwszShortName, pwcName, cwcName))
+#endif
+                       )
+                   )
+                {
+                    pCache->cChildHashHits++;
+                    pCache->cChildSearches++;
+                    return pCur;
+                }
+                pCur = pCur->pNextNameHash;
+            }
+        }
+        else
+            uNameHash = 0;
+
+        /*
+         * Do linear search.
+         */
         cLeft = pParent->cChildren;
         ppCur = pParent->papChildren;
@@ -2189,6 +2403,34 @@
 #endif
                )
+            {
+                /*
+                 * Consider entering it into the parent hash table.
+                 * Note! We hash the input, not the name we found.
+                 */
+                if (   pCur->uNameHash == 0
+                    && pParent->cChildren >= 4)
+                {
+                    if (pParent->papHashTab)
+                    {
+                        if (uNameHash != 0)
+                        {
+                            KU32 idxNameHash = uNameHash & pParent->fHashTabMask;
+                            pCur->uNameHash     = uNameHash;
+                            pCur->pNextNameHash = pParent->papHashTab[idxNameHash];
+                            pParent->papHashTab[idxNameHash] = pCur;
+                            if (pCur->pNextNameHash)
+                                pCache->cChildHashCollisions++;
+                            pCache->cChildHashed++;
+                        }
+                    }
+                    else
+                        kFsCacheDirAllocHashTabAndEnterChild(pCache, pParent, kFsCacheUtf16HashN(pwcName, cwcName), pCur);
+                }
+
+                pCache->cChildSearches++;
                 return pCur;
-        }
+            }
+        }
+        pCache->cChildSearches++;
         return NULL;
     }
@@ -2212,6 +2454,6 @@
  *                              failed.
  */
-static PKFSOBJ kFswCacheLookupUncShareA(PKFSCACHE pCache, const char *pszPath, KU32 fFlags,
-                                        KU32 *poff, KFSLOOKUPERROR *penmError)
+static PKFSOBJ kFsCacheLookupUncShareA(PKFSCACHE pCache, const char *pszPath, KU32 fFlags,
+                                       KU32 *poff, KFSLOOKUPERROR *penmError)
 {
 #if 0 /* later */
@@ -2265,6 +2507,6 @@
  *                              failed.
  */
-static PKFSOBJ kFswCacheLookupUncShareW(PKFSCACHE pCache, const wchar_t *pwszPath, KU32 fFlags,
-                                        KU32 *poff, KFSLOOKUPERROR *penmError)
+static PKFSOBJ kFsCacheLookupUncShareW(PKFSCACHE pCache, const wchar_t *pwszPath, KU32 fFlags,
+                                       KU32 *poff, KFSLOOKUPERROR *penmError)
 {
 #if 0 /* later */
@@ -2635,9 +2877,9 @@
         offEnd = 2;
         kHlpAssert(IS_SLASH(pszPath[2]));
-        pRoot = kFswCacheLookupDrive(pCache, toupper(pszPath[0]), fFlags, penmError);
+        pRoot = kFsCacheLookupDrive(pCache, toupper(pszPath[0]), fFlags, penmError);
     }
     else if (   IS_SLASH(pszPath[0])
              && IS_SLASH(pszPath[1]) )
-        pRoot = kFswCacheLookupUncShareA(pCache, pszPath, fFlags, &offEnd, penmError);
+        pRoot = kFsCacheLookupUncShareA(pCache, pszPath, fFlags, &offEnd, penmError);
     else
     {
@@ -2734,9 +2976,9 @@
         offEnd = 2;
         kHlpAssert(IS_SLASH(pwszPath[2]));
-        pRoot = kFswCacheLookupDrive(pCache, toupper(pwszPath[0]), fFlags, penmError);
+        pRoot = kFsCacheLookupDrive(pCache, toupper(pwszPath[0]), fFlags, penmError);
     }
     else if (   IS_SLASH(pwszPath[0])
              && IS_SLASH(pwszPath[1]) )
-        pRoot = kFswCacheLookupUncShareW(pCache, pwszPath, fFlags, &offEnd, penmError);
+        pRoot = kFsCacheLookupUncShareW(pCache, pwszPath, fFlags, &offEnd, penmError);
     else
     {
@@ -3421,5 +3663,5 @@
             pCache->cbObjects -= sizeof(*pDir)
                                + K_ALIGN_Z(cChildren, 16) * sizeof(pDir->papChildren)
-                               + pDir->cHashTab * sizeof(pDir->paHashTab);
+                               + (pDir->fHashTabMask + !!pDir->fHashTabMask) * sizeof(pDir->papHashTab[0]);
 
             pDir->cChildren   = 0;
@@ -3429,6 +3671,6 @@
             pDir->papChildren = NULL;
 
-            kHlpFree(pDir->paHashTab);
-            pDir->paHashTab = NULL;
+            kHlpFree(pDir->papHashTab);
+            pDir->papHashTab = NULL;
             break;
         }
@@ -4083,27 +4325,33 @@
         pCache->RootDir.papChildren         = NULL;
         pCache->RootDir.hDir                = INVALID_HANDLE_VALUE;
-        pCache->RootDir.cHashTab            = 251;
-        pCache->RootDir.paHashTab           = (PKFSOBJHASH)kHlpAllocZ(  pCache->RootDir.cHashTab
-                                                                      * sizeof(pCache->RootDir.paHashTab[0]));
-        if (pCache->RootDir.paHashTab)
+        pCache->RootDir.fHashTabMask        = 255; /* 256: 26 drive letters and 102 UNCs before we're half ways. */
+        pCache->RootDir.papHashTab          = (PKFSOBJ *)kHlpAllocZ(256 * sizeof(pCache->RootDir.papHashTab[0]));
+        if (pCache->RootDir.papHashTab)
         {
             /* The cache itself. */
-            pCache->u32Magic        = KFSCACHE_MAGIC;
-            pCache->fFlags          = fFlags;
+            pCache->u32Magic                = KFSCACHE_MAGIC;
+            pCache->fFlags                  = fFlags;
             pCache->auGenerations[0]        = KU32_MAX / 4;
             pCache->auGenerations[1]        = KU32_MAX / 32;
             pCache->auGenerationsMissing[0] = KU32_MAX / 256;
             pCache->auGenerationsMissing[1] = 1;
-            pCache->cObjects        = 1;
-            pCache->cbObjects       = sizeof(pCache->RootDir) + pCache->RootDir.cHashTab * sizeof(pCache->RootDir.paHashTab[0]);
-            pCache->cPathHashHits   = 0;
-            pCache->cWalkHits       = 0;
-            pCache->cAnsiPaths      = 0;
-            pCache->cAnsiPathCollisions = 0;
-            pCache->cbAnsiPaths     = 0;
+            pCache->cObjects                = 1;
+            pCache->cbObjects               = sizeof(pCache->RootDir)
+                                            + (pCache->RootDir.fHashTabMask + 1) * sizeof(pCache->RootDir.papHashTab[0]);
+            pCache->cPathHashHits           = 0;
+            pCache->cWalkHits               = 0;
+            pCache->cChildSearches          = 0;
+            pCache->cChildHashHits          = 0;
+            pCache->cChildHashed            = 0;
+            pCache->cChildHashTabs          = 1;
+            pCache->cChildHashEntriesTotal  = pCache->RootDir.fHashTabMask + 1;
+            pCache->cChildHashCollisions    = 0;
+            pCache->cAnsiPaths              = 0;
+            pCache->cAnsiPathCollisions     = 0;
+            pCache->cbAnsiPaths             = 0;
 #ifdef KFSCACHE_CFG_UTF16
-            pCache->cUtf16Paths     = 0;
-            pCache->cUtf16PathCollisions = 0;
-            pCache->cbUtf16Paths    = 0;
+            pCache->cUtf16Paths             = 0;
+            pCache->cUtf16PathCollisions    = 0;
+            pCache->cbUtf16Paths            = 0;
 #endif
             return pCache;
Index: /trunk/src/lib/nt/kFsCache.h
===================================================================
--- /trunk/src/lib/nt/kFsCache.h	(revision 2929)
+++ /trunk/src/lib/nt/kFsCache.h	(revision 2930)
@@ -48,5 +48,5 @@
 /** @def KFSCACHE_CFG_PATH_HASH_TAB_SIZE
  * Size of the path hash table. */
-#define KFSCACHE_CFG_PATH_HASH_TAB_SIZE     16381
+#define KFSCACHE_CFG_PATH_HASH_TAB_SIZE     99991
 /** The max length paths we consider. */
 #define KFSCACHE_CFG_MAX_PATH               1024
@@ -112,18 +112,4 @@
 
 
-/**
- * Directory hash table entry.
- *
- * There can be two of these per directory entry when the short name differs
- * from the long name.
- */
-typedef struct KFSOBJHASH
-{
-    /** Pointer to the next entry with the same hash. */
-    PKFSOBJHASH         pNext;
-    /** Pointer to the object. */
-    PKFSOBJ             pObj;
-} KFSOBJHASH;
-
 
 /** Pointer to a user data item. */
@@ -163,4 +149,15 @@
     KU32                fFlags;
 
+    /** Hash value of the name inserted into the parent hash table.
+     * This is 0 if not inserted.  Names are only hashed and inserted as they are
+     * first found thru linear searching of its siblings, and which name it is
+     * dependens on the lookup function (W or A) and whether the normal name or
+     * short name seems to have matched.
+     *
+     * @note It was ruled out as too much work to hash and track all four names,
+     *       so instead this minimalist approach was choosen in stead. */
+    KU32                uNameHash;
+    /** Pointer to the next child with the same name hash value. */
+    PKFSOBJ             pNextNameHash;
     /** Pointer to the parent (directory).
      * This is only NULL for a root. */
@@ -231,11 +228,14 @@
     KU32                cChildrenAllocated;
 
-    /** Pointer to the hash table.
-     * @todo this isn't quite there yet, structure wise. sigh.  */
-    PKFSOBJHASH         paHashTab;
-    /** The size of the hash table.
-     * @remarks The hash table is optional and only used when there are a lot of
-     *          entries in the directory. */
-    KU32                cHashTab;
+    /** Pointer to the child hash table. */
+    PKFSOBJ            *papHashTab;
+    /** The mask shift of the hash table.
+     * Hash table size is a power of two, this is the size minus one.
+     *
+     * @remarks The hash table is optional and populated by lookup hits.  The
+     *          assumption being that a lookup is repeated and will choose a good
+     *          name to hash on.  We've got up to 4 different hashes, so this
+     *          was the easy way out. */
+    KU32                fHashTabMask;
 
     /** Handle to the directory (we generally keep it open). */
@@ -401,4 +401,16 @@
     /** Number of hits walking the file system hierarchy. */
     KSIZE               cWalkHits;
+    /** Number of child searches. */
+    KSIZE               cChildSearches;
+    /** Number of cChildLookups resolved thru hash table hits. */
+    KSIZE               cChildHashHits;
+    /** The number of child hash tables. */
+    KSIZE               cChildHashTabs;
+    /** The sum of all child hash table sizes. */
+    KSIZE               cChildHashEntriesTotal;
+    /** Number of children inserted into the hash tables. */
+    KSIZE               cChildHashed;
+    /** Number of collisions in the child hash tables */
+    KSIZE               cChildHashCollisions;
 
     /** The root directory. */
