librune/strtable.c

   1 /*
   2  * STRTABLE.C   - String table routines
   3  *
   4  * (c)Copyright 1993-2014, Matthew Dillon, All Rights Reserved.  See the
   5  *    COPYRIGHT file at the base of the distribution.
   6  */
   7
   8 #include "defs.h"
   9
  10 #define STR_MAGIC       ((int)0xA5F3B211)
  11 #define STR_HSIZE       16384
  12 #define STR_HMASK       (STR_HSIZE - 1)
  13
  14 typedef struct StrTable {
  15         struct StrTable *st_Next;
  16         int             st_Magic;
  17         int             st_DataLen;     /* does not including terminator */
  18         int             st_Refs;
  19         int             st_Special;
  20         int             st_Enumerate;   /* Enumeration helper for code gen */
  21         int             st_Unused01;
  22         char            st_Data[0];     /* embedded binary or C string */
  23 } StrTable;
  24
  25 StrTable *StrTableHash[STR_HSIZE];
  26
  27 static __inline int
  28 strhash(const char *str, int bytes)
  29 {
  30         int hv = 0xA3F2B364;
  31         while (bytes) {
  32                 hv = (hv << 5) ^ *str ^ (hv >> 23);
  33                 --bytes;
  34                 ++str;
  35         }
  36         return((hv ^ (hv >> 16)) & STR_HMASK);
  37 }
  38
  39 /*
  40  * Obtain a persistent shared string representing the passed binary data.
  41  * Multple references to the same string will return the same shared pointer,
  42  * a feature we depend on heavily in the rest of the codebase in order to
  43  * avoid comparing strings over and over again.
  44  *
  45  * This code is content-agnostic and may be used for binary data.
  46  *
  47  * The caller has the choice of including the terminating zero for strings
  48  * in the official length or not.  This code always adds a terminating zero
  49  * 'out of band' to make string handling easier.
  50  */
  51 string_t
  52 StrTableAlloc(const char *ptr, int len, int special)
  53 {
  54         StrTable **pst, *st;
  55
  56         pst = &StrTableHash[strhash(ptr, len)];
  57         while ((st = *pst) != NULL) {
  58                 /*
  59                  * Look for match, bump ref count and return if found.  Note
  60                  * that we can reuse a previously dereferenced but
  61                  * not-yet-freed string.
  62                  */
  63                 if (len == st->st_DataLen &&
  64                     bcmp(ptr, st->st_Data, len) == 0) {
  65                         if (special)
  66                                 st->st_Special = special;
  67                         ++st->st_Refs;
  68                         return(st->st_Data);
  69                 }
  70                 /*
  71                  * in-scan free
  72                  */
  73                 if (st->st_Refs == 0) {
  74                         *pst = st->st_Next;
  75                         st->st_Next = NULL;
  76                         st->st_Magic = 0xDEADDEED;
  77                         zfree(st, sizeof(StrTable) + st->st_DataLen + 1);
  78                 } else {
  79                         pst = &st->st_Next;
  80                 }
  81         }
  82         st = zalloc(sizeof(StrTable) + len + 1);
  83         *pst = st;
  84         st->st_Magic = STR_MAGIC;
  85         st->st_DataLen = len;
  86         st->st_Refs = 1;
  87         st->st_Special = special;
  88         bcopy(ptr, (char *)&st->st_Data[0], len);
  89         ((char *)st->st_Data)[len] = 0; /* out of band terminator */
  90         return(st->st_Data);
  91 }
  92
  93 /*
  94  * Convert the string represented by the token into a string table string.
  95  */
  96 string_t
  97 StrTableToken(token_t *tok)
  98 {
  99         return(StrTableAlloc(tok->t_Ptr, tok->t_Len, 0));
 100 }
 101
 102 int
 103 StrCmpToken(string_t id, token_t *tok)
 104 {
 105         int len = strlen(id);
 106         int n;
 107         int r;
 108
 109         n = (len > tok->t_Len) ? tok->t_Len : len;
 110         r = strncmp(id, tok->t_Ptr, n);
 111         if (r == 0) {
 112                 if (len > tok->t_Len)
 113                         r = 1;
 114                 else if (len < tok->t_Len)
 115                         r = -1;
 116         }
 117         return(r);
 118 }
 119
 120 string_t
 121 StrTableInt(int v)
 122 {
 123         char buf[32];
 124
 125         snprintf(buf, sizeof(buf), "%d", v);
 126         return(StrTableAlloc(buf, strlen(buf), 0));
 127 }
 128
 129 /*
 130  * Bump the ref count on a string that is already in the string table.
 131  */
 132 string_t
 133 StrTableDup(const char *str)
 134 {
 135         StrTable *st = (StrTable *)(__DECONST(char *,str) -
 136                                     offsetof(StrTable, st_Data[0]));
 137
 138         dassert(st->st_Magic == STR_MAGIC);
 139         dassert(st->st_Refs > 0);
 140         ++st->st_Refs;
 141         return(str);
 142 }
 143
 144 void
 145 ReplaceStrTable(string_t *pstr, string_t id)
 146 {
 147         if (*pstr)
 148                 RelStrTable(pstr);
 149         *pstr = id;
 150 }
 151
 152 /*
 153  * Release a string in the string table.  We do not free the structure
 154  * immediately, allowing it to be potentially reused.  The structure will
 155  * be freed when a later StrTableRef() encounters it during a hash scan.
 156  */
 157 void
 158 RelStrTable(string_t *pstr)
 159 {
 160         string_t str;
 161
 162         if ((str = *pstr) != NULL) {
 163                 StrTable *st;
 164
 165                 *pstr = NULL;
 166                 st = (StrTable *)(__DECONST(char *, str) -
 167                                   offsetof(StrTable, st_Data[0]));
 168                 dassert(st->st_Magic == STR_MAGIC);
 169                 dassert(st->st_Refs > 0);
 170                 --st->st_Refs;
 171                 /* do in-line free in later allocation */
 172         }
 173 }
 174
 175 int
 176 StrTableSpecial(string_t id)
 177 {
 178         if (id) {
 179                 StrTable *st;
 180
 181                 st = (StrTable *)(__DECONST(char *, id) -
 182                                   offsetof(StrTable, st_Data[0]));
 183                 dassert(st->st_Magic == STR_MAGIC);
 184                 return(st->st_Special);
 185         }
 186         return(0);
 187 }
 188
 189 /*
 190  * Generate a unique id for this string table entry.  Typically stored
 191  * in the d_BackendId field of a declaration.
 192  */
 193 int
 194 StrTableEnumerate(string_t id)
 195 {
 196         StrTable *st;
 197
 198         st = (StrTable *)(__DECONST(char *, id) -
 199                           offsetof(StrTable, st_Data[0]));
 200         ++st->st_Enumerate;
 201
 202         return st->st_Enumerate;
 203 }
 204
 205 /*
 206  * Return the length, in bytes, of an identifier.  The length does not
 207  * include the terminating zero unless the original allocation included
 208  * it in its length.
 209  */
 210 int
 211 StrTableLen(string_t id)
 212 {
 213         StrTable *st;
 214
 215         st = (StrTable *)(__DECONST(char *, id) -
 216                           offsetof(StrTable, st_Data[0]));
 217         dassert(st->st_Magic == STR_MAGIC);
 218         return(st->st_DataLen);
 219 }
 220
 221 /*
 222  * Strip the identifier from the trailing element of the path.  This routine
 223  * takes a nul-terminated string and returns a pointer and length within
 224  * the same string.
 225  */
 226 const char *
 227 StripPathId(const char *path, int *plen)
 228 {
 229         int len = strlen(path);
 230
 231         /*
 232          * strip any trailing slashes
 233          */
 234         while (len > 0 && path[len - 1] == '/')
 235                 --len;
 236
 237         /*
 238          * Locate the last element
 239          */
 240         while (len > 0 && path[len - 1] != '/')
 241                 --len;
 242         path += len;
 243
 244         /*
 245          * Parse the identifier until we hit a '/' or a '.' (extension)
 246          */
 247         len = 0;
 248         while (path[len] && path[len] != '/' && path[len] != '.')
 249                 ++len;
 250         *plen = len;
 251         return(path);
 252 }
 253
 254 int
 255 SimpleIntToken(token_t *tok, int *rv)
 256 {
 257         int t = tok->t_Type;
 258
 259         *rv = 0;
 260         if (t != TOK_INTEGER) {
 261                 t = LexError(tok, TOK_ERR_EXPECTED_SIMPLE_INTEGER);
 262         } else {
 263                 int i;
 264                 int neg = 1;
 265
 266                 for (i = 0; i < tok->t_Len; ++i) {
 267                         char c = tok->t_Ptr[i];
 268                         if (c == '-') {
 269                                 neg = -neg;
 270                         } else if (c >= '0' && c <= '9') {
 271                                 *rv = *rv * 10 + (c - '0');
 272                         } else {
 273                                 t = LexError(tok,
 274                                              TOK_ERR_EXPECTED_SIMPLE_INTEGER);
 275                         }
 276                 }
 277                 *rv = *rv * neg;
 278         }
 279         return(t);
 280 }
 281
 282 int
 283 SimpleRunesizeToken(token_t *tok, runesize_t *rv)
 284 {
 285         int t = tok->t_Type;
 286
 287         *rv = 0;
 288         if (t != TOK_INTEGER) {
 289                 t = LexError(tok, TOK_ERR_EXPECTED_SIMPLE_INTEGER);
 290         } else {
 291                 int i;
 292                 int neg = 1;
 293
 294                 for (i = 0; i < tok->t_Len; ++i) {
 295                         char c = tok->t_Ptr[i];
 296                         if (c == '-') {
 297                                 neg = -neg;
 298                         } else if (c >= '0' && c <= '9') {
 299                                 *rv = *rv * 10 + (c - '0');
 300                         } else {
 301                                 t = LexError(tok,
 302                                              TOK_ERR_EXPECTED_SIMPLE_INTEGER);
 303                         }
 304                 }
 305                 if (neg < 0)
 306                         *rv = -*rv;
 307         }
 308         return(t);
 309 }
 310
 311 /*
 312  * StrTableEscapeQuotedString() - convert quoted string into actual string.
 313  *
 314  * NOTE: The length of the string in the string table includes the
 315  *       terminator.  The string may also be concatenated.
 316  *
 317  * NOTE: the lexical analyzer does a more robust format check.
 318  */
 319 static __inline int
 320 hexDigit(char c)
 321 {
 322         if (c >= '0' && c <= '9')
 323                 return(c - '0');
 324         if (c >= 'a' && c <= 'f')
 325                 return(c + (10 - 'a'));
 326         if (c >= 'A' && c <= 'F')
 327                 return(c + (10 - 'A'));
 328         return(-1);
 329 }
 330
 331 string_t
 332 StrTableEscapeQuotedString(const char *str, int len, int term)
 333 {
 334         int rlen;
 335         int i;
 336         int searching;
 337         char *dbuf = NULL;
 338         char type;
 339         string_t id;
 340
 341         dassert(len >= 2);
 342         type = *str;
 343 loop:
 344         searching = 1;
 345         rlen = 0;
 346
 347         for (i = 0; i < len; ++i) {
 348                 char c = str[i];
 349
 350                 if (c == type) {
 351                         searching = 1 - searching;
 352                         continue;
 353                 } else if (searching) {
 354                         continue;
 355                 }
 356
 357                 if (c == '\\') {
 358                         ++i;
 359                         dassert(i < len);
 360                         switch((c = str[i])) {
 361                         case 'n':
 362                                 c = 10;
 363                                 break;
 364                         case 't':
 365                                 c = 9;
 366                                 break;
 367                         case 'r':
 368                                 c = 13;
 369                                 break;
 370                         case 'x':
 371                                 i += 2;
 372                                 dassert(i < len);
 373                                 c = (hexDigit(str[i-1]) << 4) |
 374                                     hexDigit(str[i]);
 375                                 break;
 376                         case '\\':
 377                                 break;
 378                         default:
 379                                 dassert(c >= '0' && c <= '7');
 380                                 c &= 7;
 381                                 if (i + 1 < len &&
 382                                     str[i+1] >= '0' &&
 383                                     str[i+1] <= '7')
 384                                 {
 385                                         ++i;
 386                                         c = (c << 3) | (str[i] & 7);
 387                                         if (i + 1 < len &&
 388                                             str[i+1] >= '0' &&
 389                                             str[i+1] <= '7')
 390                                         {
 391                                                 ++i;
 392                                                 c = (c << 3) | (str[i] & 7);
 393                                         }
 394                                 }
 395                                 break;
 396                         }
 397                 }
 398                 if (dbuf)
 399                         dbuf[rlen] = c;
 400                 ++rlen;
 401         }
 402         if (dbuf == NULL) {
 403                 dbuf = malloc(rlen + 1);
 404                 goto loop;
 405         }
 406         dbuf[rlen] = 0;
 407         dassert(term == 0 || term == 1);
 408         id = StrTableAlloc(dbuf, rlen + term, 0);
 409         free(dbuf);
 410         return(id);
 411 }