|
nfs-ganesha 1.4
|
00001 /* 00002 * 00003 * 00004 * Copyright CEA/DAM/DIF (2008) 00005 * contributeur : Philippe DENIEL philippe.deniel@cea.fr 00006 * Thomas LEIBOVICI thomas.leibovici@cea.fr 00007 * 00008 * 00009 * This program is free software; you can redistribute it and/or 00010 * modify it under the terms of the GNU Lesser General Public 00011 * License as published by the Free Software Foundation; either 00012 * version 3 of the License, or (at your option) any later version. 00013 * 00014 * This program is distributed in the hope that it will be useful, 00015 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00016 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00017 * Lesser General Public License for more details. 00018 * 00019 * You should have received a copy of the GNU Lesser General Public 00020 * License along with this library; if not, write to the Free Software 00021 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 00022 * 02110-1301 USA 00023 * 00024 * --------------------------------------- 00025 */ 00026 00035 #ifndef _HASHTABLE_H 00036 #define _HASHTABLE_H 00037 00038 #include <rbt_node.h> 00039 #include <rbt_tree.h> 00040 #include <pthread.h> 00041 #include "HashData.h" 00042 #include "log.h" 00043 #include "lookup3.h" 00044 #include "abstract_mem.h" 00045 00046 #ifndef TRUE 00047 #define TRUE 1 00048 #endif 00049 00050 #ifndef FALSE 00051 #define FALSE 0 00052 #endif 00053 00059 /* Forward declaration */ 00060 00061 typedef struct hash_param hash_parameter_t; 00062 00063 typedef uint32_t (*index_function_t)(struct hash_param *, 00064 struct hash_buff *); 00065 typedef uint64_t (*rbthash_function_t)(struct hash_param *, 00066 struct hash_buff *); 00067 typedef int (*both_function_t)(struct hash_param *, 00068 struct hash_buff *, 00069 uint32_t *, 00070 uint64_t *); 00071 typedef int (*hash_buff_comparator_t)(struct hash_buff *, 00072 struct hash_buff *); 00073 typedef int (*key_display_function_t)(struct hash_buff *, 00074 char *); 00075 typedef int (*val_display_function_t)(struct hash_buff*, 00076 char *); 00077 00078 00084 #define HT_FLAG_NONE 0x0000 00085 #define HT_FLAG_CACHE 0x0001 00086 00087 struct hash_param 00088 { 00089 uint32_t flags; /*< Create flags */ 00090 uint32_t cache_entry_count; /*< 2^10 <= Power of 2 <= 2^15 */ 00091 uint32_t index_size; /*< Number of partition trees, this MUST be a 00092 prime number. */ 00093 uint32_t alphabet_length; /*< Size of the input alphabet for 00094 the template (and other polynomial 00095 style) hash functions. */ 00096 index_function_t hash_func_key; /*< Partition function, returns an 00097 integer from 0 to (index_size 00098 - 1). This should be 00099 something fairly simple and 00100 fast with a uniform 00101 distribution. */ 00102 rbthash_function_t hash_func_rbt; /*< The actual hash value, 00103 termining location within 00104 the partition tree. This 00105 should be a high quality 00106 hash function such as 00107 64 bit Lookup3 or Murmur. */ 00108 both_function_t hash_func_both; /*< Index and partition calcualtor. 00109 Returns false on 00110 failure. A single function 00111 may replace the partition 00112 and hash funcions. */ 00113 hash_buff_comparator_t compare_key; /*< Function to compare two 00114 keys. This function 00115 returns 0 on equality. */ 00116 key_display_function_t key_to_str; /*< Function to convert a key 00117 to a string. */ 00118 val_display_function_t val_to_str; /*< Function to convert a 00119 value to a string. */ 00120 char *ht_name; /*< Name of this hash table. */ 00121 log_components_t ht_log_component; /*< Log component to use for this 00122 hash table */ 00123 }; 00124 00125 typedef struct hash_stat 00126 { 00127 size_t entries; /*< Number of entries in the hash table */ 00128 size_t min_rbt_num_node; /*< Minimum size (in number of 00129 nodes) of the rbt used. */ 00130 size_t max_rbt_num_node; /*< Maximum size (in number of 00131 nodes) of the rbt used. */ 00132 size_t average_rbt_num_node; /*< Average size (in number 00133 of nodes) of the rbt used. */ 00134 } hash_stat_t; 00135 00143 struct hash_partition 00144 { 00145 size_t count; /*< Numer of entries in this partition */ 00146 struct rbt_head rbt; /*< The red-black tree */ 00147 pthread_rwlock_t lock; /*< Lock for this partition */ 00148 struct rbt_node** cache; /*< expected entry cache */ 00149 }; 00150 00151 typedef struct hash_table 00152 { 00153 struct hash_param parameter; /*< Definitive parameter for the 00154 HashTable */ 00155 pool_t *node_pool; /*< Pool of RBT nodes */ 00156 pool_t *data_pool; /*< Pool of buffer pairs */ 00157 struct hash_partition partitions[]; /*< Parameter.index_size partitions of 00158 the hash table. */ 00159 } hash_table_t; 00160 00161 struct hash_latch { 00162 uint32_t index; /*< Saved partition index */ 00163 uint64_t rbt_hash; /*< Saved red-black hash */ 00164 struct rbt_node *locator; /*< Saved location in the tree */ 00165 }; 00166 00167 typedef enum hash_set_how { 00168 HASHTABLE_SET_HOW_TEST_ONLY = 1, 00169 HASHTABLE_SET_HOW_SET_OVERWRITE = 2, 00170 HASHTABLE_SET_HOW_SET_NO_OVERWRITE = 3 00171 } hash_set_how_t; 00172 00173 /* @} */ 00174 00175 /* How many character used to display a key or value */ 00176 static const size_t HASHTABLE_DISPLAY_STRLEN = 8192; 00177 00178 /* Possible errors */ 00179 typedef enum hash_error { 00180 HASHTABLE_SUCCESS = 0, 00181 HASHTABLE_UNKNOWN_HASH_TYPE = 1, 00182 HASHTABLE_INSERT_MALLOC_ERROR = 2, 00183 HASHTABLE_ERROR_NO_SUCH_KEY = 3, 00184 HASHTABLE_ERROR_KEY_ALREADY_EXISTS = 4, 00185 HASHTABLE_ERROR_INVALID_ARGUMENT = 5, 00186 HASHTABLE_ERROR_DELALL_FAIL = 6, 00187 HASHTABLE_NOT_DELETED = 7, 00188 HASHTABLE_OVERWRITTEN = 8 00189 } hash_error_t; 00190 00191 const char *hash_table_err_to_str(hash_error_t err); 00192 00193 /* These are the primitives of the hash table */ 00194 00195 struct hash_table *HashTable_Init(struct hash_param *hparam); 00196 hash_error_t HashTable_Destroy(struct hash_table *ht, 00197 int (*free_func)(struct hash_buff, 00198 struct hash_buff)); 00199 hash_error_t HashTable_GetLatch(struct hash_table *ht, 00200 struct hash_buff *key, 00201 struct hash_buff *val, 00202 int may_write, 00203 struct hash_latch *latch); 00204 void HashTable_ReleaseLatched(struct hash_table *ht, 00205 struct hash_latch *latch); 00206 hash_error_t HashTable_SetLatched(struct hash_table *ht, 00207 struct hash_buff *key, 00208 struct hash_buff *val, 00209 struct hash_latch *latch, 00210 int overwrite, 00211 struct hash_buff *stored_key, 00212 struct hash_buff *stored_val); 00213 hash_error_t HashTable_DeleteLatched(struct hash_table *ht, 00214 struct hash_buff *key, 00215 struct hash_latch *latch, 00216 struct hash_buff *stored_key, 00217 struct hash_buff *stored_val); 00218 hash_error_t HashTable_Delall(struct hash_table *ht, 00219 int (*free_func)(struct hash_buff, 00220 struct hash_buff)); 00221 00222 void HashTable_GetStats(struct hash_table *ht, 00223 struct hash_stat *hstat); 00224 size_t HashTable_GetSize(struct hash_table *ht); 00225 void HashTable_Log(log_components_t component, struct hash_table *ht); 00226 00227 /* These are very simple wrappers around the primitives */ 00228 00243 static inline hash_error_t 00244 HashTable_Get(struct hash_table *ht, 00245 struct hash_buff *key, 00246 struct hash_buff *val) 00247 { 00248 return HashTable_GetLatch(ht, key, val, FALSE, NULL); 00249 } /* HashTable_Get */ 00250 00268 static inline hash_error_t 00269 HashTable_Set(struct hash_table *ht, 00270 struct hash_buff *key, 00271 struct hash_buff *val) 00272 { 00273 /* structure to hold retained state */ 00274 struct hash_latch latch; 00275 /* Stored return code */ 00276 hash_error_t rc = HASHTABLE_SUCCESS; 00277 00278 rc = HashTable_GetLatch(ht, key, NULL, 00279 TRUE, 00280 &latch); 00281 00282 if ((rc != HASHTABLE_SUCCESS) && 00283 (rc != HASHTABLE_ERROR_NO_SUCH_KEY)) { 00284 return rc; 00285 } 00286 00287 rc = HashTable_SetLatched(ht, 00288 key, 00289 val, 00290 &latch, 00291 FALSE, 00292 NULL, 00293 NULL); 00294 00295 return rc; 00296 } /* HashTable_Set */ 00297 00298 00313 static inline hash_error_t 00314 HashTable_Del(struct hash_table *ht, 00315 struct hash_buff *key, 00316 struct hash_buff *stored_key, 00317 struct hash_buff *stored_val) 00318 { 00319 /* Structure to hold retained state */ 00320 struct hash_latch latch; 00321 /* Stored return code */ 00322 hash_error_t rc = HASHTABLE_SUCCESS; 00323 00324 rc = HashTable_GetLatch(ht, key, NULL, 00325 TRUE, &latch); 00326 00327 switch (rc) { 00328 case HASHTABLE_SUCCESS: 00329 return HashTable_DeleteLatched(ht, 00330 key, 00331 &latch, 00332 stored_key, 00333 stored_val); 00334 00335 case HASHTABLE_ERROR_NO_SUCH_KEY: 00336 HashTable_ReleaseLatched(ht, &latch); 00337 default: 00338 return rc; 00339 } 00340 } 00341 00342 /* These are the prototypes for large wrappers implementing more 00343 complex semantics on top of the primitives. */ 00344 00345 hash_error_t HashTable_Test_And_Set(struct hash_table *ht, 00346 struct hash_buff *key, 00347 struct hash_buff *val, 00348 enum hash_set_how how); 00349 hash_error_t HashTable_GetRef(struct hash_table *ht, 00350 struct hash_buff *key, 00351 struct hash_buff *val, 00352 void (*get_ref)(struct hash_buff *)); 00353 00354 hash_error_t HashTable_Get_and_Del(struct hash_table *ht, 00355 struct hash_buff *key, 00356 struct hash_buff *val, 00357 struct hash_buff *stored_key); 00358 hash_error_t HashTable_DelRef(struct hash_table *ht, 00359 struct hash_buff *key, 00360 struct hash_buff *stored_key, 00361 struct hash_buff *stored_val, 00362 int (*put_ref)(struct hash_buff *)); 00363 hash_error_t HashTable_DelSafe(hash_table_t *ht, 00364 hash_buffer_t *key, 00365 hash_buffer_t *val); 00366 00367 #endif /* _HASHTABLE_H */
1.7.3