00001 /* 00002 * Copyright 2003, 2004, 2005, 2006 PathScale, Inc. All Rights Reserved. 00003 */ 00004 00005 /* An expandable hash tables datatype. 00006 Copyright (C) 1999, 2000, 2002, 2003, 2004 Free Software Foundation, Inc. 00007 Contributed by Vladimir Makarov (vmakarov@cygnus.com). 00008 00009 This program is free software; you can redistribute it and/or modify 00010 it under the terms of the GNU General Public License as published by 00011 the Free Software Foundation; either version 2 of the License, or 00012 (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 00017 GNU General Public License for more details. 00018 00019 You should have received a copy of the GNU General Public License 00020 along with this program; if not, write to the Free Software 00021 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ 00022 00023 /* This package implements basic hash table functionality. It is possible 00024 to search for an entry, create an entry and destroy an entry. 00025 00026 Elements in the table are generic pointers. 00027 00028 The size of the table is not fixed; if the occupancy of the table 00029 grows too high the hash table will be expanded. 00030 00031 The abstract data implementation is based on generalized Algorithm D 00032 from Knuth's book "The art of computer programming". Hash table is 00033 expanded by creation of new hash table and transferring elements from 00034 the old table to the new table. */ 00035 00036 #ifndef __HASHTAB_H__ 00037 #define __HASHTAB_H__ 00038 00039 #ifdef __cplusplus 00040 extern "C" { 00041 #endif /* __cplusplus */ 00042 00043 #include "ansidecl.h" 00044 00045 #ifndef GTY 00046 #define GTY(X) 00047 #endif 00048 00049 /* The type for a hash code. */ 00050 typedef unsigned int hashval_t; 00051 00052 /* Callback function pointer types. */ 00053 00054 /* Calculate hash of a table entry. */ 00055 typedef hashval_t (*htab_hash) PARAMS ((const void *)); 00056 00057 /* Compare a table entry with a possible entry. The entry already in 00058 the table always comes first, so the second element can be of a 00059 different type (but in this case htab_find and htab_find_slot 00060 cannot be used; instead the variants that accept a hash value 00061 must be used). */ 00062 typedef int (*htab_eq) PARAMS ((const void *, const void *)); 00063 00064 /* Cleanup function called whenever a live element is removed from 00065 the hash table. */ 00066 typedef void (*htab_del) PARAMS ((void *)); 00067 00068 /* Function called by htab_traverse for each live element. The first 00069 arg is the slot of the element (which can be passed to htab_clear_slot 00070 if desired), the second arg is the auxiliary pointer handed to 00071 htab_traverse. Return 1 to continue scan, 0 to stop. */ 00072 typedef int (*htab_trav) PARAMS ((void **, void *)); 00073 00074 /* Memory-allocation function, with the same functionality as calloc(). 00075 Iff it returns NULL, the hash table implementation will pass an error 00076 code back to the user, so if your code doesn't handle errors, 00077 best if you use xcalloc instead. */ 00078 typedef PTR (*htab_alloc) PARAMS ((size_t, size_t)); 00079 00080 /* We also need a free() routine. */ 00081 typedef void (*htab_free) PARAMS ((PTR)); 00082 00083 /* Memory allocation and deallocation; variants which take an extra 00084 argument. */ 00085 typedef PTR (*htab_alloc_with_arg) PARAMS ((void *, size_t, size_t)); 00086 typedef void (*htab_free_with_arg) PARAMS ((void *, void *)); 00087 00088 /* Hash tables are of the following type. The structure 00089 (implementation) of this type is not needed for using the hash 00090 tables. All work with hash table should be executed only through 00091 functions mentioned below. The size of this structure is subject to 00092 change. */ 00093 00094 struct htab GTY(()) 00095 { 00096 /* Pointer to hash function. */ 00097 htab_hash hash_f; 00098 00099 /* Pointer to comparison function. */ 00100 htab_eq eq_f; 00101 00102 /* Pointer to cleanup function. */ 00103 htab_del del_f; 00104 00105 /* Table itself. */ 00106 PTR * GTY ((use_param, length ("%h.size"))) entries; 00107 00108 /* Current size (in entries) of the hash table. */ 00109 size_t size; 00110 00111 /* Current number of elements including also deleted elements. */ 00112 size_t n_elements; 00113 00114 /* Current number of deleted elements in the table. */ 00115 size_t n_deleted; 00116 00117 /* The following member is used for debugging. Its value is number 00118 of all calls of `htab_find_slot' for the hash table. */ 00119 unsigned int searches; 00120 00121 /* The following member is used for debugging. Its value is number 00122 of collisions fixed for time of work with the hash table. */ 00123 unsigned int collisions; 00124 00125 /* Pointers to allocate/free functions. */ 00126 htab_alloc alloc_f; 00127 htab_free free_f; 00128 00129 /* Alternate allocate/free functions, which take an extra argument. */ 00130 PTR GTY((skip)) alloc_arg; 00131 htab_alloc_with_arg alloc_with_arg_f; 00132 htab_free_with_arg free_with_arg_f; 00133 00134 /* Current size (in entries) of the hash table, as an index into the 00135 table of primes. */ 00136 unsigned int size_prime_index; 00137 }; 00138 00139 typedef struct htab *htab_t; 00140 00141 /* An enum saying whether we insert into the hash table or not. */ 00142 enum insert_option {NO_INSERT, INSERT}; 00143 00144 /* The prototypes of the package functions. */ 00145 00146 extern htab_t htab_create_alloc PARAMS ((size_t, htab_hash, 00147 htab_eq, htab_del, 00148 htab_alloc, htab_free)); 00149 00150 extern htab_t htab_create_alloc_ex PARAMS ((size_t, htab_hash, 00151 htab_eq, htab_del, 00152 PTR, htab_alloc_with_arg, 00153 htab_free_with_arg)); 00154 00155 /* Backward-compatibility functions. */ 00156 extern htab_t htab_create PARAMS ((size_t, htab_hash, htab_eq, htab_del)); 00157 extern htab_t htab_try_create PARAMS ((size_t, htab_hash, htab_eq, htab_del)); 00158 00159 extern void htab_set_functions_ex PARAMS ((htab_t, htab_hash, 00160 htab_eq, htab_del, 00161 PTR, htab_alloc_with_arg, 00162 htab_free_with_arg)); 00163 00164 extern void htab_delete PARAMS ((htab_t)); 00165 extern void htab_empty PARAMS ((htab_t)); 00166 00167 extern PTR htab_find PARAMS ((htab_t, const void *)); 00168 extern PTR *htab_find_slot PARAMS ((htab_t, const void *, 00169 enum insert_option)); 00170 extern PTR htab_find_with_hash PARAMS ((htab_t, const void *, 00171 hashval_t)); 00172 extern PTR *htab_find_slot_with_hash PARAMS ((htab_t, const void *, 00173 hashval_t, 00174 enum insert_option)); 00175 extern void htab_clear_slot PARAMS ((htab_t, void **)); 00176 extern void htab_remove_elt PARAMS ((htab_t, void *)); 00177 extern void htab_remove_elt_with_hash PARAMS ((htab_t, void *, hashval_t)); 00178 00179 extern void htab_traverse PARAMS ((htab_t, htab_trav, void *)); 00180 extern void htab_traverse_noresize PARAMS ((htab_t, htab_trav, void *)); 00181 00182 extern size_t htab_size PARAMS ((htab_t)); 00183 extern size_t htab_elements PARAMS ((htab_t)); 00184 extern double htab_collisions PARAMS ((htab_t)); 00185 00186 /* A hash function for pointers. */ 00187 extern htab_hash htab_hash_pointer; 00188 00189 /* An equality function for pointers. */ 00190 extern htab_eq htab_eq_pointer; 00191 00192 /* A hash function for null-terminated strings. */ 00193 extern hashval_t htab_hash_string PARAMS ((const PTR)); 00194 00195 /* An iterative hash function for arbitrary data. */ 00196 extern hashval_t iterative_hash PARAMS ((const PTR, size_t, hashval_t)); 00197 /* Shorthand for hashing something with an intrinsic size. */ 00198 #define iterative_hash_object(OB,INIT) iterative_hash (&OB, sizeof (OB), INIT) 00199 00200 #ifdef __cplusplus 00201 } 00202 #endif /* __cplusplus */ 00203 00204 #endif /* __HASHTAB_H */
1.5.6