|
[ source navigation ] [ diff markup ] [ identifier search ] [ general search ] |
|||
|
001 /* Copyright (C) 2005 David Decotigny 002 003 This program is free software; you can redistribute it and/or 004 modify it under the terms of the GNU General Public License 005 as published by the Free Software Foundation; either version 2 006 of the License, or (at your option) any later version. 007 008 This program is distributed in the hope that it will be useful, 009 but WITHOUT ANY WARRANTY; without even the implied warranty of 010 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 011 GNU General Public License for more details. 012 013 You should have received a copy of the GNU General Public License 014 along with this program; if not, write to the Free Software 015 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 016 USA. 017 */ 018 #ifndef _SOS_HASH_H_ 019 #define _SOS_HASH_H_ 020 021 #include <sos/types.h> 022 #include <sos/errno.h> 023 #include <sos/macros.h> 024 025 /** 026 * hash.h 027 * 028 * Hash table implementation. The key and the element structure is 029 * user-definable. Each element must embed: 030 * - the key 031 * - a sos_hash_linkage structure 032 * 033 * The DANGER is that the key value must NOT be changed while the 034 * element is inserted in the hash 035 */ 036 037 /** Prototype of a hash function */ 038 typedef unsigned long (sos_hash_func_t)(const void * ptr_key); 039 040 /** Prototype of a key comparison function */ 041 typedef sos_bool_t (sos_hash_key_eq_func_t)(const void * ptr_key1, 042 const void * ptr_key2); 043 044 /** Opaque structure */ 045 struct sos_hash_table; 046 047 /** This structure must be embedded in the elements to be insterted in 048 the hah */ 049 struct sos_hash_linkage 050 { 051 struct sos_hash_linkage * h_prev, * h_next; 052 }; 053 054 055 /** 056 * Creation of a hash table 057 * 058 * @param name The name of the hash table (debug) 059 * @param elt_type The type of the elements 060 * @param hfunc The hash function (@see sos_hash_func_t) 061 * @param hfunc The element comparaison function (@see 062 * sos_hash_key_eq_func_t) 063 * @param nbuckets The number of bucks in the hash 064 * @param name_key_field The name of the field in the element type 065 * that holds the key 066 * @param name_key_field The name of the field in the element type 067 * that hold the prev/next hash linkage data 068 */ 069 #define sos_hash_create(name,elt_type,hfunc,eqfunc,nbuckets,\ 070 name_key_field,name_h_linkage) \ 071 _sos_hash_create_FULL(name, hfunc, eqfunc, nbuckets, \ 072 offsetof(elt_type, name_key_field), \ 073 offsetof(elt_type, name_h_linkage)) 074 075 076 /** 077 * @note Real hash creation function called by the sos_hash_create 078 * macro 079 * 080 * @param key_hasher When NULL: the value of the hash is directly the 081 * pointer address 082 * @param key_compare When NULL: compare directly the pointer addresses 083 */ 084 struct sos_hash_table * 085 _sos_hash_create_FULL(const char *name, 086 sos_hash_func_t *key_hasher, 087 sos_hash_key_eq_func_t *key_iseq, 088 sos_count_t nbuckets, 089 sos_uoffset_t offset_h_key, 090 sos_uoffset_t offset_h_linkage); 091 092 093 /** Does not free the elements themselves ! */ 094 sos_ret_t sos_hash_dispose(struct sos_hash_table *h); 095 096 097 /** 098 * Insert the element in the hash, associating it with the key that it 099 * embeds 100 * 101 * Makes sure the element is not already in the hash 102 */ 103 sos_ret_t sos_hash_insert(struct sos_hash_table *h, 104 void *elt_with_key); 105 106 107 /** Look for the element stored in the hash that has the key given by 108 ptr_key */ 109 void * sos_hash_lookup(struct sos_hash_table *h, 110 const void * ptr_key); 111 112 113 /** Remove an element from the hash, previously returned by 114 sos_hash_lookup */ 115 sos_ret_t sos_hash_remove(struct sos_hash_table *h, 116 void *elt); 117 118 119 /* 120 * Common hash functions 121 */ 122 123 /* key = 64bits integer */ 124 unsigned long sos_hash_ui64(const void * ptr_key); 125 sos_bool_t sos_hash_key_eq_ui64(const void * ptr_key1, 126 const void * ptr_key2); 127 128 129 #endif /* _SOS_HASH_H_ */
[ source navigation ] | [ diff markup ] | [ identifier search ] | [ general search ] |