git.sur5r.net Git - cc65/blob - src/common/strpool.c

   1 /*****************************************************************************/
   2 /*                                                                           */
   3 /*                                 strpool.c                                 */
   4 /*                                                                           */
   5 /*                               A string pool                               */
   6 /*                                                                           */
   7 /*                                                                           */
   8 /*                                                                           */
   9 /* (C) 2003-2011, Ullrich von Bassewitz                                      */
  10 /*                Roemerstrasse 52                                           */
  11 /*                D-70794 Filderstadt                                        */
  12 /* EMail:         uz@cc65.org                                                */
  13 /*                                                                           */
  14 /*                                                                           */
  15 /* This software is provided 'as-is', without any expressed or implied       */
  16 /* warranty.  In no event will the authors be held liable for any damages    */
  17 /* arising from the use of this software.                                    */
  18 /*                                                                           */
  19 /* Permission is granted to anyone to use this software for any purpose,     */
  20 /* including commercial applications, and to alter it and redistribute it    */
  21 /* freely, subject to the following restrictions:                            */
  22 /*                                                                           */
  23 /* 1. The origin of this software must not be misrepresented; you must not   */
  24 /*    claim that you wrote the original software. If you use this software   */
  25 /*    in a product, an acknowledgment in the product documentation would be  */
  26 /*    appreciated but is not required.                                       */
  27 /* 2. Altered source versions must be plainly marked as such, and must not   */
  28 /*    be misrepresented as being the original software.                      */
  29 /* 3. This notice may not be removed or altered from any source              */
  30 /*    distribution.                                                          */
  31 /*                                                                           */
  32 /*****************************************************************************/
  33
  34
  35
  36 /* A string pool is used to store identifiers and other strings. Each string
  37 ** stored in the pool has a unique id, which may be used to access the string
  38 ** in the pool. Identical strings are stored only once in the pool and have
  39 ** identical ids. This means that instead of comparing strings, just the
  40 ** string pool ids must be compared.
  41 */
  42
  43
  44
  45 #include <string.h>
  46
  47 /* common */
  48 #include "coll.h"
  49 #include "hashfunc.h"
  50 #include "hashtab.h"
  51 #include "strbuf.h"
  52 #include "strpool.h"
  53 #include "xmalloc.h"
  54
  55
  56
  57 /*****************************************************************************/
  58 /*                                 Forwards                                  */
  59 /*****************************************************************************/
  60
  61
  62
  63 static unsigned HT_GenHash (const void* Key);
  64 /* Generate the hash over a key. */
  65
  66 static const void* HT_GetKey (const void* Entry);
  67 /* Given a pointer to the user entry data, return a pointer to the key */
  68
  69 static int HT_Compare (const void* Key1, const void* Key2);
  70 /* Compare two keys. The function must return a value less than zero if
  71 ** Key1 is smaller than Key2, zero if both are equal, and a value greater
  72 ** than zero if Key1 is greater then Key2.
  73 */
  74
  75
  76
  77 /*****************************************************************************/
  78 /*                                     Data                                  */
  79 /*****************************************************************************/
  80
  81
  82
  83 /* A string pool entry */
  84 struct StringPoolEntry {
  85     HashNode            Node;   /* Node for the hash table */
  86     unsigned            Id;     /* The numeric string id */
  87     StrBuf              Buf;    /* The string itself */
  88 };
  89
  90 /* A string pool */
  91 struct StringPool {
  92     Collection          Entries;        /* Entries sorted by number */
  93     unsigned            TotalSize;      /* Total size of all string data */
  94     HashTable           Tab;            /* Hash table */
  95 };
  96
  97 /* Hash table functions */
  98 static const HashFunctions HashFunc = {
  99     HT_GenHash,
 100     HT_GetKey,
 101     HT_Compare
 102 };
 103
 104
 105
 106 /*****************************************************************************/
 107 /*                          struct StringPoolEntry                           */
 108 /*****************************************************************************/
 109
 110
 111
 112 static StringPoolEntry* NewStringPoolEntry (const StrBuf* S, unsigned Id)
 113 /* Create a new string pool entry and return it. */
 114 {
 115     /* Allocate memory */
 116     StringPoolEntry* E = xmalloc (sizeof (StringPoolEntry));
 117
 118     /* Initialize the fields */
 119     InitHashNode (&E->Node);
 120     E->Id   = Id;
 121     SB_Init (&E->Buf);
 122     SB_Copy (&E->Buf, S);
 123
 124     /* Always zero terminate the string */
 125     SB_Terminate (&E->Buf);
 126
 127     /* Return the new entry */
 128     return E;
 129 }
 130
 131
 132
 133 /*****************************************************************************/
 134 /*                           Hash table functions                            */
 135 /*****************************************************************************/
 136
 137
 138
 139 static unsigned HT_GenHash (const void* Key)
 140 /* Generate the hash over a key. */
 141 {
 142     return HashBuf (Key);
 143 }
 144
 145
 146
 147 static const void* HT_GetKey (const void* Entry)
 148 /* Given a pointer to the user entry data, return a pointer to the index */
 149 {
 150     return &((const StringPoolEntry*) Entry)->Buf;
 151 }
 152
 153
 154
 155 static int HT_Compare (const void* Key1, const void* Key2)
 156 /* Compare two keys. The function must return a value less than zero if
 157 ** Key1 is smaller than Key2, zero if both are equal, and a value greater
 158 ** than zero if Key1 is greater then Key2.
 159 */
 160 {
 161     return SB_Compare (Key1, Key2);
 162 }
 163
 164
 165
 166 /*****************************************************************************/
 167 /*                                     Code                                  */
 168 /*****************************************************************************/
 169
 170
 171
 172 StringPool* NewStringPool (unsigned HashSlots)
 173 /* Allocate, initialize and return a new string pool */
 174 {
 175     /* Allocate memory */
 176     StringPool* P = xmalloc (sizeof (*P));
 177
 178     /* Initialize the fields */
 179     P->Entries   = EmptyCollection;
 180     P->TotalSize = 0;
 181     InitHashTable (&P->Tab, HashSlots, &HashFunc);
 182
 183     /* Return a pointer to the new pool */
 184     return P;
 185 }
 186
 187
 188
 189 void FreeStringPool (StringPool* P)
 190 /* Free a string pool */
 191 {
 192     unsigned I;
 193
 194     /* Free all entries and clear the entry collection */
 195     for (I = 0; I < CollCount (&P->Entries); ++I) {
 196
 197         /* Get a pointer to the entry */
 198         StringPoolEntry* E = CollAtUnchecked (&P->Entries, I);
 199
 200         /* Free string buffer memory */
 201         SB_Done (&E->Buf);
 202
 203         /* Free the memory for the entry itself */
 204         xfree (E);
 205     }
 206     CollDeleteAll (&P->Entries);
 207
 208     /* Free the hash table */
 209     DoneHashTable (&P->Tab);
 210
 211     /* Free the string pool itself */
 212     xfree (P);
 213 }
 214
 215
 216
 217 const StrBuf* SP_Get (const StringPool* P, unsigned Index)
 218 /* Return a string from the pool. Index must exist, otherwise FAIL is called. */
 219 {
 220     /* Get the collection entry */
 221     const StringPoolEntry* E = CollConstAt (&P->Entries, Index);
 222
 223     /* Return the string from the entry */
 224     return &E->Buf;
 225 }
 226
 227
 228
 229 unsigned SP_Add (StringPool* P, const StrBuf* S)
 230 /* Add a string buffer to the buffer and return the index. If the string does
 231 ** already exist in the pool, SP_AddBuf will just return the index of the
 232 ** existing string.
 233 */
 234 {
 235     /* Search for a matching entry in the hash table */
 236     StringPoolEntry* E = HT_Find (&P->Tab, S);
 237
 238     /* Did we find it? */
 239     if (E == 0) {
 240
 241         /* We didn't find the entry, so create a new one */
 242         E = NewStringPoolEntry (S, CollCount (&P->Entries));
 243
 244         /* Insert the new entry into the entries collection */
 245         CollAppend (&P->Entries, E);
 246
 247         /* Insert the new entry into the hash table */
 248         HT_Insert (&P->Tab, E);
 249
 250         /* Add up the string size */
 251         P->TotalSize += SB_GetLen (&E->Buf);
 252     }
 253
 254     /* Return the id of the entry */
 255     return E->Id;
 256 }
 257
 258
 259
 260 unsigned SP_AddStr (StringPool* P, const char* S)
 261 /* Add a string to the buffer and return the index. If the string does already
 262 ** exist in the pool, SP_Add will just return the index of the existing string.
 263 */
 264 {
 265     unsigned Id;
 266
 267     /* First make a string buffer, then add it. This is some overhead, but the
 268     ** routine will probably go.
 269     */
 270     StrBuf Buf;
 271     Id = SP_Add (P, SB_InitFromString (&Buf, S));
 272
 273     /* Return the id of the new entry */
 274     return Id;
 275 }
 276
 277
 278
 279 unsigned SP_GetCount (const StringPool* P)
 280 /* Return the number of strings in the pool */
 281 {
 282     return CollCount (&P->Entries);
 283 }