/*

 * hash.c: chained hash tables

 *

 * Reference: Your favorite introductory book on algorithms

 *

 * Copyright (C) 2000 Bjorn Reese and Daniel Veillard.

 *

 * Permission to use, copy, modify, and distribute this software for any

 * purpose with or without fee is hereby granted, provided that the above

 * copyright notice and this permission notice appear in all copies.

 *

 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED

 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF

 * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND

 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.

 *

 * Author: breese@users.sourceforge.net

 */

#define IN_LIBXML

#include "XmlEnglibxml.h"

#include <string.h>

#include "Libxml2_globals.h"

#define MAX_HASH_LEN 8

/* #define DEBUG_GROW */

/*

 * A single entry in the hash table

 */

typedef struct _xmlHashEntry xmlHashEntry;

typedef xmlHashEntry *xmlHashEntryPtr;

struct _xmlHashEntry {

    struct _xmlHashEntry *next;

    xmlChar *name;

    xmlChar *name2;

    xmlChar *name3;

    void *payload;

    int valid;

};

/*

 * The entire hash table

 */

struct _xmlHashTable {

    struct _xmlHashEntry *table;

    int size;

    int nbElems;

};

/*

 * xmlHashComputeKey:

 * Calculate the hash key

 *

 * OOM: never

 */

static unsigned long

xmlHashComputeKey(xmlHashTablePtr table, const xmlChar *name,

              const xmlChar *name2, const xmlChar *name3) {

    unsigned long value = 0L;

    char ch;

    if (name != NULL) {

    value += 30 * (*name);

    while ((ch = *name++) != 0) {

        value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);

    }

    }

    if (name2 != NULL) {

    while ((ch = *name2++) != 0) {

        value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);

    }

    }

    if (name3 != NULL) {

    while ((ch = *name3++) != 0) {

        value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);

    }

    }

    return (value % table->size);

}

static unsigned long

xmlHashComputeQKey(xmlHashTablePtr table,

           const xmlChar *prefix, const xmlChar *name,

           const xmlChar *prefix2, const xmlChar *name2,

           const xmlChar *prefix3, const xmlChar *name3) {

    unsigned long value = 0L;

    char ch;

    if (prefix != NULL)

    value += 30 * (*prefix);

    else

    value += 30 * (*name);

    if (prefix != NULL) {

    while ((ch = *prefix++) != 0) {

        value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);

    }

    value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');

    }

    if (name != NULL) {

    while ((ch = *name++) != 0) {

        value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);

    }

    }

    if (prefix2 != NULL) {

    while ((ch = *prefix2++) != 0) {

        value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);

    }

    value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');

    }

    if (name2 != NULL) {

    while ((ch = *name2++) != 0) {

        value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);

    }

    }

    if (prefix3 != NULL) {

    while ((ch = *prefix3++) != 0) {

        value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);

    }

    value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');

    }

    if (name3 != NULL) {

    while ((ch = *name3++) != 0) {

        value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);

    }

    }

    return (value % table->size);

}

/**

 * xmlHashCreate:

 * @size: the size of the hash table

 *

 * Create a new xmlHashTablePtr.

 *

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

 *

 * OOM: possible --> returns NULL, OOM flag is set

 */

xmlHashTablePtr

xmlHashCreate(int size) {

    xmlHashTablePtr table;

    if (size <= 0)

        size = 256;

    table = (xmlHashTablePtr) xmlMalloc(sizeof(xmlHashTable));

    if (table) {

        table->size = size;

        table->nbElems = 0;

        table->table = (xmlHashEntryPtr)xmlMalloc(size * sizeof(xmlHashEntry)); // may set OOM flag

        if (table->table) {

            memset(table->table, 0, size * sizeof(xmlHashEntry));

            return(table);

        }

        xmlFree(table);

    }

    return(NULL);

}

/**

 * xmlHashGrow:

 * @table: the hash table

 * @size: the new size of the hash table

 *

 * resize the hash table

 *

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

 *

 * OOM: possible --> sets OOM flag when returns -1

 */

static int

xmlHashGrow(xmlHashTablePtr table, int size) {

    unsigned long key;

    int oldsize, i;

    xmlHashEntryPtr iter, next;

    struct _xmlHashEntry *oldtable;

#ifdef DEBUG_GROW

    unsigned long nbElem = 0;

#endif

    if (table == NULL)

        return(-1);

    if (size < 8)

        return(-1);

    if (size > 8 * 2048)

        return(-1);

    oldsize = table->size;

    oldtable = table->table;

    if (oldtable == NULL)

        return(-1);

    table->table = (xmlHashEntryPtr)xmlMalloc(size * sizeof(xmlHashEntry)); // may set OOM flag

    if (table->table == NULL) {

        table->table = oldtable;

        return(-1);

    }

    memset(table->table, 0, size * sizeof(xmlHashEntry));

    table->size = size;

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

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

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

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

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

    */

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

        // TODO: OPTIMIZE: cache reference to oldtable[i]

        if (oldtable[i].valid == 0)

            continue;

        key = xmlHashComputeKey(

                    table, 

                    oldtable[i].name, 

                    oldtable[i].name2,

                    oldtable[i].name3);

        memcpy(&(table->table[key]), &(oldtable[i]), sizeof(xmlHashEntry));

        table->table[key].next = NULL;

    }

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

        iter = oldtable[i].next;

        while (iter) {

            next = iter->next;

            /*

            * put back the entry in the new table

            */

            key = xmlHashComputeKey(

                    table, 

                    iter->name, 

                    iter->name2,

                    iter->name3);

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

                memcpy(&(table->table[key]), iter, sizeof(xmlHashEntry));

                table->table[key].next = NULL;

                xmlFree(iter);

            } else {

                iter->next = table->table[key].next;

                table->table[key].next = iter;

            }

#ifdef DEBUG_GROW

            nbElem++;

#endif

            iter = next;

        }

    }

    xmlFree(oldtable);

#ifdef DEBUG_GROW

    xmlGenericError(xmlGenericErrorContext,

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

#endif

    return(0);

}

/**

 * xmlHashFree:

 * @table: the hash table

 * @f:  the deallocator function for items in the hash

 *

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

 * deallocated with @f if provided.

 *

 * OOM: never //  same as argument 'f' has when f!=NULL

 */

void

xmlHashFree(xmlHashTablePtr table, xmlHashDeallocator f) {

    int i;

    xmlHashEntryPtr iter;

    xmlHashEntryPtr next;

    int inside_table = 0;

    int nbElems;

    if (table == NULL)

        return;

    if (table->table) {

    nbElems = table->nbElems;

    for(i = 0; (i < table->size) && (nbElems > 0); i++) {

        iter = &(table->table[i]);

        if (iter->valid == 0)

        continue;

        inside_table = 1;

        while (iter) {

        next = iter->next;

        if ((f != NULL) && (iter->payload != NULL))

            f(iter->payload, iter->name);

        if (iter->name)

            xmlFree(iter->name);

        if (iter->name2)

            xmlFree(iter->name2);

        if (iter->name3)

            xmlFree(iter->name3);

        iter->payload = NULL;

        if (!inside_table)

            xmlFree(iter);

        nbElems--;

        inside_table = 0;

        iter = next;

        }

        inside_table = 0;

    }

    xmlFree(table->table);

    }

    xmlFree(table);

}

/**

 * xmlHashAddEntry:

 * @table: the hash table

 * @name: the name of the userdata

 * @userdata: a pointer to the userdata

 *

 * Add the @userdata to the hash @table. This can later be retrieved

 * by using the @name. Duplicate names generate errors.

 *

 * Returns 0 the addition succeeded and -1 in case of error.

 *

 * OOM: iif returns -1 and flag is set

 */

int

xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) {

    return(xmlHashAddEntry3(table, name, NULL, NULL, userdata));

}

/**

 * xmlHashAddEntry2:

 * @table: the hash table

 * @name: the name of the userdata

 * @name2: a second name of the userdata

 * @userdata: a pointer to the userdata

 *

 * Add the @userdata to the hash @table. This can later be retrieved

 * by using the (@name, @name2) tuple. Duplicate tuples generate errors.

 *

 * Returns 0 the addition succeeded and -1 in case of error.

 */

int

xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name,

            const xmlChar *name2, void *userdata) {

    return(xmlHashAddEntry3(table, name, name2, NULL, userdata));

}

/**

 * xmlHashUpdateEntry:

 * @table: the hash table

 * @name: the name of the userdata

 * @userdata: a pointer to the userdata

 * @f: the deallocator function for replaced item (if any)

 *

 * Add the @userdata to the hash @table. This can later be retrieved

 * by using the @name. Existing entry for this @name will be removed

 * and freed with @f if found.

 *

 * Returns 0 the addition succeeded and -1 in case of error.

 */

int

xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name,

               void *userdata, xmlHashDeallocator f) {

    return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f));

}

/**

 * xmlHashUpdateEntry2:

 * @table: the hash table

 * @name: the name of the userdata

 * @name2: a second name of the userdata

 * @userdata: a pointer to the userdata

 * @f: the deallocator function for replaced item (if any)

 *

 * Add the @userdata to the hash @table. This can later be retrieved

 * by using the (@name, @name2) tuple. Existing entry for this tuple will

 * be removed and freed with @f if found.

 *

 * Returns 0 the addition succeeded and -1 in case of error.

 */

int

xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name,

               const xmlChar *name2, void *userdata,

           xmlHashDeallocator f) {

    return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f));

}

/**

 * xmlHashLookup:

 * @table: the hash table

 * @name: the name of the userdata

 *

 * Find the userdata specified by the @name.

 *

 * Returns the pointer to the userdata

 */

void *

xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) {

    return(xmlHashLookup3(table, name, NULL, NULL));

}

/**

 * xmlHashLookup2:

 * @table: the hash table

 * @name: the name of the userdata

 * @name2: a second name of the userdata

 *

 * Find the userdata specified by the (@name, @name2) tuple.

 *

 * Returns the pointer to the userdata

 *

 * OOM: never

 */

void*

xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name,

          const xmlChar *name2) {

    return(xmlHashLookup3(table, name, name2, NULL));

}

#ifndef XMLENGINE_EXCLUDE_UNUSED

/**

 * xmlHashQLookup:

 * @table: the hash table

 * @prefix: the prefix of the userdata

 * @name: the name of the userdata

 *

 * Find the userdata specified by the QName @prefix:@name/@name.

 *

 * Returns the pointer to the userdata

 *

 * OOM: never

 */

void*

xmlHashQLookup(xmlHashTablePtr table, const xmlChar *prefix,

               const xmlChar *name) {

    return(xmlHashQLookup3(table, prefix, name, NULL, NULL, NULL, NULL));

}

#endif /* ifndef XMLENGINE_EXCLUDE_UNUSED */

/**

 * xmlHashQLookup2:

 * @table: the hash table

 * @prefix: the prefix of the userdata

 * @name: the name of the userdata

 * @prefix2: the second prefix of the userdata

 * @name2: a second name of the userdata

 *

 * Find the userdata specified by the QNames tuple

 *

 * Returns the pointer to the userdata

 */

void *

xmlHashQLookup2(xmlHashTablePtr table, const xmlChar *prefix,

                const xmlChar *name, const xmlChar *prefix2,

            const xmlChar *name2) {

    return(xmlHashQLookup3(table, prefix, name, prefix2, name2, NULL, NULL));

}

/**

 * xmlHashAddEntry3:

 * @table: the hash table

 * @name: the name of the userdata

 * @name2: a second name of the userdata

 * @name3: a third name of the userdata

 * @userdata: a pointer to the userdata

 *

 * Add the @userdata to the hash @table. This can later be retrieved

 * by using the tuple (@name, @name2, @name3). Duplicate entries generate

 * errors.

 *

 * Returns 0 the addition succeeded and -1 in case of error.

 *

 * OOM: iif returns -1 and flag is set

 */

int

xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name,

             const xmlChar *name2, const xmlChar *name3,

         void *userdata) {

    unsigned long key, len = 0;

    xmlHashEntryPtr entry;

    xmlHashEntryPtr insert;

    int res;

    if ((table == NULL) || name == NULL)

        return(-1);

    /*

     * Check for duplicate and insertion location.

     */

    key = xmlHashComputeKey(table, name, name2, name3);

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

        insert = NULL;

    } else {

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

            insert = insert->next) {

            if ((xmlStrEqual(insert->name, name)) &&

            (xmlStrEqual(insert->name2, name2)) &&

            (xmlStrEqual(insert->name3, name3)))

            return(-1);

            len++;

        }

        if ((xmlStrEqual(insert->name, name)) &&

            (xmlStrEqual(insert->name2, name2)) &&

            (xmlStrEqual(insert->name3, name3)))

            return(-1);

    }

    if (insert == NULL) {

        entry = &(table->table[key]);

    } else {

        entry = (xmlHashEntryPtr) xmlMalloc(sizeof(xmlHashEntry)); // may set OOM flag

        if (entry == NULL)

            return(-1);

    }

    // TODO: Check OOM

    entry->name = xmlStrdup(name);

    entry->name2 = xmlStrdup(name2);

    entry->name3 = xmlStrdup(name3);

    if(OOM_FLAG){

        if(entry->name)  xmlFree(entry->name);

        if(entry->name2) xmlFree(entry->name2);

        if(entry->name3) xmlFree(entry->name3);

        if(insert) xmlFree(entry);

        return -1;

    }

    entry->payload = userdata;

    entry->next = NULL;