src/util/afs_lhash.h

   1 /*
   2  * Copyright 2000, International Business Machines Corporation and others.
   3  * All Rights Reserved.
   4  *
   5  * This software has been released under the terms of the IBM Public
   6  * License.  For details, see the LICENSE file in the top-level source
   7  * directory or online at http://www.openafs.org/dl/license10.html
   8  */
   9
  10 /*
  11  * An afs_lhash is a linear hash table.  It is intended for use where
  12  * the number of elements in the hash table is not known in advance.
  13  * It grows as required in order to keep the average hash chain length
  14  * within certain bounds, which keeps average lookup times small.
  15  * Growth is efficient and does not require rehashing of all the
  16  * elements in the table at once.
  17  *
  18  * The caller is responsible for doing any required locking.
  19  *
  20  * For more information on the algorithm, see
  21  *
  22  *      Dynamic Hash Tables
  23  *      Per-Åke Larson (Per-Ake Larson)
  24  *      Communications of the ACM
  25  *      Vol. 31, No. 4 (April 1988), Pages 446-457
  26  */
  27
  28 #ifndef AFS_LHASH_H
  29 #define AFS_LHASH_H
  30
  31 #include <stddef.h>
  32
  33 /*
  34  * The user is responsible for generating the key values corresponding
  35  * to the data in the hash table.  The key values should be distributed
  36  * over some interval [0,M], where M is sufficiently large, say
  37  * M > 2**20 (1048576).
  38  */
  39
  40 typedef struct afs_lhash afs_lhash;
  41
  42 struct afs_lhash_stat {
  43     size_t      min_chain_length;
  44     size_t      max_chain_length;
  45     size_t      buckets;
  46     size_t      records;
  47
  48     size_t      search_calls;   /* cumulative afs_lhash_search() call count */
  49     size_t      search_tests;   /* cumulative afs_lhash_search() comparison count */
  50     size_t      remove_calls;   /* cumulative afs_lhash_remove() call count */
  51     size_t      remove_tests;   /* cumulative afs_lhash_remove() comparison count */
  52 };
  53
  54 /*
  55  * afs_lhash_create() allocates a new hash table.
  56  *
  57  * equal() -- compares table elements for equality
  58  *
  59  * allocate() -- allocates memory
  60  *
  61  * deallocate() -- frees memory acquired via allocate()
  62  *
  63  * afs_lhash_create() returns a pointer to the new hash table, or 0 on
  64  * error.
  65  */
  66
  67 afs_lhash *
  68 afs_lhash_create
  69 ( int (*equal)(const void *a, const void *b)
  70         /* returns true if the elements pointed to by
  71            a and b are the same, false otherwise */
  72 , void *(*allocate)(size_t n)
  73 , void (*deallocate)(void *p, size_t n)
  74 );
  75
  76 /*
  77  * afs_lhash_destroy() destroys the given hash table.
  78  *
  79  * Note that the caller is responsible for freeing the table elements if
  80  * required.
  81  */
  82
  83 void
  84 afs_lhash_destroy
  85 ( afs_lhash *lh
  86 );
  87
  88 /*
  89  * afs_lhash_iter() calls the given function for each element of the
  90  * given hash table.
  91  *
  92  * The function called with the key and data pointer for each element of
  93  * the hash table.  It is also given the hash table index value, in case
  94  * the function wants to compute how many elements are in each bucket.
  95  */
  96
  97 void
  98 afs_lhash_iter
  99 ( afs_lhash *lh
 100 , void(*f)(size_t index, unsigned key, void *data)
 101 );
 102
 103 /*
 104  * afs_lhash_search() searches the given hash table for the given key
 105  * and element.
 106  *
 107  * The element may be incomplete; it is compared to elements in the hash
 108  * table using the hash table's equal() function.
 109  *
 110  * If the element is found, it is moved to the front of its hash chain
 111  * list to try to make future lookups faster.
 112  *
 113  * afs_lhash_search() returns a pointer to the desired data element if
 114  * found, 0 otherwise.
 115  */
 116
 117 void *
 118 afs_lhash_search
 119 ( afs_lhash *lh
 120 , unsigned key
 121 , const void *data
 122 );
 123
 124 /*
 125  * afs_lhash_rosearch() searches the given hash table for the given key
 126  * and element.
 127  *
 128  * The element may be incomplete; it is compared to elements in the hash
 129  * table using the hash table's equal() function.
 130  *
 131  * The hash table is not modified.
 132  *
 133  * afs_lhash_rosearch() returns a pointer to the desired data element if
 134  * found, 0 otherwise.
 135  */
 136
 137 void *
 138 afs_lhash_rosearch
 139 ( const afs_lhash *lh
 140 , unsigned key
 141 , const void *data
 142 );
 143
 144 /*
 145  * afs_lhash_remove() removes an item matching the given key and data
 146  * from the hash table.
 147  *
 148  * afs_lhash_remove() returns a pointer to the item removed on success,
 149  * 0 otherwise.
 150  */
 151
 152 void *
 153 afs_lhash_remove
 154 ( afs_lhash *lh
 155 , unsigned key
 156 , const void *data
 157 );
 158
 159 /*
 160  * afs_lhash_enter() enters the given data element into the given hash
 161  * table using the given key.
 162  *
 163  * It is not an error to enter the same [key, data] twice, so the
 164  * caller should check for duplicates if that is important.
 165  *
 166  * afs_lhash_enter() returns 0 on success, nonzero otherwise.
 167  */
 168
 169 int
 170 afs_lhash_enter
 171 ( afs_lhash *lh
 172 , unsigned key
 173 , void *data
 174 );
 175
 176 /*
 177  * afs_lhash_stat() writes certain statistics about the given hash table
 178  * into the given afs_lhash_stat structure.
 179  *
 180  * afs_lhash_stat() returns 0 on success, nonzero otherwise.
 181  */
 182
 183 int
 184 afs_lhash_stat
 185 ( afs_lhash *lh
 186 , struct afs_lhash_stat *sb
 187 );
 188
 189 #endif /* AFS_LHASH_H */