hash.h

   1 /* Generalized hash and string hash (sash) classes.
   2  * By Richard W.M. Jones <rich@annexia.org>
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public
  15  * License along with this library; if not, write to the Free
  16  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17  *
  18  * $Id: hash.h,v 1.6 2002/11/26 19:47:30 rich Exp $
  19  */
  20
  21 #ifndef HASH_H
  22 #define HASH_H
  23
  24 #include <vector.h>
  25
  26 /* Note, hash and sash are identical but for the fact that
  27  * hash maps fixed sized keys to values (eg. int -> int or
  28  * int -> struct) and sash maps nul-terminated ASCII strings
  29  * to nul-terminated ASCII strings (ie. string -> string ONLY).
  30  * shash maps nul-terminated ASCII strings to anything else.
  31  */
  32
  33 struct hash;
  34 typedef struct hash *hash;
  35
  36 struct sash;
  37 typedef struct sash *sash;
  38
  39 struct shash;
  40 typedef struct shash *shash;
  41
  42 /* Function: new_hash - allocate a new hash
  43  * Function: _hash_new
  44  *
  45  * Allocate a new hash in @code{pool} mapping
  46  * @code{key_type} to @code{value_type}. You can map both
  47  * simple types like @code{int} and also aggregate types
  48  * like structures and unions. However, beware of aggregate
  49  * types that might contain 'holes' because of alignment --
  50  * such types will probably not work as you expect, particularly
  51  * if used as keys.
  52  *
  53  * If you wish to have
  54  * a hash which maps strings to something, then calling
  55  * @code{new_hash(pool, char *, char *)} (for example) will not do what
  56  * you expect. You are better to use either a sash (string to string hash)
  57  * or a shash (string to anything hash) instead (see
  58  * @ref{new_sash(3)} and @ref{new_shash(3)}).
  59  */
  60 #define new_hash(pool,key_type,value_type) _hash_new ((pool), sizeof (key_type), sizeof (value_type))
  61 extern hash _hash_new (pool, size_t key_size, size_t value_size);
  62
  63 /* Function: copy_hash - copy a hash
  64  *
  65  * Copy a hash into a new pool. This function copies the keys
  66  * and values, but if keys and values are pointers, then it does
  67  * not perform a 'deep' copy.
  68  */
  69 extern hash copy_hash (pool, hash);
  70
  71 /* Function: hash_get - look up in a hash
  72  * Function: _hash_get
  73  * Function: hash_get_ptr
  74  * Function: _hash_get_ptr
  75  * Function: hash_exists
  76  *
  77  * Get the @code{value} associated with key @code{key} and return true.
  78  * If there is no @code{value} associated with @code{key}, this returns
  79  * false and @code{value} is left unchanged.
  80  *
  81  * The @code{*_ptr} variants return a pointer rather than copying
  82  * out the entire value object. The pointer is typically only
  83  * valid for a short period of time. Particularly if you insert
  84  * or remove elements from the hash, this pointer may become
  85  * invalid.
  86  *
  87  * @code{hash_exists} simply tests whether or not @code{key} exists
  88  * in the hash. If so, it returns true, otherwise false.
  89  */
  90 #define hash_get(h,key,value) _hash_get ((h), &(key), &(value))
  91 extern int _hash_get (hash, const void *key, void *value);
  92 #define hash_get_ptr(h,key,ptr) ((ptr) = ((typeof (ptr))_hash_get_ptr ((h), &(key))))
  93 extern const void *_hash_get_ptr (hash, const void *key);
  94 #define hash_exists(h,key) (_hash_get_ptr ((h), &(key)) ? 1 : 0)
  95
  96 /* Function: hash_insert - insert a (key, value) pair into a hash
  97  * Function: _hash_insert
  98  *
  99  * Insert an element (@code{key}, @code{value}) into the hash.
 100  * If @code{key} already
 101  * exists in the hash, then the existing value is replaced by
 102  * @code{value}
 103  * and the function returns true. If there was no previous @code{key}
 104  * in the hash then this function returns false.
 105  */
 106 #define hash_insert(h,key,value) _hash_insert((h),&(key),&(value))
 107 extern int _hash_insert (hash, const void *key, const void *value);
 108
 109 /* Function: hash_erase - erase a key from a hash
 110  * Function: _hash_erase
 111  *
 112  * Erase @code{key} from the hash. If an element was erased,
 113  * this returns true, else this returns false.
 114  */
 115 #define hash_erase(h,key) _hash_erase((h),&(key))
 116 extern int _hash_erase (hash, const void *key);
 117
 118 /* Function: hash_keys - return a vector of the keys or values in a hash
 119  * Function: hash_keys_in_pool
 120  * Function: hash_values
 121  * Function: hash_values_in_pool
 122  *
 123  * Return a vector containing all the keys or values of hash. The
 124  * @code{*_in_pool} variants allow you to allocate the vector in
 125  * another pool (the default is to allocate the vector in the same
 126  * pool as the hash).
 127  */
 128 extern vector hash_keys (hash);
 129 extern vector hash_keys_in_pool (hash, pool);
 130 extern vector hash_values (hash);
 131 extern vector hash_values_in_pool (hash, pool);
 132
 133 /* Function: hash_size - return the number of (key, value) pairs in a hash
 134  *
 135  * Count the number of (key, value) pairs in the hash.
 136  */
 137 extern int hash_size (hash);
 138
 139 /* Function: hash_get_buckets_used - return the number of buckets in a hash
 140  * Function: hash_get_buckets_allocated
 141  *
 142  * Return the number of hash buckets used and allocated. The number of
 143  * buckets allocated is always a power of 2. See also
 144  * @ref{hash_set_buckets_allocated} to change the number used
 145  * in the hash.
 146  */
 147 extern int hash_get_buckets_used (hash);
 148 extern int hash_get_buckets_allocated (hash);
 149
 150 /* Function: hash_set_buckets_allocated - set the number of buckets
 151  *
 152  * Set the number of buckets allocated. You may ONLY do this when you
 153  * have just created the hash and before you have inserted any elements.
 154  * Otherwise the results are undefined (and probably bad). The number
 155  * of buckets MUST be a power of 2.
 156  */
 157 extern void hash_set_buckets_allocated (hash, int);
 158
 159 /* Function: new_sash - allocate a new sash (string hash)
 160  *
 161  * Allocate a new sash in @code{pool} mapping
 162  * strings to strings.
 163  *
 164  * Use a string hash in preference to a hash of
 165  * @code{char *} -> @code{char *} which will probably not
 166  * quite work as you expect.
 167  */
 168 extern sash new_sash (pool);
 169
 170 /* Function: copy_sash - copy a sash
 171  *
 172  * Copy a sash into a new pool. This function copies the keys
 173  * and values, but if keys and values are pointers, then it does
 174  * not perform a 'deep' copy.
 175  */
 176 extern sash copy_sash (pool, sash);
 177
 178 /* Function: sash_get - look up in a sash
 179  * Function: _sash_get
 180  * Function: sash_exists
 181  *
 182  * Get the @code{value} associated with key @code{key} and return true.
 183  * If there is no @code{value} associated with @code{key}, this returns
 184  * false and @code{value} is left unchanged.
 185  *
 186  * @code{sash_exists} simply tests whether or not @code{key} exists
 187  * in the sash. If so, it returns true, otherwise false.
 188  */
 189 #define sash_get(sash,key,value) _sash_get((sash),(key),&(value))
 190 extern int _sash_get (sash, const char *key, const char **ptr);
 191 #define sash_exists(sash,key) _sash_get ((sash), (key), 0)
 192
 193 /* Function: sash_insert - insert a (key, value) pair into a sash
 194  *
 195  * Insert an element (@code{key}, @code{value}) into the sash.
 196  * If @code{key} already
 197  * exists in the sash, then the existing value is replaced by
 198  * @code{value}
 199  * and the function returns true. If there was no previous @code{key}
 200  * in the sash then this function returns false.
 201  */
 202 extern int sash_insert (sash, const char *key, const char *value);
 203
 204 /* Function: sash_erase - erase a key from a sash
 205  *
 206  * Erase @code{key} from the sash. If an element was erased,
 207  * this returns true, else this returns false.
 208  */
 209 extern int sash_erase (sash, const char *key);
 210
 211 /* Function: sash_keys - return a vector of the keys or values in a sash
 212  * Function: sash_keys_in_pool
 213  * Function: sash_values
 214  * Function: sash_values_in_pool
 215  *
 216  * Return a vector containing all the keys or values of sash. The
 217  * @code{*_in_pool} variants allow you to allocate the vector in
 218  * another pool (the default is to allocate the vector in the same
 219  * pool as the sash).
 220  */
 221 extern vector sash_keys (sash);
 222 extern vector sash_keys_in_pool (sash, pool);
 223 extern vector sash_values (sash);
 224 extern vector sash_values_in_pool (sash, pool);
 225
 226 /* Function: sash_size - return the number of (key, value) pairs in a sash
 227  *
 228  * Count the number of (key, value) pairs in the sash.
 229  */
 230 extern int sash_size (sash);
 231
 232 /* Function: sash_get_buckets_used - return the number of buckets in a sash
 233  * Function: sash_get_buckets_allocated
 234  *
 235  * Return the number of sash buckets used and allocated. The number of
 236  * buckets allocated is always a power of 2. See also
 237  * @ref{sash_set_buckets_allocated} to change the number used
 238  * in the sash.
 239  */
 240 extern int sash_get_buckets_used (sash);
 241 extern int sash_get_buckets_allocated (sash);
 242
 243 /* Function: sash_set_buckets_allocated - set the number of buckets
 244  *
 245  * Set the number of buckets allocated. You may ONLY do this when you
 246  * have just created the sash and before you have inserted any elements.
 247  * Otherwise the results are undefined (and probably bad). The number
 248  * of buckets MUST be a power of 2.
 249  */
 250 extern void sash_set_buckets_allocated (sash, int);
 251
 252 /* Function: new_shash - allocate a new shash (string -> something hash)
 253  *
 254  * Allocate a new shash in @code{pool} mapping
 255  * strings to strings.
 256  *
 257  * Use a shash in preference to a hash of
 258  * @code{char *} -> something which will probably not
 259  * quite work as you expect.
 260  */
 261 #define new_shash(pool,value_type) _shash_new ((pool), sizeof (value_type))
 262 extern shash _shash_new (pool, size_t value_size);
 263
 264 /* Function: copy_shash - copy a shash
 265  *
 266  * Copy a shash into a new pool. This function copies the keys
 267  * and values, but if keys and values are pointers, then it does
 268  * not perform a 'deep' copy.
 269  */
 270 extern shash copy_shash (pool, shash);
 271
 272 /* Function: shash_get - look up in a shash
 273  * Function: _shash_get
 274  * Function: shash_get_ptr
 275  * Function: _shash_get_ptr
 276  * Function: shash_exists
 277  *
 278  * Get the @code{value} associated with key @code{key} and return true.
 279  * If there is no @code{value} associated with @code{key}, this returns
 280  * false and @code{value} is left unchanged.
 281  *
 282  * The @code{*_ptr} variants return a pointer rather than copying
 283  * out the entire value object. The pointer is typically only
 284  * valid for a short period of time. Particularly if you insert
 285  * or remove elements from the shash, this pointer may become
 286  * invalid.
 287  *
 288  * @code{shash_exists} simply tests whether or not @code{key} exists
 289  * in the shash. If so, it returns true, otherwise false.
 290  */
 291 #define shash_get(shash,key,value) _shash_get((shash),(key),&(value))
 292 extern int _shash_get (shash, const char *key, void *value);
 293 #define shash_get_ptr(h,key,ptr) ((ptr) = ((typeof (ptr))_shash_get_ptr ((h),(key))))
 294 extern const void *_shash_get_ptr (shash, const char *key);
 295 #define shash_exists(shash,key) (_shash_get_ptr ((shash), (key)) ? 1 : 0)
 296
 297 /* Function: shash_insert - insert a (key, value) pair into a shash
 298  * Function: _shash_insert
 299  *
 300  * Insert an element (@code{key}, @code{value}) into the shash.
 301  * If @code{key} already
 302  * exists in the shash, then the existing value is replaced by
 303  * @code{value}
 304  * and the function returns true. If there was no previous @code{key}
 305  * in the shash then this function returns false.
 306  */
 307 #define shash_insert(h,key,value) _shash_insert((h),(key),&(value))
 308 extern int _shash_insert (shash, const char *key, const void *value);
 309
 310 /* Function: shash_erase - erase a key from a shash
 311  *
 312  * Erase @code{key} from the shash. If an element was erased,
 313  * this returns true, else this returns false.
 314  */
 315 extern int shash_erase (shash, const char *key);
 316
 317 /* Function: shash_keys - return a vector of the keys or values in a shash
 318  * Function: shash_keys_in_pool
 319  * Function: shash_values
 320  * Function: shash_values_in_pool
 321  *
 322  * Return a vector containing all the keys or values of shash. The
 323  * @code{*_in_pool} variants allow you to allocate the vector in
 324  * another pool (the default is to allocate the vector in the same
 325  * pool as the shash).
 326  */
 327 extern vector shash_keys (shash);
 328 extern vector shash_keys_in_pool (shash, pool);
 329 extern vector shash_values (shash);
 330 extern vector shash_values_in_pool (shash, pool);
 331
 332 /* Function: shash_size - return the number of (key, value) pairs in a shash
 333  *
 334  * Count the number of (key, value) pairs in the shash.
 335  */
 336 extern int shash_size (shash);
 337
 338 /* Function: shash_get_buckets_used - return the number of buckets in a shash
 339  * Function: shash_get_buckets_allocated
 340  *
 341  * Return the number of shash buckets used and allocated. The number of
 342  * buckets allocated is always a power of 2. See also
 343  * @ref{shash_set_buckets_allocated} to change the number used
 344  * in the shash.
 345  */
 346 extern int shash_get_buckets_used (shash);
 347 extern int shash_get_buckets_allocated (shash);
 348
 349 /* Function: shash_set_buckets_allocated - set the number of buckets
 350  *
 351  * Set the number of buckets allocated. You may ONLY do this when you
 352  * have just created the shash and before you have inserted any elements.
 353  * Otherwise the results are undefined (and probably bad). The number
 354  * of buckets MUST be a power of 2.
 355  */
 356 extern void shash_set_buckets_allocated (shash, int);
 357
 358 #endif /* HASH_H */