lib/rpmhash.H

   1 /**
   2  * \file lib/rpmhash.h
   3  * Hash table implemenation.
   4  */
   5
   6 #include <string.h>
   7 // Hackery to make sure that macros get expanded
   8 #define __JOIN(a,b) a##b
   9 #define JOIN(a,b) __JOIN(a,b)
  10 #define HASHPREFIX(name) JOIN(HASHTYPE,name)
  11 #define HASHSTRUCT JOIN(HASHTYPE,_s)
  12
  13 typedef struct HASHSTRUCT * HASHTYPE;
  14
  15 /* function pointer types to deal with the datatypes the hash works with */
  16
  17 #define hashFunctionType JOIN(HASHTYPE,HashFunctionType)
  18 #define hashEqualityType JOIN(HASHTYPE,HashEqualityType)
  19 #define hashFreeKey JOIN(HASHTYPE,FreeKey)
  20
  21 typedef unsigned int (*hashFunctionType) (HTKEYTYPE string);
  22 typedef int (*hashEqualityType) (HTKEYTYPE key1, HTKEYTYPE key2);
  23 typedef HTKEYTYPE (*hashFreeKey) (HTKEYTYPE);
  24
  25 #ifdef HTDATATYPE
  26 #define hashFreeData JOIN(HASHTYPE,FreeData)
  27 typedef HTDATATYPE (*hashFreeData) (HTDATATYPE);
  28 #endif
  29
  30 /**
  31  * Create hash table.
  32  * If keySize > 0, the key is duplicated within the table (which costs
  33  * memory, but may be useful anyway.
  34  * @param numBuckets    number of hash buckets
  35  * @param fn            function to generate hash value for key
  36  * @param eq            function to compare hash keys for equality
  37  * @param freeKey       function to free the keys or NULL
  38  * @param freeData      function to free the data or NULL
  39  * @return              pointer to initialized hash table
  40  */
  41 RPM_GNUC_INTERNAL
  42 HASHTYPE  HASHPREFIX(Create)(int numBuckets,
  43                              hashFunctionType fn, hashEqualityType eq,
  44                              hashFreeKey freeKey
  45 #ifdef HTDATATYPE
  46 , hashFreeData freeData
  47 #endif
  48 );
  49
  50 /**
  51  * Destroy hash table.
  52  * @param ht            pointer to hash table
  53  * @return              NULL always
  54  */
  55 RPM_GNUC_INTERNAL
  56 HASHTYPE  HASHPREFIX(Free)( HASHTYPE ht);
  57
  58 /**
  59  * Remove all entries from the hash table.
  60  * @param ht            pointer to hash table
  61  */
  62 RPM_GNUC_INTERNAL
  63 void HASHPREFIX(Empty)(HASHTYPE ht);
  64
  65 /**
  66  * Calculate hash for key.
  67  * @param @ht           pointer to hash table
  68  * @param @key          key
  69  */
  70 RPM_GNUC_INTERNAL
  71 unsigned int HASHPREFIX(KeyHash)(HASHTYPE ht, HTKEYTYPE key);
  72
  73 /**
  74  * Add item to hash table.
  75  * @param ht            pointer to hash table
  76  * @param key           key
  77  * @param data          data value
  78  */
  79 RPM_GNUC_INTERNAL
  80 void  HASHPREFIX(AddEntry)(HASHTYPE ht, HTKEYTYPE key
  81 #ifdef HTDATATYPE
  82 , HTDATATYPE data
  83 #endif
  84 );
  85
  86 /* Add item to hash table with precalculated key hash. */
  87 RPM_GNUC_INTERNAL
  88 void  HASHPREFIX(AddHEntry)(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash
  89 #ifdef HTDATATYPE
  90 , HTDATATYPE data
  91 #endif
  92 );
  93
  94 /**
  95  * Retrieve item from hash table.
  96  * @param ht            pointer to hash table
  97  * @param key           key value
  98  * @retval data         address to store data value from bucket
  99  * @retval dataCount    address to store data value size from bucket
 100  * @retval tableKey     address to store key value from bucket (may be NULL)
 101  * @return              1 on success, 0 if the item is not found.
 102  */
 103 RPM_GNUC_INTERNAL
 104 int  HASHPREFIX(GetEntry)(HASHTYPE ht, HTKEYTYPE key,
 105 #ifdef HTDATATYPE
 106                 HTDATATYPE** data,
 107                 int * dataCount,
 108 #endif
 109                 HTKEYTYPE* tableKey);
 110
 111 /* Retrieve item from hash table with precalculated key hash. */
 112 RPM_GNUC_INTERNAL
 113 int  HASHPREFIX(GetHEntry)(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash,
 114 #ifdef HTDATATYPE
 115                 HTDATATYPE** data,
 116                 int * dataCount,
 117 #endif
 118                 HTKEYTYPE* tableKey);
 119
 120 /**
 121  * Check for key in hash table.
 122  * @param ht            pointer to hash table
 123  * @param key           key value
 124  * @return              1 if the key is present, 0 otherwise
 125  */
 126 RPM_GNUC_INTERNAL
 127 int  HASHPREFIX(HasEntry)(HASHTYPE ht, HTKEYTYPE key);
 128
 129 /* Check for key in hash table with precalculated key hash. */
 130 RPM_GNUC_INTERNAL
 131 int  HASHPREFIX(HasHEntry)(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash);
 132
 133 /**
 134  * How many buckets are currently allocated (result is implementation
 135  * dependent)
 136  * @param ht            pointer to hash table
 137  * @result              number of buckets allocated
 138  */
 139 RPM_GNUC_INTERNAL
 140 unsigned int HASHPREFIX(NumBuckets)(HASHTYPE ht);
 141
 142 /**
 143  * How many buckets are used (result is implementation dependent)
 144  * @param ht            pointer to hash table
 145  * @result              number of buckets used
 146  */
 147 RPM_GNUC_INTERNAL
 148 unsigned int HASHPREFIX(UsedBuckets)(HASHTYPE ht);
 149
 150 /**
 151  * How many (unique) keys have been added to the hash table
 152  * @param ht            pointer to hash table
 153  * @result              number of unique keys
 154  */
 155 RPM_GNUC_INTERNAL
 156 unsigned int HASHPREFIX(NumKeys)(HASHTYPE ht);
 157
 158 #ifdef HTDATATYPE
 159 /**
 160  * How many data entries have been added to the hash table
 161  * @param ht            pointer to hash table
 162  * @result              number of data entries
 163  */
 164 RPM_GNUC_INTERNAL
 165 unsigned int HASHPREFIX(NumData)(HASHTYPE ht);
 166 #endif
 167
 168 /**
 169  * Print statistics about the hash to stderr
 170  * This is for debugging only
 171  * @param ht            pointer to hash table
 172  */
 173 RPM_GNUC_INTERNAL
 174 void HASHPREFIX(PrintStats)(HASHTYPE ht);