slang/slstring.c

   1 /*
   2 Copyright (C) 2004, 2005, 2006 John E. Davis
   3
   4 This file is part of the S-Lang Library.
   5
   6 The S-Lang Library is free software; you can redistribute it and/or
   7 modify it under the terms of the GNU General Public License as
   8 published by the Free Software Foundation; either version 2 of the
   9 License, or (at your option) any later version.
  10
  11 The S-Lang Library is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with this library; if not, write to the Free Software
  18 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19 USA.
  20 */
  21
  22 #include "slinclud.h"
  23
  24 #include "slang.h"
  25 #include "_slang.h"
  26
  27 typedef struct _pSLstring_Type
  28 {
  29    struct _pSLstring_Type *next;
  30    unsigned int ref_count;
  31    unsigned long hash;
  32    unsigned int len;
  33    char bytes [1];
  34 }
  35 SLstring_Type;
  36
  37 #define MAP_HASH_TO_INDEX(hash) ((hash) % SLSTRING_HASH_TABLE_SIZE)
  38
  39 static SLstring_Type *String_Hash_Table [SLSTRING_HASH_TABLE_SIZE];
  40 static char Single_Char_Strings [256 * 2];
  41
  42 #if SLANG_OPTIMIZE_FOR_SPEED
  43 #define MAX_FREE_STORE_LEN 32
  44 static SLstring_Type *SLS_Free_Store [MAX_FREE_STORE_LEN];
  45
  46 # define NUM_CACHED_STRINGS 601
  47 typedef struct
  48 {
  49    SLstring_Type *sls;
  50    char *str;
  51 }
  52 Cached_String_Type;
  53 static char *Deleted_String = "*deleted*";
  54 static Cached_String_Type Cached_Strings [NUM_CACHED_STRINGS];
  55
  56 #define GET_CACHED_STRING(s) \
  57    (Cached_Strings + (unsigned int)(((unsigned long) (s)) % NUM_CACHED_STRINGS))
  58
  59
  60 _INLINE_
  61 static void cache_string (SLstring_Type *sls)
  62 {
  63    Cached_String_Type *cs;
  64
  65    cs = GET_CACHED_STRING(sls->bytes);
  66    cs->str = sls->bytes;
  67    cs->sls = sls;
  68 }
  69
  70 _INLINE_
  71 static void uncache_string (char *s)
  72 {
  73    Cached_String_Type *cs;
  74
  75    cs = GET_CACHED_STRING(s);
  76    if (cs->str == s)
  77      {
  78         cs->sls = NULL;
  79         cs->str = Deleted_String;
  80      }
  81 }
  82 #endif
  83
  84 #if USE_NEW_HASH_CODE
  85 /* This hash algorithm comes from:
  86  *
  87  *   Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.
  88  *   You may use this code any way you wish, private, educational, or commercial.  It's free.
  89  *   See http://burtleburtle.net/bob/hash/evahash.html
  90  */
  91
  92 typedef  unsigned long uint32;
  93
  94 #define mix(a,b,c) \
  95 { \
  96   a -= b; a -= c; a ^= (c>>13); \
  97   b -= c; b -= a; b ^= (a<<8); \
  98   c -= a; c -= b; c ^= (b>>13); \
  99   a -= b; a -= c; a ^= (c>>12);  \
 100   b -= c; b -= a; b ^= (a<<16); \
 101   c -= a; c -= b; c ^= (b>>5); \
 102   a -= b; a -= c; a ^= (c>>3);  \
 103   b -= c; b -= a; b ^= (a<<10); \
 104   c -= a; c -= b; c ^= (b>>15); \
 105 }
 106
 107 _INLINE_
 108 unsigned long _pSLstring_hash (unsigned char *s, unsigned char *smax)
 109 {
 110    register uint32 a,b,c;
 111    unsigned int length = (unsigned int)(smax - s);
 112    unsigned int len = length;
 113
 114    a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
 115    c = 0;
 116
 117    /*---------------------------------------- handle most of the key */
 118    while (len >= 12)
 119      {
 120         a += (s[0] +((uint32)s[1]<<8) +((uint32)s[2]<<16) +((uint32)s[3]<<24));
 121         b += (s[4] +((uint32)s[5]<<8) +((uint32)s[6]<<16) +((uint32)s[7]<<24));
 122         c += (s[8] +((uint32)s[9]<<8) +((uint32)s[10]<<16)+((uint32)s[11]<<24));
 123         mix(a,b,c);
 124         s += 12; len -= 12;
 125      }
 126
 127    /*------------------------------------- handle the last 11 bytes */
 128    c += length;
 129    switch(len)              /* all the case statements fall through */
 130    {
 131    case 11: c+=((uint32)s[10]<<24);
 132    case 10: c+=((uint32)s[9]<<16);
 133    case 9 : c+=((uint32)s[8]<<8);
 134       /* the first byte of c is reserved for the length */
 135    case 8 : b+=((uint32)s[7]<<24);
 136    case 7 : b+=((uint32)s[6]<<16);
 137    case 6 : b+=((uint32)s[5]<<8);
 138    case 5 : b+=s[4];
 139    case 4 : a+=((uint32)s[3]<<24);
 140    case 3 : a+=((uint32)s[2]<<16);
 141    case 2 : a+=((uint32)s[1]<<8);
 142    case 1 : a+=s[0];
 143      /* case 0: nothing left to add */
 144    }
 145    mix(a,b,c);
 146    /*-------------------------------------------- report the result */
 147    return (unsigned long) c;
 148 }
 149 #else
 150 _INLINE_
 151 unsigned long _pSLstring_hash (unsigned char *s, unsigned char *smax)
 152 {
 153    register unsigned long h = 0;
 154    register unsigned long sum = 0;
 155    unsigned char *smax4;
 156
 157    smax4 = smax - 4;
 158
 159    while (s < smax4)
 160      {
 161         sum += s[0];
 162         h = sum + (h << 1);
 163         sum += s[1];
 164         h = sum + (h << 1);
 165         sum += s[2];
 166         h = sum + (h << 1);
 167         sum += s[3];
 168         h = sum + (h << 1);
 169
 170         s += 4;
 171      }
 172
 173    while (s < smax)
 174      {
 175         sum += *s++;
 176         h ^= sum + (h << 3);           /* slightly different */
 177      }
 178
 179    return h;
 180 }
 181 #endif
 182 unsigned long _pSLcompute_string_hash (char *s)
 183 {
 184 #if SLANG_OPTIMIZE_FOR_SPEED
 185    Cached_String_Type *cs;
 186
 187    cs = GET_CACHED_STRING(s);
 188    if (cs->str == s)
 189      return cs->sls->hash;
 190 #endif
 191    return _pSLstring_hash ((unsigned char *) s, (unsigned char *) s + strlen (s));
 192 }
 193
 194 _INLINE_
 195 /* This routine works with any (long) string */
 196 static SLstring_Type *find_string (char *s, unsigned int len, unsigned long hash)
 197 {
 198    SLstring_Type *sls;
 199
 200    sls = String_Hash_Table [(unsigned int) MAP_HASH_TO_INDEX(hash)];
 201
 202    if (sls == NULL)
 203      return NULL;
 204
 205    do
 206      {
 207         /* Note that we need to actually make sure that bytes[len] == 0.
 208          * In this case, it is not enough to just compare pointers.  In fact,
 209          * this is called from create_nstring, etc...  It is unlikely that the
 210          * pointer is a slstring
 211          */
 212         if ((sls->hash == hash)
 213             && (sls->len == len)
 214             && (0 == strncmp (s, sls->bytes, len)))
 215           break;
 216
 217         sls = sls->next;
 218      }
 219    while (sls != NULL);
 220
 221    return sls;
 222 }
 223
 224 _INLINE_
 225 static SLstring_Type *find_slstring (char *s, unsigned long hash)
 226 {
 227    SLstring_Type *sls;
 228
 229    sls = String_Hash_Table [MAP_HASH_TO_INDEX(hash)];
 230    while (sls != NULL)
 231      {
 232         if (s == sls->bytes)
 233           return sls;
 234
 235         sls = sls->next;
 236      }
 237    return sls;
 238 }
 239
 240 _INLINE_
 241 static SLstring_Type *allocate_sls (unsigned int len)
 242 {
 243    SLstring_Type *sls;
 244 #if SLANG_OPTIMIZE_FOR_SPEED
 245
 246    if ((len < MAX_FREE_STORE_LEN)
 247        && (NULL != (sls = SLS_Free_Store [len])))
 248      {
 249         SLS_Free_Store[len] = NULL;
 250         return sls;
 251      }
 252 #endif
 253    /* FIXME: use structure padding */
 254    sls = (SLstring_Type *) SLmalloc (len + sizeof (SLstring_Type));
 255    if (sls != NULL)
 256      sls->len = len;
 257    return sls;
 258 }
 259
 260 _INLINE_
 261 static void free_sls (SLstring_Type *sls)
 262 {
 263 #if SLANG_OPTIMIZE_FOR_SPEED
 264    unsigned int len = sls->len;
 265    if ((len < MAX_FREE_STORE_LEN)
 266        && (SLS_Free_Store[len] == NULL))
 267      {
 268         SLS_Free_Store [len] = sls;
 269         return;
 270      }
 271 #endif
 272    SLfree ((char *)sls);
 273 }
 274
 275 _INLINE_
 276 static char *create_long_string (char *s, unsigned int len, unsigned long hash)
 277 {
 278    SLstring_Type *sls;
 279
 280    sls = find_string (s, len, hash);
 281
 282    if (sls != NULL)
 283      {
 284         sls->ref_count++;
 285 #if SLANG_OPTIMIZE_FOR_SPEED
 286         cache_string (sls);
 287 #endif
 288         return sls->bytes;
 289      }
 290
 291    sls = allocate_sls (len);
 292    if (sls == NULL)
 293      return NULL;
 294
 295    strncpy (sls->bytes, s, len);
 296    sls->bytes[len] = 0;
 297    sls->ref_count = 1;
 298    sls->hash = hash;
 299 #if SLANG_OPTIMIZE_FOR_SPEED
 300    cache_string (sls);
 301 #endif
 302
 303    hash = MAP_HASH_TO_INDEX(hash);
 304    sls->next = String_Hash_Table [(unsigned int)hash];
 305    String_Hash_Table [(unsigned int)hash] = sls;
 306
 307    return sls->bytes;
 308 }
 309
 310 _INLINE_
 311 static char *create_short_string (char *s, unsigned int len)
 312 {
 313    char ch;
 314
 315    /* Note: if len is 0, then it does not matter what *s is.  This is
 316     * important for SLang_create_nslstring.
 317     */
 318    if (len) ch = *s; else ch = 0;
 319
 320    len = 2 * (unsigned int) ((unsigned char) ch);
 321    Single_Char_Strings [len] = ch;
 322    Single_Char_Strings [len + 1] = 0;
 323    return Single_Char_Strings + len;
 324 }
 325
 326 /* s cannot be NULL */
 327 _INLINE_
 328 static SLstr_Type *create_nstring (char *s, unsigned int len, unsigned long *hash_ptr)
 329 {
 330    unsigned long hash;
 331
 332    if (len < 2)
 333      return create_short_string (s, len);
 334
 335    hash = _pSLstring_hash ((unsigned char *) s, (unsigned char *) (s + len));
 336    *hash_ptr = hash;
 337
 338    return create_long_string (s, len, hash);
 339 }
 340
 341 SLstr_Type *SLang_create_nslstring (char *s, unsigned int len)
 342 {
 343    unsigned long hash;
 344    if (s == NULL)
 345      return NULL;
 346    return create_nstring (s, len, &hash);
 347 }
 348
 349 char *_pSLstring_make_hashed_string (char *s, unsigned int len, unsigned long *hashptr)
 350 {
 351    unsigned long hash;
 352
 353    if (s == NULL) return NULL;
 354
 355    hash = _pSLstring_hash ((unsigned char *) s, (unsigned char *) s + len);
 356    *hashptr = hash;
 357
 358    if (len < 2)
 359      return create_short_string (s, len);
 360
 361    return create_long_string (s, len, hash);
 362 }
 363
 364 char *_pSLstring_dup_hashed_string (char *s, unsigned long hash)
 365 {
 366    unsigned int len;
 367 #if SLANG_OPTIMIZE_FOR_SPEED
 368    Cached_String_Type *cs;
 369
 370    if (s == NULL) return NULL;
 371    if (s[0] == 0)
 372      return create_short_string (s, 0);
 373    if (s[1] == 0)
 374      return create_short_string (s, 1);
 375
 376    cs = GET_CACHED_STRING(s);
 377    if (cs->str == s)
 378      {
 379         cs->sls->ref_count += 1;
 380         return s;
 381      }
 382 #else
 383    if (s == NULL) return NULL;
 384 #endif
 385
 386    len = strlen (s);
 387 #if !SLANG_OPTIMIZE_FOR_SPEED
 388    if (len < 2) return create_short_string (s, len);
 389 #endif
 390
 391    return create_long_string (s, len, hash);
 392 }
 393
 394 /* This function requires an slstring!!! */
 395 char *_pSLstring_dup_slstring (char *s)
 396 {
 397    SLstring_Type *sls;
 398 #if SLANG_OPTIMIZE_FOR_SPEED
 399    Cached_String_Type *cs;
 400 #endif
 401
 402    if (s == NULL)
 403      return s;
 404 #if SLANG_OPTIMIZE_FOR_SPEED
 405    cs = GET_CACHED_STRING(s);
 406    if (cs->str == s)
 407      {
 408         cs->sls->ref_count += 1;
 409         return s;
 410      }
 411 #endif
 412    if ((s[0] == 0) || (s[1] == 0))
 413      return s;
 414
 415    sls = (SLstring_Type *) (s - offsetof(SLstring_Type,bytes[0]));
 416    sls->ref_count++;
 417 #if SLANG_OPTIMIZE_FOR_SPEED
 418    cache_string (sls);
 419 #endif
 420    return s;
 421 }
 422
 423 static void free_sls_string (SLstring_Type *sls)
 424 {
 425    SLstring_Type *sls1, *prev;
 426    unsigned long hash = sls->hash;
 427
 428    hash = MAP_HASH_TO_INDEX(hash);
 429
 430    sls1 = String_Hash_Table [(unsigned int) hash];
 431
 432    prev = NULL;
 433
 434    /* This should not fail. */
 435    while (sls1 != sls)
 436      {
 437         prev = sls1;
 438         sls1 = sls1->next;
 439      }
 440
 441    if (prev != NULL)
 442      prev->next = sls->next;
 443    else
 444      String_Hash_Table [(unsigned int) hash] = sls->next;
 445
 446    free_sls (sls);
 447 }
 448
 449 _INLINE_
 450 static void free_long_string (char *s, unsigned long hash)
 451 {
 452    SLstring_Type *sls;
 453
 454    if (NULL == (sls = find_slstring (s, hash)))
 455      {
 456         SLang_verror (SL_APPLICATION_ERROR, "invalid attempt to free string:%s", s);
 457         return;
 458      }
 459
 460    sls->ref_count--;
 461    if (sls->ref_count != 0)
 462      {
 463 #if SLANG_OPTIMIZE_FOR_SPEED
 464         /* cache_string (sls, len, hash); */
 465 #endif
 466         return;
 467      }
 468 #if SLANG_OPTIMIZE_FOR_SPEED
 469    uncache_string (s);
 470 #endif
 471    free_sls_string (sls);
 472 }
 473
 474 /* This routine may be passed NULL-- it is not an error. */
 475 void SLang_free_slstring (char *s)
 476 {
 477    unsigned long hash;
 478    unsigned int len;
 479 #if SLANG_OPTIMIZE_FOR_SPEED
 480    Cached_String_Type *cs;
 481 #endif
 482
 483    if (s == NULL) return;
 484
 485 #if SLANG_OPTIMIZE_FOR_SPEED
 486    cs = GET_CACHED_STRING(s);
 487    if (cs->str == s)
 488      {
 489         SLstring_Type *sls = cs->sls;
 490         if (sls->ref_count <= 1)
 491           {
 492 #if SLANG_OPTIMIZE_FOR_SPEED
 493              cs->sls = NULL;
 494              cs->str = Deleted_String;
 495 #endif
 496              free_sls_string (sls);
 497           }
 498         else
 499           sls->ref_count -= 1;
 500         return;
 501      }
 502 #endif
 503
 504    if ((len = strlen (s)) < 2)
 505      return;
 506
 507    hash = _pSLstring_hash ((unsigned char *)s, (unsigned char *) s + len);
 508    free_long_string (s, hash);
 509 }
 510
 511 char *SLang_create_slstring (char *s)
 512 {
 513    unsigned long hash;
 514 #if SLANG_OPTIMIZE_FOR_SPEED
 515    Cached_String_Type *cs;
 516 #endif
 517
 518    if (s == NULL) return NULL;
 519 #if SLANG_OPTIMIZE_FOR_SPEED
 520    cs = GET_CACHED_STRING(s);
 521    if (cs->str == s)
 522      {
 523         cs->sls->ref_count += 1;
 524         return s;
 525      }
 526 #endif
 527
 528    return create_nstring (s, strlen (s), &hash);
 529 }
 530
 531 void _pSLfree_hashed_string (char *s, unsigned int len, unsigned long hash)
 532 {
 533    if ((s == NULL) || (len < 2)) return;
 534    free_long_string (s, hash);
 535 }
 536
 537
 538 char *_pSLallocate_slstring (unsigned int len)
 539 {
 540    SLstring_Type *sls = allocate_sls (len);
 541    if (sls == NULL)
 542      return NULL;
 543
 544    sls->hash = 0;
 545    return sls->bytes;
 546 }
 547
 548 void _pSLunallocate_slstring (char *s, unsigned int len)
 549 {
 550    SLstring_Type *sls;
 551
 552    (void) len;
 553    if (s == NULL)
 554      return;
 555
 556    sls = (SLstring_Type *) (s - offsetof(SLstring_Type,bytes[0]));
 557    free_sls (sls);
 558 }
 559
 560 char *_pSLcreate_via_alloced_slstring (char *s, unsigned int len)
 561 {
 562    unsigned long hash;
 563    SLstring_Type *sls;
 564
 565    if (s == NULL)
 566      return NULL;
 567
 568    if (len < 2)
 569      {
 570         char *s1 = create_short_string (s, len);
 571         _pSLunallocate_slstring (s, len);
 572         return s1;
 573      }
 574
 575    /* s is not going to be in the cache because when it was malloced, its
 576     * value was unknown.  This simplifies the coding.
 577     */
 578    hash = _pSLstring_hash ((unsigned char *)s, (unsigned char *)s + len);
 579    sls = find_string (s, len, hash);
 580    if (sls != NULL)
 581      {
 582         sls->ref_count++;
 583         _pSLunallocate_slstring (s, len);
 584         s = sls->bytes;
 585
 586 #if SLANG_OPTIMIZE_FOR_SPEED
 587         cache_string (sls);
 588 #endif
 589         return s;
 590      }
 591
 592    sls = (SLstring_Type *) (s - offsetof(SLstring_Type,bytes[0]));
 593    sls->ref_count = 1;
 594    sls->hash = hash;
 595
 596 #if SLANG_OPTIMIZE_FOR_SPEED
 597    cache_string (sls);
 598 #endif
 599
 600    hash = MAP_HASH_TO_INDEX(hash);
 601    sls->next = String_Hash_Table [(unsigned int)hash];
 602    String_Hash_Table [(unsigned int)hash] = sls;
 603
 604    return s;
 605 }
 606
 607 /* Note, a and b may be ordinary strings.  The result is an slstring */
 608 char *SLang_concat_slstrings (char *a, char *b)
 609 {
 610    unsigned int lena, len;
 611    char *c;
 612
 613    lena = strlen (a);
 614    len = lena + strlen (b);
 615
 616    c = _pSLallocate_slstring (len);
 617    if (c == NULL)
 618      return NULL;
 619
 620    strcpy (c, a);
 621    strcpy (c + lena, b);
 622
 623    return _pSLcreate_via_alloced_slstring (c, len);
 624 }
 625
 626 /* This routine is assumed to work even if s is not an slstring */
 627 unsigned int _pSLstring_bytelen (SLstr_Type *s)
 628 {
 629 #if SLANG_OPTIMIZE_FOR_SPEED
 630    Cached_String_Type *cs;
 631
 632    cs = GET_CACHED_STRING(s);
 633    if (cs->str == s)
 634      return cs->sls->len;
 635 #endif
 636    return strlen (s);
 637 }
 638
 639 /* The caller must ensure that this is an slstring */
 640 void _pSLang_free_slstring (SLstr_Type *s)
 641 {
 642 #if SLANG_OPTIMIZE_FOR_SPEED
 643    Cached_String_Type *cs;
 644 #endif
 645    SLstring_Type *sls;
 646
 647    if (s == NULL) return;
 648
 649 #if SLANG_OPTIMIZE_FOR_SPEED
 650    cs = GET_CACHED_STRING(s);
 651    if (cs->str == s)
 652      {
 653         sls = cs->sls;
 654         if (sls->ref_count <= 1)
 655           {
 656 #if SLANG_OPTIMIZE_FOR_SPEED
 657              cs->sls = NULL;
 658              cs->str = Deleted_String;
 659 #endif
 660              free_sls_string (sls);
 661           }
 662         else
 663           sls->ref_count -= 1;
 664         return;
 665      }
 666 #endif
 667
 668    if ((s[0] == 0) || (s[1] == 0))
 669      return;
 670
 671    sls = (SLstring_Type *) (s - offsetof(SLstring_Type,bytes[0]));
 672    if (sls->ref_count > 1)
 673      {
 674         sls->ref_count--;
 675         return;
 676      }
 677    free_long_string (s, sls->hash);
 678 }
 679
 680 /* An SLstring is required */
 681 unsigned long _pSLstring_get_hash (SLstr_Type *s)
 682 {
 683    SLstring_Type *sls;
 684
 685    if (s[0] == 0)
 686      return _pSLstring_hash ((unsigned char*)s, (unsigned char *)s);
 687    if (s[1] == 0)
 688      return _pSLstring_hash ((unsigned char *)s, (unsigned char *)s+1);
 689
 690    sls = (SLstring_Type *) (s - offsetof(SLstring_Type,bytes[0]));
 691    return sls->hash;
 692 }