/* (C) Copyright 2001, 2002, 2003, 2004, 2005 Stijn van Dongen * (C) Copyright 2006, 2007 Stijn van Dongen * * This file is part of tingea. You can redistribute and/or modify tingea * under the terms of the GNU General Public License; either version 3 of the * License or (at your option) any later version. You should have received a * copy of the GPL along with tingea, in the file COPYING. */ #ifndef tingea_hash_h #define tingea_hash_h /* TODO: make sort routines for keys and values by key or value criteria. * make interface for storing integers, preferably without objectifying them. */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ** Implementation notes (a few). * * * This hash interface is very powerful. It gives you more than enough * rope to hang yourself and then some. It can be used as is, or wrappers * can be made around it that restrict a caller's ability to err. * * The danger lies in the fact that this interface only does retrieval * and storage of pointers (both for keys and values), and does not clone * anything. Anything happening with the objects pointed to during the * lifetime of the hash is the responsibility of the caller. * * What the interface cannot do currently is hash integers by value (rather * than by reference). This functionality will probably be added someday. * Features: * o Searching, inserting, and deletion are all done by * mcxHashSearch. It returns a pointer to mcxKV. In all modes, the * caller can use the returned mcxKV* structure to obtain * the 'val' and 'key' members. * * o Hashes grow automatically once the average load per bucket * exceeds a settable threshold and if the hash was not declared * constant. * * o Caller supplies both the hash function and the compare function. * This interface provides several hash functions operating on a * (void* base, int len) combo, where base is cast to char by the * hash function. These functions can be used in creating custom hash * functions for your custom objects. * * o You can (of course) have multiple hashes. This is not really * a feature - however, since the idiotic does not offer * this I thought I'd mention it. * * o Witness mcxHashWalkInit, mcxHashWalkStep. * * o There is mcxHashMerge. * * o mcxHashKeys, mcxHashKVs. * * Enjoy. * Notes * There is a utility hashfile.c (distributed in a separate package) * that can be used to stress-test this module. It allows customization * of several aspects, including the hash function that should be used. */ #include "types.h" #include "list.h" /* The hash struct is hidden. Use mcxHashGetSettings if you need * to peek into the interior. Or read hash.c */ typedef struct mcxHash mcxHash; typedef struct { void* key ; void* val ; } mcxKV ; mcxHash* mcxHashNew ( dim n_buckets , u32 (*hash) (const void *a) , int (*cmp) (const void *a, const void *b) ) ; #define MCX_HASH_OPT_DEFAULTS 0 #define MCX_HASH_OPT_CONSTANT 1 #define MCX_HASH_OPT_UNUSED 2 void mcxHashSetOpts ( mcxHash* hash , double load , int option /* negative values will be ignored (feature) */ ) ; dim mcxHashMemSize ( mcxHash* hash ) ; typedef struct mcxHashSettings { dim n_buckets ; dim n_entries ; float load ; mcxbits options ; } mcxHashSettings ; void mcxHashGetSettings ( mcxHash* hash , mcxHashSettings* settings ) ; /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ** mcxHashSearch * * action returns * * MCX_DATUM_DELETE -> deleted mcxKV* or NULL if not present * MCX_DATUM_INSERT -> new or present mcxKV* * MCX_DATUM_FIND -> mcxKV* if present NULL otherwise. * * usage: * * Values have to be inserted by the caller into the returned KV struct. * Make sure that keys point to objects that are constant * (with respect to the cmp function) during the lifetime of the hash. * YOU have to ensure the integrity of both keys and values. * This enables you to do whatever suits you, such as appending to * values. * * When inserting, check whether kv->key != key (where kv is returned value) * if this is the case, an identically comparing key is already present. * You may want to destroy one of the two keys and decide what to do * with the value. * * When deleting, the key-value pair is removed from the hash * *AND RETURNED TO CALLER* - you have to decide yourself what to do * with it. If the key was not present, a value of NULL is returned. * You have to fetch the val and key members of the returned mcxKV * object immediately: Subsequent inserts in the hash may reuse it. * * When finding, life is simple. NULL if absent, matching kv otherwise. * * note: * * memory management of keys and values is totally up to caller. * If usage is clean, you can use mcxHashFree for disposal of hash. */ #define mcxHashSearch(key, hash, ACTION) mcxHashSearchx(key, hash, ACTION, NULL) mcxKV* mcxHashSearchx ( void* key , mcxHash* hash , mcxmode ACTION , int* delta ) ; /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ** mcxHashMerge * * this one COPIES OBJECT POINTERS and DOES NOT CLONE. * so after the merge, hash1 and hash2 keys and values should not be freed. * In case there are equivalent keys in hash1 and hash2, this may * cause trouble when the caller wants to do cleaning afterwards. * This interface is still under development. * * hashd may be equal to hash1 or hash2, and it may also be NULL. */ mcxHash* mcxHashMerge ( mcxHash* hash1 , mcxHash* hash2 , mcxHash* hashd , void* merge(void* val1, void* val2) ) ; /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ** mcxHashFree * * This only works if all keys are of the same type and/or all values * are of the same type, and if your objects were created as expected by * the free routines (presumably malloced heap memory) - be careful with * constant objects like constant strings. * * freekey and freeval may not free their argument. This is because * tingea does not allow routines that leave arguments in an * inconsistent state, and free routines in tingea generally accept * an argument of the form ** pptr. * In the case of mcxHashFree this means that the interface may * feel slighly more cumbersome. * A way out would have been to make the callbacks of signature * * void freemem(void** mempp) * * The caller could access *mempp, cast it to the expected type, * and later set *mempp to NULL. However, this would require * new free routines for lots of types. With the current interface * existing Release routines can be used: * * The type of free routine expected by mcxHashFree is generally * called Release or Release_v, e.g. mcxTingRelease. * Release routines release all memory of a composite object except the * memory which holds the outer struct. * * If one of key or val is *not* a composite type or is a composite type * that does not contain malloced memory, use mcxHashFreeScalar. * * Both freekey and freeval may be NULL. When NULL, the corresponding * KV member is not loooked at. This is useful e.g. when hashing objects * owned by someone else. */ void mcxHashFree ( mcxHash** hashpp , void freekey(void* keypp) /* (yourtype1** keypp) */ , void freeval(void* valpp) /* (yourtype2** valpp) */ ) ; void mcxHashFreeScalar ( void* scalar ) ; /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * It copies the pointers stored in the hash */ void** mcxHashKeys ( mcxHash* hash , dim* n_entries , int (*cmp)(const void*, const void*) , mcxbits opts /* unused yet */ ) ; /* Future options: SORT, SORT_DESC */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * It copies the pointers stored in the hash */ void** mcxHashKVs ( mcxHash* hash , dim* n_entries , int (*cmp)(const void*, const void*) , mcxbits opts /* unused yet */ ) ; /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Prints some information to stdout. */ void mcxHashStats ( FILE* fp , mcxHash* hash ) ; typedef struct mcxHashWalk mcxHashWalk; mcxHashWalk* mcxHashWalkInit ( mcxHash *hash ) ; mcxKV* mcxHashWalkStep ( mcxHashWalk* walk , dim *i_bucket ) ; void mcxHashWalkFree ( mcxHashWalk **walkpp ) ; void mcxHashApply ( mcxHash* hash , void (*cb)(const void* key, void* val, void* data) , void* data ) ; /* UNIX ELF hash */ /* POOR! */ u32 mcxELFhash ( const void *key , u32 len ) ; /* created by Bob Jenkins */ u32 mcxBJhash ( const void* key , u32 len ) ; /* One at a time hash, Bob Jenkins/Colin Plumb */ u32 mcxOAThash ( const void *key , u32 len ) ; /* created by Daniel Phillips */ u32 mcxDPhash ( const void* key , u32 len ) ; /* "Berkely Database" hash (from Ozan Yigit's page) */ /* POOR! */ u32 mcxBDBhash ( const void *key , u32 len ) ; /* Dan Bernstein hash (from Ozan Yigit's page) */ u32 mcxDJBhash ( const void *key , u32 len ) ; /* created by Chris Torek */ u32 mcxCThash ( const void* key , u32 len ) ; /* "GNU Emacs" hash (from m4) */ /* not among the best */ u32 mcxGEhash ( const void* key , u32 len ) ; /* Fowler Noll Vo hash */ u32 mcxFNVhash ( const void *buf , u32 len ) ; /* All experimental with weak points. */ u32 mcxSvDhash ( const void *key , u32 len ) ; u32 mcxSvD2hash ( const void *key , u32 len ) ; u32 mcxSvD1hash ( const void *key , u32 len ) ; /* uses mcxDPhash */ u32 mcxStrHash ( const void* s ) ; int mcxStrCmp ( const void* a , const void* b ) ; #endif