Add hash table for fast texture lookup; refactor P_GroupLines to use an

O(n) rather than O(n^2) algorithm: faster loading maps like sid.wad map03

Subversion-branch: /trunk/chocolate-doom
Subversion-revision: 558

4 files changed, 113 insertions, 29 deletions

diff --git a/src/p_setup.c b/src/p_setup.c
index ab3847d1..f71202f5 100644
--- a/src/p_setup.c
+++ b/src/p_setup.c
@@ -1,7 +1,7 @@
 // Emacs style mode select   -*- C++ -*- 
 //-----------------------------------------------------------------------------
 //
-// $Id: p_setup.c 432 2006-03-24 16:51:28Z fraggle $
+// $Id: p_setup.c 558 2006-06-16 17:06:05Z fraggle $
 //
 // Copyright(C) 1993-1996 Id Software, Inc.
 // Copyright(C) 2005 Simon Howard
@@ -45,7 +45,7 @@
 //-----------------------------------------------------------------------------
 
 static const char
-rcsid[] = "$Id: p_setup.c 432 2006-03-24 16:51:28Z fraggle $";
+rcsid[] = "$Id: p_setup.c 558 2006-06-16 17:06:05Z fraggle $";
 
 
 #include <math.h>
@@ -554,27 +554,61 @@ void P_GroupLines (void)
 	    total++;
 	}
     }
-	
+
     // build line tables for each sector	
     linebuffer = Z_Malloc (total*sizeof(line_t *), PU_LEVEL, 0);
+
+    for (i=0; i<numsectors; ++i)
+    {
+        // Assign the line buffer for this sector
+
+        sectors[i].lines = linebuffer;
+        linebuffer += sectors[i].linecount;
+
+        // Reset linecount to zero so in the next stage we can count
+        // lines into the list.
+
+        sectors[i].linecount = 0;
+    }
+
+    // Assign lines to sectors
+
+    for (i=0; i<numlines; ++i)
+    { 
+        li = &lines[i];
+
+        if (li->frontsector != NULL)
+        {
+            sector = li->frontsector;
+
+            sector->lines[sector->linecount] = li;
+            ++sector->linecount;
+        }
+
+        if (li->backsector != NULL && li->frontsector != li->backsector)
+        {
+            sector = li->backsector;
+
+            sector->lines[sector->linecount] = li;
+            ++sector->linecount;
+        }
+    }
+    
+    // Generate bounding boxes for sectors
+	
     sector = sectors;
     for (i=0 ; i<numsectors ; i++, sector++)
     {
 	M_ClearBox (bbox);
-	sector->lines = linebuffer;
-	li = lines;
-	for (j=0 ; j<numlines ; j++, li++)
+
+	for (j=0 ; j<sector->linecount; j++)
 	{
-	    if (li->frontsector == sector || li->backsector == sector)
-	    {
-		*linebuffer++ = li;
-		M_AddToBox (bbox, li->v1->x, li->v1->y);
-		M_AddToBox (bbox, li->v2->x, li->v2->y);
-	    }
+            li = sector->lines[j];
+
+            M_AddToBox (bbox, li->v1->x, li->v1->y);
+            M_AddToBox (bbox, li->v2->x, li->v2->y);
 	}
-	if (linebuffer - sector->lines != sector->linecount)
-	    I_Error ("P_GroupLines: miscounted");
-			
+
 	// set the degenmobj_t to the middle of the bounding box
 	sector->soundorg.x = (bbox[BOXRIGHT]+bbox[BOXLEFT])/2;
 	sector->soundorg.y = (bbox[BOXTOP]+bbox[BOXBOTTOM])/2;
diff --git a/src/r_data.c b/src/r_data.c
index 3d193c39..52999dac 100644
--- a/src/r_data.c
+++ b/src/r_data.c
@@ -1,7 +1,7 @@
 // Emacs style mode select   -*- C++ -*- 
 //-----------------------------------------------------------------------------
 //
-// $Id: r_data.c 125 2005-09-22 21:42:24Z fraggle $
+// $Id: r_data.c 558 2006-06-16 17:06:05Z fraggle $
 //
 // Copyright(C) 1993-1996 Id Software, Inc.
 // Copyright(C) 2005 Simon Howard
@@ -58,7 +58,7 @@
 
 
 static const char
-rcsid[] = "$Id: r_data.c 125 2005-09-22 21:42:24Z fraggle $";
+rcsid[] = "$Id: r_data.c 558 2006-06-16 17:06:05Z fraggle $";
 
 #include "i_system.h"
 #include "z_zone.h"
@@ -139,19 +139,29 @@ typedef struct
 // A maptexturedef_t describes a rectangular texture,
 //  which is composed of one or more mappatch_t structures
 //  that arrange graphic patches.
-typedef struct
+
+typedef struct texture_s texture_t;
+
+struct texture_s
 {
     // Keep name for switch changing, etc.
     char	name[8];		
     short	width;
     short	height;
+
+    // Index in textures list
+
+    int         index;
+
+    // Next in hash table chain
+
+    texture_t  *next;
     
     // All the patches[patchcount]
     //  are drawn back to front into the cached texture.
     short	patchcount;
     texpatch_t	patches[1];		
-    
-} texture_t;
+};
 
 
 
@@ -169,6 +179,7 @@ int		numspritelumps;
 
 int		numtextures;
 texture_t**	textures;
+texture_t**     textures_hashtable;
 
 
 int*			texturewidthmask;
@@ -432,6 +443,32 @@ R_GetColumn
 }
 
 
+static void GenerateTextureHashTable(void)
+{
+    int i;
+    int key;
+
+    textures_hashtable 
+            = Z_Malloc(sizeof(texture_t *) * numtextures, PU_STATIC, 0);
+
+    memset(textures_hashtable, 0, sizeof(texture_t *) * numtextures);
+
+    // Add all textures to hash table
+
+    for (i=0; i<numtextures; ++i)
+    {
+        // Store index
+
+        textures[i]->index = i;
+
+        // Hook into hash table
+
+        key = W_LumpNameHash(textures[i]->name) % numtextures;
+
+        textures[i]->next = textures_hashtable[key];
+        textures_hashtable[key] = textures[i];
+    }
+}
 
 
 //
@@ -605,6 +642,8 @@ void R_InitTextures (void)
     
     for (i=0 ; i<numtextures ; i++)
 	texturetranslation[i] = i;
+
+    GenerateTextureHashTable();
 }
 
 
@@ -726,16 +765,25 @@ int R_FlatNumForName (char* name)
 //
 int	R_CheckTextureNumForName (char *name)
 {
-    int		i;
+    texture_t *texture;
+    int key;
 
     // "NoTexture" marker.
     if (name[0] == '-')		
 	return 0;
 		
-    for (i=0 ; i<numtextures ; i++)
-	if (!strncasecmp (textures[i]->name, name, 8) )
-	    return i;
-		
+    key = W_LumpNameHash(name) % numtextures;
+
+    texture=textures_hashtable[key]; 
+    
+    while (texture != NULL)
+    {
+	if (!strncasecmp (texture->name, name, 8) )
+	    return texture->index;
+
+        texture = texture->next;
+    }
+    
     return -1;
 }
 
diff --git a/src/w_wad.c b/src/w_wad.c
index 5e8816c6..87186645 100644
--- a/src/w_wad.c
+++ b/src/w_wad.c
@@ -1,7 +1,7 @@
 // Emacs style mode select   -*- C++ -*- 
 //-----------------------------------------------------------------------------
 //
-// $Id: w_wad.c 437 2006-03-24 20:39:28Z fraggle $
+// $Id: w_wad.c 558 2006-06-16 17:06:05Z 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 437 2006-03-24 20:39:28Z fraggle $";
+rcsid[] = "$Id: w_wad.c 558 2006-06-16 17:06:05Z fraggle $";
 
 
 #include <ctype.h>
@@ -146,7 +146,7 @@ static void ExtractFileBase(char *path, char *dest)
 // Can be used for any 8-character names.
 // by Lee Killough
 
-static unsigned int W_LumpNameHash(const char *s)
+unsigned int W_LumpNameHash(const char *s)
 {
   unsigned int hash;
 
diff --git a/src/w_wad.h b/src/w_wad.h
index 659c0b40..2126ad9a 100644
--- a/src/w_wad.h
+++ b/src/w_wad.h
@@ -1,7 +1,7 @@
 // Emacs style mode select   -*- C++ -*- 
 //-----------------------------------------------------------------------------
 //
-// $Id: w_wad.h 438 2006-03-24 20:40:08Z fraggle $
+// $Id: w_wad.h 558 2006-06-16 17:06:05Z fraggle $
 //
 // Copyright(C) 1993-1996 Id Software, Inc.
 // Copyright(C) 2005 Simon Howard
@@ -92,6 +92,8 @@ void*	W_CacheLumpName (char* name, int tag);
 
 void    W_GenerateHashTable(void);
 
+extern unsigned int W_LumpNameHash(const char *s);
+
 
 #endif
 //-----------------------------------------------------------------------------