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     void   *st_Info;            /* (used for run-time) */
  23     char    st_Data[0];         /* embedded binary or C string */
  24 } StrTable;
  25
  26 static StrTable * StrTableHash[STR_HSIZE];
  27
  28 static __inline int
  29 strhash(const char *str, int bytes)
  30 {
  31     int     hv = 0xA3F2B364;
  32     while (bytes) {
  33         hv = (hv << 5) ^ *str ^ (hv >> 23);
  34         --bytes;
  35         ++str;
  36     }
  37     return ((hv ^ (hv >> 16)) & STR_HMASK);
  38 }
  39
  40 /*
  41  * Obtain a persistent shared string representing the passed binary data.
  42  * Multple references to the same string will return the same shared pointer,
  43  * a feature we depend on heavily in the rest of the codebase in order to
  44  * avoid comparing strings over and over again.
  45  *
  46  * This code is content-agnostic and may be used for binary data.
  47  *
  48  * The caller has the choice of including the terminating zero for strings in
  49  * the official length or not.  This code always adds a terminating zero 'out
  50  * of band' to make string handling easier.
  51  */
  52 string_t
  53 StrTableAlloc(const char *ptr, int len, int special)
  54 {
  55     StrTable **pst, *st;
  56
  57     pst = &StrTableHash[strhash(ptr, len)];
  58     while ((st = *pst) != NULL) {
  59         /*
  60          * Look for match, bump ref count and return if found.  Note that we
  61          * can reuse a previously dereferenced but 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 /*
 103  * Bump the ref count on a string that is already in the string table.
 104  */
 105 string_t
 106 StrTableDup(const char *str)
 107 {
 108     StrTable *st = (StrTable *) (__DECONST(char *, str)-
 109                                  offsetof(StrTable, st_Data[0]));
 110
 111     dassert(st->st_Magic == STR_MAGIC);
 112     dassert(st->st_Refs > 0);
 113     ++st->st_Refs;
 114     return (str);
 115 }
 116
 117 void
 118 ReplaceStrTable(string_t *pstr, string_t id)
 119 {
 120     if (*pstr)
 121         RelStrTable(pstr);
 122     *pstr = id;
 123 }
 124
 125 /*
 126  * Release a string in the string table.  We do not free the structure
 127  * immediately, allowing it to be potentially reused.  The structure will be
 128  * freed when a later StrTableRef() encounters it during a hash scan.
 129  */
 130 void
 131 RelStrTable(string_t *pstr)
 132 {
 133     string_t str;
 134
 135     if ((str = *pstr) != NULL) {
 136         StrTable *st;
 137
 138         *pstr = NULL;
 139         st = (StrTable *) (__DECONST(char *, str)-
 140                            offsetof(StrTable, st_Data[0]));
 141         dassert(st->st_Magic == STR_MAGIC);
 142         dassert(st->st_Refs > 0);
 143         --st->st_Refs;
 144         /* do in-line free in later allocation */
 145     }
 146 }
 147
 148 int
 149 StrTableSpecial(string_t id)
 150 {
 151     if (id) {
 152         StrTable *st;
 153
 154         st = (StrTable *) (__DECONST(char *, id)-
 155                            offsetof(StrTable, st_Data[0]));
 156         dassert(st->st_Magic == STR_MAGIC);
 157         return (st->st_Special);
 158     }
 159     return (0);
 160 }
 161
 162 /*
 163  * Generate a unique id for this string table entry.  Typically stored in the
 164  * d_BackendId field of a declaration.
 165  */
 166 int
 167 StrTableEnumerate(string_t id)
 168 {
 169     StrTable *st;
 170
 171     st = (StrTable *) (__DECONST(char *, id)-
 172                        offsetof(StrTable, st_Data[0]));
 173     ++st->st_Enumerate;
 174
 175     return st->st_Enumerate;
 176 }
 177
 178 /*
 179  * Return the length, in bytes, of an identifier.  The length does not
 180  * include the terminating zero unless the original allocation included it in
 181  * its length.
 182  */
 183 int
 184 StrTableLen(string_t id)
 185 {
 186     StrTable *st;
 187
 188     st = (StrTable *) (__DECONST(char *, id)-
 189                        offsetof(StrTable, st_Data[0]));
 190     dassert(st->st_Magic == STR_MAGIC);
 191     return (st->st_DataLen);
 192 }
 193
 194 /*
 195  * Strip the identifier from the trailing element of the path.  This routine
 196  * takes a nul-terminated string and returns a pointer and length within the
 197  * same string.
 198  */
 199 const char *
 200 StripPathId(const char *path, int *plen)
 201 {
 202     int     len = strlen(path);
 203
 204     /*
 205      * strip any trailing slashes
 206      */
 207     while (len > 0 && path[len - 1] == '/')
 208         --len;
 209
 210     /*
 211      * Locate the last element
 212      */
 213     while (len > 0 && path[len - 1] != '/')
 214         --len;
 215     path += len;
 216
 217     /*
 218      * Parse the identifier until we hit a '/' or a '.' (extension)
 219      */
 220     len = 0;
 221     while (path[len] && path[len] != '/' && path[len] != '.')
 222         ++len;
 223     *plen = len;
 224     return (path);
 225 }
 226
 227 int
 228 SimpleIntToken(token_t *tok, int *rv)
 229 {
 230     int     t = tok->t_Type;
 231
 232     *rv = 0;
 233     if (t != TOK_INTEGER) {
 234         t = LexError(tok, TOK_ERR_EXPECTED_SIMPLE_INTEGER);
 235     } else {
 236         int     i;
 237         int     neg = 1;
 238
 239         for (i = 0; i < tok->t_Len; ++i) {
 240             char    c = tok->t_Ptr[i];
 241             if (c == '-') {
 242                 neg = -neg;
 243             } else if (c >= '0' && c <= '9') {
 244                 *rv = *rv * 10 + (c - '0');
 245             } else {
 246                 t = LexError(tok,
 247                              TOK_ERR_EXPECTED_SIMPLE_INTEGER);
 248             }
 249         }
 250         *rv = *rv * neg;
 251     }
 252     return (t);
 253 }
 254
 255 int
 256 SimpleRunesizeToken(token_t *tok, urunesize_t *rv)
 257 {
 258     int     t = tok->t_Type;
 259
 260     *rv = 0;
 261     if (t != TOK_INTEGER) {
 262         t = LexError(tok, TOK_ERR_EXPECTED_SIMPLE_INTEGER);
 263     } else {
 264         int     i;
 265         int     neg = 1;
 266
 267         for (i = 0; i < tok->t_Len; ++i) {
 268             char    c = tok->t_Ptr[i];
 269             if (c == '-') {
 270                 neg = -neg;
 271             } else if (c >= '0' && c <= '9') {
 272                 *rv = *rv * 10 + (c - '0');
 273             } else {
 274                 t = LexError(tok,
 275                              TOK_ERR_EXPECTED_SIMPLE_INTEGER);
 276             }
 277         }
 278         if (neg < 0)
 279             *rv = -*rv;
 280     }
 281     return (t);
 282 }
 283
 284 /*
 285  * StrTableEscapeQuotedString() - convert quoted string into actual string.
 286  *
 287  * NOTE: The length of the string in the string table includes the
 288  * terminator.  The string may also be concatenated.
 289  *
 290  * NOTE: the lexical analyzer does a more robust format check.
 291  */
 292 static __inline int
 293 hexDigit(char c)
 294 {
 295     if (c >= '0' && c <= '9')
 296         return (c - '0');
 297     if (c >= 'a' && c <= 'f')
 298         return (c + (10 - 'a'));
 299     if (c >= 'A' && c <= 'F')
 300         return (c + (10 - 'A'));
 301     return (-1);
 302 }
 303
 304 static
 305 char *
 306 BufEscapeQuotedString(const char *str, int *lenp)
 307 {
 308     int     rlen;
 309     int     i;
 310     int     searching;
 311     int     len = *lenp;
 312     char   *dbuf = NULL;
 313     char    btype;
 314     char    etype;
 315
 316     dassert(len >= 2);
 317     btype = len ? str[0] : 0;
 318     etype = btype;
 319     if (btype == '<')
 320         etype = '>';
 321 loop:
 322     searching = 1;
 323     rlen = 0;
 324
 325     for (i = 0; i < len; ++i) {
 326         char    c = str[i];
 327
 328         if (searching) {
 329             if (c == btype)
 330                 searching = 1 - searching;
 331             continue;
 332         }
 333         if (c == etype) {
 334             searching = 1 - searching;
 335             continue;
 336         }
 337
 338         if (btype != TOK_BSTRING && c == '\\') {
 339             ++i;
 340             dassert(i < len);
 341             switch ((c = str[i])) {
 342             case 'n':
 343                 c = 10;
 344                 break;
 345             case 't':
 346                 c = 9;
 347                 break;
 348             case 'r':
 349                 c = 13;
 350                 break;
 351             case 'x':
 352                 i += 2;
 353                 dassert(i < len);
 354                 c = (hexDigit(str[i - 1]) << 4) |
 355                     hexDigit(str[i]);
 356                 break;
 357             case '\\':
 358                 break;
 359             default:
 360                 dassert(c >= '0' && c <= '7');
 361                 c &= 7;
 362                 if (i + 1 < len &&
 363                     str[i + 1] >= '0' &&
 364                     str[i + 1] <= '7') {
 365                     ++i;
 366                     c = (c << 3) | (str[i] & 7);
 367                     if (i + 1 < len &&
 368                         str[i + 1] >= '0' &&
 369                         str[i + 1] <= '7') {
 370                         ++i;
 371                         c = (c << 3) | (str[i] & 7);
 372                     }
 373                 }
 374                 break;
 375             }
 376         }
 377         if (dbuf)
 378             dbuf[rlen] = c;
 379         ++rlen;
 380     }
 381     if (dbuf == NULL) {
 382         dbuf = malloc(rlen + 1);
 383         goto loop;
 384     }
 385     dbuf[rlen] = 0;
 386
 387     *lenp = rlen;
 388
 389     return (dbuf);
 390 }
 391
 392 string_t
 393 StrTableEscapeQuotedString(const char *str, int len, int term)
 394 {
 395     string_t id;
 396     char   *dbuf;
 397
 398     dbuf = BufEscapeQuotedString(str, &len);
 399
 400     dassert(term == 0 || term == 1);
 401     id = StrTableAlloc(dbuf, len + term, 0);
 402     free(dbuf);
 403
 404     return (id);
 405 }
 406
 407 uint64_t
 408 StrTableSingleQuotedString(const char *str, int len, Type **typep)
 409 {
 410     uint8_t  *dbuf;
 411     uint64_t key;
 412     int i;
 413
 414     dbuf = (uint8_t *)BufEscapeQuotedString(str, &len);
 415     key = 0;
 416     for (i = 0; i < len; ++i)
 417         key = (key << 8) | dbuf[i];
 418
 419     switch (len) {
 420     case 0:
 421         *typep = &UInt8Type;
 422         break;
 423     case 1:
 424         *typep = &UInt8Type;
 425         break;
 426     case 2:
 427         *typep = &UInt16Type;
 428         break;
 429     case 3:
 430     case 4:
 431         *typep = &UInt32Type;
 432         break;
 433     case 5:
 434     case 6:
 435     case 7:
 436     case 8:
 437         *typep = &UInt64Type;
 438         break;
 439     default:
 440         key = iscsi_crc32(dbuf, len) | 0x80000000U;
 441         *typep = &UInt32Type;
 442         break;
 443     }
 444     free(dbuf);
 445
 446     return key;
 447 }