--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/mcabber/libjabber/genhash.c	Sun Mar 27 20:18:21 2005 +0000
@@ -0,0 +1,490 @@
+/*
+ *  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.
+ *
+ *  Jabber
+ *  Copyright (C) 1998-1999 The Jabber Team http://jabber.org/
+ */
+#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! */
+
+    /* Convert the handle to a table pointer. */
+    tab = handle2ptr(tbl);
+    if (!tab)
+        return -1;  /* error */
+
+
+    for (i=0; running && (i<tab->bcount); i++)
+    { /* visit the contents of each bucket */
+        p = tab->buckets[i];
+        while (running && p)
+        { /* visit each node in turn */
+            p2 = p->next;
+            count++;
+            running = (*func)(user_data,p->key,p->value);
+            p = p2;
+
+        } /* end while */
+
+    } /* end for */
+
+    return count;
+
+} /* end ghash_walk */
+
+int str_hash_code(const char *s)
+/*
+    Description:
+        Generates a hash code for a string.  This function uses the ELF hashing
+        algorithm as reprinted in Andrew Binstock, "Hashing Rehashed," _Dr.
+        Dobb's Journal_, April 1996.
+ 
+    Input:
+        Parameters:
+            s - The string to be hashed.
+ 
+    Output:
+        Returns:
+            A hash code for the string.
+*/
+{
+    /* ELF hash uses unsigned chars and unsigned arithmetic for portability */
+    const unsigned char *name = (const unsigned char *)s;
+    unsigned long h = 0, g;
+
+    if (!name)
+        return 0;  /* anti-NULL guard not in the original */
+
+    while (*name)
+    { /* do some fancy bitwanking on the string */
+        h = (h << 4) + (unsigned long)(*name++);
+        if ((g = (h & 0xF0000000UL))!=0)
+            h ^= (g >> 24);
+        h &= ~g;
+
+    } /* end while */
+
+    return (int)h;
+
+}