From e1a861f0a522101547e07508ef524862b4242c8c Mon Sep 17 00:00:00 2001 From: uz Date: Sun, 21 Aug 2011 13:15:52 +0000 Subject: [PATCH] Use the hashtab to implement the string pool hash table. git-svn-id: svn://svn.cc65.org/cc65/trunk@5239 b7a2c559-68d2-44c3-8de9-860c34a00d81 --- src/common/strpool.c | 160 ++++++++++++++++++++++++++----------------- src/common/strpool.h | 35 +--------- 2 files changed, 99 insertions(+), 96 deletions(-) diff --git a/src/common/strpool.c b/src/common/strpool.c index 9157a73a8..12dab95b0 100644 --- a/src/common/strpool.c +++ b/src/common/strpool.c @@ -47,12 +47,33 @@ /* common */ #include "coll.h" #include "hashfunc.h" +#include "hashtab.h" #include "strbuf.h" #include "strpool.h" #include "xmalloc.h" +/*****************************************************************************/ +/* Forwards */ +/*****************************************************************************/ + + + +static unsigned HT_GenHash (const void* Key); +/* Generate the hash over a key. */ + +static const void* HT_GetKey (const void* Entry); +/* Given a pointer to the user entry data, return a pointer to the key */ + +static int HT_Compare (const void* Key1, const void* Key2); +/* Compare two keys. The function must return a value less than zero if + * Key1 is smaller than Key2, zero if both are equal, and a value greater + * than zero if Key1 is greater then Key2. + */ + + + /*****************************************************************************/ /* Data */ /*****************************************************************************/ @@ -61,12 +82,25 @@ /* A string pool entry */ struct StringPoolEntry { - StringPoolEntry* Next; /* Pointer to next entry in hash chain */ - unsigned Hash; /* Full hash value */ + HashNode Node; /* Node for the hash table */ unsigned Id; /* The numeric string id */ StrBuf Buf; /* The string itself */ }; +/* A string pool */ +struct StringPool { + Collection Entries; /* Entries sorted by number */ + unsigned TotalSize; /* Total size of all string data */ + HashTable Tab; /* Hash table */ +}; + +/* Hash table functions */ +static const HashFunctions HashFunc = { + HT_GenHash, + HT_GetKey, + HT_Compare +}; + /*****************************************************************************/ @@ -75,15 +109,14 @@ struct StringPoolEntry { -static StringPoolEntry* NewStringPoolEntry (const StrBuf* S, unsigned Hash, unsigned Id) +static StringPoolEntry* NewStringPoolEntry (const StrBuf* S, unsigned Id) /* Create a new string pool entry and return it. */ { /* Allocate memory */ StringPoolEntry* E = xmalloc (sizeof (StringPoolEntry)); /* Initialize the fields */ - E->Next = 0; - E->Hash = Hash; + InitHashNode (&E->Node); E->Id = Id; SB_Init (&E->Buf); SB_Copy (&E->Buf, S); @@ -97,32 +130,64 @@ static StringPoolEntry* NewStringPoolEntry (const StrBuf* S, unsigned Hash, unsi +/*****************************************************************************/ +/* Hash table functions */ +/*****************************************************************************/ + + + +static unsigned HT_GenHash (const void* Key) +/* Generate the hash over a key. */ +{ + return HashBuf (Key); +} + + + +static const void* HT_GetKey (const void* Entry) +/* Given a pointer to the user entry data, return a pointer to the index */ +{ + return &((const StringPoolEntry*) Entry)->Buf; +} + + + +static int HT_Compare (const void* Key1, const void* Key2) +/* Compare two keys. The function must return a value less than zero if + * Key1 is smaller than Key2, zero if both are equal, and a value greater + * than zero if Key1 is greater then Key2. + */ +{ + return SB_Compare (Key1, Key2); +} + + + /*****************************************************************************/ /* Code */ /*****************************************************************************/ -StringPool* InitStringPool (StringPool* P) -/* Initialize a string pool */ +StringPool* NewStringPool (unsigned HashSlots) +/* Allocate, initialize and return a new string pool */ { - unsigned I; + /* Allocate memory */ + StringPool* P = xmalloc (sizeof (*P)); /* Initialize the fields */ - for (I = 0; I < sizeof (P->Tab) / sizeof (P->Tab[0]); ++I) { - P->Tab[I] = 0; - } - P->Entries = EmptyCollection; + P->Entries = EmptyCollection; P->TotalSize = 0; + InitHashTable (&P->Tab, HashSlots, &HashFunc); - /* Return a pointer to the initialized pool */ + /* Return a pointer to the new pool */ return P; } -void DoneStringPool (StringPool* P) -/* Free the data of a string pool (but not the data itself) */ +void FreeStringPool (StringPool* P) +/* Free a string pool */ { unsigned I; @@ -140,31 +205,8 @@ void DoneStringPool (StringPool* P) } CollDeleteAll (&P->Entries); - /* Clear the hash table */ - for (I = 0; I < sizeof (P->Tab) / sizeof (P->Tab[0]); ++I) { - P->Tab[I] = 0; - } - - /* Reset the size */ - P->TotalSize = 0; -} - - - -StringPool* NewStringPool (void) -/* Allocate, initialize and return a new string pool */ -{ - /* Allocate memory, initialize and return it */ - return InitStringPool (xmalloc (sizeof (StringPool))); -} - - - -void FreeStringPool (StringPool* P) -/* Free a string pool */ -{ - /* Free all entries */ - DoneStringPool (P); + /* Free the hash table */ + DoneHashTable (&P->Tab); /* Free the string pool itself */ xfree (P); @@ -190,34 +232,24 @@ unsigned SP_Add (StringPool* P, const StrBuf* S) * existing string. */ { - /* Calculate the string hash */ - unsigned Hash = HashBuf (S); - - /* Calculate the reduced string hash */ - unsigned RHash = Hash % (sizeof (P->Tab)/sizeof (P->Tab[0])); - - /* Search for an existing entry */ - StringPoolEntry* E = P->Tab[RHash]; - while (E) { - if (E->Hash == Hash && SB_Compare (&E->Buf, S) == 0) { - /* Found, return the id of the existing string */ - return E->Id; - } - E = E->Next; - } + /* Search for a matching entry in the hash table */ + StringPoolEntry* E = HT_FindEntry (&P->Tab, S); + + /* Did we find it? */ + if (E != 0) { - /* We didn't find the entry, so create a new one */ - E = NewStringPoolEntry (S, Hash, CollCount (&P->Entries)); + /* We didn't find the entry, so create a new one */ + E = NewStringPoolEntry (S, CollCount (&P->Entries)); - /* Insert the new entry into the entry collection */ - CollAppend (&P->Entries, E); + /* Insert the new entry into the entries collection */ + CollAppend (&P->Entries, E); - /* Insert the new entry into the hash table */ - E->Next = P->Tab[RHash]; - P->Tab[RHash] = E; + /* Insert the new entry into the hash table */ + HT_InsertEntry (&P->Tab, E); - /* Add up the string size */ - P->TotalSize += SB_GetLen (&E->Buf); + /* Add up the string size */ + P->TotalSize += SB_GetLen (&E->Buf); + } /* Return the id of the entry */ return E->Id; diff --git a/src/common/strpool.h b/src/common/strpool.h index 2c7e39df1..60b8b3451 100644 --- a/src/common/strpool.h +++ b/src/common/strpool.h @@ -48,9 +48,7 @@ /* common */ -#include "attrib.h" -#include "coll.h" -#include "inline.h" +#include "hashtab.h" #include "strbuf.h" @@ -66,20 +64,6 @@ typedef struct StringPoolEntry StringPoolEntry; /* A string pool */ typedef struct StringPool StringPool; -struct StringPool { - Collection Entries; /* Entries sorted by number */ - unsigned TotalSize; /* Total size of all string data */ - StringPoolEntry* Tab[4177]; /* Entry hash table */ -}; - -/* A string pool initializer. We do only initialize the first field, all - * others will get zeroed out by the compiler. - */ -#define STATIC_STRINGPOOL_INITIALIZER { \ - STATIC_COLLECTION_INITIALIZER, \ - 0, \ - { 0 } \ -} @@ -89,13 +73,7 @@ struct StringPool { -StringPool* InitStringPool (StringPool* P); -/* Initialize a string pool */ - -void DoneStringPool (StringPool* P); -/* Free the data of a string pool (but not the data itself) */ - -StringPool* NewStringPool (void); +StringPool* NewStringPool (unsigned HashSlots); /* Allocate, initialize and return a new string pool */ void FreeStringPool (StringPool* P); @@ -115,15 +93,8 @@ unsigned SP_AddStr (StringPool* P, const char* S); * exist in the pool, SP_Add will just return the index of the existing string. */ -#if defined(HAVE_INLINE) -INLINE unsigned SP_GetCount (const StringPool* P) +unsigned SP_GetCount (const StringPool* P); /* Return the number of strings in the pool */ -{ - return CollCount (&P->Entries); -} -#else -# define SP_GetCount(P) CollCount (&(P)->Entries) -#endif -- 2.39.5