1 /*

     2  * dict.c: dictionary of reusable strings, just used to avoid allocation

     3  *         and freeing operations.

     4  *

     5  * Copyright (C) 2003 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 "XmlEnglibxml.h"

    21 

    22 #include <string.h>

    23 #include "Libxml2_globals.h"

    24 

    25 #define MAX_HASH_LEN 4

    26 // TODO: Optimize: "Magic number" -- make it configurable global parameter

    27 //       1 entry is 16 bytes

    28 #define MIN_DICT_SIZE 128

    29 #define MAX_DICT_HASH 8 * 2048

    30 

    31 /* #define ALLOW_REMOVAL */

    32 /* #define DEBUG_GROW */

    33 

    34 /*

    35  * xmlDictAddString:

    36  * @dict: the dictionnary

    37  * @name: the name of the userdata

    38  * @len: the length of the name, if -1 it is recomputed

    39  *

    40  * Add the string to the array[s]

    41  *

    42  * Returns the pointer of the local string, or NULL in case of error.

    43  *

    44  * OOM: possible --> NULL is returned, OOM flag is set

    45  */

    46 static const xmlChar*

    47 xmlDictAddString(xmlDictPtr dict, const xmlChar *name, int namelen) {

    48     xmlDictStringsPtr pool;

    49     const xmlChar *ret;

    50     int size = 0; /* + sizeof(_xmlDictStrings) == 1024 */

    51 

    52     pool = dict->strings;

    53     while (pool != NULL) {

    54         if (pool->end - pool->free > namelen)

    55             goto found_pool;

    56         if (pool->size > size) size = pool->size;

    57             pool = pool->next;

    58     }

    59     /*

    60      * Not found, need to allocate

    61      */

    62     if (pool == NULL) {

    63         if (size == 0) 

    64             size = 1000;

    65         else 

    66             size *= 4; /* exponential growth */

    67 

    68         if (size < 4 * namelen)

    69             size = 4 * namelen; /* just in case ! */

    70 

    71         pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);

    72         if (pool == NULL)

    73             return(NULL);

    74         pool->size = size;

    75         pool->nbStrings = 0;

    76         pool->free = &pool->array[0];

    77         pool->end = &pool->array[size];

    78         pool->next = dict->strings;

    79         dict->strings = pool;

    80     }

    81 found_pool:

    82     ret = pool->free;

    83     memcpy(pool->free, name, namelen);

    84     pool->free += namelen;

    85     *(pool->free++) = 0;

    86     return(ret);

    87 }

    88 

    89 /*

    90  * xmlDictAddQString:

    91  * @dict: the dictionnary

    92  * @prefix: the prefix of the userdata

    93  * @name: the name of the userdata

    94  * @len: the length of the name, if -1 it is recomputed

    95  *

    96  * Add the QName to the array[s]

    97  *

    98  * Returns the pointer of the local string, or NULL in case of error.

    99  */

   100 static const xmlChar *

   101 xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix,

   102                  const xmlChar *name, int namelen)

   103 {

   104     xmlDictStringsPtr pool;

   105     const xmlChar *ret;

   106     int size = 0; /* + sizeof(_xmlDictStrings) == 1024 */

   107     int plen;

   108 

   109     if (prefix == NULL) return(xmlDictAddString(dict, name, namelen));

   110     plen = xmlStrlen(prefix);

   111 

   112     pool = dict->strings;

   113     while (pool != NULL) {

   114     if (pool->end - pool->free > namelen)

   115         goto found_pool;

   116     if (pool->size > size) size = pool->size;

   117     pool = pool->next;

   118     }

   119     /*

   120      * Not found, need to allocate

   121      */

   122     if (pool == NULL) {

   123         if (size == 0) size = 1000;

   124     else size *= 4; /* exponential growth */

   125         if (size < 4 * namelen)

   126         size = 4 * namelen; /* just in case ! */

   127     pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);

   128     if (pool == NULL)

   129         return(NULL);

   130     pool->size = size;

   131     pool->nbStrings = 0;

   132     pool->free = &pool->array[0];

   133     pool->end = &pool->array[size];

   134     pool->next = dict->strings;

   135     dict->strings = pool;

   136     }

   137 found_pool:

   138     ret = pool->free;

   139     memcpy(pool->free, prefix, plen);

   140     pool->free += plen;

   141     *(pool->free++) = ':';

   142     namelen -= plen + 1;

   143     memcpy(pool->free, name, namelen);

   144     pool->free += namelen;

   145     *(pool->free++) = 0;

   146     return(ret);

   147 }

   148 

   149 /*

   150  * xmlDictComputeKey:

   151  * Calculate the hash key

   152  *

   153  * OOM: never

   154  */

   155 static unsigned long

   156 xmlDictComputeKey(const xmlChar *name, int namelen) {

   157     unsigned long value = 0L;

   158 

   159     if (name == NULL) return(0);

   160     value = *name;

   161     value <<= 5;

   162     if (namelen > 10) {

   163         value += name[namelen - 1];

   164         namelen = 10;

   165     }

   166     switch (namelen) {

   167         case 10: value += name[9];

   168         case 9: value += name[8];

   169         case 8: value += name[7];

   170         case 7: value += name[6];

   171         case 6: value += name[5];

   172         case 5: value += name[4];

   173         case 4: value += name[3];

   174         case 3: value += name[2];

   175         case 2: value += name[1];

   176         default: break;

   177     }

   178     return(value);

   179 }

   180 

   181 /*

   182  * xmlDictComputeQKey:

   183  * Calculate the hash key

   184  */

   185 static unsigned long

   186 xmlDictComputeQKey(const xmlChar *prefix, const xmlChar *name, int len)

   187 {

   188     unsigned long value = 0L;

   189     int plen;

   190 

   191     if (prefix == NULL)

   192         return(xmlDictComputeKey(name, len));

   193 

   194     plen = xmlStrlen(prefix);

   195     if (plen == 0)

   196     value += 30 * (unsigned long) ':';

   197     else

   198     value += 30 * (*prefix);

   199 

   200     if (len > 10) {

   201         value += name[len - (plen + 1 + 1)];

   202         len = 10;

   203     if (plen > 10)

   204         plen = 10;

   205     }

   206     switch (plen) {

   207         case 10: value += prefix[9];

   208         case 9: value += prefix[8];

   209         case 8: value += prefix[7];

   210         case 7: value += prefix[6];

   211         case 6: value += prefix[5];

   212         case 5: value += prefix[4];

   213         case 4: value += prefix[3];

   214         case 3: value += prefix[2];

   215         case 2: value += prefix[1];

   216         case 1: value += prefix[0];

   217         default: break;

   218     }

   219     len -= plen;

   220     if (len > 0) {

   221         value += (unsigned long) ':';

   222     len--;

   223     }

   224     switch (len) {

   225         case 10: value += name[9];

   226         case 9: value += name[8];

   227         case 8: value += name[7];

   228         case 7: value += name[6];

   229         case 6: value += name[5];

   230         case 5: value += name[4];

   231         case 4: value += name[3];

   232         case 3: value += name[2];

   233         case 2: value += name[1];

   234         case 1: value += name[0];

   235         default: break;

   236     }

   237     return(value);

   238 }

   239 

   240 /**

   241  * xmlDictCreate:

   242  *

   243  * Create a new dictionary

   244  *

   245  * Returns the newly created dictionnary, or NULL if an error occured.

   246  *

   247  * OOM: possible --> NULL is returned; OOM flag is set

   248  */

   249 xmlDictPtr

   250 xmlDictCreate(void) {

   251     xmlDictPtr dict;

   252 

   253     dict = (xmlDictPtr)xmlMalloc(sizeof(xmlDict));

   254     if (dict) {

   255         dict->ref_counter = 1;

   256 

   257         dict->size = MIN_DICT_SIZE;

   258         dict->nbElems = 0;

   259         dict->dict = (xmlDictEntryPtr)xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));

   260         dict->strings = NULL;

   261         dict->subdict = NULL;

   262         if (dict->dict) {

   263             memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));

   264             return(dict);

   265         }

   266         xmlFree(dict); // OOM

   267     }

   268     return(NULL); // OOM

   269 }

   270 

   271 /**

   272  * xmlDictCreateSub:

   273  * @sub: an existing dictionnary

   274  *

   275  * Create a new dictionary, inheriting strings from the read-only

   276  * dictionnary @sub. On lookup, strings are first searched in the

   277  * new dictionnary, then in @sub, and if not found are created in the

   278  * new dictionnary.

   279  *

   280  * Returns the newly created dictionnary, or NULL if an error occured.

   281  */

   282 xmlDictPtr

   283 xmlDictCreateSub(xmlDictPtr sub) {

   284     xmlDictPtr dict = xmlDictCreate();

   285 

   286     if ((dict != NULL) && (sub != NULL)) {

   287         dict->subdict = sub;

   288     xmlDictReference(dict->subdict);

   289     }

   290     return(dict);

   291 }

   292 

   293 /**

   294  * xmlDictReference:

   295  * @dict: the dictionnary

   296  *

   297  * Increment the reference counter of a dictionary

   298  *

   299  * Returns 0 in case of success and -1 in case of error

   300  *

   301  * OOM: never

   302  */

   303 int

   304 xmlDictReference(xmlDictPtr dict) {

   305     if (dict == NULL) return -1;

   306     dict->ref_counter++;

   307     return(0);

   308 }

   309 

   310 /**

   311  * xmlDictGrow:

   312  * @dict: the dictionnary

   313  * @size: the new size of the dictionnary

   314  *

   315  * resize the dictionnary

   316  *

   317  * Returns 0 in case of success, -1 in case of failure

   318  *

   319  * OOM: possible --> returns -1, OOM is set

   320  */

   321 static int

   322 xmlDictGrow(xmlDictPtr dict, int size) {

   323     unsigned long key;

   324     int oldsize, i;

   325     xmlDictEntryPtr iter, next;

   326     struct _xmlDictEntry *olddict;

   327 #ifdef DEBUG_GROW

   328     unsigned long nbElem = 0;

   329 #endif

   330 

   331     if (dict == NULL)

   332         return(-1);

   333     if (size < 8)

   334         return(-1);

   335     if (size > 8 * 2048)

   336         return(-1);

   337 

   338     oldsize = dict->size;

   339     olddict = dict->dict;

   340     if (olddict == NULL)

   341         return(-1);

   342 

   343     dict->dict = (xmlDictEntryPtr)xmlMalloc(size * sizeof(xmlDictEntry));

   344     if (dict->dict == NULL) {

   345         dict->dict = olddict;

   346         return(-1);

   347     }

   348     memset(dict->dict, 0, size * sizeof(xmlDictEntry));

   349     dict->size = size;

   350 

   351     /*  If the two loops are merged, there would be situations where

   352     a new entry needs to allocated and data copied into it from

   353     the main dict. So instead, we run through the array twice, first

   354     copying all the elements in the main array (where we can't get

   355     conflicts) and then the rest, so we only free (and don't allocate)

   356     */

   357     for (i = 0; i < oldsize; i++) {

   358         if (olddict[i].valid == 0)

   359             continue;

   360         key = xmlDictComputeKey(olddict[i].name, olddict[i].len) % dict->size;

   361         memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));

   362         dict->dict[key].next = NULL;

   363 #ifdef DEBUG_GROW

   364         nbElem++;

   365 #endif

   366     }

   367 

   368     for (i = 0; i < oldsize; i++) {

   369         iter = olddict[i].next;

   370         while (iter) {

   371             next = iter->next;

   372             /*

   373             * put back the entry in the new dict

   374             */

   375             key = xmlDictComputeKey(iter->name, iter->len) % dict->size;

   376             if (dict->dict[key].valid == 0) {

   377                 memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry));

   378                 dict->dict[key].next = NULL;

   379                 dict->dict[key].valid = 1;

   380                 xmlFree(iter);

   381             } else {

   382                 iter->next = dict->dict[key].next;

   383                 dict->dict[key].next = iter;

   384             }

   385 #ifdef DEBUG_GROW

   386             nbElem++;

   387 #endif

   388             iter = next;

   389         } // while (iter)

   390     } // for (i = 0; i < oldsize; i++)

   391 

   392     xmlFree(olddict);

   393 

   394 #ifdef DEBUG_GROW

   395     xmlGenericError(xmlGenericErrorContext,

   396         "xmlDictGrow : from %d to %d, %d elems\n", oldsize, size, nbElem);

   397 #endif

   398 

   399     return(0);

   400 }

   401 

   402 /**

   403  * xmlDictFree:

   404  * @dict: the dictionnary

   405  *

   406  * Free the hash @dict and its contents. The userdata is

   407  * deallocated with @f if provided.

   408  */

   409 void

   410 xmlDictFree(xmlDictPtr dict) {

   411     int i;

   412     xmlDictEntryPtr iter;

   413     xmlDictEntryPtr next;

   414     int inside_dict = 0;

   415     xmlDictStringsPtr pool, nextp;

   416 

   417     if (dict == NULL)

   418         return;

   419 

   420     /* decrement the counter, it may be shared by a parser and docs */

   421     dict->ref_counter--;

   422     if (dict->ref_counter > 0)

   423         return;

   424 

   425     if (dict->subdict != NULL) {

   426         xmlDictFree(dict->subdict);

   427     }

   428 

   429     if (dict->dict) {

   430         for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++)

   431         {

   432             iter = &(dict->dict[i]);

   433             if (iter->valid == 0)

   434                 continue;

   435             inside_dict = 1;

   436             while (iter)

   437             {

   438                 next = iter->next;

   439                 if (!inside_dict)

   440                     xmlFree(iter);

   441                 dict->nbElems--;

   442                 inside_dict = 0;

   443                 iter = next;

   444             }

   445             inside_dict = 0;

   446         }

   447         xmlFree(dict->dict);

   448     }

   449 

   450     pool = dict->strings;

   451     while (pool != NULL) {

   452         nextp = pool->next;

   453         xmlFree(pool);

   454         pool = nextp;

   455     }

   456     xmlFree(dict);

   457 }

   458 

   459 /**

   460  * xmlDictLookup:

   461  * @dict: the dictionnary

   462  * @name: the name of the userdata

   463  * @len: the length of the name, if -1 it is recomputed

   464  *

   465  * Add the @name to the hash @dict if not present.

   466  *

   467  * Returns the internal copy of the name or NULL in case of internal error

   468  *

   469  * OOM: possible --> returns NULL and OOM flag is set

   470  */

   471 const xmlChar*

   472 xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {

   473     unsigned long key, okey, nbi = 0;

   474     xmlDictEntryPtr entry;

   475     xmlDictEntryPtr insert;

   476     const xmlChar *ret;

   477 

   478     if ((dict == NULL) || (name == NULL))

   479         return(NULL);

   480 

   481     if (len < 0)

   482         len = xmlStrlen(name);

   483 

   484     /*

   485      * Check for duplicate and insertion location.

   486      */

   487     okey = xmlDictComputeKey(name, len);

   488     key = okey % dict->size;

   489     if (dict->dict[key].valid == 0) {

   490         insert = NULL;

   491     } else {

   492         for (insert = &(dict->dict[key]); 

   493              insert->next != NULL; 

   494              insert = insert->next)

   495         {

   496 #ifdef __GNUC__

   497             if (insert->len == len) {

   498                 if (!memcmp(insert->name, name, len))

   499                     return(insert->name);

   500             }

   501 #else

   502             if ((insert->len == len) && (!xmlStrncmp(insert->name, name, len)))

   503                 return(insert->name);

   504 #endif

   505             nbi++;

   506         }

   507 #ifdef __GNUC__

   508         if (insert->len == len) {

   509             if (!memcmp(insert->name, name, len))

   510                 return(insert->name);

   511         }

   512 #else

   513         if ((insert->len == len) && (!xmlStrncmp(insert->name, name, len)))

   514             return(insert->name);

   515 #endif

   516     }

   517 

   518     if (dict->subdict) {

   519         key = okey % dict->subdict->size;

   520         if (dict->subdict->dict[key].valid != 0) {

   521             xmlDictEntryPtr tmp;

   522     

   523             for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL; tmp = tmp->next)

   524             {

   525 #ifdef __GNUC__

   526                 if (tmp->len == len) {

   527                     if (!memcmp(tmp->name, name, len))

   528                         return(tmp->name);

   529                 }

   530 #else

   531                 if ((tmp->len == len) && (!xmlStrncmp(tmp->name, name, len)))

   532                         return(tmp->name);

   533 #endif

   534                 nbi++;

   535             }

   536 #ifdef __GNUC__

   537             if (tmp->len == len) {

   538                 if (!memcmp(tmp->name, name, len))

   539                     return(tmp->name);

   540             }

   541 #else

   542             if ((tmp->len == len) && (!xmlStrncmp(tmp->name, name, len)))

   543                 return(tmp->name);

   544 #endif

   545         } // if (dict->subdict->dict[key].valid != 0)

   546 

   547         key = okey % dict->size;

   548     } // if (dict->subdict)

   549 

   550     ret = xmlDictAddString(dict, name, len); // may set OOM flag

   551     if (!ret)

   552         return(NULL);

   553 

   554     if (insert == NULL) {

   555         entry = &(dict->dict[key]);

   556     } else {

   557         entry = (xmlDictEntryPtr)xmlMalloc(sizeof(xmlDictEntry));

   558         if (entry == NULL)

   559              return(NULL); //OOM

   560     }

   561     entry->name = ret;

   562     entry->len = len;

   563     entry->next = NULL;

   564     entry->valid = 1;

   565 

   566     if (insert != NULL)

   567         insert->next = entry;

   568 

   569     dict->nbElems++;

   570 

   571     if ((nbi > MAX_HASH_LEN) && 

   572         (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))

   573     {

   574         xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);

   575         if(OOM_FLAG)

   576             return NULL;

   577     }

   578 

   579     /* Note that entry may have been freed at this point by xmlDictGrow */

   580 

   581     return(ret);

   582 }

   583 

   584 /**

   585  * xmlDictQLookup:

   586  * @dict: the dictionnary

   587  * @prefix: the prefix

   588  * @name: the name

   589  *

   590  * Add the QName @prefix:@name to the hash @dict if not present.

   591  *

   592  * Returns the internal copy of the QName or NULL in case of internal error

   593  */

   594 const xmlChar *

   595 xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {

   596     unsigned long okey, key, nbi = 0;

   597     xmlDictEntryPtr entry;

   598     xmlDictEntryPtr insert;

   599     const xmlChar *ret;

   600     int len;

   601 

   602     if ((dict == NULL) || (name == NULL))

   603     return(NULL);

   604 

   605     len = xmlStrlen(name);

   606     if (prefix != NULL)

   607         len += 1 + xmlStrlen(prefix);

   608 

   609     /*

   610      * Check for duplicate and insertion location.

   611      */

   612     okey = xmlDictComputeQKey(prefix, name, len);

   613     key = okey % dict->size;

   614     if (dict->dict[key].valid == 0) {

   615     insert = NULL;

   616     } else {

   617     for (insert = &(dict->dict[key]); insert->next != NULL;

   618          insert = insert->next) {

   619         if ((insert->len == len) &&

   620             (xmlStrQEqual(prefix, name, insert->name)))

   621         return(insert->name);

   622         nbi++;

   623     }

   624     if ((insert->len == len) &&

   625         (xmlStrQEqual(prefix, name, insert->name)))

   626         return(insert->name);

   627     }

   628 

   629     if (dict->subdict) {

   630     key = okey % dict->subdict->size;

   631     if (dict->subdict->dict[key].valid != 0) {

   632         xmlDictEntryPtr tmp;

   633         for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;

   634          tmp = tmp->next) {

   635         if ((tmp->len == len) &&

   636             (xmlStrQEqual(prefix, name, tmp->name)))

   637             return(tmp->name);

   638         nbi++;

   639         }

   640         if ((tmp->len == len) &&

   641         (xmlStrQEqual(prefix, name, tmp->name)))

   642         return(tmp->name);

   643     }

   644     key = okey % dict->size;

   645     }

   646 

   647     ret = xmlDictAddQString(dict, prefix, name, len);

   648     if (ret == NULL)

   649         return(NULL);

   650     if (insert == NULL) {

   651     entry = &(dict->dict[key]);

   652     } else {

   653         entry = (xmlDictEntryPtr)xmlMalloc(sizeof(xmlDictEntry));

   654     if (entry == NULL)

   655          return(NULL);

   656     }

   657     entry->name = ret;

   658     entry->len = len;

   659     entry->next = NULL;

   660     entry->valid = 1;

   661 

   662     if (insert != NULL)

   663     insert->next = entry;

   664 

   665     dict->nbElems++;

   666 

   667     if ((nbi > MAX_HASH_LEN) &&

   668         (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))

   669     xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);

   670     /* Note that entry may have been freed at this point by xmlDictGrow */

   671 

   672     return(ret);

   673 }

   674 

   675 

   676 /**

   677  * xmlDictOwns:

   678  * @dict: the dictionnary

   679  * @str: the string

   680  *

   681  * check if a string is owned by the disctionary

   682  *

   683  * Returns 1 if true, 0 if false and -1 in case of error

   684  * -1 in case of error

   685  *

   686  * OOM: impossible

   687  */

   688 int

   689 xmlDictOwns(xmlDictPtr dict, const xmlChar *str) {

   690     xmlDictStringsPtr pool;

   691 

   692     if ((dict == NULL) || (str == NULL))

   693     {

   694         return(-1);

   695     }

   696     pool = dict->strings;

   697     while (pool != NULL) {

   698         if ((str >= pool->array) && (str <= pool->free))

   699         {

   700             return(1);

   701         }

   702         pool = pool->next;

   703     }

   704     if (dict->subdict)

   705         return(xmlDictOwns(dict->subdict, str));

   706     return(0);

   707 }

   708 

   709