diff src/protocols/jabber/genhash.c @ 3127:4e7cefc55971

[gaim-migrate @ 3142] Upgraded jabber to most recent stable version committer: Tailor Script <[e-mail]>

--- a/src/protocols/jabber/genhash.c	Thu Apr 04 00:59:12 2002 +0000
+++ b/src/protocols/jabber/genhash.c	Thu Apr 04 03:04:57 2002 +0000
@@ -1,490 +1,101 @@
-/*
- *  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.
+/* --------------------------------------------------------------------------
+ *
+ * License
  *
- *  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.
+ * The contents of this file are subject to the Jabber Open Source License
+ * Version 1.0 (the "JOSL").  You may not copy or use this file, in either
+ * source code or executable form, except in compliance with the JOSL. You
+ * may obtain a copy of the JOSL at http://www.jabber.org/ or at
+ * http://www.opensource.org/.  
  *
- *  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.
+ * Software distributed under the JOSL is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied.  See the JOSL
+ * for the specific language governing rights and limitations under the
+ * JOSL.
  *
- *  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 */
+ * 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.
+ * 
+ * Alternatively, the contents of this file may be used under the terms of the
+ * GNU General Public License Version 2 or later (the "GPL"), in which case
+ * the provisions of the GPL are applicable instead of those above.  If you
+ * wish to allow use of your version of this file only under the terms of the
+ * GPL and not to allow others to use your version of this file under the JOSL,
+ * indicate your decision by deleting the provisions above and replace them
+ * with the notice and other provisions required by the GPL.  If you do not
+ * delete the provisions above, a recipient may use your version of this file
+ * under either the JOSL or the GPL. 
+ * 
+ * 
+ * --------------------------------------------------------------------------*/
 
-    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 */
+#include "lib.h"
 
-    /* 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;
+/*** stubs that hook back to new xhash */
 
-} /* 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.
-*/
+HASHTABLE ghash_create(int buckets, KEYHASHFUNC hash, KEYCOMPAREFUNC cmp)
 {
-    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! */
+    return xhash_new(buckets);
 }
 
-/*****************************************************************************
- * 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 ghash_create_pool(pool p, int buckets, KEYHASHFUNC hash, KEYCOMPAREFUNC cmp)
 {
-    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 */
+    xht h = xhash_new(buckets);
+    pool_cleanup(p, (pool_cleaner)xhash_free, h);
+    return h;
+}
 
 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 */
+    xhash_free(tbl);
+}
 
 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 */
+    return xhash_get(tbl, key);
+}
 
 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 */
+    xhash_put(tbl, key, value);
+    return 1;
+}
 
 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! */
+    xhash_zap(tbl, key);
+    return 1;
+}
 
-    /* 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.
+{
+    int i;
+    xhn n;
+    xht h = (xht)tbl;
 
-    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 */
+    for(i = 0; i < h->prime; i++)
+        for(n = &h->zen[i]; n != NULL; n = n->next)
+            if(n->key != NULL && n->val != NULL)
+                (*func)(user_data, n->key, n->val);
 
-    if (!tbl || !func)
-        return -1;  /* bogus values! */
-
-    /* Convert the handle to a table pointer. */
-    tab = handle2ptr(tbl);
-    if (!tab)
-        return -1;  /* error */
+    return 1;
+}
 
 
-    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 _xhasher(const char *key);
 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 */
+    return _xhasher(s);
+}
 
-    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;
-
-}