selinux/ss/hashtab.h

0001 /* SPDX-License-Identifier: GPL-2.0 */
0002 /*
0003  * A hash table (hashtab) maintains associations between
0004  * key values and datum values.  The type of the key values
0005  * and the type of the datum values is arbitrary.  The
0006  * functions for hash computation and key comparison are
0007  * provided by the creator of the table.
0008  *
0009  * Author : Stephen Smalley, <sds@tycho.nsa.gov>
0010  */
0011 #ifndef _SS_HASHTAB_H_
0012 #define _SS_HASHTAB_H_
0013
0014 #include <linux/types.h>
0015 #include <linux/errno.h>
0016 #include <linux/sched.h>
0017
0018 #define HASHTAB_MAX_NODES   U32_MAX
0019
0020 struct hashtab_key_params {
0021     u32 (*hash)(const void *key);   /* hash function */
0022     int (*cmp)(const void *key1, const void *key2);
0023                     /* key comparison function */
0024 };
0025
0026 struct hashtab_node {
0027     void *key;
0028     void *datum;
0029     struct hashtab_node *next;
0030 };
0031
0032 struct hashtab {
0033     struct hashtab_node **htable;   /* hash table */
0034     u32 size;           /* number of slots in hash table */
0035     u32 nel;            /* number of elements in hash table */
0036 };
0037
0038 struct hashtab_info {
0039     u32 slots_used;
0040     u32 max_chain_len;
0041 };
0042
0043 /*
0044  * Initializes a new hash table with the specified characteristics.
0045  *
0046  * Returns -ENOMEM if insufficient space is available or 0 otherwise.
0047  */
0048 int hashtab_init(struct hashtab *h, u32 nel_hint);
0049
0050 int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst,
0051              void *key, void *datum);
0052
0053 /*
0054  * Inserts the specified (key, datum) pair into the specified hash table.
0055  *
0056  * Returns -ENOMEM on memory allocation error,
0057  * -EEXIST if there is already an entry with the same key,
0058  * -EINVAL for general errors or
0059   0 otherwise.
0060  */
0061 static inline int hashtab_insert(struct hashtab *h, void *key, void *datum,
0062                  struct hashtab_key_params key_params)
0063 {
0064     u32 hvalue;
0065     struct hashtab_node *prev, *cur;
0066
0067     cond_resched();
0068
0069     if (!h->size || h->nel == HASHTAB_MAX_NODES)
0070         return -EINVAL;
0071
0072     hvalue = key_params.hash(key) & (h->size - 1);
0073     prev = NULL;
0074     cur = h->htable[hvalue];
0075     while (cur) {
0076         int cmp = key_params.cmp(key, cur->key);
0077
0078         if (cmp == 0)
0079             return -EEXIST;
0080         if (cmp < 0)
0081             break;
0082         prev = cur;
0083         cur = cur->next;
0084     }
0085
0086     return __hashtab_insert(h, prev ? &prev->next : &h->htable[hvalue],
0087                 key, datum);
0088 }
0089
0090 /*
0091  * Searches for the entry with the specified key in the hash table.
0092  *
0093  * Returns NULL if no entry has the specified key or
0094  * the datum of the entry otherwise.
0095  */
0096 static inline void *hashtab_search(struct hashtab *h, const void *key,
0097                    struct hashtab_key_params key_params)
0098 {
0099     u32 hvalue;
0100     struct hashtab_node *cur;
0101
0102     if (!h->size)
0103         return NULL;
0104
0105     hvalue = key_params.hash(key) & (h->size - 1);
0106     cur = h->htable[hvalue];
0107     while (cur) {
0108         int cmp = key_params.cmp(key, cur->key);
0109
0110         if (cmp == 0)
0111             return cur->datum;
0112         if (cmp < 0)
0113             break;
0114         cur = cur->next;
0115     }
0116     return NULL;
0117 }
0118
0119 /*
0120  * Destroys the specified hash table.
0121  */
0122 void hashtab_destroy(struct hashtab *h);
0123
0124 /*
0125  * Applies the specified apply function to (key,datum,args)
0126  * for each entry in the specified hash table.
0127  *
0128  * The order in which the function is applied to the entries
0129  * is dependent upon the internal structure of the hash table.
0130  *
0131  * If apply returns a non-zero status, then hashtab_map will cease
0132  * iterating through the hash table and will propagate the error
0133  * return to its caller.
0134  */
0135 int hashtab_map(struct hashtab *h,
0136         int (*apply)(void *k, void *d, void *args),
0137         void *args);
0138
0139 int hashtab_duplicate(struct hashtab *new, struct hashtab *orig,
0140         int (*copy)(struct hashtab_node *new,
0141             struct hashtab_node *orig, void *args),
0142         int (*destroy)(void *k, void *d, void *args),
0143         void *args);
0144
0145 /* Fill info with some hash table statistics */
0146 void hashtab_stat(struct hashtab *h, struct hashtab_info *info);
0147
0148 #endif  /* _SS_HASHTAB_H */