2
Copyright (C) 2004, 2005, 2006 John E. Davis
4
This file is part of the S-Lang Library.
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.
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.
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,
27
typedef struct _pSLstring_Type
29
struct _pSLstring_Type *next;
30
unsigned int ref_count;
37
#define MAP_HASH_TO_INDEX(hash) ((hash) % SLSTRING_HASH_TABLE_SIZE)
39
static SLstring_Type *String_Hash_Table [SLSTRING_HASH_TABLE_SIZE];
40
static char Single_Char_Strings [256 * 2];
42
#if SLANG_OPTIMIZE_FOR_SPEED
43
#define MAX_FREE_STORE_LEN 32
44
static SLstring_Type *SLS_Free_Store [MAX_FREE_STORE_LEN];
46
# define NUM_CACHED_STRINGS 601
53
static char *Deleted_String = "*deleted*";
54
static Cached_String_Type Cached_Strings [NUM_CACHED_STRINGS];
56
#define GET_CACHED_STRING(s) \
57
(Cached_Strings + (unsigned int)(((unsigned long) (s)) % NUM_CACHED_STRINGS))
61
static void cache_string (SLstring_Type *sls)
63
Cached_String_Type *cs;
65
cs = GET_CACHED_STRING(sls->bytes);
71
static void uncache_string (char *s)
73
Cached_String_Type *cs;
75
cs = GET_CACHED_STRING(s);
79
cs->str = Deleted_String;
85
/* This hash algorithm comes from:
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
92
typedef unsigned long uint32;
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); \
108
unsigned long _pSLstring_hash (unsigned char *s, unsigned char *smax)
110
register uint32 a,b,c;
111
unsigned int length = (unsigned int)(smax - s);
112
unsigned int len = length;
114
a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
117
/*---------------------------------------- handle most of the key */
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));
127
/*------------------------------------- handle the last 11 bytes */
129
switch(len) /* all the case statements fall through */
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);
139
case 4 : a+=((uint32)s[3]<<24);
140
case 3 : a+=((uint32)s[2]<<16);
141
case 2 : a+=((uint32)s[1]<<8);
143
/* case 0: nothing left to add */
146
/*-------------------------------------------- report the result */
147
return (unsigned long) c;
151
unsigned long _pSLstring_hash (unsigned char *s, unsigned char *smax)
153
register unsigned long h = 0;
154
register unsigned long sum = 0;
155
unsigned char *smax4;
176
h ^= sum + (h << 3); /* slightly different */
182
unsigned long _pSLcompute_string_hash (char *s)
184
#if SLANG_OPTIMIZE_FOR_SPEED
185
Cached_String_Type *cs;
187
cs = GET_CACHED_STRING(s);
189
return cs->sls->hash;
191
return _pSLstring_hash ((unsigned char *) s, (unsigned char *) s + strlen (s));
195
/* This routine works with any (long) string */
196
static SLstring_Type *find_string (char *s, unsigned int len, unsigned long hash)
200
sls = String_Hash_Table [(unsigned int) MAP_HASH_TO_INDEX(hash)];
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
212
if ((sls->hash == hash)
214
&& (0 == strncmp (s, sls->bytes, len)))
225
static SLstring_Type *find_slstring (char *s, unsigned long hash)
229
sls = String_Hash_Table [MAP_HASH_TO_INDEX(hash)];
241
static SLstring_Type *allocate_sls (unsigned int len)
244
#if SLANG_OPTIMIZE_FOR_SPEED
246
if ((len < MAX_FREE_STORE_LEN)
247
&& (NULL != (sls = SLS_Free_Store [len])))
249
SLS_Free_Store[len] = NULL;
253
/* FIXME: use structure padding */
254
sls = (SLstring_Type *) SLmalloc (len + sizeof (SLstring_Type));
261
static void free_sls (SLstring_Type *sls)
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))
268
SLS_Free_Store [len] = sls;
272
SLfree ((char *)sls);
276
static char *create_long_string (char *s, unsigned int len, unsigned long hash)
280
sls = find_string (s, len, hash);
285
#if SLANG_OPTIMIZE_FOR_SPEED
291
sls = allocate_sls (len);
295
strncpy (sls->bytes, s, len);
299
#if SLANG_OPTIMIZE_FOR_SPEED
303
hash = MAP_HASH_TO_INDEX(hash);
304
sls->next = String_Hash_Table [(unsigned int)hash];
305
String_Hash_Table [(unsigned int)hash] = sls;
311
static char *create_short_string (char *s, unsigned int len)
315
/* Note: if len is 0, then it does not matter what *s is. This is
316
* important for SLang_create_nslstring.
318
if (len) ch = *s; else ch = 0;
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;
326
/* s cannot be NULL */
328
static SLstr_Type *create_nstring (char *s, unsigned int len, unsigned long *hash_ptr)
333
return create_short_string (s, len);
335
hash = _pSLstring_hash ((unsigned char *) s, (unsigned char *) (s + len));
338
return create_long_string (s, len, hash);
341
SLstr_Type *SLang_create_nslstring (char *s, unsigned int len)
346
return create_nstring (s, len, &hash);
349
char *_pSLstring_make_hashed_string (char *s, unsigned int len, unsigned long *hashptr)
353
if (s == NULL) return NULL;
355
hash = _pSLstring_hash ((unsigned char *) s, (unsigned char *) s + len);
359
return create_short_string (s, len);
361
return create_long_string (s, len, hash);
364
char *_pSLstring_dup_hashed_string (char *s, unsigned long hash)
367
#if SLANG_OPTIMIZE_FOR_SPEED
368
Cached_String_Type *cs;
370
if (s == NULL) return NULL;
372
return create_short_string (s, 0);
374
return create_short_string (s, 1);
376
cs = GET_CACHED_STRING(s);
379
cs->sls->ref_count += 1;
383
if (s == NULL) return NULL;
387
#if !SLANG_OPTIMIZE_FOR_SPEED
388
if (len < 2) return create_short_string (s, len);
391
return create_long_string (s, len, hash);
394
/* This function requires an slstring!!! */
395
char *_pSLstring_dup_slstring (char *s)
398
#if SLANG_OPTIMIZE_FOR_SPEED
399
Cached_String_Type *cs;
404
#if SLANG_OPTIMIZE_FOR_SPEED
405
cs = GET_CACHED_STRING(s);
408
cs->sls->ref_count += 1;
412
if ((s[0] == 0) || (s[1] == 0))
415
sls = (SLstring_Type *) (s - offsetof(SLstring_Type,bytes[0]));
417
#if SLANG_OPTIMIZE_FOR_SPEED
423
static void free_sls_string (SLstring_Type *sls)
425
SLstring_Type *sls1, *prev;
426
unsigned long hash = sls->hash;
428
hash = MAP_HASH_TO_INDEX(hash);
430
sls1 = String_Hash_Table [(unsigned int) hash];
434
/* This should not fail. */
442
prev->next = sls->next;
444
String_Hash_Table [(unsigned int) hash] = sls->next;
450
static void free_long_string (char *s, unsigned long hash)
454
if (NULL == (sls = find_slstring (s, hash)))
456
SLang_verror (SL_APPLICATION_ERROR, "invalid attempt to free string:%s", s);
461
if (sls->ref_count != 0)
463
#if SLANG_OPTIMIZE_FOR_SPEED
464
/* cache_string (sls, len, hash); */
468
#if SLANG_OPTIMIZE_FOR_SPEED
471
free_sls_string (sls);
474
/* This routine may be passed NULL-- it is not an error. */
475
void SLang_free_slstring (char *s)
479
#if SLANG_OPTIMIZE_FOR_SPEED
480
Cached_String_Type *cs;
483
if (s == NULL) return;
485
#if SLANG_OPTIMIZE_FOR_SPEED
486
cs = GET_CACHED_STRING(s);
489
SLstring_Type *sls = cs->sls;
490
if (sls->ref_count <= 1)
492
#if SLANG_OPTIMIZE_FOR_SPEED
494
cs->str = Deleted_String;
496
free_sls_string (sls);
504
if ((len = strlen (s)) < 2)
507
hash = _pSLstring_hash ((unsigned char *)s, (unsigned char *) s + len);
508
free_long_string (s, hash);
511
char *SLang_create_slstring (char *s)
514
#if SLANG_OPTIMIZE_FOR_SPEED
515
Cached_String_Type *cs;
518
if (s == NULL) return NULL;
519
#if SLANG_OPTIMIZE_FOR_SPEED
520
cs = GET_CACHED_STRING(s);
523
cs->sls->ref_count += 1;
528
return create_nstring (s, strlen (s), &hash);
531
void _pSLfree_hashed_string (char *s, unsigned int len, unsigned long hash)
533
if ((s == NULL) || (len < 2)) return;
534
free_long_string (s, hash);
538
char *_pSLallocate_slstring (unsigned int len)
540
SLstring_Type *sls = allocate_sls (len);
548
void _pSLunallocate_slstring (char *s, unsigned int len)
556
sls = (SLstring_Type *) (s - offsetof(SLstring_Type,bytes[0]));
560
char *_pSLcreate_via_alloced_slstring (char *s, unsigned int len)
570
char *s1 = create_short_string (s, len);
571
_pSLunallocate_slstring (s, len);
575
/* s is not going to be in the cache because when it was malloced, its
576
* value was unknown. This simplifies the coding.
578
hash = _pSLstring_hash ((unsigned char *)s, (unsigned char *)s + len);
579
sls = find_string (s, len, hash);
583
_pSLunallocate_slstring (s, len);
586
#if SLANG_OPTIMIZE_FOR_SPEED
592
sls = (SLstring_Type *) (s - offsetof(SLstring_Type,bytes[0]));
596
#if SLANG_OPTIMIZE_FOR_SPEED
600
hash = MAP_HASH_TO_INDEX(hash);
601
sls->next = String_Hash_Table [(unsigned int)hash];
602
String_Hash_Table [(unsigned int)hash] = sls;
607
/* Note, a and b may be ordinary strings. The result is an slstring */
608
char *SLang_concat_slstrings (char *a, char *b)
610
unsigned int lena, len;
614
len = lena + strlen (b);
616
c = _pSLallocate_slstring (len);
621
strcpy (c + lena, b);
623
return _pSLcreate_via_alloced_slstring (c, len);
626
/* This routine is assumed to work even if s is not an slstring */
627
unsigned int _pSLstring_bytelen (SLstr_Type *s)
629
#if SLANG_OPTIMIZE_FOR_SPEED
630
Cached_String_Type *cs;
632
cs = GET_CACHED_STRING(s);
639
/* The caller must ensure that this is an slstring */
640
void _pSLang_free_slstring (SLstr_Type *s)
642
#if SLANG_OPTIMIZE_FOR_SPEED
643
Cached_String_Type *cs;
647
if (s == NULL) return;
649
#if SLANG_OPTIMIZE_FOR_SPEED
650
cs = GET_CACHED_STRING(s);
654
if (sls->ref_count <= 1)
656
#if SLANG_OPTIMIZE_FOR_SPEED
658
cs->str = Deleted_String;
660
free_sls_string (sls);
668
if ((s[0] == 0) || (s[1] == 0))
671
sls = (SLstring_Type *) (s - offsetof(SLstring_Type,bytes[0]));
672
if (sls->ref_count > 1)
677
free_long_string (s, sls->hash);
680
/* An SLstring is required */
681
unsigned long _pSLstring_get_hash (SLstr_Type *s)
686
return _pSLstring_hash ((unsigned char*)s, (unsigned char *)s);
688
return _pSLstring_hash ((unsigned char *)s, (unsigned char *)s+1);
690
sls = (SLstring_Type *) (s - offsetof(SLstring_Type,bytes[0]));
added
removed
slang/slstring.c
