/* */
/* */
/* */
-/* (C) 2003 Ullrich von Bassewitz */
-/* Römerstrasse 52 */
-/* D-70794 Filderstadt */
-/* EMail: uz@cc65.org */
+/* (C) 2003-2011, Ullrich von Bassewitz */
+/* Roemerstrasse 52 */
+/* D-70794 Filderstadt */
+/* EMail: uz@cc65.org */
/* */
/* */
/* This software is provided 'as-is', without any expressed or implied */
/* A string pool is used to store identifiers and other strings. Each string
- * stored in the pool has a unique id, which may be used to access the string
- * in the pool. Identical strings are only stored once in the pool and have
- * identical ids. This means that instead of comparing strings, just the
- * string pool ids must be compared.
- */
+** stored in the pool has a unique id, which may be used to access the string
+** in the pool. Identical strings are stored only once in the pool and have
+** identical ids. This means that instead of comparing strings, just the
+** string pool ids must be compared.
+*/
/* common */
#include "coll.h"
-#include "hashstr.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 */
/*****************************************************************************/
/* A string pool entry */
-struct StrPoolEntry {
- StrPoolEntry* Next; /* Pointer to next entry in hash chain */
- unsigned Hash; /* Full hash value */
+struct StringPoolEntry {
+ HashNode Node; /* Node for the hash table */
unsigned Id; /* The numeric string id */
- unsigned Len; /* Length of the string (excluding terminator) */
- char S[1]; /* The string itself */
+ 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
};
/*****************************************************************************/
-/* struct StrPoolEntry */
+/* struct StringPoolEntry */
/*****************************************************************************/
-static StrPoolEntry* NewStrPoolEntry (const char* S, unsigned Hash, unsigned Id)
+static StringPoolEntry* NewStringPoolEntry (const StrBuf* S, unsigned Id)
/* Create a new string pool entry and return it. */
{
- /* Get the length of the string */
- unsigned Len = strlen (S);
-
/* Allocate memory */
- StrPoolEntry* E = xmalloc (sizeof (StrPoolEntry) + Len);
+ StringPoolEntry* E = xmalloc (sizeof (StringPoolEntry));
/* Initialize the fields */
- E->Next = 0;
- E->Hash = Hash;
+ InitHashNode (&E->Node);
E->Id = Id;
- E->Len = Len;
- memcpy (E->S, S, Len+1);
+ SB_Init (&E->Buf);
+ SB_Copy (&E->Buf, S);
+
+ /* Always zero terminate the string */
+ SB_Terminate (&E->Buf);
/* Return the new entry */
return E;
/*****************************************************************************/
-/* Code */
+/* Hash table functions */
/*****************************************************************************/
-StrPool* InitStrPool (StrPool* P)
-/* Initialize a string pool */
+static unsigned HT_GenHash (const void* Key)
+/* Generate the hash over a key. */
{
- unsigned I;
+ return HashBuf (Key);
+}
- /* Initialize the fields */
- for (I = 0; I < sizeof (P->Tab) / sizeof (P->Tab[0]); ++I) {
- P->Tab[I] = 0;
- }
- P->Entries = EmptyCollection;
- P->TotalSize = 0;
- /* Return a pointer to the initialized pool */
- return P;
+
+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;
}
-void DoneStrPool (StrPool* P)
-/* Free the data of a string pool (but not the data itself) */
+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.
+*/
{
- unsigned I;
+ return SB_Compare (Key1, Key2);
+}
- /* Free all entries and clear the entry collection */
- for (I = 0; I < CollCount (&P->Entries); ++I) {
- xfree (CollAtUnchecked (&P->Entries, I));
- }
- 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;
-}
+/*****************************************************************************/
+/* Code */
+/*****************************************************************************/
-StrPool* NewStrPool (void)
+StringPool* NewStringPool (unsigned HashSlots)
/* Allocate, initialize and return a new string pool */
{
- /* Allocate memory, initialize and return it */
- return InitStrPool (xmalloc (sizeof (StrPool)));
+ /* Allocate memory */
+ StringPool* P = xmalloc (sizeof (*P));
+
+ /* Initialize the fields */
+ P->Entries = EmptyCollection;
+ P->TotalSize = 0;
+ InitHashTable (&P->Tab, HashSlots, &HashFunc);
+
+ /* Return a pointer to the new pool */
+ return P;
}
-void FreeStrPool (StrPool* P)
+void FreeStringPool (StringPool* P)
/* Free a string pool */
{
- /* Free all entries */
- DoneStrPool (P);
+ unsigned I;
+
+ /* Free all entries and clear the entry collection */
+ for (I = 0; I < CollCount (&P->Entries); ++I) {
+
+ /* Get a pointer to the entry */
+ StringPoolEntry* E = CollAtUnchecked (&P->Entries, I);
+
+ /* Free string buffer memory */
+ SB_Done (&E->Buf);
+
+ /* Free the memory for the entry itself */
+ xfree (E);
+ }
+ CollDeleteAll (&P->Entries);
+
+ /* Free the hash table */
+ DoneHashTable (&P->Tab);
/* Free the string pool itself */
xfree (P);
-const char* SP_Get (const StrPool* P, unsigned Index)
+const StrBuf* SP_Get (const StringPool* P, unsigned Index)
/* Return a string from the pool. Index must exist, otherwise FAIL is called. */
{
/* Get the collection entry */
- const StrPoolEntry* E = CollConstAt (&P->Entries, Index);
+ const StringPoolEntry* E = CollConstAt (&P->Entries, Index);
/* Return the string from the entry */
- return E->S;
+ return &E->Buf;
}
-unsigned SP_Add (StrPool* P, const char* S)
-/* Add a string to the buffer and return the index. If the string does already
- * exist in the pool, SP_Add will just return the index of the existing string.
- */
+unsigned SP_Add (StringPool* P, const StrBuf* S)
+/* Add a string buffer to the buffer and return the index. If the string does
+** already exist in the pool, SP_AddBuf will just return the index of the
+** existing string.
+*/
{
- /* Calculate the string hash */
- unsigned Hash = HashStr (S);
-
- /* Calculate the reduced string hash */
- unsigned RHash = Hash % (sizeof (P->Tab)/sizeof (P->Tab[0]));
-
- /* Search for an existing entry */
- StrPoolEntry* E = P->Tab[RHash];
- while (E) {
- if (E->Hash == Hash && strcmp (E->S, 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_Find (&P->Tab, S);
- /* We didn't find the entry, so create a new one */
- E = NewStrPoolEntry (S, Hash, CollCount (&P->Entries));
+ /* Did we find it? */
+ if (E == 0) {
- /* Insert the new entry into the entry collection */
- CollAppend (&P->Entries, E);
+ /* We didn't find the entry, so create a new one */
+ E = NewStringPoolEntry (S, CollCount (&P->Entries));
- /* Insert the new entry into the hash table */
- E->Next = P->Tab[RHash];
- P->Tab[RHash] = E;
+ /* Insert the new entry into the entries collection */
+ CollAppend (&P->Entries, E);
- /* Add up the string size (plus terminator) */
- P->TotalSize += E->Len + 1;
+ /* Insert the new entry into the hash table */
+ HT_Insert (&P->Tab, E);
+
+ /* Add up the string size */
+ P->TotalSize += SB_GetLen (&E->Buf);
+ }
/* Return the id of the entry */
return E->Id;
-unsigned SP_AddBuf (StrPool* P, const void* Buffer, unsigned Size)
-/* Add strings from a string buffer. Buffer must contain a list of zero
- * terminated strings. These strings are added to the pool, starting with
- * the current index. The number of strings added is returned.
- * Beware: The function will do only loose range checking for the buffer
- * limits, so a SEGV may occur if the last string in the buffer is not
- * correctly terminated.
- */
+unsigned SP_AddStr (StringPool* P, const char* S)
+/* Add a string to the buffer and return the index. If the string does already
+** exist in the pool, SP_Add will just return the index of the existing string.
+*/
{
- /* Cast the buffer pointer to something useful */
- const char* Buf = Buffer;
-
- /* Remember the current number of strings in the buffer. */
- unsigned OldCount = SB_GetCount (P);
+ unsigned Id;
- /* Add all strings from the buffer */
- while (Size) {
+ /* First make a string buffer, then add it. This is some overhead, but the
+ ** routine will probably go.
+ */
+ StrBuf Buf;
+ Id = SP_Add (P, SB_InitFromString (&Buf, S));
- /* Add the next entry */
- unsigned Id = SP_Add (P, Buf);
-
- /* Get the entry from the id */
- const StrPoolEntry* E = CollConstAt (&P->Entries, Id);
-
- /* Skip this string */
- Buf += E->Len + 1;
- Size -= E->Len + 1;
- }
-
- /* Return the number of strings added */
- return SB_GetCount (P) - OldCount;
+ /* Return the id of the new entry */
+ return Id;
}
-void SP_Build (StrPool* P, const void* Buffer, unsigned Size)
-/* Delete existing data and use the data from Buffer instead. */
+unsigned SP_GetCount (const StringPool* P)
+/* Return the number of strings in the pool */
{
- /* Delete old data */
- DoneStrPool (P);
-
- /* Add the buffer data */
- SP_AddBuf (P, Buffer, Size);
+ return CollCount (&P->Entries);
}
-
-
-
projects / cc65 / blobdiff