hashtable.h

   1 /*
   2   Copyright (c) 2002, 2004, Christopher Clark
   3   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 are met:
   7
   8     * Redistributions of source code must retain the above copyright notice,
   9       this list of conditions and the following disclaimer.
  10
  11     * Redistributions in binary form must reproduce the above copyright notice,
  12       this list of conditions and the following disclaimer in the documentation
  13       and/or other materials provided with the distribution.
  14
  15     * Neither the name of the original author; nor the names of any
  16       contributors may be used to endorse or promote products derived from this
  17       software without specific prior written permission.
  18
  19   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20   AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21   IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  22   ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  23   LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24   CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25   SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  27   CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28   ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29   POSSIBILITY OF SUCH DAMAGE.
  30 */
  31
  32 #ifndef __HASHTABLE_CWC22_H__
  33 #define __HASHTABLE_CWC22_H__
  34
  35 #include "config.h"
  36
  37 struct hashtable;
  38
  39 /* Example of use:
  40  *
  41  *      struct hashtable  *h;
  42  *      struct some_key   *k;
  43  *      struct some_value *v;
  44  *
  45  *      static unsigned int         hash_from_key_fn( void *k );
  46  *      static int                  keys_equal_fn ( void *key1, void *key2 );
  47  *
  48  *      h = create_hashtable(16, hash_from_key_fn, keys_equal_fn);
  49  *      k = (struct some_key *)     malloc(sizeof(struct some_key));
  50  *      v = (struct some_value *)   malloc(sizeof(struct some_value));
  51  *
  52  *      (initialise k and v to suitable values)
  53  *
  54  *      if (! hashtable_insert(h,k,v) )
  55  *      {     exit(-1);               }
  56  *
  57  *      if (NULL == (found = hashtable_search(h,k) ))
  58  *      {    printf("not found!");                  }
  59  *
  60  *      if (NULL == (found = hashtable_remove(h,k) ))
  61  *      {    printf("Not found\n");                 }
  62  *
  63  */
  64
  65 /* Macros may be used to define type-safe(r) hashtable access functions, with
  66  * methods specialized to take known key and value types as parameters.
  67  *
  68  * Example:
  69  *
  70  * Insert this at the start of your file:
  71  *
  72  * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value);
  73  * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value);
  74  * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value);
  75  *
  76  * This defines the functions 'insert_some', 'search_some' and 'remove_some'.
  77  * These operate just like hashtable_insert etc., with the same parameters,
  78  * but their function signatures have 'struct some_key *' rather than
  79  * 'void *', and hence can generate compile time errors if your program is
  80  * supplying incorrect data as a key (and similarly for value).
  81  *
  82  * Note that the hash and key equality functions passed to create_hashtable
  83  * still take 'void *' parameters instead of 'some key *'. This shouldn't be
  84  * a difficult issue as they're only defined and passed once, and the other
  85  * functions will ensure that only valid keys are supplied to them.
  86  *
  87  * The cost for this checking is increased code size and runtime overhead
  88  * - if performance is important, it may be worth switching back to the
  89  * unsafe methods once your program has been debugged with the safe methods.
  90  * This just requires switching to some simple alternative defines - eg:
  91  * #define insert_some hashtable_insert
  92  *
  93  */
  94
  95 /*****************************************************************************
  96  * create_hashtable
  97
  98  * @name                    create_hashtable
  99  * @param   minsize         minimum initial size of hashtable
 100  * @param   hashfunction    function for hashing keys
 101  * @param   key_eq_fn       function for determining key equality
 102  * @return                  newly created hashtable or NULL on failure
 103  */
 104
 105 struct hashtable *
 106 create_hashtable(unsigned int minsize,
 107                  unsigned int (*hashfunction) (void*),
 108                  int (*key_eq_fn) (void*,void*));
 109
 110 /*****************************************************************************
 111  * hashtable_insert
 112
 113  * @name        hashtable_insert
 114  * @param   h   the hashtable to insert into
 115  * @param   k   the key - hashtable claims ownership and will free on removal
 116  * @param   v   the value - does not claim ownership
 117  * @return      non-zero for successful insertion
 118  *
 119  * This function will cause the table to expand if the insertion would take
 120  * the ratio of entries to table size over the maximum load factor.
 121  *
 122  * This function does not check for repeated insertions with a duplicate key.
 123  * The value returned when using a duplicate key is undefined -- when
 124  * the hashtable changes size, the order of retrieval of duplicate key
 125  * entries is reversed.
 126  * If in doubt, remove before insert.
 127  */
 128
 129 int
 130 hashtable_insert(struct hashtable *h, void *k, void *v);
 131
 132 #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \
 133 int fnname (struct hashtable *h, keytype *k, valuetype *v) \
 134 { \
 135     return hashtable_insert(h,k,v); \
 136 }
 137
 138 /*****************************************************************************
 139  * hashtable_search
 140
 141  * @name        hashtable_search
 142  * @param   h   the hashtable to search
 143  * @param   k   the key to search for  - does not claim ownership
 144  * @return      the value associated with the key, or NULL if none found
 145  */
 146
 147 void *
 148 hashtable_search(struct hashtable *h, void *k);
 149
 150 #define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \
 151 valuetype * fnname (struct hashtable *h, keytype *k) \
 152 { \
 153     return (valuetype *) (hashtable_search(h,k)); \
 154 }
 155
 156 /*****************************************************************************
 157  * hashtable_remove
 158
 159  * @name        hashtable_remove
 160  * @param   h   the hashtable to remove the item from
 161  * @param   k   the key to search for  - does not claim ownership
 162  * @return      the value associated with the key, or NULL if none found
 163  */
 164
 165 void * /* returns value */
 166 hashtable_remove(struct hashtable *h, void *k);
 167
 168 #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \
 169 valuetype * fnname (struct hashtable *h, keytype *k) \
 170 { \
 171     return (valuetype *) (hashtable_remove(h,k)); \
 172 }
 173
 174
 175 /*****************************************************************************
 176  * hashtable_count
 177
 178  * @name        hashtable_count
 179  * @param   h   the hashtable
 180  * @return      the number of items stored in the hashtable
 181  */
 182 unsigned int
 183 hashtable_count(struct hashtable *h);
 184
 185
 186 /*****************************************************************************
 187  * hashtable_destroy
 188
 189  * @name        hashtable_destroy
 190  * @param   h   the hashtable
 191  * @param       free_values     whether to call 'free' on the remaining values
 192  */
 193
 194 void
 195 hashtable_destroy(struct hashtable *h, int free_values);
 196
 197 #endif /* __HASHTABLE_CWC22_H__ */
 198
 199 /*
 200  * Copyright (c) 2002, Christopher Clark
 201  * All rights reserved.
 202  *
 203  * Redistribution and use in source and binary forms, with or without
 204  * modification, are permitted provided that the following conditions
 205  * are met:
 206  *
 207  * * Redistributions of source code must retain the above copyright
 208  * notice, this list of conditions and the following disclaimer.
 209  *
 210  * * Redistributions in binary form must reproduce the above copyright
 211  * notice, this list of conditions and the following disclaimer in the
 212  * documentation and/or other materials provided with the distribution.
 213  *
 214  * * Neither the name of the original author; nor the names of any contributors
 215  * may be used to endorse or promote products derived from this software
 216  * without specific prior written permission.
 217  *
 218  *
 219  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 220  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 221  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 222  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
 223  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 224  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 225  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 226  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 227  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 228  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 229  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 230 */