git.oblomov.eu Git - linux-2.6/blob - security/selinux/ss/hashtab.h

   1 /*
   2  * A hash table (hashtab) maintains associations between
   3  * key values and datum values.  The type of the key values
   4  * and the type of the datum values is arbitrary.  The
   5  * functions for hash computation and key comparison are
   6  * provided by the creator of the table.
   7  *
   8  * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
   9  */
  10 #ifndef _SS_HASHTAB_H_
  11 #define _SS_HASHTAB_H_
  12
  13 #define HASHTAB_MAX_NODES       0xffffffff
  14
  15 struct hashtab_node {
  16         void *key;
  17         void *datum;
  18         struct hashtab_node *next;
  19 };
  20
  21 struct hashtab {
  22         struct hashtab_node **htable;   /* hash table */
  23         u32 size;                       /* number of slots in hash table */
  24         u32 nel;                        /* number of elements in hash table */
  25         u32 (*hash_value)(struct hashtab *h, const void *key);
  26                                         /* hash function */
  27         int (*keycmp)(struct hashtab *h, const void *key1, const void *key2);
  28                                         /* key comparison function */
  29 };
  30
  31 struct hashtab_info {
  32         u32 slots_used;
  33         u32 max_chain_len;
  34 };
  35
  36 /*
  37  * Creates a new hash table with the specified characteristics.
  38  *
  39  * Returns NULL if insufficent space is available or
  40  * the new hash table otherwise.
  41  */
  42 struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, const void *key),
  43                                int (*keycmp)(struct hashtab *h, const void *key1, const void *key2),
  44                                u32 size);
  45
  46 /*
  47  * Inserts the specified (key, datum) pair into the specified hash table.
  48  *
  49  * Returns -ENOMEM on memory allocation error,
  50  * -EEXIST if there is already an entry with the same key,
  51  * -EINVAL for general errors or
  52   0 otherwise.
  53  */
  54 int hashtab_insert(struct hashtab *h, void *k, void *d);
  55
  56 /*
  57  * Searches for the entry with the specified key in the hash table.
  58  *
  59  * Returns NULL if no entry has the specified key or
  60  * the datum of the entry otherwise.
  61  */
  62 void *hashtab_search(struct hashtab *h, const void *k);
  63
  64 /*
  65  * Destroys the specified hash table.
  66  */
  67 void hashtab_destroy(struct hashtab *h);
  68
  69 /*
  70  * Applies the specified apply function to (key,datum,args)
  71  * for each entry in the specified hash table.
  72  *
  73  * The order in which the function is applied to the entries
  74  * is dependent upon the internal structure of the hash table.
  75  *
  76  * If apply returns a non-zero status, then hashtab_map will cease
  77  * iterating through the hash table and will propagate the error
  78  * return to its caller.
  79  */
  80 int hashtab_map(struct hashtab *h,
  81                 int (*apply)(void *k, void *d, void *args),
  82                 void *args);
  83
  84 /* Fill info with some hash table statistics */
  85 void hashtab_stat(struct hashtab *h, struct hashtab_info *info);
  86
  87 #endif  /* _SS_HASHTAB_H */