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