Mercurial > pidgin
view plugins/jabber/genhash.c @ 1388:7dc0a8bb4dcb
[gaim-migrate @ 1398]
Pounce stuff is not sensitive if it doesnt need to be.
committer: Tailor Script <tailor@pidgin.im>
author | Rob Flynn <gaim@robflynn.com> |
---|---|
date | Fri, 05 Jan 2001 09:13:13 +0000 |
parents | afa63ac2fd84 |
children |
line wrap: on
line source
/* * 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; }