ReactOS  0.4.14-dev-41-g31d7680
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 #define DICT_RANDOMIZATION
43 #endif
44 
45 #include <string.h>
46 #ifdef HAVE_STDINT_H
47 #include <stdint.h>
48 #else
49 #ifdef HAVE_INTTYPES_H
50 #include <inttypes.h>
51 #elif defined(_WIN32)
52 typedef unsigned __int32 uint32_t;
53 #endif
54 #endif
55 #include <libxml/tree.h>
56 #include <libxml/dict.h>
57 #include <libxml/xmlmemory.h>
58 #include <libxml/xmlerror.h>
59 #include <libxml/globals.h>
60 
61 /* #define DEBUG_GROW */
62 /* #define DICT_DEBUG_PATTERNS */
63 
64 #define MAX_HASH_LEN 3
65 #define MIN_DICT_SIZE 128
66 #define MAX_DICT_HASH 8 * 2048
67 #define WITH_BIG_KEY
68 
69 #ifdef WITH_BIG_KEY
70 #define xmlDictComputeKey(dict, name, len) \
71  (((dict)->size == MIN_DICT_SIZE) ? \
72  xmlDictComputeFastKey(name, len, (dict)->seed) : \
73  xmlDictComputeBigKey(name, len, (dict)->seed))
74 
75 #define xmlDictComputeQKey(dict, prefix, plen, name, len) \
76  (((prefix) == NULL) ? \
77  (xmlDictComputeKey(dict, name, len)) : \
78  (((dict)->size == MIN_DICT_SIZE) ? \
79  xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed) : \
80  xmlDictComputeBigQKey(prefix, plen, name, len, (dict)->seed)))
81 
82 #else /* !WITH_BIG_KEY */
83 #define xmlDictComputeKey(dict, name, len) \
84  xmlDictComputeFastKey(name, len, (dict)->seed)
85 #define xmlDictComputeQKey(dict, prefix, plen, name, len) \
86  xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed)
87 #endif /* WITH_BIG_KEY */
88 
89 /*
90  * An entry in the dictionary
91  */
92 typedef struct _xmlDictEntry xmlDictEntry;
94 struct _xmlDictEntry {
96  const xmlChar *name;
97  unsigned int len;
98  int valid;
99  unsigned long okey;
100 };
101 
108  size_t size;
109  size_t nbStrings;
111 };
112 /*
113  * The entire dictionary
114  */
115 struct _xmlDict {
117 
119  size_t size;
120  unsigned int nbElems;
122 
123  struct _xmlDict *subdict;
124  /* used for randomization */
125  int seed;
126  /* used to impose a limit on size */
127  size_t limit;
128 };
129 
130 /*
131  * A mutex for modifying the reference counter for shared
132  * dictionaries.
133  */
135 
136 /*
137  * Whether the dictionary mutex was initialized.
138  */
139 static int xmlDictInitialized = 0;
140 
141 #ifdef DICT_RANDOMIZATION
142 #ifdef HAVE_RAND_R
143 /*
144  * Internal data for random function, protected by xmlDictMutex
145  */
146 static unsigned int rand_seed = 0;
147 #endif
148 #endif
149 
159 int xmlInitializeDict(void) {
160  return(0);
161 }
162 
176  if (xmlDictInitialized)
177  return(1);
178 
179  if ((xmlDictMutex = xmlNewRMutex()) == NULL)
180  return(0);
182 
183 #ifdef DICT_RANDOMIZATION
184 #ifdef HAVE_RAND_R
185  rand_seed = time(NULL);
186  rand_r(& rand_seed);
187 #else
188  srand(time(NULL));
189 #endif
190 #endif
191  xmlDictInitialized = 1;
193  return(1);
194 }
195 
196 #ifdef DICT_RANDOMIZATION
197 int __xmlRandom(void) {
198  int ret;
199 
200  if (xmlDictInitialized == 0)
202 
204 #ifdef HAVE_RAND_R
205  ret = rand_r(& rand_seed);
206 #else
207  ret = rand();
208 #endif
210  return(ret);
211 }
212 #endif
213 
220 void
222  if (!xmlDictInitialized)
223  return;
224 
226 
227  xmlDictInitialized = 0;
228 }
229 
230 /*
231  * xmlDictAddString:
232  * @dict: the dictionary
233  * @name: the name of the userdata
234  * @len: the length of the name
235  *
236  * Add the string to the array[s]
237  *
238  * Returns the pointer of the local string, or NULL in case of error.
239  */
240 static const xmlChar *
243  const xmlChar *ret;
244  size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
245  size_t limit = 0;
246 
247 #ifdef DICT_DEBUG_PATTERNS
248  fprintf(stderr, "-");
249 #endif
250  pool = dict->strings;
251  while (pool != NULL) {
252  if ((size_t)(pool->end - pool->free) > namelen)
253  goto found_pool;
254  if (pool->size > size) size = pool->size;
255  limit += pool->size;
256  pool = pool->next;
257  }
258  /*
259  * Not found, need to allocate
260  */
261  if (pool == NULL) {
262  if ((dict->limit > 0) && (limit > dict->limit)) {
263  return(NULL);
264  }
265 
266  if (size == 0) size = 1000;
267  else size *= 4; /* exponential growth */
268  if (size < 4 * namelen)
269  size = 4 * namelen; /* just in case ! */
271  if (pool == NULL)
272  return(NULL);
273  pool->size = size;
274  pool->nbStrings = 0;
275  pool->free = &pool->array[0];
276  pool->end = &pool->array[size];
277  pool->next = dict->strings;
278  dict->strings = pool;
279 #ifdef DICT_DEBUG_PATTERNS
280  fprintf(stderr, "+");
281 #endif
282  }
283 found_pool:
284  ret = pool->free;
285  memcpy(pool->free, name, namelen);
286  pool->free += namelen;
287  *(pool->free++) = 0;
288  pool->nbStrings++;
289  return(ret);
290 }
291 
292 /*
293  * xmlDictAddQString:
294  * @dict: the dictionary
295  * @prefix: the prefix of the userdata
296  * @plen: the prefix length
297  * @name: the name of the userdata
298  * @len: the length of the name
299  *
300  * Add the QName to the array[s]
301  *
302  * Returns the pointer of the local string, or NULL in case of error.
303  */
304 static const xmlChar *
305 xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, unsigned int plen,
306  const xmlChar *name, unsigned int namelen)
307 {
309  const xmlChar *ret;
310  size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
311  size_t limit = 0;
312 
313  if (prefix == NULL) return(xmlDictAddString(dict, name, namelen));
314 
315 #ifdef DICT_DEBUG_PATTERNS
316  fprintf(stderr, "=");
317 #endif
318  pool = dict->strings;
319  while (pool != NULL) {
320  if ((size_t)(pool->end - pool->free) > namelen + plen + 1)
321  goto found_pool;
322  if (pool->size > size) size = pool->size;
323  limit += pool->size;
324  pool = pool->next;
325  }
326  /*
327  * Not found, need to allocate
328  */
329  if (pool == NULL) {
330  if ((dict->limit > 0) && (limit > dict->limit)) {
331  return(NULL);
332  }
333 
334  if (size == 0) size = 1000;
335  else size *= 4; /* exponential growth */
336  if (size < 4 * (namelen + plen + 1))
337  size = 4 * (namelen + plen + 1); /* just in case ! */
339  if (pool == NULL)
340  return(NULL);
341  pool->size = size;
342  pool->nbStrings = 0;
343  pool->free = &pool->array[0];
344  pool->end = &pool->array[size];
345  pool->next = dict->strings;
346  dict->strings = pool;
347 #ifdef DICT_DEBUG_PATTERNS
348  fprintf(stderr, "+");
349 #endif
350  }
351 found_pool:
352  ret = pool->free;
353  memcpy(pool->free, prefix, plen);
354  pool->free += plen;
355  *(pool->free++) = ':';
356  memcpy(pool->free, name, namelen);
357  pool->free += namelen;
358  *(pool->free++) = 0;
359  pool->nbStrings++;
360  return(ret);
361 }
362 
363 #ifdef WITH_BIG_KEY
364 /*
365  * xmlDictComputeBigKey:
366  *
367  * Calculate a hash key using a good hash function that works well for
368  * larger hash table sizes.
369  *
370  * Hash function by "One-at-a-Time Hash" see
371  * http://burtleburtle.net/bob/hash/doobs.html
372  */
373 
374 static uint32_t
376  uint32_t hash;
377  int i;
378 
379  if (namelen <= 0 || data == NULL) return(0);
380 
381  hash = seed;
382 
383  for (i = 0;i < namelen; i++) {
384  hash += data[i];
385  hash += (hash << 10);
386  hash ^= (hash >> 6);
387  }
388  hash += (hash << 3);
389  hash ^= (hash >> 11);
390  hash += (hash << 15);
391 
392  return hash;
393 }
394 
395 /*
396  * xmlDictComputeBigQKey:
397  *
398  * Calculate a hash key for two strings using a good hash function
399  * that works well for larger hash table sizes.
400  *
401  * Hash function by "One-at-a-Time Hash" see
402  * http://burtleburtle.net/bob/hash/doobs.html
403  *
404  * Neither of the two strings must be NULL.
405  */
406 static unsigned long
407 xmlDictComputeBigQKey(const xmlChar *prefix, int plen,
408  const xmlChar *name, int len, int seed)
409 {
410  uint32_t hash;
411  int i;
412 
413  hash = seed;
414 
415  for (i = 0;i < plen; i++) {
416  hash += prefix[i];
417  hash += (hash << 10);
418  hash ^= (hash >> 6);
419  }
420  hash += ':';
421  hash += (hash << 10);
422  hash ^= (hash >> 6);
423 
424  for (i = 0;i < len; i++) {
425  hash += name[i];
426  hash += (hash << 10);
427  hash ^= (hash >> 6);
428  }
429  hash += (hash << 3);
430  hash ^= (hash >> 11);
431  hash += (hash << 15);
432 
433  return hash;
434 }
435 #endif /* WITH_BIG_KEY */
436 
437 /*
438  * xmlDictComputeFastKey:
439  *
440  * Calculate a hash key using a fast hash function that works well
441  * for low hash table fill.
442  */
443 static unsigned long
445  unsigned long value = seed;
446 
447  if (name == NULL) return(0);
448  value = *name;
449  value <<= 5;
450  if (namelen > 10) {
451  value += name[namelen - 1];
452  namelen = 10;
453  }
454  switch (namelen) {
455  case 10: value += name[9];
456  /* Falls through. */
457  case 9: value += name[8];
458  /* Falls through. */
459  case 8: value += name[7];
460  /* Falls through. */
461  case 7: value += name[6];
462  /* Falls through. */
463  case 6: value += name[5];
464  /* Falls through. */
465  case 5: value += name[4];
466  /* Falls through. */
467  case 4: value += name[3];
468  /* Falls through. */
469  case 3: value += name[2];
470  /* Falls through. */
471  case 2: value += name[1];
472  /* Falls through. */
473  default: break;
474  }
475  return(value);
476 }
477 
478 /*
479  * xmlDictComputeFastQKey:
480  *
481  * Calculate a hash key for two strings using a fast hash function
482  * that works well for low hash table fill.
483  *
484  * Neither of the two strings must be NULL.
485  */
486 static unsigned long
487 xmlDictComputeFastQKey(const xmlChar *prefix, int plen,
488  const xmlChar *name, int len, int seed)
489 {
490  unsigned long value = (unsigned long) seed;
491 
492  if (plen == 0)
493  value += 30 * (unsigned long) ':';
494  else
495  value += 30 * (*prefix);
496 
497  if (len > 10) {
498  int offset = len - (plen + 1 + 1);
499  if (offset < 0)
500  offset = len - (10 + 1);
501  value += name[offset];
502  len = 10;
503  if (plen > 10)
504  plen = 10;
505  }
506  switch (plen) {
507  case 10: value += prefix[9];
508  /* Falls through. */
509  case 9: value += prefix[8];
510  /* Falls through. */
511  case 8: value += prefix[7];
512  /* Falls through. */
513  case 7: value += prefix[6];
514  /* Falls through. */
515  case 6: value += prefix[5];
516  /* Falls through. */
517  case 5: value += prefix[4];
518  /* Falls through. */
519  case 4: value += prefix[3];
520  /* Falls through. */
521  case 3: value += prefix[2];
522  /* Falls through. */
523  case 2: value += prefix[1];
524  /* Falls through. */
525  case 1: value += prefix[0];
526  /* Falls through. */
527  default: break;
528  }
529  len -= plen;
530  if (len > 0) {
531  value += (unsigned long) ':';
532  len--;
533  }
534  switch (len) {
535  case 10: value += name[9];
536  /* Falls through. */
537  case 9: value += name[8];
538  /* Falls through. */
539  case 8: value += name[7];
540  /* Falls through. */
541  case 7: value += name[6];
542  /* Falls through. */
543  case 6: value += name[5];
544  /* Falls through. */
545  case 5: value += name[4];
546  /* Falls through. */
547  case 4: value += name[3];
548  /* Falls through. */
549  case 3: value += name[2];
550  /* Falls through. */
551  case 2: value += name[1];
552  /* Falls through. */
553  case 1: value += name[0];
554  /* Falls through. */
555  default: break;
556  }
557  return(value);
558 }
559 
570 
571  if (!xmlDictInitialized)
572  if (!__xmlInitializeDict())
573  return(NULL);
574 
575 #ifdef DICT_DEBUG_PATTERNS
576  fprintf(stderr, "C");
577 #endif
578 
579  dict = xmlMalloc(sizeof(xmlDict));
580  if (dict) {
581  dict->ref_counter = 1;
582  dict->limit = 0;
583 
584  dict->size = MIN_DICT_SIZE;
585  dict->nbElems = 0;
586  dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));
587  dict->strings = NULL;
588  dict->subdict = NULL;
589  if (dict->dict) {
590  memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
591 #ifdef DICT_RANDOMIZATION
592  dict->seed = __xmlRandom();
593 #else
594  dict->seed = 0;
595 #endif
596  return(dict);
597  }
598  xmlFree(dict);
599  }
600  return(NULL);
601 }
602 
617 
618  if ((dict != NULL) && (sub != NULL)) {
619 #ifdef DICT_DEBUG_PATTERNS
620  fprintf(stderr, "R");
621 #endif
622  dict->seed = sub->seed;
623  dict->subdict = sub;
624  xmlDictReference(dict->subdict);
625  }
626  return(dict);
627 }
628 
637 int
639  if (!xmlDictInitialized)
640  if (!__xmlInitializeDict())
641  return(-1);
642 
643  if (dict == NULL) return -1;
645  dict->ref_counter++;
647  return(0);
648 }
649 
659 static int
661  unsigned long key, okey;
662  size_t oldsize, i;
663  xmlDictEntryPtr iter, next;
664  struct _xmlDictEntry *olddict;
665 #ifdef DEBUG_GROW
666  unsigned long nbElem = 0;
667 #endif
668  int ret = 0;
669  int keep_keys = 1;
670 
671  if (dict == NULL)
672  return(-1);
673  if (size < 8)
674  return(-1);
675  if (size > 8 * 2048)
676  return(-1);
677 
678 #ifdef DICT_DEBUG_PATTERNS
679  fprintf(stderr, "*");
680 #endif
681 
682  oldsize = dict->size;
683  olddict = dict->dict;
684  if (olddict == NULL)
685  return(-1);
686  if (oldsize == MIN_DICT_SIZE)
687  keep_keys = 0;
688 
689  dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
690  if (dict->dict == NULL) {
691  dict->dict = olddict;
692  return(-1);
693  }
694  memset(dict->dict, 0, size * sizeof(xmlDictEntry));
695  dict->size = size;
696 
697  /* If the two loops are merged, there would be situations where
698  a new entry needs to allocated and data copied into it from
699  the main dict. It is nicer to run through the array twice, first
700  copying all the elements in the main array (less probability of
701  allocate) and then the rest, so we only free in the second loop.
702  */
703  for (i = 0; i < oldsize; i++) {
704  if (olddict[i].valid == 0)
705  continue;
706 
707  if (keep_keys)
708  okey = olddict[i].okey;
709  else
710  okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len);
711  key = okey % dict->size;
712 
713  if (dict->dict[key].valid == 0) {
714  memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));
715  dict->dict[key].next = NULL;
716  dict->dict[key].okey = okey;
717  } else {
719 
720  entry = xmlMalloc(sizeof(xmlDictEntry));
721  if (entry != NULL) {
722  entry->name = olddict[i].name;
723  entry->len = olddict[i].len;
724  entry->okey = okey;
725  entry->next = dict->dict[key].next;
726  entry->valid = 1;
727  dict->dict[key].next = entry;
728  } else {
729  /*
730  * we don't have much ways to alert from herei
731  * result is losing an entry and unicity guarantee
732  */
733  ret = -1;
734  }
735  }
736 #ifdef DEBUG_GROW
737  nbElem++;
738 #endif
739  }
740 
741  for (i = 0; i < oldsize; i++) {
742  iter = olddict[i].next;
743  while (iter) {
744  next = iter->next;
745 
746  /*
747  * put back the entry in the new dict
748  */
749 
750  if (keep_keys)
751  okey = iter->okey;
752  else
753  okey = xmlDictComputeKey(dict, iter->name, iter->len);
754  key = okey % dict->size;
755  if (dict->dict[key].valid == 0) {
756  memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry));
757  dict->dict[key].next = NULL;
758  dict->dict[key].valid = 1;
759  dict->dict[key].okey = okey;
760  xmlFree(iter);
761  } else {
762  iter->next = dict->dict[key].next;
763  iter->okey = okey;
764  dict->dict[key].next = iter;
765  }
766 
767 #ifdef DEBUG_GROW
768  nbElem++;
769 #endif
770 
771  iter = next;
772  }
773  }
774 
775  xmlFree(olddict);
776 
777 #ifdef DEBUG_GROW
779  "xmlDictGrow : from %lu to %lu, %u elems\n", oldsize, size, nbElem);
780 #endif
781 
782  return(ret);
783 }
784 
792 void
794  size_t i;
795  xmlDictEntryPtr iter;
797  int inside_dict = 0;
798  xmlDictStringsPtr pool, nextp;
799 
800  if (dict == NULL)
801  return;
802 
803  if (!xmlDictInitialized)
804  if (!__xmlInitializeDict())
805  return;
806 
807  /* decrement the counter, it may be shared by a parser and docs */
809  dict->ref_counter--;
810  if (dict->ref_counter > 0) {
812  return;
813  }
814 
816 
817  if (dict->subdict != NULL) {
818  xmlDictFree(dict->subdict);
819  }
820 
821  if (dict->dict) {
822  for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) {
823  iter = &(dict->dict[i]);
824  if (iter->valid == 0)
825  continue;
826  inside_dict = 1;
827  while (iter) {
828  next = iter->next;
829  if (!inside_dict)
830  xmlFree(iter);
831  dict->nbElems--;
832  inside_dict = 0;
833  iter = next;
834  }
835  }
836  xmlFree(dict->dict);
837  }
838  pool = dict->strings;
839  while (pool != NULL) {
840  nextp = pool->next;
841  xmlFree(pool);
842  pool = nextp;
843  }
844  xmlFree(dict);
845 }
846 
857 const xmlChar *
859  unsigned long key, okey, nbi = 0;
862  const xmlChar *ret;
863  unsigned int l;
864 
865  if ((dict == NULL) || (name == NULL))
866  return(NULL);
867 
868  if (len < 0)
869  l = strlen((const char *) name);
870  else
871  l = len;
872 
873  if (((dict->limit > 0) && (l >= dict->limit)) ||
874  (l > INT_MAX / 2))
875  return(NULL);
876 
877  /*
878  * Check for duplicate and insertion location.
879  */
880  okey = xmlDictComputeKey(dict, name, l);
881  key = okey % dict->size;
882  if (dict->dict[key].valid == 0) {
883  insert = NULL;
884  } else {
885  for (insert = &(dict->dict[key]); insert->next != NULL;
886  insert = insert->next) {
887 #ifdef __GNUC__
888  if ((insert->okey == okey) && (insert->len == l)) {
889  if (!memcmp(insert->name, name, l))
890  return(insert->name);
891  }
892 #else
893  if ((insert->okey == okey) && (insert->len == l) &&
894  (!xmlStrncmp(insert->name, name, l)))
895  return(insert->name);
896 #endif
897  nbi++;
898  }
899 #ifdef __GNUC__
900  if ((insert->okey == okey) && (insert->len == l)) {
901  if (!memcmp(insert->name, name, l))
902  return(insert->name);
903  }
904 #else
905  if ((insert->okey == okey) && (insert->len == l) &&
906  (!xmlStrncmp(insert->name, name, l)))
907  return(insert->name);
908 #endif
909  }
910 
911  if (dict->subdict) {
912  unsigned long skey;
913 
914  /* we cannot always reuse the same okey for the subdict */
915  if (((dict->size == MIN_DICT_SIZE) &&
916  (dict->subdict->size != MIN_DICT_SIZE)) ||
917  ((dict->size != MIN_DICT_SIZE) &&
918  (dict->subdict->size == MIN_DICT_SIZE)))
919  skey = xmlDictComputeKey(dict->subdict, name, l);
920  else
921  skey = okey;
922 
923  key = skey % dict->subdict->size;
924  if (dict->subdict->dict[key].valid != 0) {
925  xmlDictEntryPtr tmp;
926 
927  for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
928  tmp = tmp->next) {
929 #ifdef __GNUC__
930  if ((tmp->okey == skey) && (tmp->len == l)) {
931  if (!memcmp(tmp->name, name, l))
932  return(tmp->name);
933  }
934 #else
935  if ((tmp->okey == skey) && (tmp->len == l) &&
936  (!xmlStrncmp(tmp->name, name, l)))
937  return(tmp->name);
938 #endif
939  nbi++;
940  }
941 #ifdef __GNUC__
942  if ((tmp->okey == skey) && (tmp->len == l)) {
943  if (!memcmp(tmp->name, name, l))
944  return(tmp->name);
945  }
946 #else
947  if ((tmp->okey == skey) && (tmp->len == l) &&
948  (!xmlStrncmp(tmp->name, name, l)))
949  return(tmp->name);
950 #endif
951  }
952  key = okey % dict->size;
953  }
954 
955  ret = xmlDictAddString(dict, name, l);
956  if (ret == NULL)
957  return(NULL);
958  if (insert == NULL) {
959  entry = &(dict->dict[key]);
960  } else {
961  entry = xmlMalloc(sizeof(xmlDictEntry));
962  if (entry == NULL)
963  return(NULL);
964  }
965  entry->name = ret;
966  entry->len = l;
967  entry->next = NULL;
968  entry->valid = 1;
969  entry->okey = okey;
970 
971 
972  if (insert != NULL)
973  insert->next = entry;
974 
975  dict->nbElems++;
976 
977  if ((nbi > MAX_HASH_LEN) &&
978  (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) {
979  if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0)
980  return(NULL);
981  }
982  /* Note that entry may have been freed at this point by xmlDictGrow */
983 
984  return(ret);
985 }
986 
997 const xmlChar *
999  unsigned long key, okey, nbi = 0;
1001  unsigned int l;
1002 
1003  if ((dict == NULL) || (name == NULL))
1004  return(NULL);
1005 
1006  if (len < 0)
1007  l = strlen((const char *) name);
1008  else
1009  l = len;
1010  if (((dict->limit > 0) && (l >= dict->limit)) ||
1011  (l > INT_MAX / 2))
1012  return(NULL);
1013 
1014  /*
1015  * Check for duplicate and insertion location.
1016  */
1017  okey = xmlDictComputeKey(dict, name, l);
1018  key = okey % dict->size;
1019  if (dict->dict[key].valid == 0) {
1020  insert = NULL;
1021  } else {
1022  for (insert = &(dict->dict[key]); insert->next != NULL;
1023  insert = insert->next) {
1024 #ifdef __GNUC__
1025  if ((insert->okey == okey) && (insert->len == l)) {
1026  if (!memcmp(insert->name, name, l))
1027  return(insert->name);
1028  }
1029 #else
1030  if ((insert->okey == okey) && (insert->len == l) &&
1031  (!xmlStrncmp(insert->name, name, l)))
1032  return(insert->name);
1033 #endif
1034  nbi++;
1035  }
1036 #ifdef __GNUC__
1037  if ((insert->okey == okey) && (insert->len == l)) {
1038  if (!memcmp(insert->name, name, l))
1039  return(insert->name);
1040  }
1041 #else
1042  if ((insert->okey == okey) && (insert->len == l) &&
1043  (!xmlStrncmp(insert->name, name, l)))
1044  return(insert->name);
1045 #endif
1046  }
1047 
1048  if (dict->subdict) {
1049  unsigned long skey;
1050 
1051  /* we cannot always reuse the same okey for the subdict */
1052  if (((dict->size == MIN_DICT_SIZE) &&
1053  (dict->subdict->size != MIN_DICT_SIZE)) ||
1054  ((dict->size != MIN_DICT_SIZE) &&
1055  (dict->subdict->size == MIN_DICT_SIZE)))
1056  skey = xmlDictComputeKey(dict->subdict, name, l);
1057  else
1058  skey = okey;
1059 
1060  key = skey % dict->subdict->size;
1061  if (dict->subdict->dict[key].valid != 0) {
1062  xmlDictEntryPtr tmp;
1063 
1064  for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1065  tmp = tmp->next) {
1066 #ifdef __GNUC__
1067  if ((tmp->okey == skey) && (tmp->len == l)) {
1068  if (!memcmp(tmp->name, name, l))
1069  return(tmp->name);
1070  }
1071 #else
1072  if ((tmp->okey == skey) && (tmp->len == l) &&
1073  (!xmlStrncmp(tmp->name, name, l)))
1074  return(tmp->name);
1075 #endif
1076  nbi++;
1077  }
1078 #ifdef __GNUC__
1079  if ((tmp->okey == skey) && (tmp->len == l)) {
1080  if (!memcmp(tmp->name, name, l))
1081  return(tmp->name);
1082  }
1083 #else
1084  if ((tmp->okey == skey) && (tmp->len == l) &&
1085  (!xmlStrncmp(tmp->name, name, l)))
1086  return(tmp->name);
1087 #endif
1088  }
1089  }
1090 
1091  /* not found */
1092  return(NULL);
1093 }
1094 
1105 const xmlChar *
1106 xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
1107  unsigned long okey, key, nbi = 0;
1110  const xmlChar *ret;
1111  unsigned int len, plen, l;
1112 
1113  if ((dict == NULL) || (name == NULL))
1114  return(NULL);
1115  if (prefix == NULL)
1116  return(xmlDictLookup(dict, name, -1));
1117 
1118  l = len = strlen((const char *) name);
1119  plen = strlen((const char *) prefix);
1120  len += 1 + plen;
1121 
1122  /*
1123  * Check for duplicate and insertion location.
1124  */
1125  okey = xmlDictComputeQKey(dict, prefix, plen, name, l);
1126  key = okey % dict->size;
1127  if (dict->dict[key].valid == 0) {
1128  insert = NULL;
1129  } else {
1130  for (insert = &(dict->dict[key]); insert->next != NULL;
1131  insert = insert->next) {
1132  if ((insert->okey == okey) && (insert->len == len) &&
1133  (xmlStrQEqual(prefix, name, insert->name)))
1134  return(insert->name);
1135  nbi++;
1136  }
1137  if ((insert->okey == okey) && (insert->len == len) &&
1138  (xmlStrQEqual(prefix, name, insert->name)))
1139  return(insert->name);
1140  }
1141 
1142  if (dict->subdict) {
1143  unsigned long skey;
1144 
1145  /* we cannot always reuse the same okey for the subdict */
1146  if (((dict->size == MIN_DICT_SIZE) &&
1147  (dict->subdict->size != MIN_DICT_SIZE)) ||
1148  ((dict->size != MIN_DICT_SIZE) &&
1149  (dict->subdict->size == MIN_DICT_SIZE)))
1150  skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l);
1151  else
1152  skey = okey;
1153 
1154  key = skey % dict->subdict->size;
1155  if (dict->subdict->dict[key].valid != 0) {
1156  xmlDictEntryPtr tmp;
1157  for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1158  tmp = tmp->next) {
1159  if ((tmp->okey == skey) && (tmp->len == len) &&
1160  (xmlStrQEqual(prefix, name, tmp->name)))
1161  return(tmp->name);
1162  nbi++;
1163  }
1164  if ((tmp->okey == skey) && (tmp->len == len) &&
1165  (xmlStrQEqual(prefix, name, tmp->name)))
1166  return(tmp->name);
1167  }
1168  key = okey % dict->size;
1169  }
1170 
1171  ret = xmlDictAddQString(dict, prefix, plen, name, l);
1172  if (ret == NULL)
1173  return(NULL);
1174  if (insert == NULL) {
1175  entry = &(dict->dict[key]);
1176  } else {
1177  entry = xmlMalloc(sizeof(xmlDictEntry));
1178  if (entry == NULL)
1179  return(NULL);
1180  }
1181  entry->name = ret;
1182  entry->len = len;
1183  entry->next = NULL;
1184  entry->valid = 1;
1185  entry->okey = okey;
1186 
1187  if (insert != NULL)
1188  insert->next = entry;
1189 
1190  dict->nbElems++;
1191 
1192  if ((nbi > MAX_HASH_LEN) &&
1193  (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
1194  xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
1195  /* Note that entry may have been freed at this point by xmlDictGrow */
1196 
1197  return(ret);
1198 }
1199 
1210 int
1213 
1214  if ((dict == NULL) || (str == NULL))
1215  return(-1);
1216  pool = dict->strings;
1217  while (pool != NULL) {
1218  if ((str >= &pool->array[0]) && (str <= pool->free))
1219  return(1);
1220  pool = pool->next;
1221  }
1222  if (dict->subdict)
1223  return(xmlDictOwns(dict->subdict, str));
1224  return(0);
1225 }
1226 
1236 int
1238  if (dict == NULL)
1239  return(-1);
1240  if (dict->subdict)
1241  return(dict->nbElems + dict->subdict->nbElems);
1242  return(dict->nbElems);
1243 }
1244 
1255 size_t
1257  size_t ret;
1258 
1259  if (dict == NULL)
1260  return(0);
1261  ret = dict->limit;
1262  dict->limit = limit;
1263  return(ret);
1264 }
1265 
1275 size_t
1278  size_t limit = 0;
1279 
1280  if (dict == NULL)
1281  return(0);
1282  pool = dict->strings;
1283  while (pool != NULL) {
1284  limit += pool->size;
1285  pool = pool->next;
1286  }
1287  return(limit);
1288 }
1289 
1290 #define bottom_dict
1291 #include "elfgcchack.h"
int valid
Definition: dict.c:98
static int xmlDictGrow(xmlDictPtr dict, size_t size)
Definition: dict.c:660
xmlChar * end
Definition: dict.c:107
XMLPUBFUN xmlRMutexPtr XMLCALL xmlNewRMutex(void)
Definition: threads.c:285
static unsigned long xmlDictComputeFastKey(const xmlChar *name, int namelen, int seed)
Definition: dict.c:444
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:1256
ACPI_SIZE strlen(const char *String)
Definition: utclib.c:269
#define xmlDictComputeQKey(dict, prefix, plen, name, len)
Definition: dict.c:75
#define MAX_DICT_HASH
Definition: dict.c:66
#define free
Definition: debug_ros.c:5
xmlDictStringsPtr next
Definition: dict.c:105
GLintptr offset
Definition: glext.h:5920
void __cdecl srand(_In_ unsigned int _Seed)
static int xmlDictInitialized
Definition: dict.c:139
static int insert
Definition: xmllint.c:144
xmlDictEntry * xmlDictEntryPtr
Definition: dict.c:93
__u16 time
Definition: mkdosfs.c:366
xmlDictPtr xmlDictCreateSub(xmlDictPtr sub)
Definition: dict.c:615
GLint namelen
Definition: glext.h:7232
void xmlDictCleanup(void)
Definition: dict.c:221
int xmlInitializeDict(void)
Definition: dict.c:159
int ref_counter
Definition: dict.c:116
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:118
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:793
int hash
Definition: main.c:58
int __xmlRandom(void)
Definition: dict.c:197
static const xmlChar * xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, unsigned int plen, const xmlChar *name, unsigned int namelen)
Definition: dict.c:305
_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:1276
xmlDictPtr xmlDictCreate(void)
Definition: dict.c:568
struct _xmlDict * subdict
Definition: dict.c:123
XMLPUBVAR xmlGenericErrorFunc xmlGenericError
Definition: globals.h:346
const WCHAR * str
xmlChar * free
Definition: dict.c:106
const xmlChar * xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len)
Definition: dict.c:998
smooth NULL
Definition: ftsmooth.c:416
xmlDictStrings * xmlDictStringsPtr
Definition: dict.c:103
Definition: dict.c:115
r l[0]
Definition: byte_order.h:167
const xmlChar * xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len)
Definition: dict.c:858
static xmlRMutexPtr xmlDictMutex
Definition: dict.c:134
GLsizeiptr size
Definition: glext.h:5919
int __xmlInitializeDict(void)
Definition: dict.c:175
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:95
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:65
const xmlChar * xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name)
Definition: dict.c:1106
size_t limit
Definition: dict.c:127
size_t nbStrings
Definition: dict.c:109
static unsigned __int64 next
Definition: rand_nt.c:6
__XML_EXTERNC typedef xmlDict * xmlDictPtr
Definition: dict.h:24
int seed
Definition: dict.c:125
static const xmlChar * xmlDictAddString(xmlDictPtr dict, const xmlChar *name, unsigned int namelen)
Definition: dict.c:241
#define __int32
Definition: basetyps.h:19
unsigned int len
Definition: dict.c:97
unsigned int nbElems
Definition: dict.c:120
#define MAX_HASH_LEN
Definition: dict.c:64
#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:407
XMLPUBVAR xmlMallocFunc xmlMalloc
Definition: globals.h:247
UINT32 uint32_t
Definition: types.h:75
typedef__XML_EXTERNC struct _xmlDict xmlDict
Definition: dict.h:23
Definition: name.c:36
int xmlDictSize(xmlDictPtr dict)
Definition: dict.c:1237
FILE * stderr
const xmlChar * name
Definition: dict.c:96
size_t size
Definition: dict.c:108
#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:487
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:70
size_t size
Definition: dict.c:119
unsigned long okey
Definition: dict.c:99
int xmlDictReference(xmlDictPtr dict)
Definition: dict.c:638
Definition: path.c:42
static uint32_t xmlDictComputeBigKey(const xmlChar *data, int namelen, int seed)
Definition: dict.c:375
XMLPUBVAR void * xmlGenericErrorContext
Definition: globals.h:362
int xmlDictOwns(xmlDictPtr dict, const xmlChar *str)
Definition: dict.c:1211
xmlDictStringsPtr strings
Definition: dict.c:121
GLuint const GLchar * name
Definition: glext.h:6031