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 #if !defined(KERNEL) || defined(UKERNEL)
  32 #include <stddef.h>
  33 #endif
  34
  35 /*
  36  * The user is responsible for generating the key values corresponding
  37  * to the data in the hash table.  The key values should be distributed
  38  * over some interval [0,M], where M is sufficiently large, say
  39  * M > 2**20 (1048576).
  40  */
  41
  42 typedef struct afs_lhash afs_lhash;
  43
  44 struct afs_lhash_stat {
  45     size_t min_chain_length;
  46     size_t max_chain_length;
  47     size_t buckets;
  48     size_t records;
  49
  50     size_t search_calls;        /* cumulative afs_lhash_search() call count */
  51     size_t search_tests;        /* cumulative afs_lhash_search() comparison count */
  52     size_t remove_calls;        /* cumulative afs_lhash_remove() call count */
  53     size_t remove_tests;        /* cumulative afs_lhash_remove() comparison count */
  54 };
  55
  56 /*
  57  * afs_lhash_create() allocates a new hash table.
  58  *
  59  * equal() -- compares table elements for equality
  60  *
  61  * allocate() -- allocates memory
  62  *
  63  * deallocate() -- frees memory acquired via allocate()
  64  *
  65  * afs_lhash_create() returns a pointer to the new hash table, or 0 on
  66  * error.
  67  */
  68
  69 afs_lhash *afs_lhash_create(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(afs_lhash * lh);
  85
  86 /*
  87  * afs_lhash_iter() calls the given function for each element of the
  88  * given hash table.
  89  *
  90  * The function called with the key and data pointer for each element of
  91  * the hash table.  It is also given the hash table index value, in case
  92  * the function wants to compute how many elements are in each bucket.
  93  */
  94
  95 void
  96
  97   afs_lhash_iter(afs_lhash * lh,
  98                  void (*f) (size_t index, unsigned key, void *data)
  99     );
 100
 101 /*
 102  * afs_lhash_search() searches the given hash table for the given key
 103  * and element.
 104  *
 105  * The element may be incomplete; it is compared to elements in the hash
 106  * table using the hash table's equal() function.
 107  *
 108  * If the element is found, it is moved to the front of its hash chain
 109  * list to try to make future lookups faster.
 110  *
 111  * afs_lhash_search() returns a pointer to the desired data element if
 112  * found, 0 otherwise.
 113  */
 114
 115 void *afs_lhash_search(afs_lhash * lh, unsigned key, const void *data);
 116
 117 /*
 118  * afs_lhash_rosearch() searches the given hash table for the given key
 119  * and element.
 120  *
 121  * The element may be incomplete; it is compared to elements in the hash
 122  * table using the hash table's equal() function.
 123  *
 124  * The hash table is not modified.
 125  *
 126  * afs_lhash_rosearch() returns a pointer to the desired data element if
 127  * found, 0 otherwise.
 128  */
 129
 130 void *afs_lhash_rosearch(const afs_lhash * lh, unsigned key,
 131                          const void *data);
 132
 133 /*
 134  * afs_lhash_remove() removes an item matching the given key and data
 135  * from the hash table.
 136  *
 137  * afs_lhash_remove() returns a pointer to the item removed on success,
 138  * 0 otherwise.
 139  */
 140
 141 void *afs_lhash_remove(afs_lhash * lh, unsigned key, const void *data);
 142
 143 /*
 144  * afs_lhash_enter() enters the given data element into the given hash
 145  * table using the given key.
 146  *
 147  * It is not an error to enter the same [key, data] twice, so the
 148  * caller should check for duplicates if that is important.
 149  *
 150  * afs_lhash_enter() returns 0 on success, nonzero otherwise.
 151  */
 152
 153 int
 154   afs_lhash_enter(afs_lhash * lh, unsigned key, void *data);
 155
 156 /*
 157  * afs_lhash_stat() writes certain statistics about the given hash table
 158  * into the given afs_lhash_stat structure.
 159  *
 160  * afs_lhash_stat() returns 0 on success, nonzero otherwise.
 161  */
 162
 163 int
 164   afs_lhash_stat(afs_lhash * lh, struct afs_lhash_stat *sb);
 165
 166 #endif /* AFS_LHASH_H */