libasn1common/genhash.h

   1 /*
   2  * Copyright (c) 2002-2005  Lev Walkin <vlm@lionet.info>. All rights reserved.
   3  * Copyright (c) 2001-2004  Netli, Inc. All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  *
  26  * $Id: genhash.h 447 2005-06-07 06:51:10Z vlm $
  27  */
  28 #ifndef __GENHASH_H__
  29 #define __GENHASH_H__
  30
  31 /*
  32  * General purpose hashing framework.
  33  * Refer to the corresponding .c source file for the detailed description.
  34  *
  35  * WARNING: Generally, functions don't allow NULL's to be passed
  36  * as the genhash_t pointers, if not explicitly stated otherwise.
  37  */
  38
  39 typedef struct genhash_s genhash_t;
  40
  41 /*
  42  * Create a new hash table
  43  * keycmpf      : function which returns 0 if keys are equal, else !0
  44  * keyhashf     : function which computes the hash value of a key
  45  * keydestroyf  : function for destroying keys, can be NULL for no destructor
  46  * valuedestroyf: function for destroying values, can be NULL for no destructor
  47  */
  48 genhash_t *genhash_new(
  49         int (*keycmpf) (const void *key1, const void *key2),
  50         unsigned int (*keyhashf) (const void *key),
  51         void (*keydestroyf) (void *key),
  52         void (*valuedestroyf) (void *value));
  53
  54 /*
  55  * Re-initialize genhash structure with new callback functions.
  56  * (Rarely ever used).
  57  */
  58 int genhash_reinit(
  59         genhash_t *hash,
  60         int (*keycmpf) (const void *key1, const void *key2),
  61         unsigned int (*keyhashf) (const void *key),
  62         void (*keydestroyf) (void *key),
  63         void (*valuedestroyf) (void *value));
  64
  65 /*
  66  * Initialize the LRU-driven elements count limiting
  67  * and/or set a new Least Recently Used list size limit.
  68  * If a new entry is being added to the hash, the least recently used entry
  69  * (one at the bottom of the LRU list) will be automatically deleted.
  70  * The deletion may be skipped if the hash is very small
  71  * (currently, "small" means no longer than 4 entries).
  72  * This function is immune to NULL argument.
  73  *
  74  * RETURN VALUES:
  75  *      The previous LRU limit, or -1/EINVAL when h is NULL.
  76  * EXAMPLE:
  77  *      genhash_set_lru_limit(h, 1500); // Maximum 1500 entries in the hash
  78  */
  79 int genhash_set_lru_limit(genhash_t *h, int new_lru_limit);
  80
  81 /*
  82  * Set the system-wide (!!!) limit on maximum number of buckets.
  83  * If the value is 0, the hash is allowed to store only 4 elements inline
  84  * (buckets allocation is suppressed).
  85  * If the value is 1, the hash turns out into a linked list.
  86  * The default limit is about 1M buckets.
  87  * RETURN VALUES:
  88  *      The previous buckets number limit.
  89  */
  90 int genhash_set_buckets_limit(int new_max_number_of_buckets);
  91
  92 /*
  93  * destroys a hash, freeing each key and/or value.
  94  * Keys are always destroyed before values using the destructors
  95  * specified upon hash creation.
  96  * This function is immune to NULL argument.
  97  */
  98 void genhash_destroy(genhash_t *h);
  99
 100 /*
 101  * Delete all elements from the hash, retaining the hash structure itself.
 102  * Optionally, it may be told to invoke, or not invoke the corresponding
 103  * key/value destructors.
 104  * This function is immune to NULL argument.
 105  *
 106  * EXAMPLE:
 107  *      genhash_empty(h, 1, 1); // Remove all entries, invoking destructors
 108  */
 109 void genhash_empty(genhash_t *h, int freekeys, int freevalues);
 110
 111 /*
 112  * Add, returns 0 on success, -1 on failure (ENOMEM). Note, you CAN add
 113  * records with duplicate keys. No guarantees about order preservations.
 114  *
 115  * EXAMPLE:
 116  *      char *key_str = strdup("key");
 117  *      char *val_str = strdup("arbitrary value");
 118  *      if(genhash_add(h, key_str, val_str) != 0) {
 119  *              free(key_str);
 120  *              free(val_str);
 121  *              perror("genhash_add failed");
 122  *              exit(EX_SOFTWARE);
 123  *      }
 124  */
 125 int genhash_add(genhash_t *h, void *key, void *value);
 126
 127 /*
 128  * Add, but only if a mapping is not there already.
 129  * RETURN VALUES:
 130  * 0:           Element added successfully.
 131  * -1/EINVAL:   Invalid arguments (key == NULL).
 132  * -1/EEXIST:   Duplicate entry is found.
 133  * -1/ENOMEM:   Memory allocation failed
 134  */
 135 int genhash_addunique(genhash_t *h, void *key, void *value);
 136
 137 /*
 138  * Fetch - returns pointer to a value, NULL/ESRCH if not found
 139  */
 140 void *genhash_get(genhash_t *h, const void *key);
 141
 142 /*
 143  * Delete - returns 0 on success, -1/ESRCH if not found.
 144  * Keys are always destroyed before values using the destructors
 145  * specified upon hash creation.
 146  */
 147 int genhash_del(genhash_t *h, void *key);
 148
 149 /*
 150  * Return the number of elements in a hash.
 151  * This function is immune to NULL argument.
 152  */
 153 int genhash_count(genhash_t *h);
 154
 155 /*
 156  * External iterator structure for using with iterator-based walking functions.
 157  * This declaration is NOT INTENDED TO BE USED BY AN APPLICATION DIRECTLY
 158  * The pointer to the already allocated structure must be passed to
 159  * genhash_iter*() functions.
 160  */
 161 typedef struct genhash_iter_s {
 162         genhash_t *hash_ptr;
 163         union {
 164                 int item_number;
 165                 void *location;
 166         } un;
 167         int order_lru_first;
 168         struct genhash_iter_s *iter_prev;
 169         struct genhash_iter_s *iter_next;
 170 } genhash_iter_t;
 171
 172 /*
 173  * Initialize the iterator for walking through the hash.
 174  * The memory block to be used as iterator is provided by the (*iter) pointer.
 175  * This memory must be allocated (possibly, on the stack) by the caller.
 176  * OWNERSHIP:
 177  *      The initialized iterator must be disposed of by calling
 178  *      genhash_iter_done().
 179  * ORDER:
 180  *      By default, the elements are iterated in the "most recent first" order,
 181  *      use reverse_order to change that. For very small number of entries
 182  *      (currently, 4) the order may be IGNORED.
 183  * RETURN VALUES:
 184  *      number of entries the hash had at the moment.
 185  */
 186 int genhash_iter_init(genhash_iter_t *iter,
 187         genhash_t *hash_to_use, int reverse_order);
 188
 189 /*
 190  * Returns the key and value of each element in optional (key) and (value),
 191  * which must be passed as the pointers to pointers (hence these ***'s).
 192  * OWNERSHIP:
 193  *      The key and value are pointers to the internally manageed locations.
 194  * RETURN VALUES:
 195  *      0 if no more elements will be returned, otherwise 1.
 196  * EXAMPLE:
 197  *      key_type_t *key;                        // Pointer to key
 198  *      value_type_t *val;                      // Pointer to value
 199  *      genhash_iter_t iter;                    // Iterator structure
 200  *      genhash_iter_init(&iter, hash_ptr, 0);  // Prepare iterator
 201  *      while(genhash_iter(&iter, &key, &val))  // Iterate over hash elements
 202  *              print_keyval(key, val);         // Use key and value
 203  *      genhash_iter_done(&iter);               // Done iterations.
 204  */
 205 int genhash_iter(genhash_iter_t *iter, void */***/key, void */***/val);
 206
 207 /*
 208  * Dispose of the iterator.
 209  * After this operations, the iterator contents unusable
 210  * and shall not be accesed. (genhash_iter_init() is OK).
 211  */
 212 void genhash_iter_done(genhash_iter_t *iter);
 213
 214 \f
 215 /****************************************************************************/
 216
 217 /*
 218  * The following hashing and comparison functions are provided for
 219  * you, or you may supply your own.
 220  */
 221 unsigned int hashf_int (const void *key); /* Key is an int * */
 222 int cmpf_int (const void *key1, const void *key2);
 223
 224 unsigned int hashf_void (const void *key);
 225 int cmpf_void (const void *key1, const void *key2);
 226
 227 unsigned int hashf_string (const void *key);
 228 int cmpf_string (const void *key1, const void *key2);
 229
 230 #endif  /* __GENHASH_H__ */