ReactOS  0.4.15-dev-1197-g8081ba9
dict.c
Go to the documentation of this file.
1 /*
2  * dict.c: dictionary of reusable strings, just used to avoid allocation
3  * and freeing operations.
4  *
5  * Copyright (C) 2003-2012 Daniel Veillard.
6  *
7  * Permission to use, copy, modify, and distribute this software for any
8  * purpose with or without fee is hereby granted, provided that the above
9  * copyright notice and this permission notice appear in all copies.
10  *
11  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
12  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
13  * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
14  * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
15  *
16  * Author: daniel@veillard.com
17  */
18 
19 #define IN_LIBXML
20 #include "libxml.h"
21 
22 #include <limits.h>
23 #ifdef HAVE_STDLIB_H
24 #include <stdlib.h>
25 #endif
26 #ifdef HAVE_TIME_H
27 #include <time.h>
28 #endif
29 
30 /*
31  * Following http://www.ocert.org/advisories/ocert-2011-003.html
32  * it seems that having hash randomization might be a good idea
33  * when using XML with untrusted data
34  * Note1: that it works correctly only if compiled with WITH_BIG_KEY
35  * which is the default.
36  * Note2: the fast function used for a small dict won't protect very
37  * well but since the attack is based on growing a very big hash
38  * list we will use the BigKey algo as soon as the hash size grows
39  * over MIN_DICT_SIZE so this actually works
40  */
41 #if defined(HAVE_RAND) && defined(HAVE_SRAND) && defined(HAVE_TIME) && \
42  !defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION)
43 #define DICT_RANDOMIZATION
44 #endif
45 
46 #include <string.h>
47 #ifdef HAVE_STDINT_H
48 #include <stdint.h>
49 #else
50 #ifdef HAVE_INTTYPES_H
51 #include <inttypes.h>
52 #elif defined(_WIN32)
53 typedef unsigned __int32 uint32_t;
54 #endif
55 #endif
56 #include <libxml/tree.h>
57 #include <libxml/dict.h>
58 #include <libxml/xmlmemory.h>
59 #include <libxml/xmlerror.h>
60 #include <libxml/globals.h>
61 
62 /* #define DEBUG_GROW */
63 /* #define DICT_DEBUG_PATTERNS */
64 
65 #define MAX_HASH_LEN 3
66 #define MIN_DICT_SIZE 128
67 #define MAX_DICT_HASH 8 * 2048
68 #define WITH_BIG_KEY
69 
70 #ifdef WITH_BIG_KEY
71 #define xmlDictComputeKey(dict, name, len) \
72  (((dict)->size == MIN_DICT_SIZE) ? \
73  xmlDictComputeFastKey(name, len, (dict)->seed) : \
74  xmlDictComputeBigKey(name, len, (dict)->seed))
75 
76 #define xmlDictComputeQKey(dict, prefix, plen, name, len) \
77  (((prefix) == NULL) ? \
78  (xmlDictComputeKey(dict, name, len)) : \
79  (((dict)->size == MIN_DICT_SIZE) ? \
80  xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed) : \
81  xmlDictComputeBigQKey(prefix, plen, name, len, (dict)->seed)))
82 
83 #else /* !WITH_BIG_KEY */
84 #define xmlDictComputeKey(dict, name, len) \
85  xmlDictComputeFastKey(name, len, (dict)->seed)
86 #define xmlDictComputeQKey(dict, prefix, plen, name, len) \
87  xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed)
88 #endif /* WITH_BIG_KEY */
89 
90 /*
91  * An entry in the dictionary
92  */
93 typedef struct _xmlDictEntry xmlDictEntry;
95 struct _xmlDictEntry {
97  const xmlChar *name;
98  unsigned int len;
99  int valid;
100  unsigned long okey;
101 };
102 
109  size_t size;
110  size_t nbStrings;
112 };
113 /*
114  * The entire dictionary
115  */
116 struct _xmlDict {
118 
120  size_t size;
121  unsigned int nbElems;
123 
124  struct _xmlDict *subdict;
125  /* used for randomization */
126  int seed;
127  /* used to impose a limit on size */
128  size_t limit;
129 };
130 
131 /*
132  * A mutex for modifying the reference counter for shared
133  * dictionaries.
134  */
136 
137 /*
138  * Whether the dictionary mutex was initialized.
139  */
140 static int xmlDictInitialized = 0;
141 
142 #ifdef DICT_RANDOMIZATION
143 #ifdef HAVE_RAND_R
144 /*
145  * Internal data for random function, protected by xmlDictMutex
146  */
147 static unsigned int rand_seed = 0;
148 #endif
149 #endif
150 
160 int xmlInitializeDict(void) {
161  return(0);
162 }
163 
177  if (xmlDictInitialized)
178  return(1);
179 
180  if ((xmlDictMutex = xmlNewRMutex()) == NULL)
181  return(0);
183 
184 #ifdef DICT_RANDOMIZATION
185 #ifdef HAVE_RAND_R
186  rand_seed = time(NULL);
187  rand_r(& rand_seed);
188 #else
189  srand(time(NULL));
190 #endif
191 #endif
192  xmlDictInitialized = 1;
194  return(1);
195 }
196 
197 #ifdef DICT_RANDOMIZATION
198 int __xmlRandom(void) {
199  int ret;
200 
201  if (xmlDictInitialized == 0)
203 
205 #ifdef HAVE_RAND_R
206  ret = rand_r(& rand_seed);
207 #else
208  ret = rand();
209 #endif
211  return(ret);
212 }
213 #endif
214 
221 void
223  if (!xmlDictInitialized)
224  return;
225 
227 
228  xmlDictInitialized = 0;
229 }
230 
231 /*
232  * xmlDictAddString:
233  * @dict: the dictionary
234  * @name: the name of the userdata
235  * @len: the length of the name
236  *
237  * Add the string to the array[s]
238  *
239  * Returns the pointer of the local string, or NULL in case of error.
240  */
241 static const xmlChar *
244  const xmlChar *ret;
245  size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
246  size_t limit = 0;
247 
248 #ifdef DICT_DEBUG_PATTERNS
249  fprintf(stderr, "-");
250 #endif
251  pool = dict->strings;
252  while (pool != NULL) {
253  if ((size_t)(pool->end - pool->free) > namelen)
254  goto found_pool;
255  if (pool->size > size) size = pool->size;
256  limit += pool->size;
257  pool = pool->next;
258  }
259  /*
260  * Not found, need to allocate
261  */
262  if (pool == NULL) {
263  if ((dict->limit > 0) && (limit > dict->limit)) {
264  return(NULL);
265  }
266 
267  if (size == 0) size = 1000;
268  else size *= 4; /* exponential growth */
269  if (size < 4 * namelen)
270  size = 4 * namelen; /* just in case ! */
272  if (pool == NULL)
273  return(NULL);
274  pool->size = size;
275  pool->nbStrings = 0;
276  pool->free = &pool->array[0];
277  pool->end = &pool->array[size];
278  pool->next = dict->strings;
279  dict->strings = pool;
280 #ifdef DICT_DEBUG_PATTERNS
281  fprintf(stderr, "+");
282 #endif
283  }
284 found_pool:
285  ret = pool->free;
286  memcpy(pool->free, name, namelen);
287  pool->free += namelen;
288  *(pool->free++) = 0;
289  pool->nbStrings++;
290  return(ret);
291 }
292 
293 /*
294  * xmlDictAddQString:
295  * @dict: the dictionary
296  * @prefix: the prefix of the userdata
297  * @plen: the prefix length
298  * @name: the name of the userdata
299  * @len: the length of the name
300  *
301  * Add the QName to the array[s]
302  *
303  * Returns the pointer of the local string, or NULL in case of error.
304  */
305 static const xmlChar *
306 xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, unsigned int plen,
307  const xmlChar *name, unsigned int namelen)
308 {
310  const xmlChar *ret;
311  size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
312  size_t limit = 0;
313 
314  if (prefix == NULL) return(xmlDictAddString(dict, name, namelen));
315 
316 #ifdef DICT_DEBUG_PATTERNS
317  fprintf(stderr, "=");
318 #endif
319  pool = dict->strings;
320  while (pool != NULL) {
321  if ((size_t)(pool->end - pool->free) > namelen + plen + 1)
322  goto found_pool;
323  if (pool->size > size) size = pool->size;
324  limit += pool->size;
325  pool = pool->next;
326  }
327  /*
328  * Not found, need to allocate
329  */
330  if (pool == NULL) {
331  if ((dict->limit > 0) && (limit > dict->limit)) {
332  return(NULL);
333  }
334 
335  if (size == 0) size = 1000;
336  else size *= 4; /* exponential growth */
337  if (size < 4 * (namelen + plen + 1))
338  size = 4 * (namelen + plen + 1); /* just in case ! */
340  if (pool == NULL)
341  return(NULL);
342  pool->size = size;
343  pool->nbStrings = 0;
344  pool->free = &pool->array[0];
345  pool->end = &pool->array[size];
346  pool->next = dict->strings;
347  dict->strings = pool;
348 #ifdef DICT_DEBUG_PATTERNS
349  fprintf(stderr, "+");
350 #endif
351  }
352 found_pool:
353  ret = pool->free;
354  memcpy(pool->free, prefix, plen);
355  pool->free += plen;
356  *(pool->free++) = ':';
357  memcpy(pool->free, name, namelen);
358  pool->free += namelen;
359  *(pool->free++) = 0;
360  pool->nbStrings++;
361  return(ret);
362 }
363 
364 #ifdef WITH_BIG_KEY
365 /*
366  * xmlDictComputeBigKey:
367  *
368  * Calculate a hash key using a good hash function that works well for
369  * larger hash table sizes.
370  *
371  * Hash function by "One-at-a-Time Hash" see
372  * http://burtleburtle.net/bob/hash/doobs.html
373  */
374 
375 #ifdef __clang__
376 ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow")
377 #endif
378 static uint32_t
380  uint32_t hash;
381  int i;
382 
383  if (namelen <= 0 || data == NULL) return(0);
384 
385  hash = seed;
386 
387  for (i = 0;i < namelen; i++) {
388  hash += data[i];
389  hash += (hash << 10);
390  hash ^= (hash >> 6);
391  }
392  hash += (hash << 3);
393  hash ^= (hash >> 11);
394  hash += (hash << 15);
395 
396  return hash;
397 }
398 
399 /*
400  * xmlDictComputeBigQKey:
401  *
402  * Calculate a hash key for two strings using a good hash function
403  * that works well for larger hash table sizes.
404  *
405  * Hash function by "One-at-a-Time Hash" see
406  * http://burtleburtle.net/bob/hash/doobs.html
407  *
408  * Neither of the two strings must be NULL.
409  */
410 #ifdef __clang__
411 ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow")
412 #endif
413 static unsigned long
414 xmlDictComputeBigQKey(const xmlChar *prefix, int plen,
415  const xmlChar *name, int len, int seed)
416 {
417  uint32_t hash;
418  int i;
419 
420  hash = seed;
421 
422  for (i = 0;i < plen; i++) {
423  hash += prefix[i];
424  hash += (hash << 10);
425  hash ^= (hash >> 6);
426  }
427  hash += ':';
428  hash += (hash << 10);
429  hash ^= (hash >> 6);
430 
431  for (i = 0;i < len; i++) {
432  hash += name[i];
433  hash += (hash << 10);
434  hash ^= (hash >> 6);
435  }
436  hash += (hash << 3);
437  hash ^= (hash >> 11);
438  hash += (hash << 15);
439 
440  return hash;
441 }
442 #endif /* WITH_BIG_KEY */
443 
444 /*
445  * xmlDictComputeFastKey:
446  *
447  * Calculate a hash key using a fast hash function that works well
448  * for low hash table fill.
449  */
450 static unsigned long
452  unsigned long value = seed;
453 
454  if (name == NULL) return(0);
455  value = *name;
456  value <<= 5;
457  if (namelen > 10) {
458  value += name[namelen - 1];
459  namelen = 10;
460  }
461  switch (namelen) {
462  case 10: value += name[9];
463  /* Falls through. */
464  case 9: value += name[8];
465  /* Falls through. */
466  case 8: value += name[7];
467  /* Falls through. */
468  case 7: value += name[6];
469  /* Falls through. */
470  case 6: value += name[5];
471  /* Falls through. */
472  case 5: value += name[4];
473  /* Falls through. */
474  case 4: value += name[3];
475  /* Falls through. */
476  case 3: value += name[2];
477  /* Falls through. */
478  case 2: value += name[1];
479  /* Falls through. */
480  default: break;
481  }
482  return(value);
483 }
484 
485 /*
486  * xmlDictComputeFastQKey:
487  *
488  * Calculate a hash key for two strings using a fast hash function
489  * that works well for low hash table fill.
490  *
491  * Neither of the two strings must be NULL.
492  */
493 static unsigned long
494 xmlDictComputeFastQKey(const xmlChar *prefix, int plen,
495  const xmlChar *name, int len, int seed)
496 {
497  unsigned long value = (unsigned long) seed;
498 
499  if (plen == 0)
500  value += 30 * (unsigned long) ':';
501  else
502  value += 30 * (*prefix);
503 
504  if (len > 10) {
505  int offset = len - (plen + 1 + 1);
506  if (offset < 0)
507  offset = len - (10 + 1);
508  value += name[offset];
509  len = 10;
510  if (plen > 10)
511  plen = 10;
512  }
513  switch (plen) {
514  case 10: value += prefix[9];
515  /* Falls through. */
516  case 9: value += prefix[8];
517  /* Falls through. */
518  case 8: value += prefix[7];
519  /* Falls through. */
520  case 7: value += prefix[6];
521  /* Falls through. */
522  case 6: value += prefix[5];
523  /* Falls through. */
524  case 5: value += prefix[4];
525  /* Falls through. */
526  case 4: value += prefix[3];
527  /* Falls through. */
528  case 3: value += prefix[2];
529  /* Falls through. */
530  case 2: value += prefix[1];
531  /* Falls through. */
532  case 1: value += prefix[0];
533  /* Falls through. */
534  default: break;
535  }
536  len -= plen;
537  if (len > 0) {
538  value += (unsigned long) ':';
539  len--;
540  }
541  switch (len) {
542  case 10: value += name[9];
543  /* Falls through. */
544  case 9: value += name[8];
545  /* Falls through. */
546  case 8: value += name[7];
547  /* Falls through. */
548  case 7: value += name[6];
549  /* Falls through. */
550  case 6: value += name[5];
551  /* Falls through. */
552  case 5: value += name[4];
553  /* Falls through. */
554  case 4: value += name[3];
555  /* Falls through. */
556  case 3: value += name[2];
557  /* Falls through. */
558  case 2: value += name[1];
559  /* Falls through. */
560  case 1: value += name[0];
561  /* Falls through. */
562  default: break;
563  }
564  return(value);
565 }
566 
577 
578  if (!xmlDictInitialized)
579  if (!__xmlInitializeDict())
580  return(NULL);
581 
582 #ifdef DICT_DEBUG_PATTERNS
583  fprintf(stderr, "C");
584 #endif
585 
586  dict = xmlMalloc(sizeof(xmlDict));
587  if (dict) {
588  dict->ref_counter = 1;
589  dict->limit = 0;
590 
591  dict->size = MIN_DICT_SIZE;
592  dict->nbElems = 0;
593  dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));
594  dict->strings = NULL;
595  dict->subdict = NULL;
596  if (dict->dict) {
597  memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
598 #ifdef DICT_RANDOMIZATION
599  dict->seed = __xmlRandom();
600 #else
601  dict->seed = 0;
602 #endif
603  return(dict);
604  }
605  xmlFree(dict);
606  }
607  return(NULL);
608 }
609 
624 
625  if ((dict != NULL) && (sub != NULL)) {
626 #ifdef DICT_DEBUG_PATTERNS
627  fprintf(stderr, "R");
628 #endif
629  dict->seed = sub->seed;
630  dict->subdict = sub;
631  xmlDictReference(dict->subdict);
632  }
633  return(dict);
634 }
635 
644 int
646  if (!xmlDictInitialized)
647  if (!__xmlInitializeDict())
648  return(-1);
649 
650  if (dict == NULL) return -1;
652  dict->ref_counter++;
654  return(0);
655 }
656 
666 static int
668  unsigned long key, okey;
669  size_t oldsize, i;
670  xmlDictEntryPtr iter, next;
671  struct _xmlDictEntry *olddict;
672 #ifdef DEBUG_GROW
673  unsigned long nbElem = 0;
674 #endif
675  int ret = 0;
676  int keep_keys = 1;
677 
678  if (dict == NULL)
679  return(-1);
680  if (size < 8)
681  return(-1);
682  if (size > 8 * 2048)
683  return(-1);
684 
685 #ifdef DICT_DEBUG_PATTERNS
686  fprintf(stderr, "*");
687 #endif
688 
689  oldsize = dict->size;
690  olddict = dict->dict;
691  if (olddict == NULL)
692  return(-1);
693  if (oldsize == MIN_DICT_SIZE)
694  keep_keys = 0;
695 
696  dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
697  if (dict->dict == NULL) {
698  dict->dict = olddict;
699  return(-1);
700  }
701  memset(dict->dict, 0, size * sizeof(xmlDictEntry));
702  dict->size = size;
703 
704  /* If the two loops are merged, there would be situations where
705  a new entry needs to allocated and data copied into it from
706  the main dict. It is nicer to run through the array twice, first
707  copying all the elements in the main array (less probability of
708  allocate) and then the rest, so we only free in the second loop.
709  */
710  for (i = 0; i < oldsize; i++) {
711  if (olddict[i].valid == 0)
712  continue;
713 
714  if (keep_keys)
715  okey = olddict[i].okey;
716  else
717  okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len);
718  key = okey % dict->size;
719 
720  if (dict->dict[key].valid == 0) {
721  memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));
722  dict->dict[key].next = NULL;
723  dict->dict[key].okey = okey;
724  } else {
726 
727  entry = xmlMalloc(sizeof(xmlDictEntry));
728  if (entry != NULL) {
729  entry->name = olddict[i].name;
730  entry->len = olddict[i].len;
731  entry->okey = okey;
732  entry->next = dict->dict[key].next;
733  entry->valid = 1;
734  dict->dict[key].next = entry;
735  } else {
736  /*
737  * we don't have much ways to alert from here
738  * result is losing an entry and unicity guarantee
739  */
740  ret = -1;
741  }
742  }
743 #ifdef DEBUG_GROW
744  nbElem++;
745 #endif
746  }
747 
748  for (i = 0; i < oldsize; i++) {
749  iter = olddict[i].next;
750  while (iter) {
751  next = iter->next;
752 
753  /*
754  * put back the entry in the new dict
755  */
756 
757  if (keep_keys)
758  okey = iter->okey;
759  else
760  okey = xmlDictComputeKey(dict, iter->name, iter->len);
761  key = okey % dict->size;
762  if (dict->dict[key].valid == 0) {
763  memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry));
764  dict->dict[key].next = NULL;
765  dict->dict[key].valid = 1;
766  dict->dict[key].okey = okey;
767  xmlFree(iter);
768  } else {
769  iter->next = dict->dict[key].next;
770  iter->okey = okey;
771  dict->dict[key].next = iter;
772  }
773 
774 #ifdef DEBUG_GROW
775  nbElem++;
776 #endif
777 
778  iter = next;
779  }
780  }
781 
782  xmlFree(olddict);
783 
784 #ifdef DEBUG_GROW
786  "xmlDictGrow : from %lu to %lu, %u elems\n", oldsize, size, nbElem);
787 #endif
788 
789  return(ret);
790 }
791 
799 void
801  size_t i;
802  xmlDictEntryPtr iter;
804  int inside_dict = 0;
805  xmlDictStringsPtr pool, nextp;
806 
807  if (dict == NULL)
808  return;
809 
810  if (!xmlDictInitialized)
811  if (!__xmlInitializeDict())
812  return;
813 
814  /* decrement the counter, it may be shared by a parser and docs */
816  dict->ref_counter--;
817  if (dict->ref_counter > 0) {
819  return;
820  }
821 
823 
824  if (dict->subdict != NULL) {
825  xmlDictFree(dict->subdict);
826  }
827 
828  if (dict->dict) {
829  for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) {
830  iter = &(dict->dict[i]);
831  if (iter->valid == 0)
832  continue;
833  inside_dict = 1;
834  while (iter) {
835  next = iter->next;
836  if (!inside_dict)
837  xmlFree(iter);
838  dict->nbElems--;
839  inside_dict = 0;
840  iter = next;
841  }
842  }
843  xmlFree(dict->dict);
844  }
845  pool = dict->strings;
846  while (pool != NULL) {
847  nextp = pool->next;
848  xmlFree(pool);
849  pool = nextp;
850  }
851  xmlFree(dict);
852 }
853 
864 const xmlChar *
866  unsigned long key, okey, nbi = 0;
869  const xmlChar *ret;
870  unsigned int l;
871 
872  if ((dict == NULL) || (name == NULL))
873  return(NULL);
874 
875  if (len < 0)
876  l = strlen((const char *) name);
877  else
878  l = len;
879 
880  if (((dict->limit > 0) && (l >= dict->limit)) ||
881  (l > INT_MAX / 2))
882  return(NULL);
883 
884  /*
885  * Check for duplicate and insertion location.
886  */
887  okey = xmlDictComputeKey(dict, name, l);
888  key = okey % dict->size;
889  if (dict->dict[key].valid == 0) {
890  insert = NULL;
891  } else {
892  for (insert = &(dict->dict[key]); insert->next != NULL;
893  insert = insert->next) {
894 #ifdef __GNUC__
895  if ((insert->okey == okey) && (insert->len == l)) {
896  if (!memcmp(insert->name, name, l))
897  return(insert->name);
898  }
899 #else
900  if ((insert->okey == okey) && (insert->len == l) &&
901  (!xmlStrncmp(insert->name, name, l)))
902  return(insert->name);
903 #endif
904  nbi++;
905  }
906 #ifdef __GNUC__
907  if ((insert->okey == okey) && (insert->len == l)) {
908  if (!memcmp(insert->name, name, l))
909  return(insert->name);
910  }
911 #else
912  if ((insert->okey == okey) && (insert->len == l) &&
913  (!xmlStrncmp(insert->name, name, l)))
914  return(insert->name);
915 #endif
916  }
917 
918  if (dict->subdict) {
919  unsigned long skey;
920 
921  /* we cannot always reuse the same okey for the subdict */
922  if (((dict->size == MIN_DICT_SIZE) &&
923  (dict->subdict->size != MIN_DICT_SIZE)) ||
924  ((dict->size != MIN_DICT_SIZE) &&
925  (dict->subdict->size == MIN_DICT_SIZE)))
926  skey = xmlDictComputeKey(dict->subdict, name, l);
927  else
928  skey = okey;
929 
930  key = skey % dict->subdict->size;
931  if (dict->subdict->dict[key].valid != 0) {
932  xmlDictEntryPtr tmp;
933 
934  for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
935  tmp = tmp->next) {
936 #ifdef __GNUC__
937  if ((tmp->okey == skey) && (tmp->len == l)) {
938  if (!memcmp(tmp->name, name, l))
939  return(tmp->name);
940  }
941 #else
942  if ((tmp->okey == skey) && (tmp->len == l) &&
943  (!xmlStrncmp(tmp->name, name, l)))
944  return(tmp->name);
945 #endif
946  nbi++;
947  }
948 #ifdef __GNUC__
949  if ((tmp->okey == skey) && (tmp->len == l)) {
950  if (!memcmp(tmp->name, name, l))
951  return(tmp->name);
952  }
953 #else
954  if ((tmp->okey == skey) && (tmp->len == l) &&
955  (!xmlStrncmp(tmp->name, name, l)))
956  return(tmp->name);
957 #endif
958  }
959  key = okey % dict->size;
960  }
961 
962  ret = xmlDictAddString(dict, name, l);
963  if (ret == NULL)
964  return(NULL);
965  if (insert == NULL) {
966  entry = &(dict->dict[key]);
967  } else {
968  entry = xmlMalloc(sizeof(xmlDictEntry));
969  if (entry == NULL)
970  return(NULL);
971  }
972  entry->name = ret;
973  entry->len = l;
974  entry->next = NULL;
975  entry->valid = 1;
976  entry->okey = okey;
977 
978 
979  if (insert != NULL)
980  insert->next = entry;
981 
982  dict->nbElems++;
983 
984  if ((nbi > MAX_HASH_LEN) &&
985  (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) {
986  if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0)
987  return(NULL);
988  }
989  /* Note that entry may have been freed at this point by xmlDictGrow */
990 
991  return(ret);
992 }
993 
1004 const xmlChar *
1006  unsigned long key, okey, nbi = 0;
1008  unsigned int l;
1009 
1010  if ((dict == NULL) || (name == NULL))
1011  return(NULL);
1012 
1013  if (len < 0)
1014  l = strlen((const char *) name);
1015  else
1016  l = len;
1017  if (((dict->limit > 0) && (l >= dict->limit)) ||
1018  (l > INT_MAX / 2))
1019  return(NULL);
1020 
1021  /*
1022  * Check for duplicate and insertion location.
1023  */
1024  okey = xmlDictComputeKey(dict, name, l);
1025  key = okey % dict->size;
1026  if (dict->dict[key].valid == 0) {
1027  insert = NULL;
1028  } else {
1029  for (insert = &(dict->dict[key]); insert->next != NULL;
1030  insert = insert->next) {
1031 #ifdef __GNUC__
1032  if ((insert->okey == okey) && (insert->len == l)) {
1033  if (!memcmp(insert->name, name, l))
1034  return(insert->name);
1035  }
1036 #else
1037  if ((insert->okey == okey) && (insert->len == l) &&
1038  (!xmlStrncmp(insert->name, name, l)))
1039  return(insert->name);
1040 #endif
1041  nbi++;
1042  }
1043 #ifdef __GNUC__
1044  if ((insert->okey == okey) && (insert->len == l)) {
1045  if (!memcmp(insert->name, name, l))
1046  return(insert->name);
1047  }
1048 #else
1049  if ((insert->okey == okey) && (insert->len == l) &&
1050  (!xmlStrncmp(insert->name, name, l)))
1051  return(insert->name);
1052 #endif
1053  }
1054 
1055  if (dict->subdict) {
1056  unsigned long skey;
1057 
1058  /* we cannot always reuse the same okey for the subdict */
1059  if (((dict->size == MIN_DICT_SIZE) &&
1060  (dict->subdict->size != MIN_DICT_SIZE)) ||
1061  ((dict->size != MIN_DICT_SIZE) &&
1062  (dict->subdict->size == MIN_DICT_SIZE)))
1063  skey = xmlDictComputeKey(dict->subdict, name, l);
1064  else
1065  skey = okey;
1066 
1067  key = skey % dict->subdict->size;
1068  if (dict->subdict->dict[key].valid != 0) {
1069  xmlDictEntryPtr tmp;
1070 
1071  for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1072  tmp = tmp->next) {
1073 #ifdef __GNUC__
1074  if ((tmp->okey == skey) && (tmp->len == l)) {
1075  if (!memcmp(tmp->name, name, l))
1076  return(tmp->name);
1077  }
1078 #else
1079  if ((tmp->okey == skey) && (tmp->len == l) &&
1080  (!xmlStrncmp(tmp->name, name, l)))
1081  return(tmp->name);
1082 #endif
1083  nbi++;
1084  }
1085 #ifdef __GNUC__
1086  if ((tmp->okey == skey) && (tmp->len == l)) {
1087  if (!memcmp(tmp->name, name, l))
1088  return(tmp->name);
1089  }
1090 #else
1091  if ((tmp->okey == skey) && (tmp->len == l) &&
1092  (!xmlStrncmp(tmp->name, name, l)))
1093  return(tmp->name);
1094 #endif
1095  }
1096  }
1097 
1098  /* not found */
1099  return(NULL);
1100 }
1101 
1112 const xmlChar *
1113 xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
1114  unsigned long okey, key, nbi = 0;
1117  const xmlChar *ret;
1118  unsigned int len, plen, l;
1119 
1120  if ((dict == NULL) || (name == NULL))
1121  return(NULL);
1122  if (prefix == NULL)
1123  return(xmlDictLookup(dict, name, -1));
1124 
1125  l = len = strlen((const char *) name);
1126  plen = strlen((const char *) prefix);
1127  len += 1 + plen;
1128 
1129  /*
1130  * Check for duplicate and insertion location.
1131  */
1132  okey = xmlDictComputeQKey(dict, prefix, plen, name, l);
1133  key = okey % dict->size;
1134  if (dict->dict[key].valid == 0) {
1135  insert = NULL;
1136  } else {
1137  for (insert = &(dict->dict[key]); insert->next != NULL;
1138  insert = insert->next) {
1139  if ((insert->okey == okey) && (insert->len == len) &&
1140  (xmlStrQEqual(prefix, name, insert->name)))
1141  return(insert->name);
1142  nbi++;
1143  }
1144  if ((insert->okey == okey) && (insert->len == len) &&
1145  (xmlStrQEqual(prefix, name, insert->name)))
1146  return(insert->name);
1147  }
1148 
1149  if (dict->subdict) {
1150  unsigned long skey;
1151 
1152  /* we cannot always reuse the same okey for the subdict */
1153  if (((dict->size == MIN_DICT_SIZE) &&
1154  (dict->subdict->size != MIN_DICT_SIZE)) ||
1155  ((dict->size != MIN_DICT_SIZE) &&
1156  (dict->subdict->size == MIN_DICT_SIZE)))
1157  skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l);
1158  else
1159  skey = okey;
1160 
1161  key = skey % dict->subdict->size;
1162  if (dict->subdict->dict[key].valid != 0) {
1163  xmlDictEntryPtr tmp;
1164  for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1165  tmp = tmp->next) {
1166  if ((tmp->okey == skey) && (tmp->len == len) &&
1167  (xmlStrQEqual(prefix, name, tmp->name)))
1168  return(tmp->name);
1169  nbi++;
1170  }
1171  if ((tmp->okey == skey) && (tmp->len == len) &&
1172  (xmlStrQEqual(prefix, name, tmp->name)))
1173  return(tmp->name);
1174  }
1175  key = okey % dict->size;
1176  }
1177 
1178  ret = xmlDictAddQString(dict, prefix, plen, name, l);
1179  if (ret == NULL)
1180  return(NULL);
1181  if (insert == NULL) {
1182  entry = &(dict->dict[key]);
1183  } else {
1184  entry = xmlMalloc(sizeof(xmlDictEntry));
1185  if (entry == NULL)
1186  return(NULL);
1187  }
1188  entry->name = ret;
1189  entry->len = len;
1190  entry->next = NULL;
1191  entry->valid = 1;
1192  entry->okey = okey;
1193 
1194  if (insert != NULL)
1195  insert->next = entry;
1196 
1197  dict->nbElems++;
1198 
1199  if ((nbi > MAX_HASH_LEN) &&
1200  (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
1201  xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
1202  /* Note that entry may have been freed at this point by xmlDictGrow */
1203 
1204  return(ret);
1205 }
1206 
1217 int
1220 
1221  if ((dict == NULL) || (str == NULL))
1222  return(-1);
1223  pool = dict->strings;
1224  while (pool != NULL) {
1225  if ((str >= &pool->array[0]) && (str <= pool->free))
1226  return(1);
1227  pool = pool->next;
1228  }
1229  if (dict->subdict)
1230  return(xmlDictOwns(dict->subdict, str));
1231  return(0);
1232 }
1233 
1243 int
1245  if (dict == NULL)
1246  return(-1);
1247  if (dict->subdict)
1248  return(dict->nbElems + dict->subdict->nbElems);
1249  return(dict->nbElems);
1250 }
1251 
1262 size_t
1264  size_t ret;
1265 
1266  if (dict == NULL)
1267  return(0);
1268  ret = dict->limit;
1269  dict->limit = limit;
1270  return(ret);
1271 }
1272 
1282 size_t
1285  size_t limit = 0;
1286 
1287  if (dict == NULL)
1288  return(0);
1289  pool = dict->strings;
1290  while (pool != NULL) {
1291  limit += pool->size;
1292  pool = pool->next;
1293  }
1294  return(limit);
1295 }
1296 
1297 #define bottom_dict
1298 #include "elfgcchack.h"
int valid
Definition: dict.c:99
static int xmlDictGrow(xmlDictPtr dict, size_t size)
Definition: dict.c:667
xmlChar * end
Definition: dict.c:108
XMLPUBFUN xmlRMutexPtr XMLCALL xmlNewRMutex(void)
Definition: threads.c:285
static unsigned long xmlDictComputeFastKey(const xmlChar *name, int namelen, int seed)
Definition: dict.c:451
int memcmp(void *Buffer1, void *Buffer2, ACPI_SIZE Count)
Definition: utclib.c:112
#define INT_MAX
Definition: limits.h:40
XMLPUBFUN void XMLCALL xmlRMutexLock(xmlRMutexPtr tok)
Definition: threads.c:343
size_t xmlDictSetLimit(xmlDictPtr dict, size_t limit)
Definition: dict.c:1263
ACPI_SIZE strlen(const char *String)
Definition: utclib.c:269
#define xmlDictComputeQKey(dict, prefix, plen, name, len)
Definition: dict.c:76
#define MAX_DICT_HASH
Definition: dict.c:67
#define free
Definition: debug_ros.c:5
xmlDictStringsPtr next
Definition: dict.c:106
GLintptr offset
Definition: glext.h:5920
void __cdecl srand(_In_ unsigned int _Seed)
static int xmlDictInitialized
Definition: dict.c:140
static int insert
Definition: xmllint.c:144
xmlDictEntry * xmlDictEntryPtr
Definition: dict.c:94
__u16 time
Definition: mkdosfs.c:366
xmlDictPtr xmlDictCreateSub(xmlDictPtr sub)
Definition: dict.c:622
GLint namelen
Definition: glext.h:7232
void xmlDictCleanup(void)
Definition: dict.c:222
int xmlInitializeDict(void)
Definition: dict.c:160
int ref_counter
Definition: dict.c:117
XMLPUBFUN int XMLCALL xmlStrQEqual(const xmlChar *pref, const xmlChar *name, const xmlChar *str)
Definition: xmlstring.c:179
GLint limit
Definition: glext.h:10326
struct _xmlDictEntry * dict
Definition: dict.c:119
#define ATTRIBUTE_NO_SANITIZE(arg)
Definition: libxml.h:79
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
void xmlDictFree(xmlDictPtr dict)
Definition: dict.c:800
int hash
Definition: main.c:58
int __xmlRandom(void)
Definition: dict.c:198
static const xmlChar * xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, unsigned int plen, const xmlChar *name, unsigned int namelen)
Definition: dict.c:306
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
_Check_return_ int __cdecl rand(void)
Definition: rand.c:10
size_t xmlDictGetUsage(xmlDictPtr dict)
Definition: dict.c:1283
xmlDictPtr xmlDictCreate(void)
Definition: dict.c:575
struct _xmlDict * subdict
Definition: dict.c:124
XMLPUBVAR xmlGenericErrorFunc xmlGenericError
Definition: globals.h:346
const WCHAR * str
xmlChar * free
Definition: dict.c:107
const xmlChar * xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len)
Definition: dict.c:1005
smooth NULL
Definition: ftsmooth.c:416
xmlDictStrings * xmlDictStringsPtr
Definition: dict.c:104
Definition: dict.c:116
r l[0]
Definition: byte_order.h:167
const xmlChar * xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len)
Definition: dict.c:865
static xmlRMutexPtr xmlDictMutex
Definition: dict.c:135
GLsizeiptr size
Definition: glext.h:5919
int __xmlInitializeDict(void)
Definition: dict.c:176
XMLPUBVAR xmlFreeFunc xmlFree
Definition: globals.h:250
XMLPUBFUN void XMLCALL xmlRMutexUnlock(xmlRMutexPtr tok)
Definition: threads.c:388
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
int ret
struct _xmlDictEntry * next
Definition: dict.c:96
HKEY key
Definition: reg.c:42
uint32_t entry
Definition: isohybrid.c:63
unsigned char xmlChar
Definition: xmlstring.h:28
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
GLenum GLsizei len
Definition: glext.h:6722
XMLPUBFUN int XMLCALL xmlStrncmp(const xmlChar *str1, const xmlChar *str2, int len)
Definition: xmlstring.c:206
#define MIN_DICT_SIZE
Definition: dict.c:66
const xmlChar * xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name)
Definition: dict.c:1113
size_t limit
Definition: dict.c:128
size_t nbStrings
Definition: dict.c:110
static unsigned __int64 next
Definition: rand_nt.c:6
int seed
Definition: dict.c:126
static const xmlChar * xmlDictAddString(xmlDictPtr dict, const xmlChar *name, unsigned int namelen)
Definition: dict.c:242
#define __int32
Definition: basetyps.h:19
unsigned int len
Definition: dict.c:98
unsigned int nbElems
Definition: dict.c:121
#define MAX_HASH_LEN
Definition: dict.c:65
#define long
Definition: qsort.c:33
static unsigned long xmlDictComputeBigQKey(const xmlChar *prefix, int plen, const xmlChar *name, int len, int seed)
Definition: dict.c:414
XMLPUBVAR xmlMallocFunc xmlMalloc
Definition: globals.h:247
UINT32 uint32_t
Definition: types.h:75
Definition: name.c:38
int xmlDictSize(xmlDictPtr dict)
Definition: dict.c:1244
FILE * stderr
const xmlChar * name
Definition: dict.c:97
size_t size
Definition: dict.c:109
#define uint32_t
Definition: nsiface.idl:61
static unsigned long xmlDictComputeFastQKey(const xmlChar *prefix, int plen, const xmlChar *name, int len, int seed)
Definition: dict.c:494
Definition: _hash_fun.h:40
#define memset(x, y, z)
Definition: compat.h:39
XMLPUBFUN void XMLCALL xmlFreeRMutex(xmlRMutexPtr tok)
Definition: threads.c:319
#define xmlDictComputeKey(dict, name, len)
Definition: dict.c:71
size_t size
Definition: dict.c:120
unsigned long okey
Definition: dict.c:100
int xmlDictReference(xmlDictPtr dict)
Definition: dict.c:645
Definition: path.c:41
static uint32_t xmlDictComputeBigKey(const xmlChar *data, int namelen, int seed)
Definition: dict.c:379
XMLPUBVAR void * xmlGenericErrorContext
Definition: globals.h:362
int xmlDictOwns(xmlDictPtr dict, const xmlChar *str)
Definition: dict.c:1218
xmlDictStringsPtr strings
Definition: dict.c:122
GLuint const GLchar * name
Definition: glext.h:6031