2 * Copyright (c) 2007, Novell Inc.
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
12 #define STRING_BLOCK 2047
13 #define STRINGSPACE_BLOCK 65535
16 stringpool_init(Stringpool *ss, const char *strs[])
18 unsigned totalsize = 0;
21 memset(ss, 0, sizeof(*ss));
22 // count number and total size of predefined strings
23 for (count = 0; strs[count]; count++)
24 totalsize += strlen(strs[count]) + 1;
26 // alloc appropriate space
27 ss->stringspace = sat_extend_resize(0, totalsize, 1, STRINGSPACE_BLOCK);
28 ss->strings = sat_extend_resize(0, count, sizeof(Offset), STRING_BLOCK);
30 // now copy predefined strings into allocated space
32 for (count = 0; strs[count]; count++)
34 strcpy(ss->stringspace + ss->sstrings, strs[count]);
35 ss->strings[count] = ss->sstrings;
36 ss->sstrings += strlen(strs[count]) + 1;
42 stringpool_free(Stringpool *ss)
44 sat_free(ss->strings);
45 sat_free(ss->stringspace);
46 sat_free(ss->stringhashtbl);
50 stringpool_init_empty(Stringpool *ss)
52 const char *emptystrs[] = {
57 stringpool_init(ss, emptystrs);
61 stringpool_clone(Stringpool *ss, Stringpool *from)
63 memset(ss, 0, sizeof(*ss));
64 ss->strings = sat_extend_resize(0, from->nstrings, sizeof(Offset), STRING_BLOCK);
65 memcpy(ss->strings, from->strings, from->nstrings * sizeof(Offset));
66 ss->stringspace = sat_extend_resize(0, from->sstrings, 1, STRINGSPACE_BLOCK);
67 memcpy(ss->stringspace, from->stringspace, from->sstrings);
68 ss->nstrings = from->nstrings;
69 ss->sstrings = from->sstrings;
73 stringpool_strn2id (Stringpool *ss, const char *str, unsigned len, int create)
88 hashmask = ss->stringhashmask;
89 hashtbl = ss->stringhashtbl;
91 // expand hashtable if needed
94 if (ss->nstrings * 2 > hashmask)
99 ss->stringhashmask = hashmask = mkmask(ss->nstrings + STRING_BLOCK);
100 ss->stringhashtbl = hashtbl = (Hashtable)sat_calloc(hashmask + 1, sizeof(Id));
102 // rehash all strings into new hashtable
103 for (i = 1; i < ss->nstrings; i++)
105 h = strhash(ss->stringspace + ss->strings[i]) & hashmask;
106 hh = HASHCHAIN_START;
107 while (hashtbl[h] != 0) // follow overflow chain
108 h = HASHCHAIN_NEXT(h, hh, hashmask);
113 // compute hash and check for match
115 h = strnhash(str, len) & hashmask;
116 hh = HASHCHAIN_START;
117 while ((id = hashtbl[h]) != 0) // follow hash overflow chain
119 // break if string already hashed
120 if(!memcmp(ss->stringspace + ss->strings[id], str, len)
121 && ss->stringspace[ss->strings[id] + len] == 0)
123 h = HASHCHAIN_NEXT(h, hh, hashmask);
125 if (id || !create) // exit here if string found
128 // generate next id and save in table
132 ss->strings = sat_extend(ss->strings, id, 1, sizeof(Offset), STRING_BLOCK);
133 // 'pointer' into stringspace is Offset of next free pos: sstrings
134 ss->strings[id] = ss->sstrings;
136 space_needed = len + 1;
137 // make room in string buffer
138 ss->stringspace = sat_extend(ss->stringspace, ss->sstrings, space_needed, 1, STRINGSPACE_BLOCK);
139 // copy new string into buffer
140 memcpy(ss->stringspace + ss->sstrings, str, space_needed - 1);
141 // add the sentinel, we can't rely on it being in the source string (in
142 // case the LEN is not really strlen(str))
143 ss->stringspace[ss->sstrings + space_needed - 1] = 0;
144 // next free pos is behind new string
145 ss->sstrings += space_needed;
151 stringpool_str2id (Stringpool *ss, const char *str, int create)
157 unsigned len = strlen (str);
158 return stringpool_strn2id (ss, str, len, create);
162 stringpool_shrink (Stringpool *ss)
164 ss->stringspace = sat_extend_resize(ss->stringspace, ss->sstrings, 1, STRINGSPACE_BLOCK);
165 ss->strings = sat_extend_resize(ss->strings, ss->nstrings, sizeof(Offset), STRING_BLOCK);