1 /* SPDX-License-Identifier: GPL-2.0 */ 2 /* 3 * A hash table (hashtab) maintains associations between 4 * key values and datum values. The type of the key values 5 * and the type of the datum values is arbitrary. The 6 * functions for hash computation and key comparison are 7 * provided by the creator of the table. 8 * 9 * Author : Stephen Smalley, <sds@tycho.nsa.gov> 10 */ 11 #ifndef _SS_HASHTAB_H_ 12 #define _SS_HASHTAB_H_ 13 14 #include <linux/types.h> 15 #include <linux/errno.h> 16 #include <linux/sched.h> 17 18 #define HASHTAB_MAX_NODES U32_MAX 19 20 struct hashtab_key_params { 21 u32 (*hash)(const void *key); /* hash function */ 22 int (*cmp)(const void *key1, const void *key2); 23 /* key comparison function */ 24 }; 25 26 struct hashtab_node { 27 void *key; 28 void *datum; 29 struct hashtab_node *next; 30 }; 31 32 struct hashtab { 33 struct hashtab_node **htable; /* hash table */ 34 u32 size; /* number of slots in hash table */ 35 u32 nel; /* number of elements in hash table */ 36 }; 37 38 struct hashtab_info { 39 u32 slots_used; 40 u32 max_chain_len; 41 }; 42 43 /* 44 * Initializes a new hash table with the specified characteristics. 45 * 46 * Returns -ENOMEM if insufficient space is available or 0 otherwise. 47 */ 48 int hashtab_init(struct hashtab *h, u32 nel_hint); 49 50 int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst, 51 void *key, void *datum); 52 53 /* 54 * Inserts the specified (key, datum) pair into the specified hash table. 55 * 56 * Returns -ENOMEM on memory allocation error, 57 * -EEXIST if there is already an entry with the same key, 58 * -EINVAL for general errors or 59 0 otherwise. 60 */ 61 static inline int hashtab_insert(struct hashtab *h, void *key, void *datum, 62 struct hashtab_key_params key_params) 63 { 64 u32 hvalue; 65 struct hashtab_node *prev, *cur; 66 67 cond_resched(); 68 69 if (!h->size || h->nel == HASHTAB_MAX_NODES) 70 return -EINVAL; 71 72 hvalue = key_params.hash(key) & (h->size - 1); 73 prev = NULL; 74 cur = h->htable[hvalue]; 75 while (cur) { 76 int cmp = key_params.cmp(key, cur->key); 77 78 if (cmp == 0) 79 return -EEXIST; 80 if (cmp < 0) 81 break; 82 prev = cur; 83 cur = cur->next; 84 } 85 86 return __hashtab_insert(h, prev ? &prev->next : &h->htable[hvalue], 87 key, datum); 88 } 89 90 /* 91 * Searches for the entry with the specified key in the hash table. 92 * 93 * Returns NULL if no entry has the specified key or 94 * the datum of the entry otherwise. 95 */ 96 static inline void *hashtab_search(struct hashtab *h, const void *key, 97 struct hashtab_key_params key_params) 98 { 99 u32 hvalue; 100 struct hashtab_node *cur; 101 102 if (!h->size) 103 return NULL; 104 105 hvalue = key_params.hash(key) & (h->size - 1); 106 cur = h->htable[hvalue]; 107 while (cur) { 108 int cmp = key_params.cmp(key, cur->key); 109 110 if (cmp == 0) 111 return cur->datum; 112 if (cmp < 0) 113 break; 114 cur = cur->next; 115 } 116 return NULL; 117 } 118 119 /* 120 * Destroys the specified hash table. 121 */ 122 void hashtab_destroy(struct hashtab *h); 123 124 /* 125 * Applies the specified apply function to (key,datum,args) 126 * for each entry in the specified hash table. 127 * 128 * The order in which the function is applied to the entries 129 * is dependent upon the internal structure of the hash table. 130 * 131 * If apply returns a non-zero status, then hashtab_map will cease 132 * iterating through the hash table and will propagate the error 133 * return to its caller. 134 */ 135 int hashtab_map(struct hashtab *h, 136 int (*apply)(void *k, void *d, void *args), 137 void *args); 138 139 int hashtab_duplicate(struct hashtab *new, struct hashtab *orig, 140 int (*copy)(struct hashtab_node *new, 141 struct hashtab_node *orig, void *args), 142 int (*destroy)(void *k, void *d, void *args), 143 void *args); 144 145 /* Fill info with some hash table statistics */ 146 void hashtab_stat(struct hashtab *h, struct hashtab_info *info); 147 148 #endif /* _SS_HASHTAB_H */ 149