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      Ullrich von Bassewitz                                       */
  10 /*               Römerstrasse 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 only stored 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 StrPoolEntry {
  64     StrPoolEntry*       Next;   /* Pointer to next entry in hash chain */
  65     unsigned            Hash;   /* Full hash value */
  66     unsigned            Id;     /* The numeric string id */
  67     unsigned            Len;    /* Length of the string (excluding terminator) */
  68     char                S[1];   /* The string itself */
  69 };
  70
  71
  72
  73 /*****************************************************************************/
  74 /*                            struct StrPoolEntry                            */
  75 /*****************************************************************************/
  76
  77
  78
  79 static StrPoolEntry* NewStrPoolEntry (const char* S, unsigned Hash, unsigned Id)
  80 /* Create a new string pool entry and return it. */
  81 {
  82     /* Get the length of the string */
  83     unsigned Len = strlen (S);
  84
  85     /* Allocate memory */
  86     StrPoolEntry* E = xmalloc (sizeof (StrPoolEntry) + Len);
  87
  88     /* Initialize the fields */
  89     E->Next = 0;
  90     E->Hash = Hash;
  91     E->Id   = Id;
  92     E->Len  = Len;
  93     memcpy (E->S, S, Len+1);
  94
  95     /* Return the new entry */
  96     return E;
  97 }
  98
  99
 100
 101 /*****************************************************************************/
 102 /*                                     Code                                  */
 103 /*****************************************************************************/
 104
 105
 106
 107 StrPool* InitStrPool (StrPool* P)
 108 /* Initialize a string pool */
 109 {
 110     unsigned I;
 111
 112     /* Initialize the fields */
 113     for (I = 0; I < sizeof (P->Tab) / sizeof (P->Tab[0]); ++I) {
 114         P->Tab[I] = 0;
 115     }
 116     P->Entries = EmptyCollection;
 117     P->TotalSize = 0;
 118
 119     /* Return a pointer to the initialized pool */
 120     return P;
 121 }
 122
 123
 124
 125 void DoneStrPool (StrPool* P)
 126 /* Free the data of a string pool (but not the data itself) */
 127 {
 128     unsigned I;
 129
 130     /* Free all entries and clear the entry collection */
 131     for (I = 0; I < CollCount (&P->Entries); ++I) {
 132         xfree (CollAtUnchecked (&P->Entries, I));
 133     }
 134     CollDeleteAll (&P->Entries);
 135
 136     /* Clear the hash table */
 137     for (I = 0; I < sizeof (P->Tab) / sizeof (P->Tab[0]); ++I) {
 138         P->Tab[I] = 0;
 139     }
 140
 141     /* Reset the size */
 142     P->TotalSize = 0;
 143 }
 144
 145
 146
 147 StrPool* NewStrPool (void)
 148 /* Allocate, initialize and return a new string pool */
 149 {
 150     /* Allocate memory, initialize and return it */
 151     return InitStrPool (xmalloc (sizeof (StrPool)));
 152 }
 153
 154
 155
 156 void FreeStrPool (StrPool* P)
 157 /* Free a string pool */
 158 {
 159     /* Free all entries */
 160     DoneStrPool (P);
 161
 162     /* Free the string pool itself */
 163     xfree (P);
 164 }
 165
 166
 167
 168 const char* SP_Get (const StrPool* P, unsigned Index)
 169 /* Return a string from the pool. Index must exist, otherwise FAIL is called. */
 170 {
 171     /* Get the collection entry */
 172     const StrPoolEntry* E = CollConstAt (&P->Entries, Index);
 173
 174     /* Return the string from the entry */
 175     return E->S;
 176 }
 177
 178
 179
 180 unsigned SP_Add (StrPool* P, const char* S)
 181 /* Add a string to the buffer and return the index. If the string does already
 182  * exist in the pool, SP_Add will just return the index of the existing string.
 183  */
 184 {
 185     /* Calculate the string hash */
 186     unsigned Hash = HashStr (S);
 187
 188     /* Calculate the reduced string hash */
 189     unsigned RHash = Hash % (sizeof (P->Tab)/sizeof (P->Tab[0]));
 190
 191     /* Search for an existing entry */
 192     StrPoolEntry* E = P->Tab[RHash];
 193     while (E) {
 194         if (E->Hash == Hash && strcmp (E->S, S) == 0) {
 195             /* Found, return the id of the existing string */
 196             return E->Id;
 197         }
 198         E = E->Next;
 199     }
 200
 201     /* We didn't find the entry, so create a new one */
 202     E = NewStrPoolEntry (S, Hash, CollCount (&P->Entries));
 203
 204     /* Insert the new entry into the entry collection */
 205     CollAppend (&P->Entries, E);
 206
 207     /* Insert the new entry into the hash table */
 208     E->Next = P->Tab[RHash];
 209     P->Tab[RHash] = E;
 210
 211     /* Add up the string size (plus terminator) */
 212     P->TotalSize += E->Len + 1;
 213
 214     /* Return the id of the entry */
 215     return E->Id;
 216 }
 217
 218
 219
 220 unsigned SP_AddBuf (StrPool* P, const void* Buffer, unsigned Size)
 221 /* Add strings from a string buffer. Buffer must contain a list of zero
 222  * terminated strings. These strings are added to the pool, starting with
 223  * the current index. The number of strings added is returned.
 224  * Beware: The function will do only loose range checking for the buffer
 225  * limits, so a SEGV may occur if the last string in the buffer is not
 226  * correctly terminated.
 227  */
 228 {
 229     /* Cast the buffer pointer to something useful */
 230     const char* Buf = Buffer;
 231
 232     /* Remember the current number of strings in the buffer. */
 233     unsigned OldCount = SB_GetCount (P);
 234
 235     /* Add all strings from the buffer */
 236     while (Size) {
 237
 238         /* Add the next entry */
 239         unsigned Id = SP_Add (P, Buf);
 240
 241         /* Get the entry from the id */
 242         const StrPoolEntry* E = CollConstAt (&P->Entries, Id);
 243
 244         /* Skip this string */
 245         Buf  += E->Len + 1;
 246         Size -= E->Len + 1;
 247     }
 248
 249     /* Return the number of strings added */
 250     return SB_GetCount (P) - OldCount;
 251 }
 252
 253
 254
 255 void SP_Build (StrPool* P, const void* Buffer, unsigned Size)
 256 /* Delete existing data and use the data from Buffer instead. */
 257 {
 258     /* Delete old data */
 259     DoneStrPool (P);
 260
 261     /* Add the buffer data */
 262     SP_AddBuf (P, Buffer, Size);
 263 }
 264
 265
 266