00001 /** @file 00002 00003 A brief file description 00004 00005 @section license License 00006 00007 Licensed to the Apache Software Foundation (ASF) under one 00008 or more contributor license agreements. See the NOTICE file 00009 distributed with this work for additional information 00010 regarding copyright ownership. The ASF licenses this file 00011 to you under the Apache License, Version 2.0 (the 00012 "License"); you may not use this file except in compliance 00013 with the License. You may obtain a copy of the License at 00014 00015 http://www.apache.org/licenses/LICENSE-2.0 00016 00017 Unless required by applicable law or agreed to in writing, software 00018 distributed under the License is distributed on an "AS IS" BASIS, 00019 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00020 See the License for the specific language governing permissions and 00021 limitations under the License. 00022 */ 00023 00024 /**************************************************************************** 00025 00026 ink_hash_table.c 00027 00028 This file implements hash tables. This allows us to provide alternative 00029 implementations of hash tables. 00030 00031 ****************************************************************************/ 00032 00033 #include "ink_error.h" 00034 #include "ink_hash_table.h" 00035 #include "ink_memory.h" 00036 00037 /*===========================================================================* 00038 00039 This is the Tcl implementation of InkHashTable 00040 00041 *===========================================================================*/ 00042 00043 /*---------------------------------------------------------------------------* 00044 00045 InkHashTable *ink_hash_table_create(InkHashTableKeyType key_type) 00046 00047 This routine allocates an initializes an empty InkHashTable, and returns a 00048 pointer to the new table. The <key_type> argument indicates whether keys 00049 are represented as strings, or as words. Legal values are 00050 InkHashTableKeyType_String and InkHashTableKeyType_Word. 00051 00052 *---------------------------------------------------------------------------*/ 00053 00054 InkHashTable * 00055 ink_hash_table_create(InkHashTableKeyType key_type) 00056 { 00057 InkHashTable *ht_ptr; 00058 Tcl_HashTable *tcl_ht_ptr; 00059 int tcl_key_type; 00060 00061 tcl_ht_ptr = (Tcl_HashTable*)ats_malloc(sizeof(Tcl_HashTable)); 00062 00063 if (key_type == InkHashTableKeyType_String) 00064 tcl_key_type = TCL_STRING_KEYS; 00065 else if (key_type == InkHashTableKeyType_Word) 00066 tcl_key_type = TCL_ONE_WORD_KEYS; 00067 else 00068 ink_fatal(1, "ink_hash_table_create: bad key_type %d", key_type); 00069 00070 Tcl_InitHashTable(tcl_ht_ptr, tcl_key_type); 00071 00072 ht_ptr = (InkHashTable *) tcl_ht_ptr; 00073 return (ht_ptr); 00074 } /* End ink_hash_table_create */ 00075 00076 00077 /*---------------------------------------------------------------------------* 00078 00079 void ink_hash_table_destroy(InkHashTable *ht_ptr) 00080 00081 This routine takes a hash table <ht_ptr>, and frees its storage. 00082 00083 *---------------------------------------------------------------------------*/ 00084 00085 InkHashTable * 00086 ink_hash_table_destroy(InkHashTable * ht_ptr) 00087 { 00088 Tcl_HashTable *tcl_ht_ptr; 00089 00090 tcl_ht_ptr = (Tcl_HashTable *) ht_ptr; 00091 Tcl_DeleteHashTable(tcl_ht_ptr); 00092 ats_free(tcl_ht_ptr); 00093 return (InkHashTable *) 0; 00094 } /* End ink_hash_table_destroy */ 00095 00096 00097 /*---------------------------------------------------------------------------* 00098 00099 void ink_hash_table_destroy_and_free_values(InkHashTable *ht_ptr) 00100 00101 This routine takes a hash table <ht_ptr>, and frees its storage, after 00102 first calling ink_free on all the values. You better darn well make sure the 00103 values have been dynamically allocated. 00104 00105 *---------------------------------------------------------------------------*/ 00106 00107 static int 00108 _ink_hash_table_free_entry_value(InkHashTable * ht_ptr, InkHashTableEntry * e) 00109 { 00110 InkHashTableValue value; 00111 00112 value = ink_hash_table_entry_value(ht_ptr, e); 00113 if (value != NULL) { 00114 ats_free(value); 00115 } 00116 00117 return (0); 00118 } /* End _ink_hash_table_free_entry_value */ 00119 00120 00121 static int 00122 _ink_hash_table_xfree_entry_value(InkHashTable * ht_ptr, InkHashTableEntry * e) 00123 { 00124 InkHashTableValue value; 00125 00126 value = ink_hash_table_entry_value(ht_ptr, e); 00127 if (value != NULL) { 00128 ats_free(value); 00129 } 00130 00131 return (0); 00132 } /* End _ink_hash_table_xfree_entry_value */ 00133 00134 InkHashTable * 00135 ink_hash_table_destroy_and_free_values(InkHashTable * ht_ptr) 00136 { 00137 ink_hash_table_map(ht_ptr, _ink_hash_table_free_entry_value); 00138 ink_hash_table_destroy(ht_ptr); 00139 return (InkHashTable *) 0; 00140 } /* End ink_hash_table_destroy_and_free_values */ 00141 00142 InkHashTable * 00143 ink_hash_table_destroy_and_xfree_values(InkHashTable * ht_ptr) 00144 { 00145 ink_hash_table_map(ht_ptr, _ink_hash_table_xfree_entry_value); 00146 ink_hash_table_destroy(ht_ptr); 00147 return (InkHashTable *) 0; 00148 } /* End ink_hash_table_destroy_and_xfree_values */ 00149 00150 00151 /*---------------------------------------------------------------------------* 00152 00153 int ink_hash_table_isbound(InkHashTable *ht_ptr, InkHashTableKey key) 00154 00155 This routine takes a hash table <ht_ptr>, a key <key>, and returns 1 00156 if the value <key> is bound in the hash table, 0 otherwise. 00157 00158 *---------------------------------------------------------------------------*/ 00159 00160 int 00161 ink_hash_table_isbound(InkHashTable * ht_ptr, const char *key) 00162 { 00163 InkHashTableEntry *he_ptr; 00164 00165 he_ptr = ink_hash_table_lookup_entry(ht_ptr, key); 00166 return ((he_ptr == NULL) ? 0 : 1); 00167 } /* End ink_hash_table_isbound */ 00168 00169 00170 /*---------------------------------------------------------------------------* 00171 int ink_hash_table_lookup(InkHashTable *ht_ptr, 00172 InkHashTableKey key, 00173 InkHashTableValue *value_ptr) 00174 00175 This routine takes a hash table <ht_ptr>, a key <key>, and stores the 00176 value bound to the key by reference through <value_ptr>. If no binding is 00177 found, 0 is returned, else 1 is returned. 00178 00179 *---------------------------------------------------------------------------*/ 00180 00181 int 00182 ink_hash_table_lookup(InkHashTable *ht_ptr, const char* key, InkHashTableValue *value_ptr) 00183 { 00184 InkHashTableEntry *he_ptr; 00185 InkHashTableValue value; 00186 00187 he_ptr = ink_hash_table_lookup_entry(ht_ptr, key); 00188 if (he_ptr == NULL) 00189 return (0); 00190 00191 value = ink_hash_table_entry_value(ht_ptr, he_ptr); 00192 *value_ptr = value; 00193 return (1); 00194 } /* End ink_hash_table_lookup */ 00195 00196 00197 /*---------------------------------------------------------------------------* 00198 00199 int ink_hash_table_delete(InkHashTable *ht_ptr, InkHashTableKey key) 00200 00201 This routine takes a hash table <ht_ptr> and a key <key>, and deletes the 00202 binding for the <key> in the hash table if it exists. This routine 00203 returns 1 if the key existed, else 0. 00204 00205 *---------------------------------------------------------------------------*/ 00206 00207 int 00208 ink_hash_table_delete(InkHashTable * ht_ptr, const char *key) 00209 { 00210 char *tcl_key; 00211 Tcl_HashTable *tcl_ht_ptr; 00212 Tcl_HashEntry *tcl_he_ptr; 00213 00214 tcl_key = (char *) key; 00215 tcl_ht_ptr = (Tcl_HashTable *) ht_ptr; 00216 tcl_he_ptr = Tcl_FindHashEntry(tcl_ht_ptr, tcl_key); 00217 00218 if (!tcl_he_ptr) 00219 return (0); 00220 Tcl_DeleteHashEntry(tcl_he_ptr); 00221 00222 return (1); 00223 } /* End ink_hash_table_delete */ 00224 00225 00226 /*---------------------------------------------------------------------------* 00227 00228 InkHashTableEntry *ink_hash_table_lookup_entry(InkHashTable *ht_ptr, 00229 InkHashTableKey key) 00230 00231 This routine takes a hash table <ht_ptr> and a key <key>, and returns the 00232 entry matching the key, or NULL otherwise. 00233 00234 *---------------------------------------------------------------------------*/ 00235 00236 InkHashTableEntry * 00237 ink_hash_table_lookup_entry(InkHashTable * ht_ptr, const char* key) 00238 { 00239 Tcl_HashTable *tcl_ht_ptr; 00240 Tcl_HashEntry *tcl_he_ptr; 00241 InkHashTableEntry *he_ptr; 00242 00243 tcl_ht_ptr = (Tcl_HashTable *) ht_ptr; 00244 tcl_he_ptr = Tcl_FindHashEntry(tcl_ht_ptr, key); 00245 he_ptr = (InkHashTableEntry *) tcl_he_ptr; 00246 00247 return (he_ptr); 00248 } /* End ink_hash_table_lookup_entry */ 00249 00250 00251 /*---------------------------------------------------------------------------* 00252 00253 InkHashTableEntry *ink_hash_table_get_entry(InkHashTable *ht_ptr, 00254 InkHashTableKey key, 00255 int *new_value) 00256 00257 This routine takes a hash table <ht_ptr> and a key <key>, and returns the 00258 entry matching the key, or creates, binds, and returns a new entry. 00259 If the binding already existed, *new is set to 0, else 1. 00260 00261 *---------------------------------------------------------------------------*/ 00262 00263 InkHashTableEntry * 00264 ink_hash_table_get_entry(InkHashTable *ht_ptr, const char *key, int *new_value) 00265 { 00266 Tcl_HashTable *tcl_ht_ptr; 00267 Tcl_HashEntry *tcl_he_ptr; 00268 00269 tcl_ht_ptr = (Tcl_HashTable *) ht_ptr; 00270 tcl_he_ptr = Tcl_CreateHashEntry(tcl_ht_ptr, key, new_value); 00271 00272 if (tcl_he_ptr == NULL) { 00273 ink_fatal(1, "%s: Tcl_CreateHashEntry returned NULL", "ink_hash_table_get_entry"); 00274 } 00275 00276 return ((InkHashTableEntry *) tcl_he_ptr); 00277 } /* End ink_hash_table_get_entry */ 00278 00279 00280 /*---------------------------------------------------------------------------* 00281 00282 void ink_hash_table_set_entry(InkHashTable *ht_ptr, 00283 InkHashTableEntry *he_ptr, 00284 InkHashTableValue value) 00285 00286 This routine takes a hash table <ht_ptr>, a hash table entry <he_ptr>, 00287 and changes the value field of the entry to <value>. 00288 00289 *---------------------------------------------------------------------------*/ 00290 00291 void 00292 ink_hash_table_set_entry(InkHashTable * ht_ptr, InkHashTableEntry * he_ptr, InkHashTableValue value) 00293 { 00294 (void) ht_ptr; 00295 ClientData tcl_value; 00296 Tcl_HashEntry *tcl_he_ptr; 00297 00298 tcl_value = (ClientData) value; 00299 tcl_he_ptr = (Tcl_HashEntry *) he_ptr; 00300 Tcl_SetHashValue(tcl_he_ptr, tcl_value); 00301 } /* End ink_hash_table_set_entry */ 00302 00303 00304 /*---------------------------------------------------------------------------* 00305 00306 void ink_hash_table_insert(InkHashTable *ht_ptr, 00307 InkHashTableKey key, 00308 InkHashTableValue value) 00309 00310 This routine takes a hash table <ht_ptr>, a key <key>, and binds the value 00311 <value> to the key, replacing any previous binding, if any. 00312 00313 *---------------------------------------------------------------------------*/ 00314 00315 void 00316 ink_hash_table_insert(InkHashTable * ht_ptr, const char *key, InkHashTableValue value) 00317 { 00318 int new_value; 00319 InkHashTableEntry *he_ptr; 00320 00321 he_ptr = ink_hash_table_get_entry(ht_ptr, key, &new_value); 00322 ink_hash_table_set_entry(ht_ptr, he_ptr, value); 00323 } /* End ink_hash_table_insert */ 00324 00325 00326 /*---------------------------------------------------------------------------* 00327 00328 void ink_hash_table_map(InkHashTable *ht_ptr, InkHashTableEntryFunction map) 00329 00330 This routine takes a hash table <ht_ptr> and a function pointer <map>, and 00331 applies the function <map> to each entry in the hash table. The function 00332 <map> should return 0 normally, otherwise the iteration will stop. 00333 00334 *---------------------------------------------------------------------------*/ 00335 00336 void 00337 ink_hash_table_map(InkHashTable * ht_ptr, InkHashTableEntryFunction map) 00338 { 00339 int retcode; 00340 InkHashTableEntry *e; 00341 InkHashTableIteratorState state; 00342 00343 for (e = ink_hash_table_iterator_first(ht_ptr, &state); e != NULL; e = ink_hash_table_iterator_next(ht_ptr, &state)) { 00344 retcode = (*map) (ht_ptr, e); 00345 if (retcode != 0) 00346 break; 00347 } 00348 } /* End ink_hash_table_map */ 00349 00350 00351 /*---------------------------------------------------------------------------* 00352 00353 InkHashTableKey ink_hash_table_entry_key(InkHashTable *ht_ptr, 00354 InkHashTableEntry *entry_ptr) 00355 00356 This routine takes a hash table <ht_ptr> and a pointer to a hash table 00357 entry <entry_ptr>, and returns the key portion of the entry. 00358 00359 *---------------------------------------------------------------------------*/ 00360 00361 InkHashTableKey 00362 ink_hash_table_entry_key(InkHashTable * ht_ptr, InkHashTableEntry * entry_ptr) 00363 { 00364 char *tcl_key; 00365 00366 tcl_key = (char*) Tcl_GetHashKey((Tcl_HashTable *) ht_ptr, (Tcl_HashEntry *) entry_ptr); 00367 return ((InkHashTableKey) tcl_key); 00368 } /* End ink_hash_table_entry_key */ 00369 00370 00371 /*---------------------------------------------------------------------------* 00372 00373 InkHashTableValue ink_hash_table_entry_value(InkHashTable *ht_ptr, 00374 InkHashTableEntry *entry_ptr) 00375 00376 This routine takes a hash table <ht_ptr> and a pointer to a hash table 00377 entry <entry_ptr>, and returns the value portion of the entry. 00378 00379 *---------------------------------------------------------------------------*/ 00380 00381 InkHashTableValue 00382 ink_hash_table_entry_value(InkHashTable * ht_ptr, InkHashTableEntry * entry_ptr) 00383 { 00384 (void) ht_ptr; 00385 ClientData tcl_value; 00386 00387 tcl_value = Tcl_GetHashValue((Tcl_HashEntry *) entry_ptr); 00388 return ((InkHashTableValue) tcl_value); 00389 } /* End ink_hash_table_entry_value */ 00390 00391 00392 00393 /*---------------------------------------------------------------------------* 00394 00395 void ink_hash_table_dump_strings(InkHashTable *ht_ptr) 00396 00397 This routine takes a hash table of string values, and dumps the keys and 00398 string values to stdout. It is the caller's responsibility to ensure that 00399 both the key and the value are NUL terminated strings. 00400 00401 *---------------------------------------------------------------------------*/ 00402 00403 static int 00404 DumpStringEntry(InkHashTable * ht_ptr, InkHashTableEntry * e) 00405 { 00406 InkHashTableKey key; 00407 InkHashTableValue value; 00408 00409 key = ink_hash_table_entry_key(ht_ptr, e); 00410 value = ink_hash_table_entry_value(ht_ptr, e); 00411 00412 fprintf(stderr, "key = '%s', value = '%s'\n", (char *) key, (char *) value); 00413 00414 return (0); 00415 } 00416 00417 00418 void 00419 ink_hash_table_dump_strings(InkHashTable * ht_ptr) 00420 { 00421 ink_hash_table_map(ht_ptr, DumpStringEntry); 00422 } /* End ink_hash_table_dump_strings */ 00423 00424 00425 /*---------------------------------------------------------------------------* 00426 00427 void ink_hash_table_replace_string(InkHashTable *ht_ptr, 00428 char *string_key, char *string_value) 00429 00430 This conveninece routine is intended for hash tables with keys of type 00431 InkHashTableKeyType_String, and values being dynamically allocated strings. 00432 This routine binds <string_key> to a copy of <string_value>, and any 00433 previous bound value is deallocated. 00434 00435 *---------------------------------------------------------------------------*/ 00436 00437 void 00438 ink_hash_table_replace_string(InkHashTable * ht_ptr, char *string_key, char *string_value) 00439 { 00440 int new_value; 00441 char *old_str; 00442 InkHashTableEntry *he_ptr; 00443 00444 /* 00445 * The following line will flag a type-conversion warning on the 00446 * DEC Alpha, but that message can be ignored, since we're 00447 * still dealing with pointers, and we aren't loosing any bits. 00448 */ 00449 00450 he_ptr = ink_hash_table_get_entry(ht_ptr, (InkHashTableKey) string_key, &new_value); 00451 if (new_value == 0) { 00452 old_str = (char *) ink_hash_table_entry_value(ht_ptr, he_ptr); 00453 if (old_str) 00454 ats_free(old_str); 00455 } 00456 00457 ink_hash_table_set_entry(ht_ptr, he_ptr, (InkHashTableValue)(ats_strdup(string_value))); 00458 } /* End ink_hash_table_replace_string */
1.7.1