From 77e5d2063724defc57b60599d27f1e7488463f69 Mon Sep 17 00:00:00 2001 From: Simon Howard Date: Fri, 16 Jun 2006 17:06:05 +0000 Subject: 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 --- src/p_setup.c | 64 ++++++++++++++++++++++++++++++++++++++++++------------- src/r_data.c | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++--------- src/w_wad.c | 6 +++--- src/w_wad.h | 4 +++- 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 @@ -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; ifrontsector != 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 ; ilines = linebuffer; - li = lines; - for (j=0 ; jlinecount; 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; iindex = 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 ; iname, 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 @@ -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 //----------------------------------------------------------------------------- -- cgit v1.2.3