1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Implementation of the hash table type. 4 * 5 * Author : Stephen Smalley, <sds@tycho.nsa.gov> 6 */ 7 #include <linux/kernel.h> 8 #include <linux/slab.h> 9 #include <linux/errno.h> 10 #include <linux/sched.h> 11 #include "hashtab.h" 12 13 static struct kmem_cache *hashtab_node_cachep; 14 15 struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, const void *key), 16 int (*keycmp)(struct hashtab *h, const void *key1, const void *key2), 17 u32 size) 18 { 19 struct hashtab *p; 20 u32 i; 21 22 p = kzalloc(sizeof(*p), GFP_KERNEL); 23 if (!p) 24 return p; 25 26 p->size = size; 27 p->nel = 0; 28 p->hash_value = hash_value; 29 p->keycmp = keycmp; 30 p->htable = kmalloc_array(size, sizeof(*p->htable), GFP_KERNEL); 31 if (!p->htable) { 32 kfree(p); 33 return NULL; 34 } 35 36 for (i = 0; i < size; i++) 37 p->htable[i] = NULL; 38 39 return p; 40 } 41 42 int hashtab_insert(struct hashtab *h, void *key, void *datum) 43 { 44 u32 hvalue; 45 struct hashtab_node *prev, *cur, *newnode; 46 47 cond_resched(); 48 49 if (!h || h->nel == HASHTAB_MAX_NODES) 50 return -EINVAL; 51 52 hvalue = h->hash_value(h, key); 53 prev = NULL; 54 cur = h->htable[hvalue]; 55 while (cur && h->keycmp(h, key, cur->key) > 0) { 56 prev = cur; 57 cur = cur->next; 58 } 59 60 if (cur && (h->keycmp(h, key, cur->key) == 0)) 61 return -EEXIST; 62 63 newnode = kmem_cache_zalloc(hashtab_node_cachep, GFP_KERNEL); 64 if (!newnode) 65 return -ENOMEM; 66 newnode->key = key; 67 newnode->datum = datum; 68 if (prev) { 69 newnode->next = prev->next; 70 prev->next = newnode; 71 } else { 72 newnode->next = h->htable[hvalue]; 73 h->htable[hvalue] = newnode; 74 } 75 76 h->nel++; 77 return 0; 78 } 79 80 void *hashtab_search(struct hashtab *h, const void *key) 81 { 82 u32 hvalue; 83 struct hashtab_node *cur; 84 85 if (!h) 86 return NULL; 87 88 hvalue = h->hash_value(h, key); 89 cur = h->htable[hvalue]; 90 while (cur && h->keycmp(h, key, cur->key) > 0) 91 cur = cur->next; 92 93 if (!cur || (h->keycmp(h, key, cur->key) != 0)) 94 return NULL; 95 96 return cur->datum; 97 } 98 99 void hashtab_destroy(struct hashtab *h) 100 { 101 u32 i; 102 struct hashtab_node *cur, *temp; 103 104 if (!h) 105 return; 106 107 for (i = 0; i < h->size; i++) { 108 cur = h->htable[i]; 109 while (cur) { 110 temp = cur; 111 cur = cur->next; 112 kmem_cache_free(hashtab_node_cachep, temp); 113 } 114 h->htable[i] = NULL; 115 } 116 117 kfree(h->htable); 118 h->htable = NULL; 119 120 kfree(h); 121 } 122 123 int hashtab_map(struct hashtab *h, 124 int (*apply)(void *k, void *d, void *args), 125 void *args) 126 { 127 u32 i; 128 int ret; 129 struct hashtab_node *cur; 130 131 if (!h) 132 return 0; 133 134 for (i = 0; i < h->size; i++) { 135 cur = h->htable[i]; 136 while (cur) { 137 ret = apply(cur->key, cur->datum, args); 138 if (ret) 139 return ret; 140 cur = cur->next; 141 } 142 } 143 return 0; 144 } 145 146 147 void hashtab_stat(struct hashtab *h, struct hashtab_info *info) 148 { 149 u32 i, chain_len, slots_used, max_chain_len; 150 struct hashtab_node *cur; 151 152 slots_used = 0; 153 max_chain_len = 0; 154 for (i = 0; i < h->size; i++) { 155 cur = h->htable[i]; 156 if (cur) { 157 slots_used++; 158 chain_len = 0; 159 while (cur) { 160 chain_len++; 161 cur = cur->next; 162 } 163 164 if (chain_len > max_chain_len) 165 max_chain_len = chain_len; 166 } 167 } 168 169 info->slots_used = slots_used; 170 info->max_chain_len = max_chain_len; 171 } 172 173 void __init hashtab_cache_init(void) 174 { 175 hashtab_node_cachep = kmem_cache_create("hashtab_node", 176 sizeof(struct hashtab_node), 177 0, SLAB_PANIC, NULL); 178 } 179