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