Adding upstream version 1:0.1.9998svn3589+dfsg.upstream/1%0.1.9998svn3589+dfsg

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1087 insertions, 0 deletions

diff --git a/src/kmk/kdepdb.c b/src/kmk/kdepdb.c
new file mode 100644
index 0000000..260e695
--- /dev/null
+++ b/src/kmk/kdepdb.c
@@ -0,0 +1,1087 @@
+/* $Id: incdep.c 2283 2009-02-24 04:54:00Z bird $ */
+/** @file
+ * kdepdb - Dependency database.
+ */
+
+/*
+ * Copyright (c) 2009-2010 knut st. osmundsen <bird-kBuild-spamx@anduin.net>
+ *
+ * This file is part of kBuild.
+ *
+ * kBuild is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * kBuild is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with kBuild.  If not, see <http://www.gnu.org/licenses/>
+ *
+ */
+
+/*******************************************************************************
+*   Header Files                                                               *
+*******************************************************************************/
+#include "makeint.h"
+#include "../lib/k/kDefs.h"
+#include "../lib/k/kTypes.h"
+#include <assert.h>
+#include <glob.h>
+
+#include "dep.h"
+#include "filedef.h"
+#include "job.h"
+#include "commands.h"
+#include "variable.h"
+#include "rule.h"
+#include "debug.h"
+#include "strcache2.h"
+
+#ifdef HAVE_FCNTL_H
+# include <fcntl.h>
+#else
+# include <sys/file.h>
+#endif
+
+#if K_OS == K_WINDOWS
+# include <Windows.h>
+#else
+# include <unistd.h>
+# include <sys/mman.h>
+#endif
+
+
+/*******************************************************************************
+*   Defined Constants And Macros                                               *
+*******************************************************************************/
+/** @def KDEPDB_ASSERT_SIZE
+ * Check the size of an on-disk type.
+ *
+ * @param   Type    The type which size it being checked.
+ * @param   Size    The size it should have.
+ */
+#ifdef __GNUC__
+# define KDEPDB_ASSERT_SIZE(Type, Size) \
+    extern int kDepDbAssertSize[1] __attribute__((unused)), \
+               kDepDbAssertSize[sizeof(Type) == (Size)] __attribute__((unused))
+#else
+# define KDEPDB_ASSERT_SIZE(Type, Size) \
+    typedef int kDepDbAssertSize[sizeof(Type) == (Size)]
+#endif
+KDEPDB_ASSERT_SIZE(KU8,  1);
+KDEPDB_ASSERT_SIZE(KU16, 2);
+KDEPDB_ASSERT_SIZE(KU32, 4);
+KDEPDB_ASSERT_SIZE(KU64, 8);
+
+
+/*******************************************************************************
+*   Structures and Typedefs                                                    *
+*******************************************************************************/
+/**
+ * File header.
+ *
+ * @remarks     All on-disk formats are in little-endian format.
+ */
+typedef struct KDEPDBHDR
+{
+    /** The file magic.  */
+    KU8             szMagic[8];
+    /** The major file format version. */
+    KU8             uVerMajor;
+    /** The minor file format version. */
+    KU8             uVerMinor;
+    /** Reserved \#2. */
+    KU16            uReserved2;
+    /** Reserved \#1. */
+    KU32            uReserved1;
+    /** The internal name of this file. */
+    KU8             szName[16];
+} KDEPDBHDR;
+KDEPDB_ASSERT_SIZE(KDEPDBHDR, 32);
+
+/** The file header magic value. */
+#define KDEPDBHDR_MAGIC             "kDepDb\0"
+/** The current major file format version number.  */
+#define KDEPDBHDR_VERSION_MAJOR     0
+/** The current minor file format version number.
+ * Numbers above 240 indicate unsupported development variants. */
+#define KDEPDBHDR_VERSION_MINOR     240
+
+
+/**
+ * Hash table file.
+ *
+ * The hash table is recreated in a new file when we have to grow it.
+ */
+typedef struct KDEPDBHASH
+{
+    /** The file header. */
+    KDEPDBHDR       Hdr;
+    /** The number of hash table entries. */
+    KU32            cEntries;
+    /** The number of hash table entries with content. */
+    KU32            cUsedEntries;
+    /** The number of collisions on insert. */
+    KU32            cCollisions;
+    /** Reserved member \#5. */
+    KU32            uReserved5;
+    /** Reserved member \#4. */
+    KU32            uReserved4;
+    /** Reserved member \#3. */
+    KU32            uReserved3;
+    /** Reserved member \#2. */
+    KU32            uReserved2;
+    /** Reserved member \#1. */
+    KU32            uReserved1;
+    /** The hash table. */
+    KU32            auEntries[32];
+} KDEPDBHASH;
+KDEPDB_ASSERT_SIZE(KDEPDBHASH, 32+32+4*32);
+
+/** The item value indicating that it is unused. */
+#define KDEPDBHASH_UNUSED   KU32_C(0xffffffff)
+/** The item indicating that it hash been deleted. */
+#define KDEPDBHASH_DELETED  KU32_C(0xfffffffe)
+/** The first special item value. */
+#define KDEPDBHASH_END      KU32_C(0xfffffff0)
+
+
+/**
+ * A string table string entry.
+ *
+ * This should be a multiple of 32 bytes.
+ */
+typedef struct KDEPDBSTRING
+{
+    /** The hash number for the string. */
+    KU32            uHash;
+    /** The string length, excluding the zero terminator. */
+    KU32            cchString;
+    /** The string. */
+    KU8             szString[24];
+} KDEPDBSTRING;
+KDEPDB_ASSERT_SIZE(KDEPDBSTRING, 32);
+
+
+/**
+ * String table file.
+ *
+ * The file is insertion only and will grow forever.
+ */
+typedef struct KDEPDBSTRTAB
+{
+    /** The file header. */
+    KDEPDBHDR       Hdr;
+    /** The end of the valid string table indexes. */
+    KU32            iStringEnd;
+    /** Reserved member \#7. */
+    KU32            uReserved7;
+    /** Reserved member \#6. */
+    KU32            uReserved6;
+    /** Reserved member \#5. */
+    KU32            uReserved5;
+    /** Reserved member \#4. */
+    KU32            uReserved4;
+    /** Reserved member \#3. */
+    KU32            uReserved3;
+    /** Reserved member \#2. */
+    KU32            uReserved2;
+    /** Reserved member \#1. */
+    KU32            uReserved1;
+    /** The string table. */
+    KDEPDBSTRING    aStrings[1];
+} KDEPDBSTRTAB;
+KDEPDB_ASSERT_SIZE(KDEPDBSTRTAB, 32+32+32);
+
+/** The end of the valid string table indexes (exclusive). */
+#define KDEPDBG_STRTAB_IDX_END          KU32_C(0x80000000)
+/** The string was not found. */
+#define KDEPDBG_STRTAB_IDX_NOT_FOUND    KU32_C(0xfffffffd)
+/** Error during string table operation.  */
+#define KDEPDBG_STRTAB_IDX_ERROR        KU32_C(0xfffffffe)
+/** Generic invalid string table index. */
+#define KDEPDBG_STRTAB_IDX_INVALID      KU32_C(0xffffffff)
+
+
+/**
+ * Directory entry.
+ */
+typedef struct KDEPDBDIRENTRY
+{
+    /** The string table index of the entry name.
+     * Unused entries are set to KDEPDBG_STRTAB_IDX_INVALID. */
+    KU32            iName;
+    /** The actual data stream size.
+     * Unused entries are set to KU32_MAX. */
+    KU32            cbData;
+    /** The number of blocks allocated for this stream.
+     * Unused entries are set to KU32_MAX. */
+    KU32            cBlocks;
+    /** The start block number.
+     * The stream is a contiguous sequence of blocks. This optimizes and
+     * simplifies reading the stream at the expense of operations extending it.
+     *
+     * In unused entries, this serves as the free chain pointer with KU32_MAX as
+     * nil value. */
+    KU32            iStartBlock;
+} KDEPDBDIRENTRY;
+KDEPDB_ASSERT_SIZE(KDEPDBDIRENTRY, 16);
+
+/**
+ * Directory file.
+ */
+typedef struct KDEPDBDIR
+{
+    /** The file header. */
+    KDEPDBHDR       Hdr;
+    /** The number of entries. */
+    KU32            cEntries;
+    /** The head of the free chain. (Index into aEntries.) */
+    KU32            iFreeHead;
+    /** Reserved member \#6. */
+    KU32            uReserved6;
+    /** Reserved member \#5. */
+    KU32            uReserved5;
+    /** Reserved member \#4. */
+    KU32            uReserved4;
+    /** Reserved member \#3. */
+    KU32            uReserved3;
+    /** Reserved member \#2. */
+    KU32            uReserved2;
+    /** Reserved member \#1. */
+    KU32            uReserved1;
+    /** Directory entries. */
+    KDEPDBDIRENTRY  aEntries[2];
+} KDEPDBDIR;
+KDEPDB_ASSERT_SIZE(KDEPDBDIR, 32+32+32);
+
+
+/**
+ * A block allocation bitmap.
+ *
+ * This can track 2^(12+8) = 2^20 = 1M blocks.
+ */
+typedef struct KDEPDBDATABITMAP
+{
+    /** Bitmap where each bit is a block.
+     * 0 indicates unused blocks and 1 indicates used ones. */
+    KU8             bm[4096];
+} KDEPDBDATABITMAP;
+KDEPDB_ASSERT_SIZE(KDEPDBDATABITMAP, 4096);
+
+/**
+ * Data file.
+ *
+ * The block numbering starts with this structure as block 0.
+ */
+typedef struct KDEPDBDATA
+{
+    /** The file header. */
+    KDEPDBHDR       Hdr;
+    /** The size of a block. */
+    KU32            cbBlock;
+    /** Reserved member \#7. */
+    KU32            uReserved7;
+    /** Reserved member \#6. */
+    KU32            uReserved6;
+    /** Reserved member \#5. */
+    KU32            uReserved5;
+    /** Reserved member \#4. */
+    KU32            uReserved4;
+    /** Reserved member \#3. */
+    KU32            uReserved3;
+    /** Reserved member \#2. */
+    KU32            uReserved2;
+    /** Reserved member \#1. */
+    KU32            uReserved1;
+
+    /** Block numbers for the allocation bitmaps.  */
+    KU32            aiBitmaps[4096];
+} KDEPDBDATA;
+
+/** The end of the valid block indexes (exclusive). */
+#define KDEPDB_BLOCK_IDX_END            KU32_C(0xfffffff0)
+/** The index of an unallocated bitmap block. */
+#define KDEPDB_BLOCK_IDX_UNALLOCATED    KU32_C(0xffffffff)
+
+
+/**
+ * Stream storing dependencies.
+ *
+ * The stream name gives the output file name, so all that we need is the list
+ * of files it depends on. These are serialized as a list of string table
+ * indexes.
+ */
+typedef struct KDEPDBDEPSTREAM
+{
+    /** String table indexes for the dependencies. */
+    KU32            aiDeps[1];
+} KDEPDBDEPSTREAM;
+
+
+/**
+ * A file handle structure.
+ */
+typedef struct KDEPDBFH
+{
+#if K_OS == K_OS_WINDOWS
+    /** The file handle. */
+    HANDLE      hFile;
+    /** The mapping object handle. */
+    HANDLE      hMapObj;
+#else
+    /** The file handle. */
+    int         fd;
+#endif
+    /** The current file size. */
+    KU32        cb;
+} KDEPDBFH;
+
+
+/**
+ * Internal control structure for a string table.
+ */
+typedef struct KDEPDBINTSTRTAB
+{
+    /** The hash file. */
+    KDEPDBHASH     *pHash;
+    /** The handle of the hash file. */
+    KDEPDBFH        hHash;
+    /** The string table file. */
+    KDEPDBSTRTAB   *pStrTab;
+    /** The handle of the string table file. */
+    KDEPDBFH        hStrTab;
+    /** The end of the allocated string table indexes (i.e. when to grow the
+     * file). */
+    KU32            iStringAlloced;
+} KDEPDBINTSTRTAB;
+
+
+/**
+ * Internal control structure for a data set.
+ *
+ * This governs the directory file, the directory hash file and the data file.
+ */
+typedef struct KDEPDBINTDATASET
+{
+    /** The hash file. */
+    KDEPDBHASH      pHash;
+    /** The size of the hash file. */
+    KU32            cbHash;
+    /** The size of the directory file. */
+    KU32            cbDir;
+    /** The mapping of the directory file. */
+    KDEPDBHASH      pDir;
+    /** The data file. */
+    KDEPDBDATA      pData;
+    /** The size of the data file. */
+    KU32            cbData;
+    /** The handle of the hash file. */
+    KDEPDBFH        hHash;
+    /** The handle of the directory file. */
+    KDEPDBFH        hDir;
+    /** The handle of the data file. */
+    KDEPDBFH        hData;
+} KDEPDBINTDATASET;
+
+
+/**
+ * The database instance.
+ *
+ * To simplifiy things the database uses 8 files for storing the different kinds
+ * of data. This greatly reduces the complexity compared to a single file
+ * solution.
+ */
+typedef struct KDEPDB
+{
+    /** The string table. */
+    KDEPDBINTSTRTAB     StrTab;
+    /** The variable data set. */
+    KDEPDBINTDATASET    DepSet;
+    /** The command data set. */
+    KDEPDBINTDATASET    CmdSet;
+} KDEPDB;
+
+
+/*******************************************************************************
+*   Internal Functions                                                         *
+*******************************************************************************/
+static void *kDepDbAlloc(KSIZE cb);
+static void kDepDbFree(void *pv);
+static void kDepDbFHInit(KDEPDBFH *pFH);
+static int  kDepDbFHUpdateSize(KDEPDBFH *pFH);
+static int  kDepDbFHOpen(KDEPDBFH *pFH, const char *pszFilename, KBOOL fCreate, KBOOL *pfNew);
+static int  kDepDbFHClose(KDEPDBFH *pFH);
+static int  kDepDbFHWriteAt(KDEPDBFH *pFH, KU32 off, void const *pvBuf, KSIZE cbBuf);
+static int  kDepDbFHMap(KDEPDBFH *pFH, void **ppvMap);
+static int  kDepDbFHUnmap(KDEPDBFH *pFH, void **ppvMap);
+static int  kDepDbFHGrow(KDEPDBFH *pFH, KSIZE cbNew, void **ppvMap);
+static KU32 kDepDbHashString(const char *pszString, size_t cchString);
+
+
+/** xmalloc wrapper. */
+static void *kDepDbAlloc(KSIZE cb)
+{
+    return xmalloc(cb);
+}
+
+/** free wrapper. */
+static void kDepDbFree(void *pv)
+{
+    if (pv)
+        free(pv);
+}
+
+
+/**
+ * Initializes the file handle structure so closing it without first opening it
+ * will work smoothly.
+ *
+ * @param   pFH         The file handle structure.
+ */
+static void kDepDbFHInit(KDEPDBFH *pFH)
+{
+#if K_OS == K_OS_WINDOWS
+    pFH->hFile   = INVALID_HANDLE_VALUE;
+    pFH->hMapObj = INVALID_HANDLE_VALUE;
+#else
+    pFH->fd = -1;
+#endif
+    pFH->cb = 0;
+}
+
+/**
+ * Updates the file size.
+ *
+ * @returns 0 on success. Some non-zero native error code on failure.
+ * @param   pFH             The file handle structure.
+ */
+static int  kDepDbFHUpdateSize(KDEPDBFH *pFH)
+{
+#if K_OS == K_OS_WINDOWS
+    DWORD   rc;
+    DWORD   dwHigh;
+    DWORD   dwLow;
+
+    SetLastError(0);
+    dwLow = GetFileSize(File, &High);
+    rc = GetLastError();
+    if (rc)
+    {
+        pFH->cb = 0;
+        return (int)rc;
+    }
+    if (High)
+        pFH->cb = KU32_MAX;
+    else
+        pFH->cb = dwLow;
+#else
+    off_t cb;
+
+    cb = lseek(pFH->fd, 0, SEEK_END);
+    if (cb == -1)
+    {
+        pFH->cb = 0;
+        return errno;
+    }
+    pFH->cb = cb;
+    if ((off_t)pFH->cb != cb)
+        pFH->cb = KU32_MAX;
+#endif
+    return 0;
+}
+
+/**
+ * Opens an existing file or creates a new one.
+ *
+ * @returns 0 on success. Some non-zero native error code on failure.
+ *
+ * @param   pFH             The file handle structure.
+ * @param   pszFilename     The name of the file.
+ * @param   fCreate         Whether we should create the file or not.
+ * @param   pfCreated       Where to return whether we created it or not.
+ */
+static int  kDepDbFHOpen(KDEPDBFH *pFH, const char *pszFilename, KBOOL fCreate, KBOOL *pfCreated)
+{
+    int                 rc;
+#if K_OS == K_OS_WINDOWS
+    SECURITY_ATTRIBUTES SecAttr;
+
+    SecAttr.bInheritHandle = FALSE;
+    SecAttr.lpSecurityDescriptor = NULL;
+    SecAttr.nLength = 0;
+    pFH->cb = 0;
+    SetLastError(0);
+    pFH->hFile = CreateFile(pszFilename, GENERIC_READ | GENERIC_WRITE, FILE_SHARE_READ, &SecAttr,
+                            fCreate ? OPEN_ALWAYS : OPEN_EXISTING, 0, NULL);
+    if (pFH->hFile == INVALID_HANDLE_VALUE)
+        return GetLastError();
+    *pfCreated = GetLastError() == 0;
+
+#else
+    int fFlags = O_RDWR;
+# ifdef O_BINARY
+    fFlags |= O_BINARY;
+# endif
+    pFH->cb = 0;
+    pFH->fd = open(pszFilename, fFlags, 0);
+    if (pFH->fd >= 0)
+        *pfCreated = K_FALSE;
+    else if (!fCreate)
+        return errno;
+    else
+    {
+        pFH->fd = open(pszFilename, fFlags | O_EXCL | O_CREAT, 0666);
+        if (pFH->fd < 0)
+            return errno;
+        *pfCreated = K_TRUE;
+    }
+    fcntl(pFH->fd, F_SETFD, FD_CLOEXEC);
+#endif
+
+    /* update the size */
+    rc = kDepDbFHUpdateSize(pFH);
+    if (rc)
+        kDepDbFHClose(pFH);
+    return rc;
+}
+
+/**
+ * Closes an open file.
+ *
+ * @returns 0 on success. Some non-zero native error code on failure.
+ *
+ * @param   pFH         The file handle structure.
+ */
+static int  kDepDbFHClose(KDEPDBFH *pFH)
+{
+#if K_OS == K_OS_WINDOWS
+    if (pFH->hFile != INVALID_HANDLE_VALUE)
+    {
+        if (!CloseHandle(pFH->hFile))
+            return GetLastError();
+        pFH->hFile = INVALID_HANDLE_VALUE;
+    }
+
+#else
+    if (pFH->fd >= 0)
+    {
+        if (close(pFH->fd) != 0)
+            return errno;
+        pFH->fd = -1;
+    }
+#endif
+    pFH->cb = 0;
+    return 0;
+}
+
+/**
+ * Writes to a file.
+ *
+ * @returns 0 on success. Some non-zero native error code on failure.
+ *
+ * @param   pFH         The file handle structure.
+ * @param   off         The offset into the file to start writing at.
+ * @param   pvBuf       What to write.
+ * @param   cbBuf       How much to write.
+ */
+static int  kDepDbFHWriteAt(KDEPDBFH *pFH, KU32 off, void const *pvBuf, KSIZE cbBuf)
+{
+#if K_OS == K_OS_WINDOWS
+    ULONG cbWritten;
+
+    if (SetFilePointer(pFH->hFile, off, NULL, FILE_CURRENT) == INVALID_SET_FILE_POINTER)
+        return GetLastError();
+
+    if (!WriteFile(pFH->hFile, pvBuf, cbBuf, &cbWritten, NULL))
+        return GetLastError();
+    if (cbWritten != cbBuf)
+        return -1;
+
+#else
+    ssize_t cbWritten;
+    if (lseek(pFH->fd, off, SEEK_SET) == -1)
+        return errno;
+    errno = 0;
+    cbWritten = write(pFH->fd, pvBuf, cbBuf);
+    if ((size_t)cbWritten != cbBuf)
+        return errno ? errno : EIO;
+#endif
+    return kDepDbFHUpdateSize(pFH);
+}
+
+
+/**
+ * Creates a memory mapping of the file.
+ *
+ * @returns 0 on success. Some non-zero native error code on failure.
+ *
+ * @param   pFH         The file handle structure.
+ * @param   ppvMap      Where to return the map address.
+ */
+static int  kDepDbFHMap(KDEPDBFH *pFH, void **ppvMap)
+{
+#if K_OS == K_OS_WINDOWS
+    *ppvMap = NULL;
+    return -1;
+#else
+    *ppvMap = mmap(NULL, pFH->cb, PROT_READ | PROT_WRITE, MAP_FILE | MAP_SHARED, pFH->fd, 0);
+    if (*ppvMap == (void *)-1)
+    {
+        *ppvMap = NULL;
+        return errno;
+    }
+#endif
+    return 0;
+}
+
+
+/**
+ * Flushes and destroys a memory of the file.
+ *
+ * @returns 0 on success. Some non-zero native error code on failure.
+ *
+ * @param   pFH         The file handle structure.
+ * @param   ppvMap      The pointer to the mapping pointer. This will be set to
+ *                      NULL on success.
+ */
+static int  kDepDbFHUnmap(KDEPDBFH *pFH, void **ppvMap)
+{
+#if K_OS == K_OS_WINDOWS
+    return -1;
+#else
+    if (msync(*ppvMap, pFH->cb, MS_SYNC) == -1)
+        return errno;
+    if (munmap(*ppvMap, pFH->cb) == -1)
+        return errno;
+    *ppvMap = NULL;
+#endif
+    return 0;
+}
+
+
+/**
+ * Grows the memory mapping of the file.
+ *
+ * The content of the new space is undefined.
+ *
+ * @returns 0 on success. Some non-zero native error code on failure.
+ *
+ * @param   pFH         The file handle structure.
+ * @param   cbNew       The new mapping size.
+ * @param   ppvMap      The pointer to the mapping pointer. This may change and
+ *                      may be set to NULL on failure.
+ */
+static int  kDepDbFHGrow(KDEPDBFH *pFH, KSIZE cbNew, void **ppvMap)
+{
+#if K_OS == K_OS_WINDOWS
+    return -1;
+#else
+    if ((KU32)cbNew != cbNew)
+        return ERANGE;
+    if (cbNew <= pFH->cb)
+        return 0;
+
+    if (munmap(*ppvMap, pFH->cb) == -1)
+        return errno;
+    *ppvMap = NULL;
+
+    pFH->cb = cbNew;
+    return kDepDbFHMap(pFH, ppvMap);
+#endif
+}
+
+
+/** Macro for reading an potentially unaligned 16-bit word from a string. */
+# if K_ARCH == K_ARCH_AMD64 \
+  || K_ARCH == K_ARCH_X86_32 \
+  || K_ARCH == K_ARCH_X86_16
+#  define kDepDbHashString_get_unaligned_16bits(ptr)   ( *((const KU16 *)(ptr)) )
+# elif K_ENDIAN == K_ENDIAN_LITTLE
+#  define kDepDbHashString_get_unaligned_16bits(ptr)   (  (((const KU8 *)(ptr))[0]) \
+                                                        | (((const KU8 *)(ptr))[1] << 8) )
+# else
+#  define kDepDbHashString_get_unaligned_16bits(ptr)   (  (((const KU8 *)(ptr))[0] << 8) \
+                                                        | (((const KU8 *)(ptr))[1]) )
+# endif
+
+
+/**
+ * Hash a string.
+ *
+ * @returns Hash value.
+ *
+ * @param   pszString       The string to hash.
+ * @param   cchString       How much to hash.
+ */
+static KU32 kDepDbHashString(const char *pszString, size_t cchString)
+{
+    /*
+     * Paul Hsieh hash SuperFast function:
+     * http://www.azillionmonkeys.com/qed/hash.html
+     */
+    /** @todo A path for well aligned data should be added to speed up execution on
+     *        alignment sensitive systems. */
+    unsigned int uRem;
+    KU32 uHash;
+    KU32 uTmp;
+
+    assert(sizeof(KU8) == sizeof(char));
+
+    /* main loop, walking on 2 x KU16 */
+    uHash = cchString;
+    uRem  = cchString & 3;
+    cchString >>= 2;
+    while (cchString > 0)
+    {
+        uHash      += kDepDbHashString_get_unaligned_16bits(pszString);
+        uTmp        = (kDepDbHashString_get_unaligned_16bits(pszString + 2) << 11) ^ uHash;
+        uHash       = (uHash << 16) ^ uTmp;
+        pszString  += 2 * sizeof(KU16);
+        uHash      += uHash >> 11;
+        cchString--;
+    }
+
+    /* the remainder */
+    switch (uRem)
+    {
+        case 3:
+            uHash += kDepDbHashString_get_unaligned_16bits(pszString);
+            uHash ^= uHash << 16;
+            uHash ^= pszString[sizeof(KU16)] << 18;
+            uHash += uHash >> 11;
+            break;
+        case 2:
+            uHash += kDepDbHashString_get_unaligned_16bits(pszString);
+            uHash ^= uHash << 11;
+            uHash += uHash >> 17;
+            break;
+        case 1:
+            uHash += *pszString;
+            uHash ^= uHash << 10;
+            uHash += uHash >> 1;
+            break;
+    }
+
+    /* force "avalanching" of final 127 bits. */
+    uHash ^= uHash << 3;
+    uHash += uHash >> 5;
+    uHash ^= uHash << 4;
+    uHash += uHash >> 17;
+    uHash ^= uHash << 25;
+    uHash += uHash >> 6;
+
+    return uHash;
+}
+
+
+/***
+ * Looks up a string in the string table.
+ *
+ * @returns The string table index.
+ * @retval  KDEPDBG_STRTAB_IDX_NOT_FOUND is not found.
+ * @retval  KDEPDBG_STRTAB_IDX_ERROR on internal inconsistency.
+ *
+ * @param   pStrTab         The string table.
+ * @param   pszString       The string.
+ * @param   cchStringIn     The string length.
+ * @param   uHash           The hash of the string.
+ */
+static KU32 kDepDbStrTabLookupHashed(KDEPDBINTSTRTAB const *pStrTab, const char *pszString, size_t cchStringIn, KU32 uHash)
+{
+    KU32 const          cchString  = (KU32)cchStringIn;
+    KDEPDBHASH const   *pHash      = pStrTab->pHash;
+    KDEPDBSTRING const *paStrings  = &pStrTab->pStrTab->aStrings[0];
+    KU32 const          iStringEnd = K_LE2H_U32(pStrTab->pStrTab->iStringEnd);
+    KU32                iHash;
+
+    /* sanity */
+    if (cchString != cchStringIn)
+        return KDEPDBG_STRTAB_IDX_NOT_FOUND;
+
+    /*
+     * Hash lookup of the string.
+     */
+    iHash = uHash % pHash->cEntries;
+    for (;;)
+    {
+        KU32 iString = K_LE2H_U32(pHash->auEntries[iHash]);
+        if (iString < iStringEnd)
+        {
+            KDEPDBSTRING const *pString = &paStrings[iString];
+            if (    K_LE2H_U32(pString->uHash)     == uHash
+                &&  K_LE2H_U32(pString->cchString) == cchString
+                &&  !memcmp(pString->szString, pszString, cchString))
+                return iString;
+        }
+        else if (iString == KDEPDBHASH_UNUSED)
+            return KDEPDBG_STRTAB_IDX_NOT_FOUND;
+        else if (iString != KDEPDBHASH_DELETED)
+            return KDEPDBG_STRTAB_IDX_ERROR;
+
+        /* advance */
+        iHash = (iHash + 1) % pHash->cEntries;
+    }
+}
+
+
+/**
+ * Doubles the hash table size and rehashes it.
+ *
+ * @returns 0 on success, -1 on failure.
+ * @param   pStrTab         The string table.
+ * @todo    Rebuild from string table, we'll be accessing it anyways.
+ */
+static int kDepDbStrTabReHash(KDEPDBINTSTRTAB *pStrTab)
+{
+    KDEPDBSTRING const *paStrings   = &pStrTab->pStrTab->aStrings[0];
+    KU32 const          iStringEnd  = K_LE2H_U32(pStrTab->pStrTab->iStringEnd);
+    KDEPDBHASH         *pHash       = pStrTab->pHash;
+    KDEPDBHASH          HashHdr     = *pHash;
+    KU32               *pauNew;
+    KU32                cEntriesNew;
+    KU32                i;
+
+    /*
+     * Calc the size of the new hash table.
+     */
+    if (pHash->cEntries >= KU32_C(0x80000000))
+        return -1;
+    cEntriesNew = 1024;
+    while (cEntriesNew <= pHash->cEntries)
+        cEntriesNew <<= 1;
+
+    /*
+     * Allocate and initialize an empty hash table in memory.
+     */
+    pauNew = kDepDbAlloc(cEntriesNew * sizeof(KU32));
+    if (!pauNew)
+        return -1;
+    i = cEntriesNew;
+    while (i-- > 0)
+        pauNew[i] = KDEPDBHASH_UNUSED;
+
+    /*
+     * Popuplate the new table.
+     */
+    HashHdr.cEntries     = K_LE2H_U32(cEntriesNew);
+    HashHdr.cCollisions  = 0;
+    HashHdr.cUsedEntries = 0;
+    i = pHash->cEntries;
+    while (i-- > 0)
+    {
+        KU32 iString = K_LE2H_U32(pHash->auEntries[i]);
+        if (iString < iStringEnd)
+        {
+            KU32 iHash = (paStrings[iString].uHash % cEntriesNew);
+            if (pauNew[iHash] != K_H2LE_U32(KDEPDBHASH_UNUSED))
+            {
+                do
+                {
+                    iHash = (iHash + 1) % cEntriesNew;
+                    HashHdr.cCollisions++;
+                } while (pauNew[iHash] != K_H2LE_U32(KDEPDBHASH_UNUSED));
+            }
+            pauNew[iHash] = iString;
+            HashHdr.cUsedEntries++;
+        }
+        else if (   iString != KDEPDBHASH_UNUSED
+                 && iString != KDEPDBHASH_DELETED)
+        {
+            kDepDbFree(pauNew);
+            return -1;
+        }
+    }
+    HashHdr.cCollisions  = K_H2LE_U32(HashHdr.cCollisions);
+    HashHdr.cUsedEntries = K_H2LE_U32(HashHdr.cUsedEntries);
+
+    /*
+     * Unmap the hash, write the new hash table and map it again.
+     */
+    if (!kDepDbFHUnmap(&pStrTab->hHash, (void **)&pStrTab->pHash))
+    {
+        if (   !kDepDbFHWriteAt(&pStrTab->hHash, 0, &HashHdr, K_OFFSETOF(KDEPDBHASH, auEntries))
+            && !kDepDbFHWriteAt(&pStrTab->hHash, K_OFFSETOF(KDEPDBHASH, auEntries), pauNew, sizeof(pauNew[0]) * cEntriesNew))
+        {
+            kDepDbFree(pauNew);
+            pauNew = NULL;
+            if (!kDepDbFHMap(&pStrTab->hHash, (void **)&pStrTab->pHash))
+                return 0;
+        }
+        else
+            kDepDbFHWriteAt(&pStrTab->hHash, 0, "\0\0\0\0", 4); /* file is screwed, trash the magic. */
+    }
+
+    kDepDbFree(pauNew);
+    return -1;
+}
+
+
+/**
+ * Add a string to the string table.
+ *
+ * If already in the table, the index of the existing entry is returned.
+ *
+ * @returns String index on success,
+ * @retval  KDEPDBG_STRTAB_IDX_ERROR on I/O and inconsistency errors.
+ *
+ * @param   pStrTab     The string table.
+ * @param   pszString   The string to add.
+ * @param   cchStringIn The length of the string.
+ * @param   uHash       The hash of the string.
+ */
+static KU32 kDepDbStrTabAddHashed(KDEPDBINTSTRTAB *pStrTab, const char *pszString, size_t cchStringIn, KU32 uHash)
+{
+    KU32 const          cchString   = (KU32)cchStringIn;
+    KDEPDBHASH         *pHash       = pStrTab->pHash;
+    KDEPDBSTRING       *paStrings   = &pStrTab->pStrTab->aStrings[0];
+    KU32 const          iStringEnd  = K_LE2H_U32(pStrTab->pStrTab->iStringEnd);
+    KU32                iInsertAt   = KDEPDBHASH_UNUSED;
+    KU32                cCollisions = 0;
+    KU32                iHash;
+    KU32                iString;
+    KU32                cEntries;
+    KDEPDBSTRING       *pNewString;
+
+    /* sanity */
+    if (cchString != cchStringIn)
+        return KDEPDBG_STRTAB_IDX_NOT_FOUND;
+
+    /*
+     * Hash lookup of the string, finding either an existing copy or where to
+     * insert the new string at in the hash table.
+     */
+    iHash = uHash % pHash->cEntries;
+    for (;;)
+    {
+        iString = K_LE2H_U32(pHash->auEntries[iHash]);
+        if (iString < iStringEnd)
+        {
+            KDEPDBSTRING const *pString = &paStrings[iString];
+            if (    K_LE2H_U32(pString->uHash)     == uHash
+                &&  K_LE2H_U32(pString->cchString) == cchString
+                &&  !memcmp(pString->szString, pszString, cchString))
+                return iString;
+        }
+        else
+        {
+            if (iInsertAt == KDEPDBHASH_UNUSED)
+                iInsertAt = iHash;
+            if (iString == KDEPDBHASH_UNUSED)
+                break;
+            if (iString != KDEPDBHASH_DELETED)
+                return KDEPDBG_STRTAB_IDX_ERROR;
+        }
+
+        /* advance */
+        cCollisions++;
+        iHash = (iHash + 1) % pHash->cEntries;
+    }
+
+    /*
+     * Add string to the string table.
+     * The string table file is grown in 256KB increments and ensuring at least 64KB unused new space.
+     */
+    cEntries = cchString + 1 <= sizeof(paStrings[0].szString)
+             ? 1
+             : (cchString + 1 - sizeof(paStrings[0].szString) + sizeof(KDEPDBSTRING) - 1) / sizeof(KDEPDBSTRING);
+    if (iStringEnd + cEntries > pStrTab->iStringAlloced)
+    {
+        KSIZE cbNewSize      = K_ALIGN_Z((iStringEnd + cEntries) * sizeof(KDEPDBSTRING) + 64*1024, 256*1024);
+        KU32  iStringAlloced = (pStrTab->hStrTab.cb - K_OFFSETOF(KDEPDBSTRTAB, aStrings)) / sizeof(KDEPDBSTRING);
+        if (    iStringAlloced <= pStrTab->iStringAlloced
+            ||  iStringAlloced >= KDEPDBG_STRTAB_IDX_END
+            ||  iStringAlloced >= KDEPDBHASH_END)
+            return KDEPDBG_STRTAB_IDX_ERROR;
+        if (kDepDbFHGrow(&pStrTab->hStrTab, cbNewSize, (void **)&pStrTab->pStrTab) != 0)
+            return KDEPDBG_STRTAB_IDX_ERROR;
+        pStrTab->iStringAlloced = iStringAlloced;
+        paStrings = &pStrTab->pStrTab->aStrings[0];
+    }
+
+    pNewString = &paStrings[iStringEnd];
+    pNewString->uHash     = K_H2LE_U32(uHash);
+    pNewString->cchString = K_H2LE_U32(cchString);
+    memcpy(&pNewString->szString, pszString, cchString);
+    pNewString->szString[cchString] = '\0';
+
+    pStrTab->pStrTab->iStringEnd = K_H2LE_U32(iStringEnd + cEntries);
+
+    /*
+     * Insert hash table entry, rehash it if necessary.
+     */
+    pHash->auEntries[iInsertAt] = K_H2LE_U32(iStringEnd);
+    pHash->cUsedEntries = K_H2LE_U32(K_LE2H_U32(pHash->cUsedEntries) + 1);
+    pHash->cCollisions  = K_H2LE_U32(K_LE2H_U32(pHash->cCollisions)  + cCollisions);
+    if (    K_LE2H_U32(pHash->cUsedEntries) > K_LE2H_U32(pHash->cEntries) / 3 * 2
+        &&  kDepDbStrTabReHash(pStrTab) != 0)
+        return KDEPDBG_STRTAB_IDX_ERROR;
+
+    return iStringEnd;
+}
+
+
+/** Wrapper for kDepDbStrTabLookupHashed.  */
+static KU32 kDepDbStrTabLookupN(KDEPDBINTSTRTAB const *pStrTab, const char *pszString, size_t cchString)
+{
+    return kDepDbStrTabLookupHashed(pStrTab, pszString, cchString, kDepDbHashString(pszString, cchString));
+}
+
+
+/** Wrapper for kDepDbStrTabAddHashed.  */
+static KU32 kDepDbStrTabAddN(KDEPDBINTSTRTAB *pStrTab, const char *pszString, size_t cchString)
+{
+    return kDepDbStrTabAddHashed(pStrTab, pszString, cchString, kDepDbHashString(pszString, cchString));
+}
+
+
+/** Wrapper for kDepDbStrTabLookupHashed.  */
+static KU32 kDepDbStrTabLookup(KDEPDBINTSTRTAB const *pStrTab, const char *pszString)
+{
+    return kDepDbStrTabLookupN(pStrTab, pszString, strlen(pszString));
+}
+
+
+/** Wrapper for kDepDbStrTabAddHashed.  */
+static KU32 kDepDbStrTabAdd(KDEPDBINTSTRTAB *pStrTab, const char *pszString)
+{
+    return kDepDbStrTabAddN(pStrTab, pszString, strlen(pszString));
+}
+
+
+/**
+ * Opens the string table files, creating them if necessary.
+ */
+static int kDepDbStrTabInit(KDEPDBINTSTRTAB *pStrTab, const char *pszFilenameBase)
+{
+    size_t  cchFilenameBase = strlen(pszFilenameBase);
+    char    szPath[4096];
+    int     rc;
+    KBOOL   fNew;
+
+    /* Basic member init, so kDepDbStrTabTerm always works. */
+    pStrTab->pHash = NULL;
+    kDepDbFHInit(&pStrTab->hHash);
+    pStrTab->pStrTab = NULL;
+    kDepDbFHInit(&pStrTab->hStrTab);
+    pStrTab->iStringAlloced = 0;
+
+    /* check the length. */
+    if (cchFilenameBase + sizeof(".strtab.hash") > sizeof(szPath))
+        return -1;
+
+    /*
+     * Open the string table first.
+     */
+    memcpy(szPath, pszFilenameBase, cchFilenameBase);
+    memcpy(&szPath[cchFilenameBase], ".strtab", sizeof(".strtab"));
+    rc = kDepDbFHOpen(&pStrTab->hStrTab, szPath, K_TRUE, &fNew);
+
+
+    return -1;
+}
+