1 /*
2 * Copyright (c) 2007, Novell Inc.
3 *
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
6 */
7
8 #include <string.h>
9 #include "util.h"
10 #include "strpool.h"
11
12 #define STRING_BLOCK 2047
13 #define STRINGSPACE_BLOCK 65535
14
15 void
stringpool_init(Stringpool * ss,const char * strs[])16 stringpool_init(Stringpool *ss, const char *strs[])
17 {
18 unsigned totalsize = 0;
19 unsigned count;
20
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;
25
26 /* alloc appropriate space */
27 ss->stringspace = solv_extend_resize(0, totalsize, 1, STRINGSPACE_BLOCK);
28 ss->strings = solv_extend_resize(0, count, sizeof(Offset), STRING_BLOCK);
29
30 /* now copy predefined strings into allocated space */
31 ss->sstrings = 0;
32 for (count = 0; strs[count]; count++)
33 {
34 strcpy(ss->stringspace + ss->sstrings, strs[count]);
35 ss->strings[count] = ss->sstrings;
36 ss->sstrings += strlen(strs[count]) + 1;
37 }
38 ss->nstrings = count;
39 }
40
41 void
stringpool_free(Stringpool * ss)42 stringpool_free(Stringpool *ss)
43 {
44 solv_free(ss->strings);
45 solv_free(ss->stringspace);
46 solv_free(ss->stringhashtbl);
47 }
48
49 void
stringpool_freehash(Stringpool * ss)50 stringpool_freehash(Stringpool *ss)
51 {
52 ss->stringhashtbl = solv_free(ss->stringhashtbl);
53 ss->stringhashmask = 0;
54 }
55
56 void
stringpool_init_empty(Stringpool * ss)57 stringpool_init_empty(Stringpool *ss)
58 {
59 static const char *emptystrs[] = { "<NULL>", "", 0 };
60 stringpool_init(ss, emptystrs);
61 }
62
63 void
stringpool_clone(Stringpool * ss,Stringpool * from)64 stringpool_clone(Stringpool *ss, Stringpool *from)
65 {
66 memset(ss, 0, sizeof(*ss));
67 ss->strings = solv_extend_resize(0, from->nstrings, sizeof(Offset), STRING_BLOCK);
68 memcpy(ss->strings, from->strings, from->nstrings * sizeof(Offset));
69 ss->stringspace = solv_extend_resize(0, from->sstrings, 1, STRINGSPACE_BLOCK);
70 memcpy(ss->stringspace, from->stringspace, from->sstrings);
71 ss->nstrings = from->nstrings;
72 ss->sstrings = from->sstrings;
73 }
74
75 void
stringpool_resize_hash(Stringpool * ss,int numnew)76 stringpool_resize_hash(Stringpool *ss, int numnew)
77 {
78 Hashval h, hh, hashmask;
79 Hashtable hashtbl;
80 int i;
81
82 if (numnew <= 0)
83 return;
84 hashmask = mkmask(ss->nstrings + numnew);
85 if (hashmask <= ss->stringhashmask)
86 return; /* same as before */
87
88 /* realloc hash table */
89 ss->stringhashmask = hashmask;
90 solv_free(ss->stringhashtbl);
91 ss->stringhashtbl = hashtbl = (Hashtable)solv_calloc(hashmask + 1, sizeof(Id));
92
93 /* rehash all strings into new hashtable */
94 for (i = 1; i < ss->nstrings; i++)
95 {
96 h = strhash(ss->stringspace + ss->strings[i]) & hashmask;
97 hh = HASHCHAIN_START;
98 while (hashtbl[h] != 0)
99 h = HASHCHAIN_NEXT(h, hh, hashmask);
100 hashtbl[h] = i;
101 }
102 }
103
104 Id
stringpool_strn2id(Stringpool * ss,const char * str,unsigned int len,int create)105 stringpool_strn2id(Stringpool *ss, const char *str, unsigned int len, int create)
106 {
107 Hashval h, hh, hashmask, oldhashmask;
108 Id id;
109 Hashtable hashtbl;
110
111 if (!str)
112 return STRID_NULL;
113 if (!len)
114 return STRID_EMPTY;
115
116 hashmask = oldhashmask = ss->stringhashmask;
117 /* expand hashtable if needed */
118 if ((Hashval)ss->nstrings * 2 > hashmask)
119 {
120 stringpool_resize_hash(ss, STRING_BLOCK);
121 hashmask = ss->stringhashmask;
122 }
123 hashtbl = ss->stringhashtbl;
124
125 /* compute hash and check for match */
126 h = strnhash(str, len) & hashmask;
127 hh = HASHCHAIN_START;
128 while ((id = hashtbl[h]) != 0)
129 {
130 if(!memcmp(ss->stringspace + ss->strings[id], str, len)
131 && ss->stringspace[ss->strings[id] + len] == 0)
132 break;
133 h = HASHCHAIN_NEXT(h, hh, hashmask);
134 }
135 if (id || !create) /* exit here if string found */
136 return id;
137
138 /* this should be a test for a flag that tells us if the
139 * correct blocking is used, but adding a flag would break
140 * the ABI. So we use the existance of the hash area as
141 * indication instead */
142 if (!oldhashmask)
143 {
144 ss->stringspace = solv_extend_resize(ss->stringspace, ss->sstrings + len + 1, 1, STRINGSPACE_BLOCK);
145 ss->strings = solv_extend_resize(ss->strings, ss->nstrings + 1, sizeof(Offset), STRING_BLOCK);
146 }
147
148 /* generate next id and save in table */
149 id = ss->nstrings++;
150 hashtbl[h] = id;
151
152 ss->strings = solv_extend(ss->strings, id, 1, sizeof(Offset), STRING_BLOCK);
153 ss->strings[id] = ss->sstrings; /* we will append to the end */
154
155 /* append string to stringspace */
156 ss->stringspace = solv_extend(ss->stringspace, ss->sstrings, len + 1, 1, STRINGSPACE_BLOCK);
157 memcpy(ss->stringspace + ss->sstrings, str, len);
158 ss->stringspace[ss->sstrings + len] = 0;
159 ss->sstrings += len + 1;
160 return id;
161 }
162
163 Id
stringpool_str2id(Stringpool * ss,const char * str,int create)164 stringpool_str2id(Stringpool *ss, const char *str, int create)
165 {
166 if (!str)
167 return STRID_NULL;
168 if (!*str)
169 return STRID_EMPTY;
170 return stringpool_strn2id(ss, str, (unsigned int)strlen(str), create);
171 }
172
173 void
stringpool_shrink(Stringpool * ss)174 stringpool_shrink(Stringpool *ss)
175 {
176 ss->stringspace = solv_extend_resize(ss->stringspace, ss->sstrings, 1, STRINGSPACE_BLOCK);
177 ss->strings = solv_extend_resize(ss->strings, ss->nstrings, sizeof(Offset), STRING_BLOCK);
178 }
179