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 018 019 #include <sos/kmalloc.h> 019 #include <sos/kmalloc.h> 020 #include <sos/klibc.h> 020 #include <sos/klibc.h> 021 #include <sos/list.h> 021 #include <sos/list.h> 022 #include <sos/assert.h> 022 #include <sos/assert.h> 023 023 024 #include "hash.h" 024 #include "hash.h" 025 025 026 #define SOS_HASH_NAME_MAXLEN 32 026 #define SOS_HASH_NAME_MAXLEN 32 027 027 028 028 029 /** 029 /** 030 * @file hash.c 030 * @file hash.c 031 * 031 * 032 * A hash table is simply a table of lists: ea 032 * A hash table is simply a table of lists: each list hash a "bucket 033 * index". Each list contains the element for 033 * index". Each list contains the element for which the hash of the 034 * key is equal to the bucket index (modulo th 034 * key is equal to the bucket index (modulo the number of buckets). 035 */ 035 */ 036 036 037 037 038 /** 038 /** 039 * Structure of one list of elements 039 * Structure of one list of elements 040 */ 040 */ 041 struct bucket 041 struct bucket 042 { 042 { 043 sos_count_t nb_elems; 043 sos_count_t nb_elems; 044 struct sos_hash_linkage * list; 044 struct sos_hash_linkage * list; 045 }; 045 }; 046 046 047 047 048 /** 048 /** 049 * The table of buckets, ie the hash itself 049 * The table of buckets, ie the hash itself 050 */ 050 */ 051 struct sos_hash_table 051 struct sos_hash_table 052 { 052 { 053 char name[SOS_HASH_NAME_MAXLEN]; 053 char name[SOS_HASH_NAME_MAXLEN]; 054 054 055 /** Hash function */ 055 /** Hash function */ 056 sos_hash_func_t * key_hasher; 056 sos_hash_func_t * key_hasher; 057 057 058 /** Key comparison function */ 058 /** Key comparison function */ 059 sos_hash_key_eq_func_t * key_iseq; 059 sos_hash_key_eq_func_t * key_iseq; 060 060 061 /** Memory-offset of the key in the element 061 /** Memory-offset of the key in the element structure */ 062 sos_uoffset_t offset_h_key; 062 sos_uoffset_t offset_h_key; 063 063 064 /** Memory-offset of the hash linkage in the 064 /** Memory-offset of the hash linkage in the element structure */ 065 sos_uoffset_t offset_h_linkage; 065 sos_uoffset_t offset_h_linkage; 066 066 067 /** Number of buckets in this hash table */ 067 /** Number of buckets in this hash table */ 068 sos_count_t nbuckets; 068 sos_count_t nbuckets; 069 069 070 struct bucket bucket[0]; 070 struct bucket bucket[0]; 071 }; 071 }; 072 072 073 073 074 /** From the address of the given element, acc 074 /** From the address of the given element, access to its hash_linkage 075 structrure */ 075 structrure */ 076 #define h_linkage_of_elt(h,elt) \ 076 #define h_linkage_of_elt(h,elt) \ 077 ( (struct sos_hash_linkage*) \ 077 ( (struct sos_hash_linkage*) \ 078 ( ((unsigned long)(elt)) + (h)->offset_h_l 078 ( ((unsigned long)(elt)) + (h)->offset_h_linkage) ) 079 079 080 080 081 /** From the address of the given element, acc 081 /** From the address of the given element, access to its pointer to 082 the key */ 082 the key */ 083 #define h_keyptr_of_elt(h,elt) \ 083 #define h_keyptr_of_elt(h,elt) \ 084 ( (void*) \ 084 ( (void*) \ 085 ( ((unsigned long)(elt)) + (h)->offset_h_k 085 ( ((unsigned long)(elt)) + (h)->offset_h_key) ) 086 086 087 087 088 /** From the given hash linkage structure addr 088 /** From the given hash linkage structure address, retrieve the 089 address of the surronding element */ 089 address of the surronding element */ 090 #define elt_for_h_linkage(h,linkage) \ 090 #define elt_for_h_linkage(h,linkage) \ 091 ( (void*) \ 091 ( (void*) \ 092 ( ((unsigned long)(linkage)) - (h)->offset 092 ( ((unsigned long)(linkage)) - (h)->offset_h_linkage) ) 093 093 094 094 095 struct sos_hash_table * 095 struct sos_hash_table * 096 _sos_hash_create_FULL(const char * 096 _sos_hash_create_FULL(const char *name, 097 sos_hash_func_t * 097 sos_hash_func_t *key_hasher, 098 sos_hash_key_eq_func_t * 098 sos_hash_key_eq_func_t *key_iseq, 099 sos_count_t n 099 sos_count_t nbuckets, 100 sos_uoffset_t o 100 sos_uoffset_t offset_h_key, 101 sos_uoffset_t o 101 sos_uoffset_t offset_h_linkage) 102 { 102 { 103 struct sos_hash_table * h; 103 struct sos_hash_table * h; 104 h = (struct sos_hash_table*) 104 h = (struct sos_hash_table*) 105 sos_kmalloc(sizeof(struct sos_hash_table) 105 sos_kmalloc(sizeof(struct sos_hash_table) 106 + nbuckets*sizeof(struct bucke 106 + nbuckets*sizeof(struct bucket), 0); 107 107 108 memset(h, 0x0, 108 memset(h, 0x0, 109 sizeof(struct sos_hash_table) + nbuck 109 sizeof(struct sos_hash_table) + nbuckets*sizeof(struct bucket)); 110 h->key_hasher = key_hasher; 110 h->key_hasher = key_hasher; 111 h->key_iseq = key_iseq; 111 h->key_iseq = key_iseq; 112 h->offset_h_linkage = offset_h_linkage; 112 h->offset_h_linkage = offset_h_linkage; 113 h->offset_h_key = offset_h_key; 113 h->offset_h_key = offset_h_key; 114 h->nbuckets = nbuckets; 114 h->nbuckets = nbuckets; 115 strzcpy(h->name, name, SOS_HASH_NAME_MAXLEN) 115 strzcpy(h->name, name, SOS_HASH_NAME_MAXLEN); 116 116 117 return h; 117 return h; 118 } 118 } 119 119 120 120 121 sos_ret_t sos_hash_dispose(struct sos_hash_tab 121 sos_ret_t sos_hash_dispose(struct sos_hash_table *h) 122 { 122 { 123 unsigned int i; !! 123 int i; 124 for (i = 0 ; i < h->nbuckets ; i++) 124 for (i = 0 ; i < h->nbuckets ; i++) 125 { 125 { 126 struct sos_hash_linkage * elt; 126 struct sos_hash_linkage * elt; 127 127 128 list_collapse_named(h->bucket[i].list, e 128 list_collapse_named(h->bucket[i].list, elt, h_prev, h_next) 129 { 129 { 130 elt->h_prev = elt->h_next = NULL; 130 elt->h_prev = elt->h_next = NULL; 131 } 131 } 132 } 132 } 133 133 134 return sos_kfree((sos_vaddr_t)h); 134 return sos_kfree((sos_vaddr_t)h); 135 } 135 } 136 136 137 137 138 sos_ret_t sos_hash_insert(struct sos_hash_tabl 138 sos_ret_t sos_hash_insert(struct sos_hash_table *h, 139 void *elt_with_key) 139 void *elt_with_key) 140 { 140 { 141 struct sos_hash_linkage * h_elt; 141 struct sos_hash_linkage * h_elt; 142 sos_uoffset_t bucket; 142 sos_uoffset_t bucket; 143 143 144 h_elt = h_linkage_of_elt(h, elt_with_key); 144 h_elt = h_linkage_of_elt(h, elt_with_key); 145 if (h_elt->h_prev || h_elt->h_next) 145 if (h_elt->h_prev || h_elt->h_next) 146 return -SOS_EBUSY; 146 return -SOS_EBUSY; 147 147 148 if (h->key_hasher) 148 if (h->key_hasher) 149 bucket = h->key_hasher(h_keyptr_of_elt(h, 149 bucket = h->key_hasher(h_keyptr_of_elt(h, elt_with_key)) % h->nbuckets; 150 else 150 else 151 { 151 { 152 /* The key is assumed to be an integer * 152 /* The key is assumed to be an integer */ 153 unsigned long * keyval = h_keyptr_of_elt 153 unsigned long * keyval = h_keyptr_of_elt(h, elt_with_key); 154 bucket = *keyval % h->nbuckets; 154 bucket = *keyval % h->nbuckets; 155 } 155 } 156 156 157 list_add_head_named(h->bucket[bucket].list, 157 list_add_head_named(h->bucket[bucket].list, h_elt, h_prev, h_next); 158 h->bucket[bucket].nb_elems ++; 158 h->bucket[bucket].nb_elems ++; 159 159 160 return SOS_OK; 160 return SOS_OK; 161 } 161 } 162 162 163 163 164 void * sos_hash_lookup(struct sos_hash_table * 164 void * sos_hash_lookup(struct sos_hash_table *h, 165 const void * ptr_key) 165 const void * ptr_key) 166 { 166 { 167 struct sos_hash_linkage * h_elt; 167 struct sos_hash_linkage * h_elt; 168 sos_uoffset_t bucket; 168 sos_uoffset_t bucket; 169 int nb; 169 int nb; 170 170 171 if (h->key_hasher) 171 if (h->key_hasher) 172 bucket = h->key_hasher(ptr_key) % h->nbuck 172 bucket = h->key_hasher(ptr_key) % h->nbuckets; 173 else 173 else 174 { 174 { 175 /* The key is assumed to be an integer * 175 /* The key is assumed to be an integer */ 176 const unsigned long * keyval = ptr_key; 176 const unsigned long * keyval = ptr_key; 177 bucket = *keyval % h->nbuckets; 177 bucket = *keyval % h->nbuckets; 178 } 178 } 179 179 180 list_foreach_forward_named(h->bucket[bucket] 180 list_foreach_forward_named(h->bucket[bucket].list, h_elt, nb, h_prev, h_next) 181 { 181 { 182 void * elt = elt_for_h_linkage(h 182 void * elt = elt_for_h_linkage(h, h_elt); 183 void * elt_ptr_key = h_keyptr_of_elt(h, 183 void * elt_ptr_key = h_keyptr_of_elt(h, elt); 184 184 185 if (ptr_key == elt_ptr_key) 185 if (ptr_key == elt_ptr_key) 186 return elt; 186 return elt; 187 187 188 if (! h->key_iseq) 188 if (! h->key_iseq) 189 continue; 189 continue; 190 190 191 if (h->key_iseq(ptr_key, elt_ptr_key)) 191 if (h->key_iseq(ptr_key, elt_ptr_key)) 192 return elt; 192 return elt; 193 } 193 } 194 194 195 return NULL; 195 return NULL; 196 } 196 } 197 197 198 198 199 sos_ret_t sos_hash_remove(struct sos_hash_tabl 199 sos_ret_t sos_hash_remove(struct sos_hash_table *h, 200 void * elt) 200 void * elt) 201 { 201 { 202 struct sos_hash_linkage * h_elt; 202 struct sos_hash_linkage * h_elt; 203 sos_uoffset_t bucket; 203 sos_uoffset_t bucket; 204 204 205 h_elt = h_linkage_of_elt(h, elt); 205 h_elt = h_linkage_of_elt(h, elt); 206 SOS_ASSERT_FATAL(h_elt->h_prev && h_elt->h_n 206 SOS_ASSERT_FATAL(h_elt->h_prev && h_elt->h_next); 207 207 208 if (h->key_hasher) 208 if (h->key_hasher) 209 bucket = h->key_hasher(h_keyptr_of_elt(h, 209 bucket = h->key_hasher(h_keyptr_of_elt(h, elt)) % h->nbuckets; 210 else 210 else 211 { 211 { 212 unsigned long * keyval = h_keyptr_of_elt 212 unsigned long * keyval = h_keyptr_of_elt(h, elt); 213 bucket = *keyval % h->nbuckets; 213 bucket = *keyval % h->nbuckets; 214 } 214 } 215 215 216 list_delete_named(h->bucket[bucket].list, h_ 216 list_delete_named(h->bucket[bucket].list, h_elt, h_prev, h_next); 217 h->bucket[bucket].nb_elems --; 217 h->bucket[bucket].nb_elems --; 218 218 219 return SOS_OK; 219 return SOS_OK; 220 } 220 } 221 221 222 222 223 unsigned long sos_hash_ui64(const void * ptr_k 223 unsigned long sos_hash_ui64(const void * ptr_key) 224 { 224 { 225 const sos_ui64_t * keyval = ptr_key; 225 const sos_ui64_t * keyval = ptr_key; 226 return ((*keyval) * 302954987) & 0xffffffff; 226 return ((*keyval) * 302954987) & 0xffffffff; 227 } 227 } 228 228 229 229 230 sos_bool_t sos_hash_key_eq_ui64(const void * p 230 sos_bool_t sos_hash_key_eq_ui64(const void * ptr_key1, 231 const void * p 231 const void * ptr_key2) 232 { 232 { 233 const sos_ui64_t * keyval1 = ptr_key1; 233 const sos_ui64_t * keyval1 = ptr_key1; 234 const sos_ui64_t * keyval2 = ptr_key2; 234 const sos_ui64_t * keyval2 = ptr_key2; 235 235 236 return (*keyval1 == *keyval2); 236 return (*keyval1 == *keyval2); 237 } 237 }
| [ source navigation ] | [ diff markup ] | [ identifier search ] | [ general search ] |