1 | #include <stdlib.h>
|
---|
2 | #include <string.h>
|
---|
3 | #include <libxml/parser.h>
|
---|
4 | #include <libxml/dict.h>
|
---|
5 |
|
---|
6 |
|
---|
7 | /**** dictionary tests ****/
|
---|
8 |
|
---|
9 | #ifdef __clang__
|
---|
10 | #define ATTRIBUTE_NO_SANITIZE_INTEGER \
|
---|
11 | __attribute__ ((no_sanitize("unsigned-integer-overflow"))) \
|
---|
12 | __attribute__ ((no_sanitize("unsigned-shift-base")))
|
---|
13 | #else
|
---|
14 | #define ATTRIBUTE_NO_SANITIZE_INTEGER
|
---|
15 | #endif
|
---|
16 |
|
---|
17 | /* #define WITH_PRINT */
|
---|
18 |
|
---|
19 | static const char *seeds1[] = {
|
---|
20 | "a", "b", "c",
|
---|
21 | "d", "e", "f",
|
---|
22 | "g", "h", "i",
|
---|
23 | "j", "k", "l",
|
---|
24 |
|
---|
25 | NULL
|
---|
26 | };
|
---|
27 |
|
---|
28 | static const char *seeds2[] = {
|
---|
29 | "m", "n", "o",
|
---|
30 | "p", "q", "r",
|
---|
31 | "s", "t", "u",
|
---|
32 | "v", "w", "x",
|
---|
33 |
|
---|
34 | NULL
|
---|
35 | };
|
---|
36 |
|
---|
37 | #define NB_STRINGS_MAX 100000
|
---|
38 | #define NB_STRINGS_NS 10000
|
---|
39 | #define NB_STRINGS_PREFIX (NB_STRINGS_NS / 20)
|
---|
40 | #define NB_STRINGS_MIN 10
|
---|
41 |
|
---|
42 | static xmlChar **strings1;
|
---|
43 | static xmlChar **strings2;
|
---|
44 | static const xmlChar **test1;
|
---|
45 | static const xmlChar **test2;
|
---|
46 | static int nbErrors = 0;
|
---|
47 |
|
---|
48 | static void
|
---|
49 | fill_string_pool(xmlChar **strings, const char **seeds) {
|
---|
50 | int i, j, k;
|
---|
51 | int start_ns = NB_STRINGS_MAX - NB_STRINGS_NS;
|
---|
52 |
|
---|
53 | /*
|
---|
54 | * That's a bit nasty but the output is fine and it doesn't take hours
|
---|
55 | * there is a small but sufficient number of duplicates, and we have
|
---|
56 | * ":xxx" and full QNames in the last NB_STRINGS_NS values
|
---|
57 | */
|
---|
58 | for (i = 0; seeds[i] != NULL; i++) {
|
---|
59 | strings[i] = xmlStrdup((const xmlChar *) seeds[i]);
|
---|
60 | if (strings[i] == NULL) {
|
---|
61 | fprintf(stderr, "Out of memory while generating strings\n");
|
---|
62 | exit(1);
|
---|
63 | }
|
---|
64 | }
|
---|
65 | for (j = 0, k = 0; i < start_ns; i++) {
|
---|
66 | strings[i] = xmlStrncatNew(strings[j], strings[k], -1);
|
---|
67 | if (strings[i] == NULL) {
|
---|
68 | fprintf(stderr, "Out of memory while generating strings\n");
|
---|
69 | exit(1);
|
---|
70 | }
|
---|
71 | if (xmlStrlen(strings[i]) > 30) {
|
---|
72 | fprintf(stderr, "### %s %s\n", strings[start_ns+j], strings[k]);
|
---|
73 | abort();
|
---|
74 | }
|
---|
75 | j++;
|
---|
76 | if (j >= 50) {
|
---|
77 | j = 0;
|
---|
78 | k++;
|
---|
79 | }
|
---|
80 | }
|
---|
81 | for (j = 0, k = 0; (j < NB_STRINGS_PREFIX) && (i < NB_STRINGS_MAX);
|
---|
82 | i++, j++) {
|
---|
83 | strings[i] = xmlStrncatNew(strings[k], (const xmlChar *) ":", -1);
|
---|
84 | if (strings[i] == NULL) {
|
---|
85 | fprintf(stderr, "Out of memory while generating strings\n");
|
---|
86 | exit(1);
|
---|
87 | }
|
---|
88 | k += 1;
|
---|
89 | if (k >= start_ns) k = 0;
|
---|
90 | }
|
---|
91 | for (j = 0, k = 0; i < NB_STRINGS_MAX; i++) {
|
---|
92 | strings[i] = xmlStrncatNew(strings[start_ns+j], strings[k], -1);
|
---|
93 | if (strings[i] == NULL) {
|
---|
94 | fprintf(stderr, "Out of memory while generating strings\n");
|
---|
95 | exit(1);
|
---|
96 | }
|
---|
97 | j++;
|
---|
98 | if (j >= NB_STRINGS_PREFIX) j = 0;
|
---|
99 | k += 5;
|
---|
100 | if (k >= start_ns) k = 0;
|
---|
101 | }
|
---|
102 | }
|
---|
103 |
|
---|
104 | #ifdef WITH_PRINT
|
---|
105 | static void print_strings(void) {
|
---|
106 | int i;
|
---|
107 |
|
---|
108 | for (i = 0; i < NB_STRINGS_MAX;i++) {
|
---|
109 | printf("%s\n", strings1[i]);
|
---|
110 | }
|
---|
111 | for (i = 0; i < NB_STRINGS_MAX;i++) {
|
---|
112 | printf("%s\n", strings2[i]);
|
---|
113 | }
|
---|
114 | }
|
---|
115 | #endif
|
---|
116 |
|
---|
117 | static void clean_strings(void) {
|
---|
118 | int i;
|
---|
119 |
|
---|
120 | for (i = 0; i < NB_STRINGS_MAX; i++) {
|
---|
121 | if (strings1[i] != NULL) /* really should not happen */
|
---|
122 | xmlFree(strings1[i]);
|
---|
123 | }
|
---|
124 | for (i = 0; i < NB_STRINGS_MAX; i++) {
|
---|
125 | if (strings2[i] != NULL) /* really should not happen */
|
---|
126 | xmlFree(strings2[i]);
|
---|
127 | }
|
---|
128 | }
|
---|
129 |
|
---|
130 | /*
|
---|
131 | * This tests the sub-dictionary support
|
---|
132 | */
|
---|
133 | static int
|
---|
134 | test_subdict(xmlDictPtr parent) {
|
---|
135 | int i, j;
|
---|
136 | xmlDictPtr dict;
|
---|
137 | int ret = 0;
|
---|
138 | xmlChar prefix[40];
|
---|
139 | xmlChar *cur, *pref;
|
---|
140 | const xmlChar *tmp;
|
---|
141 |
|
---|
142 | dict = xmlDictCreateSub(parent);
|
---|
143 | if (dict == NULL) {
|
---|
144 | fprintf(stderr, "Out of memory while creating sub-dictionary\n");
|
---|
145 | exit(1);
|
---|
146 | }
|
---|
147 | /* Cast to avoid buggy warning on MSVC. */
|
---|
148 | memset((void *) test2, 0, sizeof(test2));
|
---|
149 |
|
---|
150 | /*
|
---|
151 | * Fill in NB_STRINGS_MIN, at this point the dictionary should not grow
|
---|
152 | * and we allocate all those doing the fast key computations
|
---|
153 | * All the strings are based on a different seeds subset so we know
|
---|
154 | * they are allocated in the main dictionary, not coming from the parent
|
---|
155 | */
|
---|
156 | for (i = 0;i < NB_STRINGS_MIN;i++) {
|
---|
157 | test2[i] = xmlDictLookup(dict, strings2[i], -1);
|
---|
158 | if (test2[i] == NULL) {
|
---|
159 | fprintf(stderr, "Failed lookup for '%s'\n", strings2[i]);
|
---|
160 | ret = 1;
|
---|
161 | nbErrors++;
|
---|
162 | }
|
---|
163 | }
|
---|
164 | j = NB_STRINGS_MAX - NB_STRINGS_NS;
|
---|
165 | /* ":foo" like strings2 */
|
---|
166 | for (i = 0;i < NB_STRINGS_MIN;i++, j++) {
|
---|
167 | test2[j] = xmlDictLookup(dict, strings2[j], xmlStrlen(strings2[j]));
|
---|
168 | if (test2[j] == NULL) {
|
---|
169 | fprintf(stderr, "Failed lookup for '%s'\n", strings2[j]);
|
---|
170 | ret = 1;
|
---|
171 | nbErrors++;
|
---|
172 | }
|
---|
173 | }
|
---|
174 | /* "a:foo" like strings2 */
|
---|
175 | j = NB_STRINGS_MAX - NB_STRINGS_MIN;
|
---|
176 | for (i = 0;i < NB_STRINGS_MIN;i++, j++) {
|
---|
177 | test2[j] = xmlDictLookup(dict, strings2[j], xmlStrlen(strings2[j]));
|
---|
178 | if (test2[j] == NULL) {
|
---|
179 | fprintf(stderr, "Failed lookup for '%s'\n", strings2[j]);
|
---|
180 | ret = 1;
|
---|
181 | nbErrors++;
|
---|
182 | }
|
---|
183 | }
|
---|
184 |
|
---|
185 | /*
|
---|
186 | * At this point allocate all the strings
|
---|
187 | * the dictionary will grow in the process, reallocate more string tables
|
---|
188 | * and switch to the better key generator
|
---|
189 | */
|
---|
190 | for (i = 0;i < NB_STRINGS_MAX;i++) {
|
---|
191 | if (test2[i] != NULL)
|
---|
192 | continue;
|
---|
193 | test2[i] = xmlDictLookup(dict, strings2[i], -1);
|
---|
194 | if (test2[i] == NULL) {
|
---|
195 | fprintf(stderr, "Failed lookup for '%s'\n", strings2[i]);
|
---|
196 | ret = 1;
|
---|
197 | nbErrors++;
|
---|
198 | }
|
---|
199 | }
|
---|
200 |
|
---|
201 | /*
|
---|
202 | * Now we can start to test things, first that all strings2 belongs to
|
---|
203 | * the dict, and that none of them was actually allocated in the parent
|
---|
204 | */
|
---|
205 | for (i = 0;i < NB_STRINGS_MAX;i++) {
|
---|
206 | if (!xmlDictOwns(dict, test2[i])) {
|
---|
207 | fprintf(stderr, "Failed ownership failure for '%s'\n",
|
---|
208 | strings2[i]);
|
---|
209 | ret = 1;
|
---|
210 | nbErrors++;
|
---|
211 | }
|
---|
212 | if (xmlDictOwns(parent, test2[i])) {
|
---|
213 | fprintf(stderr, "Failed parent ownership failure for '%s'\n",
|
---|
214 | strings2[i]);
|
---|
215 | ret = 1;
|
---|
216 | nbErrors++;
|
---|
217 | }
|
---|
218 | }
|
---|
219 |
|
---|
220 | /*
|
---|
221 | * Also verify that all strings from the parent are seen from the subdict
|
---|
222 | */
|
---|
223 | for (i = 0;i < NB_STRINGS_MAX;i++) {
|
---|
224 | if (!xmlDictOwns(dict, test1[i])) {
|
---|
225 | fprintf(stderr, "Failed sub-ownership failure for '%s'\n",
|
---|
226 | strings1[i]);
|
---|
227 | ret = 1;
|
---|
228 | nbErrors++;
|
---|
229 | }
|
---|
230 | }
|
---|
231 |
|
---|
232 | /*
|
---|
233 | * Then that another lookup to the string in sub will return the same
|
---|
234 | */
|
---|
235 | for (i = 0;i < NB_STRINGS_MAX;i++) {
|
---|
236 | if (xmlDictLookup(dict, strings2[i], -1) != test2[i]) {
|
---|
237 | fprintf(stderr, "Failed re-lookup check for %d, '%s'\n",
|
---|
238 | i, strings2[i]);
|
---|
239 | ret = 1;
|
---|
240 | nbErrors++;
|
---|
241 | }
|
---|
242 | }
|
---|
243 | /*
|
---|
244 | * But also that any lookup for a string in the parent will be provided
|
---|
245 | * as in the parent
|
---|
246 | */
|
---|
247 | for (i = 0;i < NB_STRINGS_MAX;i++) {
|
---|
248 | if (xmlDictLookup(dict, strings1[i], -1) != test1[i]) {
|
---|
249 | fprintf(stderr, "Failed parent string lookup check for %d, '%s'\n",
|
---|
250 | i, strings1[i]);
|
---|
251 | ret = 1;
|
---|
252 | nbErrors++;
|
---|
253 | }
|
---|
254 | }
|
---|
255 |
|
---|
256 | /*
|
---|
257 | * check the QName lookups
|
---|
258 | */
|
---|
259 | for (i = NB_STRINGS_MAX - NB_STRINGS_NS;i < NB_STRINGS_MAX;i++) {
|
---|
260 | cur = strings2[i];
|
---|
261 | pref = &prefix[0];
|
---|
262 | while (*cur != ':') *pref++ = *cur++;
|
---|
263 | cur++;
|
---|
264 | *pref = 0;
|
---|
265 | tmp = xmlDictQLookup(dict, &prefix[0], cur);
|
---|
266 | if (tmp != test2[i]) {
|
---|
267 | fprintf(stderr, "Failed lookup check for '%s':'%s'\n",
|
---|
268 | &prefix[0], cur);
|
---|
269 | ret = 1;
|
---|
270 | nbErrors++;
|
---|
271 | }
|
---|
272 | }
|
---|
273 | /*
|
---|
274 | * check the QName lookups for strings from the parent
|
---|
275 | */
|
---|
276 | for (i = NB_STRINGS_MAX - NB_STRINGS_NS;i < NB_STRINGS_MAX;i++) {
|
---|
277 | cur = strings1[i];
|
---|
278 | pref = &prefix[0];
|
---|
279 | while (*cur != ':') *pref++ = *cur++;
|
---|
280 | cur++;
|
---|
281 | *pref = 0;
|
---|
282 | tmp = xmlDictQLookup(dict, &prefix[0], cur);
|
---|
283 | if (xmlDictQLookup(dict, &prefix[0], cur) != test1[i]) {
|
---|
284 | fprintf(stderr, "Failed parent lookup check for '%s':'%s'\n",
|
---|
285 | &prefix[0], cur);
|
---|
286 | ret = 1;
|
---|
287 | nbErrors++;
|
---|
288 | }
|
---|
289 | }
|
---|
290 |
|
---|
291 | xmlDictFree(dict);
|
---|
292 | return(ret);
|
---|
293 | }
|
---|
294 |
|
---|
295 | /*
|
---|
296 | * Test a single dictionary
|
---|
297 | */
|
---|
298 | static int
|
---|
299 | test_dict(xmlDict *dict) {
|
---|
300 | int i, j;
|
---|
301 | int ret = 0;
|
---|
302 | xmlChar prefix[40];
|
---|
303 | xmlChar *cur, *pref;
|
---|
304 | const xmlChar *tmp;
|
---|
305 |
|
---|
306 | /* Cast to avoid buggy warning on MSVC. */
|
---|
307 | memset((void *) test1, 0, sizeof(test1));
|
---|
308 |
|
---|
309 | /*
|
---|
310 | * Fill in NB_STRINGS_MIN, at this point the dictionary should not grow
|
---|
311 | * and we allocate all those doing the fast key computations
|
---|
312 | */
|
---|
313 | for (i = 0;i < NB_STRINGS_MIN;i++) {
|
---|
314 | test1[i] = xmlDictLookup(dict, strings1[i], -1);
|
---|
315 | if (test1[i] == NULL) {
|
---|
316 | fprintf(stderr, "Failed lookup for '%s'\n", strings1[i]);
|
---|
317 | ret = 1;
|
---|
318 | nbErrors++;
|
---|
319 | }
|
---|
320 | }
|
---|
321 | j = NB_STRINGS_MAX - NB_STRINGS_NS;
|
---|
322 | /* ":foo" like strings1 */
|
---|
323 | for (i = 0;i < NB_STRINGS_MIN;i++, j++) {
|
---|
324 | test1[j] = xmlDictLookup(dict, strings1[j], xmlStrlen(strings1[j]));
|
---|
325 | if (test1[j] == NULL) {
|
---|
326 | fprintf(stderr, "Failed lookup for '%s'\n", strings1[j]);
|
---|
327 | ret = 1;
|
---|
328 | nbErrors++;
|
---|
329 | }
|
---|
330 | }
|
---|
331 | /* "a:foo" like strings1 */
|
---|
332 | j = NB_STRINGS_MAX - NB_STRINGS_MIN;
|
---|
333 | for (i = 0;i < NB_STRINGS_MIN;i++, j++) {
|
---|
334 | test1[j] = xmlDictLookup(dict, strings1[j], xmlStrlen(strings1[j]));
|
---|
335 | if (test1[j] == NULL) {
|
---|
336 | fprintf(stderr, "Failed lookup for '%s'\n", strings1[j]);
|
---|
337 | ret = 1;
|
---|
338 | nbErrors++;
|
---|
339 | }
|
---|
340 | }
|
---|
341 |
|
---|
342 | /*
|
---|
343 | * At this point allocate all the strings
|
---|
344 | * the dictionary will grow in the process, reallocate more string tables
|
---|
345 | * and switch to the better key generator
|
---|
346 | */
|
---|
347 | for (i = 0;i < NB_STRINGS_MAX;i++) {
|
---|
348 | if (test1[i] != NULL)
|
---|
349 | continue;
|
---|
350 | test1[i] = xmlDictLookup(dict, strings1[i], -1);
|
---|
351 | if (test1[i] == NULL) {
|
---|
352 | fprintf(stderr, "Failed lookup for '%s'\n", strings1[i]);
|
---|
353 | ret = 1;
|
---|
354 | nbErrors++;
|
---|
355 | }
|
---|
356 | }
|
---|
357 |
|
---|
358 | /*
|
---|
359 | * Now we can start to test things, first that all strings1 belongs to
|
---|
360 | * the dict
|
---|
361 | */
|
---|
362 | for (i = 0;i < NB_STRINGS_MAX;i++) {
|
---|
363 | if (!xmlDictOwns(dict, test1[i])) {
|
---|
364 | fprintf(stderr, "Failed ownership failure for '%s'\n",
|
---|
365 | strings1[i]);
|
---|
366 | ret = 1;
|
---|
367 | nbErrors++;
|
---|
368 | }
|
---|
369 | }
|
---|
370 |
|
---|
371 | /*
|
---|
372 | * Then that another lookup to the string will return the same
|
---|
373 | */
|
---|
374 | for (i = 0;i < NB_STRINGS_MAX;i++) {
|
---|
375 | if (xmlDictLookup(dict, strings1[i], -1) != test1[i]) {
|
---|
376 | fprintf(stderr, "Failed re-lookup check for %d, '%s'\n",
|
---|
377 | i, strings1[i]);
|
---|
378 | ret = 1;
|
---|
379 | nbErrors++;
|
---|
380 | }
|
---|
381 | }
|
---|
382 |
|
---|
383 | /*
|
---|
384 | * More complex, check the QName lookups
|
---|
385 | */
|
---|
386 | for (i = NB_STRINGS_MAX - NB_STRINGS_NS;i < NB_STRINGS_MAX;i++) {
|
---|
387 | cur = strings1[i];
|
---|
388 | pref = &prefix[0];
|
---|
389 | while (*cur != ':') *pref++ = *cur++;
|
---|
390 | cur++;
|
---|
391 | *pref = 0;
|
---|
392 | tmp = xmlDictQLookup(dict, &prefix[0], cur);
|
---|
393 | if (tmp != test1[i]) {
|
---|
394 | fprintf(stderr, "Failed lookup check for '%s':'%s'\n",
|
---|
395 | &prefix[0], cur);
|
---|
396 | ret = 1;
|
---|
397 | nbErrors++;
|
---|
398 | }
|
---|
399 | }
|
---|
400 |
|
---|
401 | return(ret);
|
---|
402 | }
|
---|
403 |
|
---|
404 | static int
|
---|
405 | testall_dict(void) {
|
---|
406 | xmlDictPtr dict;
|
---|
407 | int ret = 0;
|
---|
408 |
|
---|
409 | strings1 = xmlMalloc(NB_STRINGS_MAX * sizeof(strings1[0]));
|
---|
410 | memset(strings1, 0, NB_STRINGS_MAX * sizeof(strings1[0]));
|
---|
411 | strings2 = xmlMalloc(NB_STRINGS_MAX * sizeof(strings2[0]));
|
---|
412 | memset(strings2, 0, NB_STRINGS_MAX * sizeof(strings2[0]));
|
---|
413 | test1 = xmlMalloc(NB_STRINGS_MAX * sizeof(test1[0]));
|
---|
414 | memset(test1, 0, NB_STRINGS_MAX * sizeof(test1[0]));
|
---|
415 | test2 = xmlMalloc(NB_STRINGS_MAX * sizeof(test2[0]));
|
---|
416 | memset(test2, 0, NB_STRINGS_MAX * sizeof(test2[0]));
|
---|
417 |
|
---|
418 | fill_string_pool(strings1, seeds1);
|
---|
419 | fill_string_pool(strings2, seeds2);
|
---|
420 | #ifdef WITH_PRINT
|
---|
421 | print_strings();
|
---|
422 | #endif
|
---|
423 |
|
---|
424 | dict = xmlDictCreate();
|
---|
425 | if (dict == NULL) {
|
---|
426 | fprintf(stderr, "Out of memory while creating dictionary\n");
|
---|
427 | exit(1);
|
---|
428 | }
|
---|
429 | if (test_dict(dict) != 0) {
|
---|
430 | ret = 1;
|
---|
431 | }
|
---|
432 | if (test_subdict(dict) != 0) {
|
---|
433 | ret = 1;
|
---|
434 | }
|
---|
435 | xmlDictFree(dict);
|
---|
436 |
|
---|
437 | clean_strings();
|
---|
438 | xmlFree(strings1);
|
---|
439 | xmlFree(strings2);
|
---|
440 | xmlFree(test1);
|
---|
441 | xmlFree(test2);
|
---|
442 |
|
---|
443 | return ret;
|
---|
444 | }
|
---|
445 |
|
---|
446 |
|
---|
447 | /**** Hash table tests ****/
|
---|
448 |
|
---|
449 | static unsigned
|
---|
450 | rng_state[2] = { 123, 456 };
|
---|
451 |
|
---|
452 | #define HASH_ROL(x,n) ((x) << (n) | ((x) & 0xFFFFFFFF) >> (32 - (n)))
|
---|
453 |
|
---|
454 | ATTRIBUTE_NO_SANITIZE_INTEGER
|
---|
455 | static unsigned
|
---|
456 | my_rand(unsigned max) {
|
---|
457 | unsigned s0 = rng_state[0];
|
---|
458 | unsigned s1 = rng_state[1];
|
---|
459 | unsigned result = HASH_ROL(s0 * 0x9E3779BB, 5) * 5;
|
---|
460 |
|
---|
461 | s1 ^= s0;
|
---|
462 | rng_state[0] = HASH_ROL(s0, 26) ^ s1 ^ (s1 << 9);
|
---|
463 | rng_state[1] = HASH_ROL(s1, 13);
|
---|
464 |
|
---|
465 | return((result & 0xFFFFFFFF) % max);
|
---|
466 | }
|
---|
467 |
|
---|
468 | static xmlChar *
|
---|
469 | gen_random_string(xmlChar id) {
|
---|
470 | unsigned size = my_rand(64) + 1;
|
---|
471 | unsigned id_pos = my_rand(size);
|
---|
472 | size_t j;
|
---|
473 |
|
---|
474 | xmlChar *str = xmlMalloc(size + 1);
|
---|
475 | for (j = 0; j < size; j++) {
|
---|
476 | str[j] = 'a' + my_rand(26);
|
---|
477 | }
|
---|
478 | str[id_pos] = id;
|
---|
479 | str[size] = 0;
|
---|
480 |
|
---|
481 | /* Generate QName in 75% of cases */
|
---|
482 | if (size > 3 && my_rand(4) > 0) {
|
---|
483 | unsigned colon_pos = my_rand(size - 3) + 1;
|
---|
484 |
|
---|
485 | if (colon_pos >= id_pos)
|
---|
486 | colon_pos++;
|
---|
487 | str[colon_pos] = ':';
|
---|
488 | }
|
---|
489 |
|
---|
490 | return str;
|
---|
491 | }
|
---|
492 |
|
---|
493 | typedef struct {
|
---|
494 | xmlChar **strings;
|
---|
495 | size_t num_entries;
|
---|
496 | size_t num_keys;
|
---|
497 | size_t num_strings;
|
---|
498 | size_t index;
|
---|
499 | xmlChar id;
|
---|
500 | } StringPool;
|
---|
501 |
|
---|
502 | static StringPool *
|
---|
503 | pool_new(size_t num_entries, size_t num_keys, xmlChar id) {
|
---|
504 | StringPool *ret;
|
---|
505 | size_t num_strings;
|
---|
506 |
|
---|
507 | ret = xmlMalloc(sizeof(*ret));
|
---|
508 | ret->num_entries = num_entries;
|
---|
509 | ret->num_keys = num_keys;
|
---|
510 | num_strings = num_entries * num_keys;
|
---|
511 | ret->strings = xmlMalloc(num_strings * sizeof(ret->strings[0]));
|
---|
512 | memset(ret->strings, 0, num_strings * sizeof(ret->strings[0]));
|
---|
513 | ret->num_strings = num_strings;
|
---|
514 | ret->index = 0;
|
---|
515 | ret->id = id;
|
---|
516 |
|
---|
517 | return ret;
|
---|
518 | }
|
---|
519 |
|
---|
520 | static void
|
---|
521 | pool_free(StringPool *pool) {
|
---|
522 | size_t i;
|
---|
523 |
|
---|
524 | for (i = 0; i < pool->num_strings; i++) {
|
---|
525 | xmlFree(pool->strings[i]);
|
---|
526 | }
|
---|
527 | xmlFree(pool->strings);
|
---|
528 | xmlFree(pool);
|
---|
529 | }
|
---|
530 |
|
---|
531 | static int
|
---|
532 | pool_done(StringPool *pool) {
|
---|
533 | return pool->index >= pool->num_strings;
|
---|
534 | }
|
---|
535 |
|
---|
536 | static void
|
---|
537 | pool_reset(StringPool *pool) {
|
---|
538 | pool->index = 0;
|
---|
539 | }
|
---|
540 |
|
---|
541 | static int
|
---|
542 | pool_bulk_insert(StringPool *pool, xmlHashTablePtr hash, size_t num) {
|
---|
543 | size_t i, j;
|
---|
544 | int ret = 0;
|
---|
545 |
|
---|
546 | for (i = pool->index, j = 0; i < pool->num_strings && j < num; j++) {
|
---|
547 | xmlChar *str[3];
|
---|
548 | size_t k;
|
---|
549 |
|
---|
550 | while (1) {
|
---|
551 | xmlChar tmp_key[1];
|
---|
552 | int res;
|
---|
553 |
|
---|
554 | for (k = 0; k < pool->num_keys; k++)
|
---|
555 | str[k] = gen_random_string(pool->id);
|
---|
556 |
|
---|
557 | switch (pool->num_keys) {
|
---|
558 | case 1:
|
---|
559 | res = xmlHashAddEntry(hash, str[0], tmp_key);
|
---|
560 | if (res == 0 &&
|
---|
561 | xmlHashUpdateEntry(hash, str[0], str[0], NULL) != 0)
|
---|
562 | ret = -1;
|
---|
563 | break;
|
---|
564 | case 2:
|
---|
565 | res = xmlHashAddEntry2(hash, str[0], str[1], tmp_key);
|
---|
566 | if (res == 0 &&
|
---|
567 | xmlHashUpdateEntry2(hash, str[0], str[1], str[0],
|
---|
568 | NULL) != 0)
|
---|
569 | ret = -1;
|
---|
570 | break;
|
---|
571 | case 3:
|
---|
572 | res = xmlHashAddEntry3(hash, str[0], str[1], str[2],
|
---|
573 | tmp_key);
|
---|
574 | if (res == 0 &&
|
---|
575 | xmlHashUpdateEntry3(hash, str[0], str[1], str[2],
|
---|
576 | str[0], NULL) != 0)
|
---|
577 | ret = -1;
|
---|
578 | break;
|
---|
579 | }
|
---|
580 |
|
---|
581 | if (res == 0)
|
---|
582 | break;
|
---|
583 | for (k = 0; k < pool->num_keys; k++)
|
---|
584 | xmlFree(str[k]);
|
---|
585 | }
|
---|
586 |
|
---|
587 | for (k = 0; k < pool->num_keys; k++)
|
---|
588 | pool->strings[i++] = str[k];
|
---|
589 | }
|
---|
590 |
|
---|
591 | pool->index = i;
|
---|
592 | return ret;
|
---|
593 | }
|
---|
594 |
|
---|
595 | static xmlChar *
|
---|
596 | hash_qlookup(xmlHashTable *hash, xmlChar **names, size_t num_keys) {
|
---|
597 | xmlChar *prefix[3];
|
---|
598 | const xmlChar *local[3];
|
---|
599 | xmlChar *res;
|
---|
600 | size_t i;
|
---|
601 |
|
---|
602 | for (i = 0; i < 3; ++i) {
|
---|
603 | if (i >= num_keys) {
|
---|
604 | prefix[i] = NULL;
|
---|
605 | local[i] = NULL;
|
---|
606 | } else {
|
---|
607 | const xmlChar *name = names[i];
|
---|
608 | const xmlChar *colon = BAD_CAST strchr((const char *) name, ':');
|
---|
609 |
|
---|
610 | if (colon == NULL) {
|
---|
611 | prefix[i] = NULL;
|
---|
612 | local[i] = name;
|
---|
613 | } else {
|
---|
614 | prefix[i] = xmlStrndup(name, colon - name);
|
---|
615 | local[i] = &colon[1];
|
---|
616 | }
|
---|
617 | }
|
---|
618 | }
|
---|
619 |
|
---|
620 | res = xmlHashQLookup3(hash, prefix[0], local[0], prefix[1], local[1],
|
---|
621 | prefix[2], local[2]);
|
---|
622 |
|
---|
623 | for (i = 0; i < 3; ++i)
|
---|
624 | xmlFree(prefix[i]);
|
---|
625 |
|
---|
626 | return res;
|
---|
627 | }
|
---|
628 |
|
---|
629 | static int
|
---|
630 | pool_bulk_lookup(StringPool *pool, xmlHashTablePtr hash, size_t num,
|
---|
631 | int existing) {
|
---|
632 | size_t i, j;
|
---|
633 | int ret = 0;
|
---|
634 |
|
---|
635 | for (i = pool->index, j = 0; i < pool->num_strings && j < num; j++) {
|
---|
636 | xmlChar **str = &pool->strings[i];
|
---|
637 | int q;
|
---|
638 |
|
---|
639 | for (q = 0; q < 2; q++) {
|
---|
640 | xmlChar *res = NULL;
|
---|
641 |
|
---|
642 | if (q) {
|
---|
643 | res = hash_qlookup(hash, str, pool->num_keys);
|
---|
644 | } else {
|
---|
645 | switch (pool->num_keys) {
|
---|
646 | case 1:
|
---|
647 | res = xmlHashLookup(hash, str[0]);
|
---|
648 | break;
|
---|
649 | case 2:
|
---|
650 | res = xmlHashLookup2(hash, str[0], str[1]);
|
---|
651 | break;
|
---|
652 | case 3:
|
---|
653 | res = xmlHashLookup3(hash, str[0], str[1], str[2]);
|
---|
654 | break;
|
---|
655 | }
|
---|
656 | }
|
---|
657 |
|
---|
658 | if (existing) {
|
---|
659 | if (res != str[0])
|
---|
660 | ret = -1;
|
---|
661 | } else {
|
---|
662 | if (res != NULL)
|
---|
663 | ret = -1;
|
---|
664 | }
|
---|
665 | }
|
---|
666 |
|
---|
667 | i += pool->num_keys;
|
---|
668 | }
|
---|
669 |
|
---|
670 | pool->index = i;
|
---|
671 | return ret;
|
---|
672 | }
|
---|
673 |
|
---|
674 | static int
|
---|
675 | pool_bulk_remove(StringPool *pool, xmlHashTablePtr hash, size_t num) {
|
---|
676 | size_t i, j;
|
---|
677 | int ret = 0;
|
---|
678 |
|
---|
679 | for (i = pool->index, j = 0; i < pool->num_strings && j < num; j++) {
|
---|
680 | xmlChar **str = &pool->strings[i];
|
---|
681 | int res = -1;
|
---|
682 |
|
---|
683 | switch (pool->num_keys) {
|
---|
684 | case 1:
|
---|
685 | res = xmlHashRemoveEntry(hash, str[0], NULL);
|
---|
686 | break;
|
---|
687 | case 2:
|
---|
688 | res = xmlHashRemoveEntry2(hash, str[0], str[1], NULL);
|
---|
689 | break;
|
---|
690 | case 3:
|
---|
691 | res = xmlHashRemoveEntry3(hash, str[0], str[1], str[2], NULL);
|
---|
692 | break;
|
---|
693 | }
|
---|
694 |
|
---|
695 | if (res != 0)
|
---|
696 | ret = -1;
|
---|
697 |
|
---|
698 | i += pool->num_keys;
|
---|
699 | }
|
---|
700 |
|
---|
701 | pool->index = i;
|
---|
702 | return ret;
|
---|
703 | }
|
---|
704 |
|
---|
705 | static int
|
---|
706 | test_hash(size_t num_entries, size_t num_keys, int use_dict) {
|
---|
707 | xmlDict *dict = NULL;
|
---|
708 | xmlHashTable *hash;
|
---|
709 | StringPool *pool1, *pool2;
|
---|
710 | int ret = 0;
|
---|
711 |
|
---|
712 | if (use_dict) {
|
---|
713 | dict = xmlDictCreate();
|
---|
714 | hash = xmlHashCreateDict(0, dict);
|
---|
715 | } else {
|
---|
716 | hash = xmlHashCreate(0);
|
---|
717 | }
|
---|
718 | pool1 = pool_new(num_entries, num_keys, '1');
|
---|
719 | pool2 = pool_new(num_entries, num_keys, '2');
|
---|
720 |
|
---|
721 | /* Insert all strings from pool2 and about half of pool1. */
|
---|
722 | while (!pool_done(pool2)) {
|
---|
723 | if (pool_bulk_insert(pool1, hash, my_rand(50)) != 0) {
|
---|
724 | fprintf(stderr, "pool1: hash insert failed\n");
|
---|
725 | ret = 1;
|
---|
726 | }
|
---|
727 | if (pool_bulk_insert(pool2, hash, my_rand(100)) != 0) {
|
---|
728 | fprintf(stderr, "pool1: hash insert failed\n");
|
---|
729 | ret = 1;
|
---|
730 | }
|
---|
731 | }
|
---|
732 |
|
---|
733 | /* Check existing entries */
|
---|
734 | pool_reset(pool2);
|
---|
735 | if (pool_bulk_lookup(pool2, hash, pool2->num_entries, 1) != 0) {
|
---|
736 | fprintf(stderr, "pool2: hash lookup failed\n");
|
---|
737 | ret = 1;
|
---|
738 | }
|
---|
739 |
|
---|
740 | /* Remove all strings from pool2 and insert the rest of pool1. */
|
---|
741 | pool_reset(pool2);
|
---|
742 | while (!pool_done(pool1) || !pool_done(pool2)) {
|
---|
743 | if (pool_bulk_insert(pool1, hash, my_rand(50)) != 0) {
|
---|
744 | fprintf(stderr, "pool1: hash insert failed\n");
|
---|
745 | ret = 1;
|
---|
746 | }
|
---|
747 | if (pool_bulk_remove(pool2, hash, my_rand(100)) != 0) {
|
---|
748 | fprintf(stderr, "pool2: hash remove failed\n");
|
---|
749 | ret = 1;
|
---|
750 | }
|
---|
751 | }
|
---|
752 |
|
---|
753 | /* Check existing entries */
|
---|
754 | pool_reset(pool1);
|
---|
755 | if (pool_bulk_lookup(pool1, hash, pool1->num_entries, 1) != 0) {
|
---|
756 | fprintf(stderr, "pool1: hash lookup failed\n");
|
---|
757 | ret = 1;
|
---|
758 | }
|
---|
759 |
|
---|
760 | /* Check removed entries */
|
---|
761 | pool_reset(pool2);
|
---|
762 | if (pool_bulk_lookup(pool2, hash, pool2->num_entries, 0) != 0) {
|
---|
763 | fprintf(stderr, "pool2: hash lookup succeeded unexpectedly\n");
|
---|
764 | ret = 1;
|
---|
765 | }
|
---|
766 |
|
---|
767 | pool_free(pool1);
|
---|
768 | pool_free(pool2);
|
---|
769 | xmlHashFree(hash, NULL);
|
---|
770 | xmlDictFree(dict);
|
---|
771 |
|
---|
772 | return ret;
|
---|
773 | }
|
---|
774 |
|
---|
775 | static int
|
---|
776 | testall_hash(void) {
|
---|
777 | size_t num_keys;
|
---|
778 |
|
---|
779 | for (num_keys = 1; num_keys <= 3; num_keys++) {
|
---|
780 | size_t num_strings;
|
---|
781 | size_t max_strings = num_keys == 1 ? 100000 : 1000;
|
---|
782 |
|
---|
783 | for (num_strings = 10; num_strings <= max_strings; num_strings *= 10) {
|
---|
784 | size_t reps, i;
|
---|
785 |
|
---|
786 | reps = 1000 / num_strings;
|
---|
787 | if (reps == 0)
|
---|
788 | reps = 1;
|
---|
789 |
|
---|
790 | for (i = 0; i < reps; i++) {
|
---|
791 | if (test_hash(num_strings, num_keys, /* use_dict */ 0) != 0)
|
---|
792 | return(1);
|
---|
793 | }
|
---|
794 |
|
---|
795 | if (test_hash(num_strings, num_keys, /* use_dict */ 1) != 0)
|
---|
796 | return(1);
|
---|
797 | }
|
---|
798 | }
|
---|
799 |
|
---|
800 | return(0);
|
---|
801 | }
|
---|
802 |
|
---|
803 |
|
---|
804 | /**** main ****/
|
---|
805 |
|
---|
806 | int
|
---|
807 | main(void) {
|
---|
808 | int ret = 0;
|
---|
809 |
|
---|
810 | LIBXML_TEST_VERSION
|
---|
811 |
|
---|
812 | if (testall_dict() != 0) {
|
---|
813 | fprintf(stderr, "dictionary tests failed\n");
|
---|
814 | ret = 1;
|
---|
815 | }
|
---|
816 | if (testall_hash() != 0) {
|
---|
817 | fprintf(stderr, "hash tests failed\n");
|
---|
818 | ret = 1;
|
---|
819 | }
|
---|
820 |
|
---|
821 | xmlCleanupParser();
|
---|
822 | return(ret);
|
---|
823 | }
|
---|