/*

 *  This program is free software; you can redistribute it and/or modify

 *  it under the terms of the GNU General Public License as published by

 *  the Free Software Foundation; either version 2 of the License, or

 *  (at your option) any later version.

 *

 *  This program is distributed in the hope that it will be useful,

 *  but WITHOUT ANY WARRANTY; without even the implied warranty of

 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 *  GNU General Public License for more details.

 *

 *  You should have received a copy of the GNU General Public License

 *  along with this program; if not, write to the Free Software

 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

 *

 * Copyrights

 *

 * Portions created by or assigned to Jabber.com, Inc. are 

 * Copyright (c) 1999-2002 Jabber.com, Inc.  All Rights Reserved.  Contact

 * information for Jabber.com, Inc. is available at http://www.jabber.com/.

 *

 * Portions Copyright (c) 1998-1999 Jeremie Miller.

 *

 * Acknowledgements

 *

 * Special thanks to the Jabber Open Source Contributors for their

 * suggestions and support of Jabber.

 *

 */

#include <libxode.h>

/*****************************************************************************

 * Internal type definitions

 */

typedef struct tagHNODE

{

    struct tagHNODE *next;             /* next node in list */

    const void *key;                   /* key pointer */

    void *value;                       /* value pointer */

} HNODE;

#define SLAB_NUM_NODES     64        /* allocate this many nodes per slab */

typedef struct tagHSLAB

{

    struct tagHSLAB *next;             /* next slab pointer */

    HNODE nodes[SLAB_NUM_NODES];       /* the actual nodes */

} HSLAB;

#define HASH_NUM_BUCKETS   509       /* should be a prime number; see Knuth */

typedef struct tagHASHTABLE_INTERNAL

{

    unsigned long sig1;                /* first signature word */

    KEYHASHFUNC hash;                  /* hash function */

    KEYCOMPAREFUNC cmp;                /* comparison function */

    int count;                         /* table entry count */

    int bcount;                        /* bucket count */

    HNODE **buckets;                   /* the hash buckets */

    unsigned long sig2;                /* second signature word */

} HASHTABLE_INTERNAL;

#define HASH_SIG1      0x68736148UL  /* "Hash" */

#define HASH_SIG2      0x6F627245UL  /* "Erbo" */

#define do_hash(tb,key)     ((*((tb)->hash))(key) % ((tb)->bcount))

static HNODE *s_free_nodes = NULL;   /* free nodes list */

static HSLAB *s_slabs = NULL;        /* node slabs list */

/*****************************************************************************

 * Internal functions

 */

static HNODE *allocate_node(

    const void *key,   /* key pointer for this node */

    void *value)       /* value pointer for this node */

/*

    allocate_node allocates a new hash node and fills it.  Returns NULL if the

    node could not be allocated.

*/

{

    HNODE *rc;   /* return from this function */

    if (!s_free_nodes)

    { /* allocate a new slabful of nodes and chain them to make a new free list */

        register int i;  /* loop counter */

        HSLAB *slab = (HSLAB *)malloc(sizeof(HSLAB));

        if (!slab)

            return NULL;

        memset(slab,0,sizeof(HSLAB));

        slab->next = s_slabs;

        for (i=0; i<(SLAB_NUM_NODES-1); i++)

            slab->nodes[i].next = &(slab->nodes[i+1]);

        s_free_nodes = &(slab->nodes[0]);

        s_slabs = slab;

    } /* end if */

    /* grab a node off the fron of the free list and fill it */

    rc = s_free_nodes;

    s_free_nodes = rc->next;

    rc->next = NULL;

    rc->key = key;

    rc->value = value;

    return rc;

} /* end allocate_node */

static void free_node(

    HNODE *node)   /* node to be freed */

/*

    free_node returns a hash node to the list.

*/

{

    /* zap the node contents to avoid problems later */

    memset(node,0,sizeof(HNODE));

    /* chain it onto the free list */

    node->next = s_free_nodes;

    s_free_nodes = node;

} /* end free_node */

static HNODE *find_node(

    HASHTABLE_INTERNAL *tab,  /* pointer to hash table */

    const void *key,          /* key value to look up */

    int bucket)               /* bucket number (-1 to have function compute it) */

/*

    find_node walks a hash bucket to find a node whose key matches the named key value.

    Returns the node pointer, or NULL if it's not found.

*/

{

    register HNODE *p;  /* search pointer/return from this function */

    if (bucket<0)  /* compute hash value if we don't know it already */

        bucket = do_hash(tab,key);

    /* search through the bucket contents */

    for (p=tab->buckets[bucket]; p; p=p->next)

        if ((*(tab->cmp))(key,p->key)==0)

            return p;  /* found! */

    return NULL;   /* not found */

} /* end find_node */

static HASHTABLE_INTERNAL *handle2ptr(

    HASHTABLE tbl)  /* hash table handle */

/*

    handle2ptr converts a hash table handle into a pointer and checks its signatures

    to make sure someone's not trying to pull a whizzer on this module.

*/

{

    register HASHTABLE_INTERNAL *rc = (HASHTABLE_INTERNAL *)tbl;

    if ((rc->sig1==HASH_SIG1) && (rc->sig2==HASH_SIG2))

        return rc;     /* signatures match */

    else

        return NULL;   /* yIkes! */

}

/*****************************************************************************

 * External functions

 */

HASHTABLE ghash_create(int buckets, KEYHASHFUNC hash, KEYCOMPAREFUNC cmp)

/*

    Description:

        Creates a new hash table.

    Input:

        Parameters:

        buckets - Number of buckets to allocate for the hash table; this value

                  should be a prime number for maximum efficiency.

        hash - Key hash code function to use.

        cmp - Key comparison function to use.

    Output:

        Returns:

        NULL - Table could not be allocated.

        Other - Handle to the new hashtable.

*/

{

    HASHTABLE_INTERNAL *tab;  /* new table structure */

    char *allocated;

    if (!hash || !cmp)

        return NULL;  /* bogus! */

    if (buckets<=0)

        buckets = HASH_NUM_BUCKETS;

    /* allocate a hash table structure */

    allocated = malloc(sizeof(HASHTABLE_INTERNAL) + (buckets * sizeof(HNODE *)));

    if (!allocated)

        return NULL;  /* memory error */

    /* fill the fields of the hash table */

    tab = (HASHTABLE_INTERNAL *)allocated;

    allocated += sizeof(HASHTABLE_INTERNAL);

    memset(tab,0,sizeof(HASHTABLE_INTERNAL));

    memset(allocated,0,buckets * sizeof(HNODE *));

    tab->sig1 = HASH_SIG1;

    tab->hash = hash;

    tab->cmp = cmp;

    tab->bcount = buckets;

    tab->buckets = (HNODE **)allocated;

    tab->sig2 = HASH_SIG2;

    return (HASHTABLE)tab;  /* Qa'pla! */

} /* end ghash_create */

void ghash_destroy(HASHTABLE tbl)

/*

    Description:

        Destroys a hash table.

    Input:

        Parameters:

        tbl - Table to be destroyed.

    Output:

        Returns:

        Nothing.

*/

{

    HASHTABLE_INTERNAL *tab;  /* new table structure */

    int i;                    /* loop counter */

    HNODE *p, *p2;            /* temporary pointers */

    if (!tbl)

        return;  /* bogus! */

    /* Convert the handle to a table pointer. */

    tab = handle2ptr(tbl);

    if (!tab)

        return;

    /* Nuke the nodes it contains. */

    for (i=0; i<tab->bcount; i++)

    { /* free the contents of each bucket */

        p = tab->buckets[i];

        while (p)

        { /* free each node in turn */

            p2 = p->next;

            free_node(p);

            p = p2;

        } /* end while */

    } /* end for */

    free(tab);  /* bye bye now! */

} /* end ghash_destroy */

void *ghash_get(HASHTABLE tbl, const void *key)

/*

    Description:

        Retrieves a value stored in the hash table.

    Input:

        Parameters:

        tbl - The hash table to look in.

        key - The key value to search on.

    Output:

        Returns:

        NULL - Value not found.

        Other - Value corresponding to the specified key.

*/

{

    HASHTABLE_INTERNAL *tab;  /* internal table pointer */

    HNODE *node;              /* hash node */

    void *rc = NULL;          /* return from this function */

    if (!tbl || !key)

        return NULL;  /* bogus! */

    /* Convert the handle to a table pointer. */

    tab = handle2ptr(tbl);

    if (!tab)

        return NULL;  /* error */

    /* Attempt to find the node. */

    node = find_node(tab,key,-1);

    if (node)

        rc = node->value;  /* found it! */

    return rc;

} /* end ghash_get */

int ghash_put(HASHTABLE tbl, const void *key, void *value)

/*

    Description:

        Associates a key with a value in this hash table.

    Input:

        Parameters:

        tbl - Hash table to add.

        key - Key to use for the value in the table.

        value - Value to add for this key.

    Output:

        Returns:

        1 - Success.

        0 - Failure.

    Notes:

        If the specified key is already in the hashtable, its value will be replaced.

*/

{

    HASHTABLE_INTERNAL *tab;  /* internal table pointer */

    int bucket;               /* bucket value goes into */

    HNODE *node;              /* hash node */

    int rc = 1;               /* return from this function */

    if (!tbl || !key || !value)

        return 0;  /* bogus! */

    /* Convert the handle to a table pointer. */

    tab = handle2ptr(tbl);

    if (!tab)

        return 0;  /* error */

    /* Compute the hash bucket and try to find an existing node. */

    bucket = do_hash(tab,key);

    node = find_node(tab,key,bucket);

    if (!node)

    { /* OK, try to allocate a new node. */

        node = allocate_node(key,value);

        if (node)

        { /* Chain the new node into the hash table. */

            node->next = tab->buckets[bucket];

            tab->buckets[bucket] = node;

            tab->count++;

        } /* end if */

        else  /* allocation error */

            rc = 0;

    } /* end if */

    else  /* already in table - just reassign value */

        node->value = value;

    return rc;

} /* end ghash_put */

int ghash_remove(HASHTABLE tbl, const void *key)

/*

    Description:

        Removes an entry from a hash table, given its key.

    Input:

        Parameters:

        tbl - Hash table to remove from.

        key - Key of value to remove.

    Output:

        Returns:

        1 - Success.

        0 - Failure; key not present in hash table.

*/

{

    HASHTABLE_INTERNAL *tab;  /* internal table pointer */

    int bucket;               /* bucket value goes into */

    HNODE *node;              /* hash node */

    register HNODE *p;        /* removal pointer */

    int rc = 1;               /* return from this function */

    if (!tbl || !key)

        return 0;  /* bogus! */

    /* Convert the handle to a table pointer. */

    tab = handle2ptr(tbl);

    if (!tab)

        return 0;  /* error */

    /* Compute the hash bucket and try to find an existing node. */

    bucket = do_hash(tab,key);

    node = find_node(tab,key,bucket);

    if (node)

    { /* look to unchain it from the bucket it's in */

        if (node==tab->buckets[bucket])

            tab->buckets[bucket] = node->next;  /* unchain at head */

        else

        { /* unchain in middle of list */

            for (p=tab->buckets[bucket]; p->next!=node; p=p->next) ;

            p->next = node->next;

        } /* end else */

        free_node(node);  /* bye bye now! */

        tab->count--;

    } /* end if */

    else  /* node not found */

        rc = 0;

    return rc;

} /* end ghash_remove */

int ghash_walk(HASHTABLE tbl, TABLEWALKFUNC func, void *user_data)

/*

    Description:

        "Walks" through a hash table, calling a callback function for each element

    stored in it.

    Input:

        Parameters:

        tbl - Hash table to walk.

        func - Function to be called for each node.  It takes three parameters,

                   a user data pointer, a key value pointer, and a data value pointer.

           It returns 0 to stop the enumeration or 1 to keep it going.

        user_data - Value to use as the first parameter for the callback

                    function.

    Output:

        Returns:

        0 - Error occurred.

        Other - Number of nodes visited up to and including the one for which

                the callback function returned 0, if it did; ranges from 1

            to the number of nodes in the hashtable.

*/

{

    HASHTABLE_INTERNAL *tab;  /* internal table pointer */

    int i;                    /* loop counter */

    int running = 1;          /* we're still running */

    int count = 0;            /* number of nodes visited before stop node */

    register HNODE *p, *p2;   /* loop pointer */

    if (!tbl || !func)

        return -1;  /* bogus values! */