/*****************************************************************************/ /* */ /* strpool.c */ /* */ /* A string pool */ /* */ /* */ /* */ /* (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 */ /* warranty. In no event will the authors be held liable for any damages */ /* arising from the use of this software. */ /* */ /* Permission is granted to anyone to use this software for any purpose, */ /* including commercial applications, and to alter it and redistribute it */ /* freely, subject to the following restrictions: */ /* */ /* 1. The origin of this software must not be misrepresented; you must not */ /* claim that you wrote the original software. If you use this software */ /* in a product, an acknowledgment in the product documentation would be */ /* appreciated but is not required. */ /* 2. Altered source versions must be plainly marked as such, and must not */ /* be misrepresented as being the original software. */ /* 3. This notice may not be removed or altered from any source */ /* distribution. */ /* */ /*****************************************************************************/ /* 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 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. */ #include /* 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 */ /*****************************************************************************/ /* A string pool entry */ struct StringPoolEntry { 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 }; /*****************************************************************************/ /* struct StringPoolEntry */ /*****************************************************************************/ 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 */ InitHashNode (&E->Node); E->Id = Id; SB_Init (&E->Buf); SB_Copy (&E->Buf, S); /* Always zero terminate the string */ SB_Terminate (&E->Buf); /* Return the new entry */ return E; } /*****************************************************************************/ /* 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* NewStringPool (unsigned HashSlots) /* Allocate, initialize and return a new string pool */ { /* 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 FreeStringPool (StringPool* P) /* Free a string pool */ { 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 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 StringPoolEntry* E = CollConstAt (&P->Entries, Index); /* Return the string from the entry */ return &E->Buf; } 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. */ { /* Search for a matching entry in the hash table */ StringPoolEntry* E = HT_Find (&P->Tab, S); /* Did we find it? */ if (E == 0) { /* We didn't find the entry, so create a new one */ E = NewStringPoolEntry (S, CollCount (&P->Entries)); /* Insert the new entry into the entries collection */ CollAppend (&P->Entries, E); /* 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_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. */ { unsigned Id; /* 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)); /* Return the id of the new entry */ return Id; } unsigned SP_GetCount (const StringPool* P) /* Return the number of strings in the pool */ { return CollCount (&P->Entries); }