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-2008 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 "hashstr.h"
  50 #include "strbuf.h"
  51 #include "strpool.h"
  52 #include "xmalloc.h"
  53
  54
  55
  56 /*****************************************************************************/
  57 /*                                     Data                                  */
  58 /*****************************************************************************/
  59
  60
  61
  62 /* A string pool entry */
  63 struct StringPoolEntry {
  64     StringPoolEntry*    Next;   /* Pointer to next entry in hash chain */
  65     unsigned            Hash;   /* Full hash value */
  66     unsigned            Id;     /* The numeric string id */
  67     StrBuf              Buf;    /* The string itself */
  68 };
  69
  70
  71
  72 /*****************************************************************************/
  73 /*                          struct StringPoolEntry                           */
  74 /*****************************************************************************/
  75
  76
  77
  78 static StringPoolEntry* NewStringPoolEntry (const StrBuf* S, unsigned Hash, unsigned Id)
  79 /* Create a new string pool entry and return it. */
  80 {
  81     /* Allocate memory */
  82     StringPoolEntry* E = xmalloc (sizeof (StringPoolEntry));
  83
  84     /* Initialize the fields */
  85     E->Next = 0;
  86     E->Hash = Hash;
  87     E->Id   = Id;
  88     E->Buf  = AUTO_STRBUF_INITIALIZER;
  89     SB_Copy (&E->Buf, S);
  90
  91     /* Always zero terminate the string */
  92     SB_Terminate (&E->Buf);
  93
  94     /* Return the new entry */
  95     return E;
  96 }
  97
  98
  99
 100 /*****************************************************************************/
 101 /*                                     Code                                  */
 102 /*****************************************************************************/
 103
 104
 105
 106 StringPool* InitStringPool (StringPool* P)
 107 /* Initialize a string pool */
 108 {
 109     unsigned I;
 110
 111     /* Initialize the fields */
 112     for (I = 0; I < sizeof (P->Tab) / sizeof (P->Tab[0]); ++I) {
 113         P->Tab[I] = 0;
 114     }
 115     P->Entries = EmptyCollection;
 116     P->TotalSize = 0;
 117
 118     /* Return a pointer to the initialized pool */
 119     return P;
 120 }
 121
 122
 123
 124 void DoneStringPool (StringPool* P)
 125 /* Free the data of a string pool (but not the data itself) */
 126 {
 127     unsigned I;
 128
 129     /* Free all entries and clear the entry collection */
 130     for (I = 0; I < CollCount (&P->Entries); ++I) {
 131
 132         /* Get a pointer to the entry */
 133         StringPoolEntry* E = CollAtUnchecked (&P->Entries, I);
 134
 135         /* Free string buffer memory */
 136         SB_Done (&E->Buf);
 137
 138         /* Free the memory for the entry itself */
 139         xfree (E);
 140     }
 141     CollDeleteAll (&P->Entries);
 142
 143     /* Clear the hash table */
 144     for (I = 0; I < sizeof (P->Tab) / sizeof (P->Tab[0]); ++I) {
 145         P->Tab[I] = 0;
 146     }
 147
 148     /* Reset the size */
 149     P->TotalSize = 0;
 150 }
 151
 152
 153
 154 StringPool* NewStringPool (void)
 155 /* Allocate, initialize and return a new string pool */
 156 {
 157     /* Allocate memory, initialize and return it */
 158     return InitStringPool (xmalloc (sizeof (StringPool)));
 159 }
 160
 161
 162
 163 void FreeStringPool (StringPool* P)
 164 /* Free a string pool */
 165 {
 166     /* Free all entries */
 167     DoneStringPool (P);
 168
 169     /* Free the string pool itself */
 170     xfree (P);
 171 }
 172
 173
 174
 175 const StrBuf* SP_Get (const StringPool* P, unsigned Index)
 176 /* Return a string from the pool. Index must exist, otherwise FAIL is called. */
 177 {
 178     /* Get the collection entry */
 179     const StringPoolEntry* E = CollConstAt (&P->Entries, Index);
 180
 181     /* Return the string from the entry */
 182     return &E->Buf;
 183 }
 184
 185
 186
 187 unsigned SP_Add (StringPool* P, const StrBuf* S)
 188 /* Add a string buffer to the buffer and return the index. If the string does
 189  * already exist in the pool, SP_AddBuf will just return the index of the
 190  * existing string.
 191  */
 192 {
 193     /* Calculate the string hash */
 194     unsigned Hash = HashBuf (S);
 195
 196     /* Calculate the reduced string hash */
 197     unsigned RHash = Hash % (sizeof (P->Tab)/sizeof (P->Tab[0]));
 198
 199     /* Search for an existing entry */
 200     StringPoolEntry* E = P->Tab[RHash];
 201     while (E) {
 202         if (E->Hash == Hash && SB_Compare (&E->Buf, S) == 0) {
 203             /* Found, return the id of the existing string */
 204             return E->Id;
 205         }
 206         E = E->Next;
 207     }
 208
 209     /* We didn't find the entry, so create a new one */
 210     E = NewStringPoolEntry (S, Hash, CollCount (&P->Entries));
 211
 212     /* Insert the new entry into the entry collection */
 213     CollAppend (&P->Entries, E);
 214
 215     /* Insert the new entry into the hash table */
 216     E->Next = P->Tab[RHash];
 217     P->Tab[RHash] = E;
 218
 219     /* Add up the string size */
 220     P->TotalSize += SB_GetLen (&E->Buf);
 221
 222     /* Return the id of the entry */
 223     return E->Id;
 224 }
 225
 226
 227
 228 unsigned SP_AddStr (StringPool* P, const char* S)
 229 /* Add a string to the buffer and return the index. If the string does already
 230  * exist in the pool, SP_Add will just return the index of the existing string.
 231  */
 232 {
 233     unsigned Id;
 234
 235     /* First make a string buffer, then add it. This is some overhead, but the
 236      * routine will probably go.
 237      */
 238     StrBuf Buf;
 239     Id = SP_Add (P, SB_InitFromString (&Buf, S));
 240
 241     /* Return the id of the new entry */
 242     return Id;
 243 }
 244
 245
 246