Annotation of embedaddon/libxml2/hash.c, revision 1.1.1.2

1.1       misho       1: /*
                      2:  * hash.c: chained hash tables
                      3:  *
                      4:  * Reference: Your favorite introductory book on algorithms
                      5:  *
1.1.1.2 ! misho       6:  * Copyright (C) 2000,2012 Bjorn Reese and Daniel Veillard.
1.1       misho       7:  *
                      8:  * Permission to use, copy, modify, and distribute this software for any
                      9:  * purpose with or without fee is hereby granted, provided that the above
                     10:  * copyright notice and this permission notice appear in all copies.
                     11:  *
                     12:  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
                     13:  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
                     14:  * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
                     15:  * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
                     16:  *
                     17:  * Author: breese@users.sourceforge.net
                     18:  */
                     19: 
                     20: #define IN_LIBXML
                     21: #include "libxml.h"
                     22: 
                     23: #include <string.h>
1.1.1.2 ! misho      24: #ifdef HAVE_STDLIB_H
        !            25: #include <stdlib.h>
        !            26: #endif
        !            27: #ifdef HAVE_TIME_H
        !            28: #include <time.h>
        !            29: #endif
        !            30: 
        !            31: /*
        !            32:  * Following http://www.ocert.org/advisories/ocert-2011-003.html
        !            33:  * it seems that having hash randomization might be a good idea
        !            34:  * when using XML with untrusted data
        !            35:  */
        !            36: #if defined(HAVE_RAND) && defined(HAVE_SRAND) && defined(HAVE_TIME)
        !            37: #define HASH_RANDOMIZATION
        !            38: #endif
        !            39: 
1.1       misho      40: #include <libxml/parser.h>
                     41: #include <libxml/hash.h>
                     42: #include <libxml/xmlmemory.h>
                     43: #include <libxml/xmlerror.h>
                     44: #include <libxml/globals.h>
                     45: 
                     46: #define MAX_HASH_LEN 8
                     47: 
                     48: /* #define DEBUG_GROW */
                     49: 
                     50: /*
                     51:  * A single entry in the hash table
                     52:  */
                     53: typedef struct _xmlHashEntry xmlHashEntry;
                     54: typedef xmlHashEntry *xmlHashEntryPtr;
                     55: struct _xmlHashEntry {
                     56:     struct _xmlHashEntry *next;
                     57:     xmlChar *name;
                     58:     xmlChar *name2;
                     59:     xmlChar *name3;
                     60:     void *payload;
                     61:     int valid;
                     62: };
                     63: 
                     64: /*
                     65:  * The entire hash table
                     66:  */
                     67: struct _xmlHashTable {
                     68:     struct _xmlHashEntry *table;
                     69:     int size;
                     70:     int nbElems;
                     71:     xmlDictPtr dict;
1.1.1.2 ! misho      72: #ifdef HASH_RANDOMIZATION
        !            73:     int random_seed;
        !            74: #endif
1.1       misho      75: };
                     76: 
                     77: /*
                     78:  * xmlHashComputeKey:
                     79:  * Calculate the hash key
                     80:  */
                     81: static unsigned long
                     82: xmlHashComputeKey(xmlHashTablePtr table, const xmlChar *name,
                     83:                  const xmlChar *name2, const xmlChar *name3) {
                     84:     unsigned long value = 0L;
                     85:     char ch;
                     86:     
1.1.1.2 ! misho      87: #ifdef HASH_RANDOMIZATION
        !            88:     value = table->random_seed;
        !            89: #endif
1.1       misho      90:     if (name != NULL) {
                     91:        value += 30 * (*name);
                     92:        while ((ch = *name++) != 0) {
                     93:            value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
                     94:        }
                     95:     }
                     96:     if (name2 != NULL) {
                     97:        while ((ch = *name2++) != 0) {
                     98:            value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
                     99:        }
                    100:     }
                    101:     if (name3 != NULL) {
                    102:        while ((ch = *name3++) != 0) {
                    103:            value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
                    104:        }
                    105:     }
                    106:     return (value % table->size);
                    107: }
                    108: 
                    109: static unsigned long
                    110: xmlHashComputeQKey(xmlHashTablePtr table,
                    111:                   const xmlChar *prefix, const xmlChar *name,
                    112:                   const xmlChar *prefix2, const xmlChar *name2,
                    113:                   const xmlChar *prefix3, const xmlChar *name3) {
                    114:     unsigned long value = 0L;
                    115:     char ch;
                    116:     
1.1.1.2 ! misho     117: #ifdef HASH_RANDOMIZATION
        !           118:     value = table->random_seed;
        !           119: #endif
1.1       misho     120:     if (prefix != NULL)
                    121:        value += 30 * (*prefix);
                    122:     else
                    123:        value += 30 * (*name);
                    124: 
                    125:     if (prefix != NULL) {
                    126:        while ((ch = *prefix++) != 0) {
                    127:            value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
                    128:        }
                    129:        value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
                    130:     }
                    131:     if (name != NULL) {
                    132:        while ((ch = *name++) != 0) {
                    133:            value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
                    134:        }
                    135:     }
                    136:     if (prefix2 != NULL) {
                    137:        while ((ch = *prefix2++) != 0) {
                    138:            value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
                    139:        }
                    140:        value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
                    141:     }
                    142:     if (name2 != NULL) {
                    143:        while ((ch = *name2++) != 0) {
                    144:            value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
                    145:        }
                    146:     }
                    147:     if (prefix3 != NULL) {
                    148:        while ((ch = *prefix3++) != 0) {
                    149:            value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
                    150:        }
                    151:        value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
                    152:     }
                    153:     if (name3 != NULL) {
                    154:        while ((ch = *name3++) != 0) {
                    155:            value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
                    156:        }
                    157:     }
                    158:     return (value % table->size);
                    159: }
                    160: 
                    161: /**
                    162:  * xmlHashCreate:
                    163:  * @size: the size of the hash table
                    164:  *
                    165:  * Create a new xmlHashTablePtr.
                    166:  *
                    167:  * Returns the newly created object, or NULL if an error occured.
                    168:  */
                    169: xmlHashTablePtr
                    170: xmlHashCreate(int size) {
                    171:     xmlHashTablePtr table;
                    172:   
                    173:     if (size <= 0)
                    174:         size = 256;
                    175:   
                    176:     table = xmlMalloc(sizeof(xmlHashTable));
                    177:     if (table) {
                    178:         table->dict = NULL;
                    179:         table->size = size;
                    180:        table->nbElems = 0;
                    181:         table->table = xmlMalloc(size * sizeof(xmlHashEntry));
                    182:         if (table->table) {
                    183:            memset(table->table, 0, size * sizeof(xmlHashEntry));
1.1.1.2 ! misho     184: #ifdef HASH_RANDOMIZATION
        !           185:             table->random_seed = __xmlRandom();
        !           186: #endif
1.1       misho     187:            return(table);
                    188:         }
                    189:         xmlFree(table);
                    190:     }
                    191:     return(NULL);
                    192: }
                    193: 
                    194: /**
                    195:  * xmlHashCreateDict:
                    196:  * @size: the size of the hash table
                    197:  * @dict: a dictionary to use for the hash
                    198:  *
                    199:  * Create a new xmlHashTablePtr which will use @dict as the internal dictionary
                    200:  *
                    201:  * Returns the newly created object, or NULL if an error occured.
                    202:  */
                    203: xmlHashTablePtr
                    204: xmlHashCreateDict(int size, xmlDictPtr dict) {
                    205:     xmlHashTablePtr table;
                    206: 
                    207:     table = xmlHashCreate(size);
                    208:     if (table != NULL) {
                    209:         table->dict = dict;
                    210:        xmlDictReference(dict);
                    211:     }
                    212:     return(table);
                    213: }
                    214: 
                    215: /**
                    216:  * xmlHashGrow:
                    217:  * @table: the hash table
                    218:  * @size: the new size of the hash table
                    219:  *
                    220:  * resize the hash table
                    221:  *
                    222:  * Returns 0 in case of success, -1 in case of failure
                    223:  */
                    224: static int
                    225: xmlHashGrow(xmlHashTablePtr table, int size) {
                    226:     unsigned long key;
                    227:     int oldsize, i;
                    228:     xmlHashEntryPtr iter, next;
                    229:     struct _xmlHashEntry *oldtable;
                    230: #ifdef DEBUG_GROW
                    231:     unsigned long nbElem = 0;
                    232: #endif
                    233:   
                    234:     if (table == NULL)
                    235:        return(-1);
                    236:     if (size < 8)
                    237:         return(-1);
                    238:     if (size > 8 * 2048)
                    239:        return(-1);
                    240: 
                    241:     oldsize = table->size;
                    242:     oldtable = table->table;
                    243:     if (oldtable == NULL)
                    244:         return(-1);
                    245:   
                    246:     table->table = xmlMalloc(size * sizeof(xmlHashEntry));
                    247:     if (table->table == NULL) {
                    248:        table->table = oldtable;
                    249:        return(-1);
                    250:     }
                    251:     memset(table->table, 0, size * sizeof(xmlHashEntry));
                    252:     table->size = size;
                    253: 
                    254:     /* If the two loops are merged, there would be situations where
                    255:        a new entry needs to allocated and data copied into it from 
                    256:        the main table. So instead, we run through the array twice, first
                    257:        copying all the elements in the main array (where we can't get
                    258:        conflicts) and then the rest, so we only free (and don't allocate)
                    259:     */
                    260:     for (i = 0; i < oldsize; i++) {
                    261:        if (oldtable[i].valid == 0) 
                    262:            continue;
                    263:        key = xmlHashComputeKey(table, oldtable[i].name, oldtable[i].name2,
                    264:                                oldtable[i].name3);
                    265:        memcpy(&(table->table[key]), &(oldtable[i]), sizeof(xmlHashEntry));
                    266:        table->table[key].next = NULL;
                    267:     }
                    268: 
                    269:     for (i = 0; i < oldsize; i++) {
                    270:        iter = oldtable[i].next;
                    271:        while (iter) {
                    272:            next = iter->next;
                    273: 
                    274:            /*
                    275:             * put back the entry in the new table
                    276:             */
                    277: 
                    278:            key = xmlHashComputeKey(table, iter->name, iter->name2,
                    279:                                    iter->name3);
                    280:            if (table->table[key].valid == 0) {
                    281:                memcpy(&(table->table[key]), iter, sizeof(xmlHashEntry));
                    282:                table->table[key].next = NULL;
                    283:                xmlFree(iter);
                    284:            } else {
                    285:                iter->next = table->table[key].next;
                    286:                table->table[key].next = iter;
                    287:            }
                    288: 
                    289: #ifdef DEBUG_GROW
                    290:            nbElem++;
                    291: #endif
                    292: 
                    293:            iter = next;
                    294:        }
                    295:     }
                    296: 
                    297:     xmlFree(oldtable);
                    298: 
                    299: #ifdef DEBUG_GROW
                    300:     xmlGenericError(xmlGenericErrorContext,
                    301:            "xmlHashGrow : from %d to %d, %d elems\n", oldsize, size, nbElem);
                    302: #endif
                    303: 
                    304:     return(0);
                    305: }
                    306: 
                    307: /**
                    308:  * xmlHashFree:
                    309:  * @table: the hash table
                    310:  * @f:  the deallocator function for items in the hash
                    311:  *
                    312:  * Free the hash @table and its contents. The userdata is
                    313:  * deallocated with @f if provided.
                    314:  */
                    315: void
                    316: xmlHashFree(xmlHashTablePtr table, xmlHashDeallocator f) {
                    317:     int i;
                    318:     xmlHashEntryPtr iter;
                    319:     xmlHashEntryPtr next;
                    320:     int inside_table = 0;
                    321:     int nbElems;
                    322: 
                    323:     if (table == NULL)
                    324:        return;
                    325:     if (table->table) {
                    326:        nbElems = table->nbElems;
                    327:        for(i = 0; (i < table->size) && (nbElems > 0); i++) {
                    328:            iter = &(table->table[i]);
                    329:            if (iter->valid == 0)
                    330:                continue;
                    331:            inside_table = 1;
                    332:            while (iter) {
                    333:                next = iter->next;
                    334:                if ((f != NULL) && (iter->payload != NULL))
                    335:                    f(iter->payload, iter->name);
                    336:                if (table->dict == NULL) {
                    337:                    if (iter->name)
                    338:                        xmlFree(iter->name);
                    339:                    if (iter->name2)
                    340:                        xmlFree(iter->name2);
                    341:                    if (iter->name3)
                    342:                        xmlFree(iter->name3);
                    343:                }
                    344:                iter->payload = NULL;
                    345:                if (!inside_table)
                    346:                    xmlFree(iter);
                    347:                nbElems--;
                    348:                inside_table = 0;
                    349:                iter = next;
                    350:            }
                    351:        }
                    352:        xmlFree(table->table);
                    353:     }
                    354:     if (table->dict)
                    355:         xmlDictFree(table->dict);
                    356:     xmlFree(table);
                    357: }
                    358: 
                    359: /**
                    360:  * xmlHashAddEntry:
                    361:  * @table: the hash table
                    362:  * @name: the name of the userdata
                    363:  * @userdata: a pointer to the userdata
                    364:  *
                    365:  * Add the @userdata to the hash @table. This can later be retrieved
                    366:  * by using the @name. Duplicate names generate errors.
                    367:  *
                    368:  * Returns 0 the addition succeeded and -1 in case of error.
                    369:  */
                    370: int
                    371: xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) {
                    372:     return(xmlHashAddEntry3(table, name, NULL, NULL, userdata));
                    373: }
                    374: 
                    375: /**
                    376:  * xmlHashAddEntry2:
                    377:  * @table: the hash table
                    378:  * @name: the name of the userdata
                    379:  * @name2: a second name of the userdata
                    380:  * @userdata: a pointer to the userdata
                    381:  *
                    382:  * Add the @userdata to the hash @table. This can later be retrieved
                    383:  * by using the (@name, @name2) tuple. Duplicate tuples generate errors.
                    384:  *
                    385:  * Returns 0 the addition succeeded and -1 in case of error.
                    386:  */
                    387: int
                    388: xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name,
                    389:                const xmlChar *name2, void *userdata) {
                    390:     return(xmlHashAddEntry3(table, name, name2, NULL, userdata));
                    391: }
                    392: 
                    393: /**
                    394:  * xmlHashUpdateEntry:
                    395:  * @table: the hash table
                    396:  * @name: the name of the userdata
                    397:  * @userdata: a pointer to the userdata
                    398:  * @f: the deallocator function for replaced item (if any)
                    399:  *
                    400:  * Add the @userdata to the hash @table. This can later be retrieved
                    401:  * by using the @name. Existing entry for this @name will be removed
                    402:  * and freed with @f if found.
                    403:  *
                    404:  * Returns 0 the addition succeeded and -1 in case of error.
                    405:  */
                    406: int
                    407: xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name,
                    408:                   void *userdata, xmlHashDeallocator f) {
                    409:     return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f));
                    410: }
                    411: 
                    412: /**
                    413:  * xmlHashUpdateEntry2:
                    414:  * @table: the hash table
                    415:  * @name: the name of the userdata
                    416:  * @name2: a second name of the userdata
                    417:  * @userdata: a pointer to the userdata
                    418:  * @f: the deallocator function for replaced item (if any)
                    419:  *
                    420:  * Add the @userdata to the hash @table. This can later be retrieved
                    421:  * by using the (@name, @name2) tuple. Existing entry for this tuple will
                    422:  * be removed and freed with @f if found.
                    423:  *
                    424:  * Returns 0 the addition succeeded and -1 in case of error.
                    425:  */
                    426: int
                    427: xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name,
                    428:                   const xmlChar *name2, void *userdata,
                    429:                   xmlHashDeallocator f) {
                    430:     return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f));
                    431: }
                    432: 
                    433: /**
                    434:  * xmlHashLookup:
                    435:  * @table: the hash table
                    436:  * @name: the name of the userdata
                    437:  *
                    438:  * Find the userdata specified by the @name.
                    439:  *
                    440:  * Returns the pointer to the userdata
                    441:  */
                    442: void *
                    443: xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) {
                    444:     return(xmlHashLookup3(table, name, NULL, NULL));
                    445: }
                    446: 
                    447: /**
                    448:  * xmlHashLookup2:
                    449:  * @table: the hash table
                    450:  * @name: the name of the userdata
                    451:  * @name2: a second name of the userdata
                    452:  *
                    453:  * Find the userdata specified by the (@name, @name2) tuple.
                    454:  *
                    455:  * Returns the pointer to the userdata
                    456:  */
                    457: void *
                    458: xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name,
                    459:              const xmlChar *name2) {
                    460:     return(xmlHashLookup3(table, name, name2, NULL));
                    461: }
                    462: 
                    463: /**
                    464:  * xmlHashQLookup:
                    465:  * @table: the hash table
                    466:  * @prefix: the prefix of the userdata
                    467:  * @name: the name of the userdata
                    468:  *
                    469:  * Find the userdata specified by the QName @prefix:@name/@name.
                    470:  *
                    471:  * Returns the pointer to the userdata
                    472:  */
                    473: void *
                    474: xmlHashQLookup(xmlHashTablePtr table, const xmlChar *prefix,
                    475:                const xmlChar *name) {
                    476:     return(xmlHashQLookup3(table, prefix, name, NULL, NULL, NULL, NULL));
                    477: }
                    478: 
                    479: /**
                    480:  * xmlHashQLookup2:
                    481:  * @table: the hash table
                    482:  * @prefix: the prefix of the userdata
                    483:  * @name: the name of the userdata
                    484:  * @prefix2: the second prefix of the userdata
                    485:  * @name2: a second name of the userdata
                    486:  *
                    487:  * Find the userdata specified by the QNames tuple
                    488:  *
                    489:  * Returns the pointer to the userdata
                    490:  */
                    491: void *
                    492: xmlHashQLookup2(xmlHashTablePtr table, const xmlChar *prefix,
                    493:                 const xmlChar *name, const xmlChar *prefix2,
                    494:                const xmlChar *name2) {
                    495:     return(xmlHashQLookup3(table, prefix, name, prefix2, name2, NULL, NULL));
                    496: }
                    497: 
                    498: /**
                    499:  * xmlHashAddEntry3:
                    500:  * @table: the hash table
                    501:  * @name: the name of the userdata
                    502:  * @name2: a second name of the userdata
                    503:  * @name3: a third name of the userdata
                    504:  * @userdata: a pointer to the userdata
                    505:  *
                    506:  * Add the @userdata to the hash @table. This can later be retrieved
                    507:  * by using the tuple (@name, @name2, @name3). Duplicate entries generate
                    508:  * errors.
                    509:  *
                    510:  * Returns 0 the addition succeeded and -1 in case of error.
                    511:  */
                    512: int
                    513: xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name,
                    514:                 const xmlChar *name2, const xmlChar *name3,
                    515:                 void *userdata) {
                    516:     unsigned long key, len = 0;
                    517:     xmlHashEntryPtr entry;
                    518:     xmlHashEntryPtr insert;
                    519: 
                    520:     if ((table == NULL) || (name == NULL))
                    521:        return(-1);
                    522: 
                    523:     /*
                    524:      * If using a dict internalize if needed
                    525:      */
                    526:     if (table->dict) {
                    527:         if (!xmlDictOwns(table->dict, name)) {
                    528:            name = xmlDictLookup(table->dict, name, -1);
                    529:            if (name == NULL)
                    530:                return(-1);
                    531:        }
                    532:         if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) {
                    533:            name2 = xmlDictLookup(table->dict, name2, -1);
                    534:            if (name2 == NULL)
                    535:                return(-1);
                    536:        }
                    537:         if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) {
                    538:            name3 = xmlDictLookup(table->dict, name3, -1);
                    539:            if (name3 == NULL)
                    540:                return(-1);
                    541:        }
                    542:     }
                    543: 
                    544:     /*
                    545:      * Check for duplicate and insertion location.
                    546:      */
                    547:     key = xmlHashComputeKey(table, name, name2, name3);
                    548:     if (table->table[key].valid == 0) {
                    549:        insert = NULL;
                    550:     } else {
                    551:         if (table->dict) {
                    552:            for (insert = &(table->table[key]); insert->next != NULL;
                    553:                 insert = insert->next) {
                    554:                if ((insert->name == name) &&
                    555:                    (insert->name2 == name2) &&
                    556:                    (insert->name3 == name3))
                    557:                    return(-1);
                    558:                len++;
                    559:            }
                    560:            if ((insert->name == name) &&
                    561:                (insert->name2 == name2) &&
                    562:                (insert->name3 == name3))
                    563:                return(-1);
                    564:        } else {
                    565:            for (insert = &(table->table[key]); insert->next != NULL;
                    566:                 insert = insert->next) {
                    567:                if ((xmlStrEqual(insert->name, name)) &&
                    568:                    (xmlStrEqual(insert->name2, name2)) &&
                    569:                    (xmlStrEqual(insert->name3, name3)))
                    570:                    return(-1);
                    571:                len++;
                    572:            }
                    573:            if ((xmlStrEqual(insert->name, name)) &&
                    574:                (xmlStrEqual(insert->name2, name2)) &&
                    575:                (xmlStrEqual(insert->name3, name3)))
                    576:                return(-1);
                    577:        }
                    578:     }
                    579: 
                    580:     if (insert == NULL) {
                    581:        entry = &(table->table[key]);
                    582:     } else {
                    583:        entry = xmlMalloc(sizeof(xmlHashEntry));
                    584:        if (entry == NULL)
                    585:             return(-1);
                    586:     }
                    587: 
                    588:     if (table->dict != NULL) {
                    589:         entry->name = (xmlChar *) name;
                    590:         entry->name2 = (xmlChar *) name2;
                    591:         entry->name3 = (xmlChar *) name3;
                    592:     } else {
                    593:        entry->name = xmlStrdup(name);
                    594:        entry->name2 = xmlStrdup(name2);
                    595:        entry->name3 = xmlStrdup(name3);
                    596:     }
                    597:     entry->payload = userdata;
                    598:     entry->next = NULL;
                    599:     entry->valid = 1;
                    600: 
                    601: 
                    602:     if (insert != NULL) 
                    603:        insert->next = entry;
                    604: 
                    605:     table->nbElems++;
                    606: 
                    607:     if (len > MAX_HASH_LEN)
                    608:        xmlHashGrow(table, MAX_HASH_LEN * table->size);
                    609: 
                    610:     return(0);
                    611: }
                    612: 
                    613: /**
                    614:  * xmlHashUpdateEntry3:
                    615:  * @table: the hash table
                    616:  * @name: the name of the userdata
                    617:  * @name2: a second name of the userdata
                    618:  * @name3: a third name of the userdata
                    619:  * @userdata: a pointer to the userdata
                    620:  * @f: the deallocator function for replaced item (if any)
                    621:  *
                    622:  * Add the @userdata to the hash @table. This can later be retrieved
                    623:  * by using the tuple (@name, @name2, @name3). Existing entry for this tuple
                    624:  * will be removed and freed with @f if found.
                    625:  *
                    626:  * Returns 0 the addition succeeded and -1 in case of error.
                    627:  */
                    628: int
                    629: xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name,
                    630:                   const xmlChar *name2, const xmlChar *name3,
                    631:                   void *userdata, xmlHashDeallocator f) {
                    632:     unsigned long key;
                    633:     xmlHashEntryPtr entry;
                    634:     xmlHashEntryPtr insert;
                    635: 
                    636:     if ((table == NULL) || name == NULL)
                    637:        return(-1);
                    638: 
                    639:     /*
                    640:      * If using a dict internalize if needed
                    641:      */
                    642:     if (table->dict) {
                    643:         if (!xmlDictOwns(table->dict, name)) {
                    644:            name = xmlDictLookup(table->dict, name, -1);
                    645:            if (name == NULL)
                    646:                return(-1);
                    647:        }
                    648:         if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) {
                    649:            name2 = xmlDictLookup(table->dict, name2, -1);
                    650:            if (name2 == NULL)
                    651:                return(-1);
                    652:        }
                    653:         if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) {
                    654:            name3 = xmlDictLookup(table->dict, name3, -1);
                    655:            if (name3 == NULL)
                    656:                return(-1);
                    657:        }
                    658:     }
                    659: 
                    660:     /*
                    661:      * Check for duplicate and insertion location.
                    662:      */
                    663:     key = xmlHashComputeKey(table, name, name2, name3);
                    664:     if (table->table[key].valid == 0) {
                    665:        insert = NULL;
                    666:     } else {
                    667:         if (table ->dict) {
                    668:            for (insert = &(table->table[key]); insert->next != NULL;
                    669:                 insert = insert->next) {
                    670:                if ((insert->name == name) &&
                    671:                    (insert->name2 == name2) &&
                    672:                    (insert->name3 == name3)) {
                    673:                    if (f)
                    674:                        f(insert->payload, insert->name);
                    675:                    insert->payload = userdata;
                    676:                    return(0);
                    677:                }
                    678:            }
                    679:            if ((insert->name == name) &&
                    680:                (insert->name2 == name2) &&
                    681:                (insert->name3 == name3)) {
                    682:                if (f)
                    683:                    f(insert->payload, insert->name);
                    684:                insert->payload = userdata;
                    685:                return(0);
                    686:            }
                    687:        } else {
                    688:            for (insert = &(table->table[key]); insert->next != NULL;
                    689:                 insert = insert->next) {
                    690:                if ((xmlStrEqual(insert->name, name)) &&
                    691:                    (xmlStrEqual(insert->name2, name2)) &&
                    692:                    (xmlStrEqual(insert->name3, name3))) {
                    693:                    if (f)
                    694:                        f(insert->payload, insert->name);
                    695:                    insert->payload = userdata;
                    696:                    return(0);
                    697:                }
                    698:            }
                    699:            if ((xmlStrEqual(insert->name, name)) &&
                    700:                (xmlStrEqual(insert->name2, name2)) &&
                    701:                (xmlStrEqual(insert->name3, name3))) {
                    702:                if (f)
                    703:                    f(insert->payload, insert->name);
                    704:                insert->payload = userdata;
                    705:                return(0);
                    706:            }
                    707:        }
                    708:     }
                    709: 
                    710:     if (insert == NULL) {
                    711:        entry =  &(table->table[key]);
                    712:     } else {
                    713:        entry = xmlMalloc(sizeof(xmlHashEntry));
                    714:        if (entry == NULL)
                    715:             return(-1);
                    716:     }
                    717: 
                    718:     if (table->dict != NULL) {
                    719:         entry->name = (xmlChar *) name;
                    720:         entry->name2 = (xmlChar *) name2;
                    721:         entry->name3 = (xmlChar *) name3;
                    722:     } else {
                    723:        entry->name = xmlStrdup(name);
                    724:        entry->name2 = xmlStrdup(name2);
                    725:        entry->name3 = xmlStrdup(name3);
                    726:     }
                    727:     entry->payload = userdata;
                    728:     entry->next = NULL;
                    729:     entry->valid = 1;
                    730:     table->nbElems++;
                    731: 
                    732: 
                    733:     if (insert != NULL) {
                    734:        insert->next = entry;
                    735:     }
                    736:     return(0);
                    737: }
                    738: 
                    739: /**
                    740:  * xmlHashLookup3:
                    741:  * @table: the hash table
                    742:  * @name: the name of the userdata
                    743:  * @name2: a second name of the userdata
                    744:  * @name3: a third name of the userdata
                    745:  *
                    746:  * Find the userdata specified by the (@name, @name2, @name3) tuple.
                    747:  *
                    748:  * Returns the a pointer to the userdata
                    749:  */
                    750: void *
                    751: xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name, 
                    752:               const xmlChar *name2, const xmlChar *name3) {
                    753:     unsigned long key;
                    754:     xmlHashEntryPtr entry;
                    755: 
                    756:     if (table == NULL)
                    757:        return(NULL);
                    758:     if (name == NULL)
                    759:        return(NULL);
                    760:     key = xmlHashComputeKey(table, name, name2, name3);
                    761:     if (table->table[key].valid == 0)
                    762:        return(NULL);
                    763:     if (table->dict) {
                    764:        for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
                    765:            if ((entry->name == name) &&
                    766:                (entry->name2 == name2) &&
                    767:                (entry->name3 == name3))
                    768:                return(entry->payload);
                    769:        }
                    770:     }
                    771:     for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
                    772:        if ((xmlStrEqual(entry->name, name)) &&
                    773:            (xmlStrEqual(entry->name2, name2)) &&
                    774:            (xmlStrEqual(entry->name3, name3)))
                    775:            return(entry->payload);
                    776:     }
                    777:     return(NULL);
                    778: }
                    779: 
                    780: /**
                    781:  * xmlHashQLookup3:
                    782:  * @table: the hash table
                    783:  * @prefix: the prefix of the userdata
                    784:  * @name: the name of the userdata
                    785:  * @prefix2: the second prefix of the userdata
                    786:  * @name2: a second name of the userdata
                    787:  * @prefix3: the third prefix of the userdata
                    788:  * @name3: a third name of the userdata
                    789:  *
                    790:  * Find the userdata specified by the (@name, @name2, @name3) tuple.
                    791:  *
                    792:  * Returns the a pointer to the userdata
                    793:  */
                    794: void *
                    795: xmlHashQLookup3(xmlHashTablePtr table,
                    796:                 const xmlChar *prefix, const xmlChar *name,
                    797:                const xmlChar *prefix2, const xmlChar *name2,
                    798:                const xmlChar *prefix3, const xmlChar *name3) {
                    799:     unsigned long key;
                    800:     xmlHashEntryPtr entry;
                    801: 
                    802:     if (table == NULL)
                    803:        return(NULL);
                    804:     if (name == NULL)
                    805:        return(NULL);
                    806:     key = xmlHashComputeQKey(table, prefix, name, prefix2,
                    807:                              name2, prefix3, name3);
                    808:     if (table->table[key].valid == 0)
                    809:        return(NULL);
                    810:     for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
                    811:        if ((xmlStrQEqual(prefix, name, entry->name)) &&
                    812:            (xmlStrQEqual(prefix2, name2, entry->name2)) &&
                    813:            (xmlStrQEqual(prefix3, name3, entry->name3)))
                    814:            return(entry->payload);
                    815:     }
                    816:     return(NULL);
                    817: }
                    818: 
                    819: typedef struct {
                    820:     xmlHashScanner hashscanner;
                    821:     void *data;
                    822: } stubData;
                    823: 
                    824: static void 
                    825: stubHashScannerFull (void *payload, void *data, const xmlChar *name, 
                    826:                      const xmlChar *name2 ATTRIBUTE_UNUSED,
                    827:                     const xmlChar *name3 ATTRIBUTE_UNUSED) {
                    828:     stubData *stubdata = (stubData *) data;
                    829:     stubdata->hashscanner (payload, stubdata->data, (xmlChar *) name);
                    830: }                                  
                    831:  
                    832: /**
                    833:  * xmlHashScan:
                    834:  * @table: the hash table
                    835:  * @f:  the scanner function for items in the hash
                    836:  * @data:  extra data passed to f
                    837:  *
                    838:  * Scan the hash @table and applied @f to each value.
                    839:  */
                    840: void
                    841: xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) {
                    842:     stubData stubdata;
                    843:     stubdata.data = data;
                    844:     stubdata.hashscanner = f; 
                    845:     xmlHashScanFull (table, stubHashScannerFull, &stubdata);
                    846: }
                    847: 
                    848: /**
                    849:  * xmlHashScanFull:
                    850:  * @table: the hash table
                    851:  * @f:  the scanner function for items in the hash
                    852:  * @data:  extra data passed to f
                    853:  *
                    854:  * Scan the hash @table and applied @f to each value.
                    855:  */
                    856: void
                    857: xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) {
                    858:     int i, nb;
                    859:     xmlHashEntryPtr iter;
                    860:     xmlHashEntryPtr next;
                    861: 
                    862:     if (table == NULL)
                    863:        return;
                    864:     if (f == NULL)
                    865:        return;
                    866: 
                    867:     if (table->table) {
                    868:        for(i = 0; i < table->size; i++) {
                    869:            if (table->table[i].valid == 0) 
                    870:                continue;
                    871:            iter = &(table->table[i]);
                    872:            while (iter) {
                    873:                next = iter->next;
                    874:                 nb = table->nbElems;
                    875:                if ((f != NULL) && (iter->payload != NULL))
                    876:                    f(iter->payload, data, iter->name,
                    877:                      iter->name2, iter->name3);
                    878:                 if (nb != table->nbElems) {
                    879:                     /* table was modified by the callback, be careful */
                    880:                     if (iter == &(table->table[i])) {
                    881:                         if (table->table[i].valid == 0)
                    882:                             iter = NULL;
                    883:                         if (table->table[i].next != next)
                    884:                            iter = &(table->table[i]);
                    885:                     } else
                    886:                        iter = next;
                    887:                 } else
                    888:                    iter = next;
                    889:            }
                    890:        }
                    891:     }
                    892: }
                    893: 
                    894: /**
                    895:  * xmlHashScan3:
                    896:  * @table: the hash table
                    897:  * @name: the name of the userdata or NULL
                    898:  * @name2: a second name of the userdata or NULL
                    899:  * @name3: a third name of the userdata or NULL
                    900:  * @f:  the scanner function for items in the hash
                    901:  * @data:  extra data passed to f
                    902:  *
                    903:  * Scan the hash @table and applied @f to each value matching
                    904:  * (@name, @name2, @name3) tuple. If one of the names is null,
                    905:  * the comparison is considered to match.
                    906:  */
                    907: void
                    908: xmlHashScan3(xmlHashTablePtr table, const xmlChar *name, 
                    909:             const xmlChar *name2, const xmlChar *name3,
                    910:             xmlHashScanner f, void *data) {
                    911:     xmlHashScanFull3 (table, name, name2, name3,
                    912:                      (xmlHashScannerFull) f, data);
                    913: }
                    914: 
                    915: /**
                    916:  * xmlHashScanFull3:
                    917:  * @table: the hash table
                    918:  * @name: the name of the userdata or NULL
                    919:  * @name2: a second name of the userdata or NULL
                    920:  * @name3: a third name of the userdata or NULL
                    921:  * @f:  the scanner function for items in the hash
                    922:  * @data:  extra data passed to f
                    923:  *
                    924:  * Scan the hash @table and applied @f to each value matching
                    925:  * (@name, @name2, @name3) tuple. If one of the names is null,
                    926:  * the comparison is considered to match.
                    927:  */
                    928: void
                    929: xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name, 
                    930:                 const xmlChar *name2, const xmlChar *name3,
                    931:                 xmlHashScannerFull f, void *data) {
                    932:     int i;
                    933:     xmlHashEntryPtr iter;
                    934:     xmlHashEntryPtr next;
                    935: 
                    936:     if (table == NULL)
                    937:        return;
                    938:     if (f == NULL)
                    939:        return;
                    940: 
                    941:     if (table->table) {
                    942:        for(i = 0; i < table->size; i++) {
                    943:            if (table->table[i].valid == 0)
                    944:                continue;
                    945:            iter = &(table->table[i]);
                    946:            while (iter) {
                    947:                next = iter->next;
                    948:                if (((name == NULL) || (xmlStrEqual(name, iter->name))) &&
                    949:                    ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) &&
                    950:                    ((name3 == NULL) || (xmlStrEqual(name3, iter->name3))) &&
                    951:                    (iter->payload != NULL)) {
                    952:                    f(iter->payload, data, iter->name,
                    953:                      iter->name2, iter->name3);
                    954:                }
                    955:                iter = next;
                    956:            }
                    957:        }
                    958:     }
                    959: }
                    960: 
                    961: /**
                    962:  * xmlHashCopy:
                    963:  * @table: the hash table
                    964:  * @f:  the copier function for items in the hash
                    965:  *
                    966:  * Scan the hash @table and applied @f to each value.
                    967:  *
                    968:  * Returns the new table or NULL in case of error.
                    969:  */
                    970: xmlHashTablePtr
                    971: xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f) {
                    972:     int i;
                    973:     xmlHashEntryPtr iter;
                    974:     xmlHashEntryPtr next;
                    975:     xmlHashTablePtr ret;
                    976: 
                    977:     if (table == NULL)
                    978:        return(NULL);
                    979:     if (f == NULL)
                    980:        return(NULL);
                    981: 
                    982:     ret = xmlHashCreate(table->size);
                    983:     if (table->table) {
                    984:        for(i = 0; i < table->size; i++) {
                    985:            if (table->table[i].valid == 0)
                    986:                continue;
                    987:            iter = &(table->table[i]);
                    988:            while (iter) {
                    989:                next = iter->next;
                    990:                xmlHashAddEntry3(ret, iter->name, iter->name2,
                    991:                                 iter->name3, f(iter->payload, iter->name));
                    992:                iter = next;
                    993:            }
                    994:        }
                    995:     }
                    996:     ret->nbElems = table->nbElems;
                    997:     return(ret);
                    998: }
                    999: 
                   1000: /**
                   1001:  * xmlHashSize:
                   1002:  * @table: the hash table
                   1003:  *
                   1004:  * Query the number of elements installed in the hash @table.
                   1005:  *
                   1006:  * Returns the number of elements in the hash table or
                   1007:  * -1 in case of error
                   1008:  */
                   1009: int
                   1010: xmlHashSize(xmlHashTablePtr table) {
                   1011:     if (table == NULL)
                   1012:        return(-1);
                   1013:     return(table->nbElems);
                   1014: }
                   1015: 
                   1016: /**
                   1017:  * xmlHashRemoveEntry:
                   1018:  * @table: the hash table
                   1019:  * @name: the name of the userdata
                   1020:  * @f: the deallocator function for removed item (if any)
                   1021:  *
                   1022:  * Find the userdata specified by the @name and remove
                   1023:  * it from the hash @table. Existing userdata for this tuple will be removed
                   1024:  * and freed with @f.
                   1025:  *
                   1026:  * Returns 0 if the removal succeeded and -1 in case of error or not found.
                   1027:  */
                   1028: int xmlHashRemoveEntry(xmlHashTablePtr table, const xmlChar *name,
                   1029:                       xmlHashDeallocator f) {
                   1030:     return(xmlHashRemoveEntry3(table, name, NULL, NULL, f));
                   1031: }
                   1032: 
                   1033: /**
                   1034:  * xmlHashRemoveEntry2:
                   1035:  * @table: the hash table
                   1036:  * @name: the name of the userdata
                   1037:  * @name2: a second name of the userdata
                   1038:  * @f: the deallocator function for removed item (if any)
                   1039:  *
                   1040:  * Find the userdata specified by the (@name, @name2) tuple and remove
                   1041:  * it from the hash @table. Existing userdata for this tuple will be removed
                   1042:  * and freed with @f.
                   1043:  *
                   1044:  * Returns 0 if the removal succeeded and -1 in case of error or not found.
                   1045:  */
                   1046: int
                   1047: xmlHashRemoveEntry2(xmlHashTablePtr table, const xmlChar *name,
                   1048:                        const xmlChar *name2, xmlHashDeallocator f) {
                   1049:     return(xmlHashRemoveEntry3(table, name, name2, NULL, f));
                   1050: }
                   1051: 
                   1052: /**
                   1053:  * xmlHashRemoveEntry3:
                   1054:  * @table: the hash table
                   1055:  * @name: the name of the userdata
                   1056:  * @name2: a second name of the userdata
                   1057:  * @name3: a third name of the userdata
                   1058:  * @f: the deallocator function for removed item (if any)
                   1059:  *
                   1060:  * Find the userdata specified by the (@name, @name2, @name3) tuple and remove
                   1061:  * it from the hash @table. Existing userdata for this tuple will be removed
                   1062:  * and freed with @f.
                   1063:  *
                   1064:  * Returns 0 if the removal succeeded and -1 in case of error or not found.
                   1065:  */
                   1066: int
                   1067: xmlHashRemoveEntry3(xmlHashTablePtr table, const xmlChar *name,
                   1068:     const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f) {
                   1069:     unsigned long key;
                   1070:     xmlHashEntryPtr entry;
                   1071:     xmlHashEntryPtr prev = NULL;
                   1072: 
                   1073:     if (table == NULL || name == NULL)
                   1074:         return(-1);
                   1075: 
                   1076:     key = xmlHashComputeKey(table, name, name2, name3);
                   1077:     if (table->table[key].valid == 0) {
                   1078:         return(-1);
                   1079:     } else {
                   1080:         for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
                   1081:             if (xmlStrEqual(entry->name, name) &&
                   1082:                     xmlStrEqual(entry->name2, name2) &&
                   1083:                     xmlStrEqual(entry->name3, name3)) {
                   1084:                 if ((f != NULL) && (entry->payload != NULL))
                   1085:                     f(entry->payload, entry->name);
                   1086:                 entry->payload = NULL;
                   1087:                if (table->dict == NULL) {
                   1088:                    if(entry->name)
                   1089:                        xmlFree(entry->name);
                   1090:                    if(entry->name2)
                   1091:                        xmlFree(entry->name2);
                   1092:                    if(entry->name3)
                   1093:                        xmlFree(entry->name3);
                   1094:                }
                   1095:                 if(prev) {
                   1096:                     prev->next = entry->next;
                   1097:                    xmlFree(entry);
                   1098:                } else {
                   1099:                    if (entry->next == NULL) {
                   1100:                        entry->valid = 0;
                   1101:                    } else {
                   1102:                        entry = entry->next;
                   1103:                        memcpy(&(table->table[key]), entry, sizeof(xmlHashEntry));
                   1104:                        xmlFree(entry);
                   1105:                    }
                   1106:                }
                   1107:                 table->nbElems--;
                   1108:                 return(0);
                   1109:             }
                   1110:             prev = entry;
                   1111:         }
                   1112:         return(-1);
                   1113:     }
                   1114: }
                   1115: 
                   1116: #define bottom_hash
                   1117: #include "elfgcchack.h"

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>