commit f6c1c4765e7f9785fb8b764bd65e801522c10ba4
Author: Simon Howard <fraggle@gmail.com>
AuthorDate: Fri Mar 24 20:39:08 2006 +0000
Commit: Simon Howard <fraggle@gmail.com>
CommitDate: Fri Mar 24 20:39:08 2006 +0000
Generate a hash table for fast lump name lookups.
Subversion-branch: /trunk/chocolate-doom
Subversion-revision: 436
---
src/w_wad.c | 157 ++++++++++++++++++++++++++++++++++++++++--------------------
1 file changed, 104 insertions(+), 53 deletions(-)
diff --git a/src/w_wad.c b/src/w_wad.c
index 86da932d..4e9a3808 100644
--- a/src/w_wad.c
+++ b/src/w_wad.c
@@ -1,7 +1,7 @@
// Emacs style mode select -*- C++ -*-
//-----------------------------------------------------------------------------
//
-// $Id: w_wad.c 434 2006-03-24 19:55:04Z fraggle $
+// $Id: w_wad.c 436 2006-03-24 20:39:08Z fraggle $
//
// Copyright(C) 1993-1996 Id Software, Inc.
// Copyright(C) 2005 Simon Howard
@@ -66,7 +66,7 @@
static const char
-rcsid[] = "$Id: w_wad.c 434 2006-03-24 19:55:04Z fraggle $";
+rcsid[] = "$Id: w_wad.c 436 2006-03-24 20:39:08Z fraggle $";
#include <ctype.h>
@@ -82,27 +82,20 @@ rcsid[] = "$Id: w_wad.c 434 2006-03-24 19:55:04Z fraggle $";
#include "w_wad.h"
-
-
-
-
-
//
// GLOBALS
//
// Location of each lump on disk.
-lumpinfo_t* lumpinfo;
-int numlumps = 0;
-#define strcmpi strcasecmp
+lumpinfo_t *lumpinfo;
+int numlumps = 0;
-void string_to_upper (char* s)
-{
- while (*s) { *s = toupper(*s); s++; }
-}
+// Hash table for fast lookups
+
+static lumpinfo_t **lumphash;
-int filelength (FILE *handle)
+static int FileLength (FILE *handle)
{
long savedpos;
long length;
@@ -120,10 +113,7 @@ int filelength (FILE *handle)
}
-void
-ExtractFileBase
-( char* path,
- char* dest )
+static void ExtractFileBase(char *path, char *dest)
{
char* src;
int length;
@@ -151,9 +141,27 @@ ExtractFileBase
}
}
+// Hash function used for lump names.
+// Must be mod'ed with table size.
+// Can be used for any 8-character names.
+// by Lee Killough
-
-
+static unsigned int W_LumpNameHash(const char *s)
+{
+ unsigned int hash;
+
+ ((hash = toupper(s[0]), s[1]) &&
+ (hash = hash*3+toupper(s[1]), s[2]) &&
+ (hash = hash*2+toupper(s[2]), s[3]) &&
+ (hash = hash*2+toupper(s[3]), s[4]) &&
+ (hash = hash*2+toupper(s[4]), s[5]) &&
+ (hash = hash*2+toupper(s[5]), s[6]) &&
+ (hash = hash*2+toupper(s[6]),
+ hash = hash*2+toupper(s[7]))
+ );
+
+ return hash;
+}
//
// LUMP BASED ROUTINES.
@@ -206,12 +214,12 @@ boolean W_AddFile (char *filename)
startlump = numlumps;
- if (strcmpi (filename+strlen(filename)-3 , "wad" ) )
+ if (strcasecmp(filename+strlen(filename)-3 , "wad" ) )
{
// single lump file
fileinfo = Z_Malloc(sizeof(filelump_t), PU_STATIC, 0);
fileinfo->filepos = 0;
- fileinfo->size = filelength(handle);
+ fileinfo->size = FileLength(handle);
ExtractFileBase (filename, fileinfo->name);
numlumps++;
}
@@ -264,6 +272,12 @@ boolean W_AddFile (char *filename)
Z_Free(fileinfo);
+ if (lumphash != NULL)
+ {
+ Z_Free(lumphash);
+ lumphash = NULL;
+ }
+
return true;
}
@@ -337,42 +351,46 @@ int W_NumLumps (void)
int W_CheckNumForName (char* name)
{
- union {
- char s[9];
- int x[2];
-
- } name8;
-
- int v1;
- int v2;
- lumpinfo_t* lump_p;
-
- // make the name into two integers for easy compares
- strncpy (name8.s,name,8);
-
- // in case the name was a fill 8 chars
- name8.s[8] = 0;
-
- // case insensitive
- string_to_upper (name8.s);
-
- v1 = name8.x[0];
- v2 = name8.x[1];
-
+ lumpinfo_t *lump_p;
+ int i;
- // scan backwards so patch lump files take precedence
- lump_p = lumpinfo + numlumps;
+ // Do we have a hash table yet?
- while (lump_p-- != lumpinfo)
+ if (lumphash != NULL)
{
- if ( *(int *)lump_p->name == v1
- && *(int *)&lump_p->name[4] == v2)
- {
- return lump_p - lumpinfo;
- }
+ int hash;
+
+ printf("looking up %s\n", name);
+
+ // We do! Excellent.
+
+ hash = W_LumpNameHash(name) % numlumps;
+
+ for (lump_p = lumphash[hash]; lump_p != NULL; lump_p = lump_p->next)
+ {
+ if (!strncasecmp(lump_p->name, name, 8))
+ {
+ return lump_p - lumpinfo;
+ }
+ }
+ }
+ else
+ {
+ // We don't have a hash table generate yet. Linear search :-(
+ //
+ // scan backwards so patch lump files take precedence
+
+ for (i=numlumps-1; i >= 0; --i)
+ {
+ if (!strncasecmp(lumpinfo[i].name, name, 8))
+ {
+ return i;
+ }
+ }
}
// TFB. Not found.
+
return -1;
}
@@ -565,3 +583,36 @@ void W_Profile (void)
#endif
+// Generate a hash table for fast lookups
+
+void W_GenerateHashTable(void)
+{
+ int i;
+
+ // Free the old hash table, if there is one
+
+ if (lumphash != NULL)
+ {
+ Z_Free(lumphash);
+ }
+
+ // Generate hash table
+
+ lumphash = Z_Malloc(sizeof(lumpinfo_t *) * numlumps, PU_STATIC, NULL);
+ memset(lumphash, 0, sizeof(lumpinfo_t *) * numlumps);
+
+ for (i=0; i<numlumps; ++i)
+ {
+ unsigned int hash;
+
+ hash = W_LumpNameHash(lumpinfo[i].name) % numlumps;
+
+ // Hook into the hash table
+
+ lumpinfo[i].next = lumphash[hash];
+ lumphash[hash] = &lumpinfo[i];
+ }
+
+ // All done!
+}
+