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 /**
  87  * Retrieve item from hash table.
  88  * @param ht            pointer to hash table
  89  * @param key           key value
  90  * @retval data         address to store data value from bucket
  91  * @retval dataCount    address to store data value size from bucket
  92  * @retval tableKey     address to store key value from bucket (may be NULL)
  93  * @return              1 on success, 0 if the item is not found.
  94  */
  95 RPM_GNUC_INTERNAL
  96 int  HASHPREFIX(GetEntry)(HASHTYPE ht, HTKEYTYPE key,
  97 #ifdef HTDATATYPE
  98                 HTDATATYPE** data,
  99                 int * dataCount,
 100 #endif
 101                 HTKEYTYPE* tableKey);
 102
 103 /**
 104  * Check for key in hash table.
 105  * @param ht            pointer to hash table
 106  * @param key           key value
 107  * @return              1 if the key is present, 0 otherwise
 108  */
 109 RPM_GNUC_INTERNAL
 110 int  HASHPREFIX(HasEntry)(HASHTYPE ht, HTKEYTYPE key);
 111
 112 /**
 113  * How many buckets are currently allocated (result is implementation
 114  * dependent)
 115  * @param ht            pointer to hash table
 116  * @result              number of buckets allocated
 117  */
 118 RPM_GNUC_INTERNAL
 119 unsigned int HASHPREFIX(NumBuckets)(HASHTYPE ht);
 120
 121 /**
 122  * How many buckets are used (result is implementation dependent)
 123  * @param ht            pointer to hash table
 124  * @result              number of buckets used
 125  */
 126 RPM_GNUC_INTERNAL
 127 unsigned int HASHPREFIX(UsedBuckets)(HASHTYPE ht);
 128
 129 /**
 130  * How many (unique) keys have been added to the hash table
 131  * @param ht            pointer to hash table
 132  * @result              number of unique keys
 133  */
 134 RPM_GNUC_INTERNAL
 135 unsigned int HASHPREFIX(NumKeys)(HASHTYPE ht);
 136
 137 #ifdef HTDATATYPE
 138 /**
 139  * How many data entries have been added to the hash table
 140  * @param ht            pointer to hash table
 141  * @result              number of data entries
 142  */
 143 RPM_GNUC_INTERNAL
 144 unsigned int HASHPREFIX(NumData)(HASHTYPE ht);
 145 #endif
 146
 147 /**
 148  * Print statistics about the hash to stderr
 149  * This is for debugging only
 150  * @param ht            pointer to hash table
 151  */
 152 RPM_GNUC_INTERNAL
 153 void HASHPREFIX(PrintStats)(HASHTYPE ht);