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 const char *emptystrs[] = {
60 "<NULL>",
61 "",
62 0,
63 };
64 stringpool_init(ss, emptystrs);
65 }
66
67 void
stringpool_clone(Stringpool * ss,Stringpool * from)68 stringpool_clone(Stringpool *ss, Stringpool *from)
69 {
70 memset(ss, 0, sizeof(*ss));
71 ss->strings = solv_extend_resize(0, from->nstrings, sizeof(Offset), STRING_BLOCK);
72 memcpy(ss->strings, from->strings, from->nstrings * sizeof(Offset));
73 ss->stringspace = solv_extend_resize(0, from->sstrings, 1, STRINGSPACE_BLOCK);
74 memcpy(ss->stringspace, from->stringspace, from->sstrings);
75 ss->nstrings = from->nstrings;
76 ss->sstrings = from->sstrings;
77 }
78
79 Id
stringpool_strn2id(Stringpool * ss,const char * str,unsigned int len,int create)80 stringpool_strn2id(Stringpool *ss, const char *str, unsigned int len, int create)
81 {
82 Hashval h, hh, hashmask, oldhashmask;
83 int i;
84 Id id;
85 Hashtable hashtbl;
86
87 if (!str)
88 return STRID_NULL;
89 if (!len)
90 return STRID_EMPTY;
91
92 hashmask = oldhashmask = ss->stringhashmask;
93 hashtbl = ss->stringhashtbl;
94
95 /* expand hashtable if needed */
96 if (ss->nstrings * 2 > hashmask)
97 {
98 solv_free(hashtbl);
99
100 /* realloc hash table */
101 ss->stringhashmask = hashmask = mkmask(ss->nstrings + STRING_BLOCK);
102 ss->stringhashtbl = hashtbl = (Hashtable)solv_calloc(hashmask + 1, sizeof(Id));
103
104 /* rehash all strings into new hashtable */
105 for (i = 1; i < ss->nstrings; i++)
106 {
107 h = strhash(ss->stringspace + ss->strings[i]) & hashmask;
108 hh = HASHCHAIN_START;
109 while (hashtbl[h] != 0)
110 h = HASHCHAIN_NEXT(h, hh, hashmask);
111 hashtbl[h] = i;
112 }
113 }
114
115 /* compute hash and check for match */
116 h = strnhash(str, len) & hashmask;
117 hh = HASHCHAIN_START;
118 while ((id = hashtbl[h]) != 0)
119 {
120 if(!memcmp(ss->stringspace + ss->strings[id], str, len)
121 && ss->stringspace[ss->strings[id] + len] == 0)
122 break;
123 h = HASHCHAIN_NEXT(h, hh, hashmask);
124 }
125 if (id || !create) /* exit here if string found */
126 return id;
127
128 /* this should be a test for a flag that tells us if the
129 * correct blocking is used, but adding a flag would break
130 * the ABI. So we use the existance of the hash area as
131 * indication instead */
132 if (!oldhashmask)
133 {
134 ss->stringspace = solv_extend_resize(ss->stringspace, ss->sstrings + len + 1, 1, STRINGSPACE_BLOCK);
135 ss->strings = solv_extend_resize(ss->strings, ss->nstrings + 1, sizeof(Offset), STRING_BLOCK);
136 }
137
138 /* generate next id and save in table */
139 id = ss->nstrings++;
140 hashtbl[h] = id;
141
142 ss->strings = solv_extend(ss->strings, id, 1, sizeof(Offset), STRING_BLOCK);
143 ss->strings[id] = ss->sstrings; /* we will append to the end */
144
145 /* append string to stringspace */
146 ss->stringspace = solv_extend(ss->stringspace, ss->sstrings, len + 1, 1, STRINGSPACE_BLOCK);
147 memcpy(ss->stringspace + ss->sstrings, str, len);
148 ss->stringspace[ss->sstrings + len] = 0;
149 ss->sstrings += len + 1;
150 return id;
151 }
152
153 Id
stringpool_str2id(Stringpool * ss,const char * str,int create)154 stringpool_str2id(Stringpool *ss, const char *str, int create)
155 {
156 if (!str)
157 return STRID_NULL;
158 if (!*str)
159 return STRID_EMPTY;
160 return stringpool_strn2id(ss, str, (unsigned int)strlen(str), create);
161 }
162
163 void
stringpool_shrink(Stringpool * ss)164 stringpool_shrink(Stringpool *ss)
165 {
166 ss->stringspace = solv_extend_resize(ss->stringspace, ss->sstrings, 1, STRINGSPACE_BLOCK);
167 ss->strings = solv_extend_resize(ss->strings, ss->nstrings, sizeof(Offset), STRING_BLOCK);
168 }
169