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 struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, const void *key), 14 int (*keycmp)(struct hashtab *h, const void *key1, const void *key2), 15 u32 size) 16 { 17 struct hashtab *p; 18 u32 i; 19 20 p = kzalloc(sizeof(*p), GFP_KERNEL); 21 if (!p) 22 return p; 23 24 p->size = size; 25 p->nel = 0; 26 p->hash_value = hash_value; 27 p->keycmp = keycmp; 28 p->htable = kmalloc_array(size, sizeof(*p->htable), GFP_KERNEL); 29 if (!p->htable) { 30 kfree(p); 31 return NULL; 32 } 33 34 for (i = 0; i < size; i++) 35 p->htable[i] = NULL; 36 37 return p; 38 } 39 40 int hashtab_insert(struct hashtab *h, void *key, void *datum) 41 { 42 u32 hvalue; 43 struct hashtab_node *prev, *cur, *newnode; 44 45 cond_resched(); 46 47 if (!h || h->nel == HASHTAB_MAX_NODES) 48 return -EINVAL; 49 50 hvalue = h->hash_value(h, key); 51 prev = NULL; 52 cur = h->htable[hvalue]; 53 while (cur && h->keycmp(h, key, cur->key) > 0) { 54 prev = cur; 55 cur = cur->next; 56 } 57 58 if (cur && (h->keycmp(h, key, cur->key) == 0)) 59 return -EEXIST; 60 61 newnode = kzalloc(sizeof(*newnode), GFP_KERNEL); 62 if (!newnode) 63 return -ENOMEM; 64 newnode->key = key; 65 newnode->datum = datum; 66 if (prev) { 67 newnode->next = prev->next; 68 prev->next = newnode; 69 } else { 70 newnode->next = h->htable[hvalue]; 71 h->htable[hvalue] = newnode; 72 } 73 74 h->nel++; 75 return 0; 76 } 77 78 void *hashtab_search(struct hashtab *h, const void *key) 79 { 80 u32 hvalue; 81 struct hashtab_node *cur; 82 83 if (!h) 84 return NULL; 85 86 hvalue = h->hash_value(h, key); 87 cur = h->htable[hvalue]; 88 while (cur && h->keycmp(h, key, cur->key) > 0) 89 cur = cur->next; 90 91 if (!cur || (h->keycmp(h, key, cur->key) != 0)) 92 return NULL; 93 94 return cur->datum; 95 } 96 97 void hashtab_destroy(struct hashtab *h) 98 { 99 u32 i; 100 struct hashtab_node *cur, *temp; 101 102 if (!h) 103 return; 104 105 for (i = 0; i < h->size; i++) { 106 cur = h->htable[i]; 107 while (cur) { 108 temp = cur; 109 cur = cur->next; 110 kfree(temp); 111 } 112 h->htable[i] = NULL; 113 } 114 115 kfree(h->htable); 116 h->htable = NULL; 117 118 kfree(h); 119 } 120 121 int hashtab_map(struct hashtab *h, 122 int (*apply)(void *k, void *d, void *args), 123 void *args) 124 { 125 u32 i; 126 int ret; 127 struct hashtab_node *cur; 128 129 if (!h) 130 return 0; 131 132 for (i = 0; i < h->size; i++) { 133 cur = h->htable[i]; 134 while (cur) { 135 ret = apply(cur->key, cur->datum, args); 136 if (ret) 137 return ret; 138 cur = cur->next; 139 } 140 } 141 return 0; 142 } 143 144 145 void hashtab_stat(struct hashtab *h, struct hashtab_info *info) 146 { 147 u32 i, chain_len, slots_used, max_chain_len; 148 struct hashtab_node *cur; 149 150 slots_used = 0; 151 max_chain_len = 0; 152 for (slots_used = max_chain_len = i = 0; i < h->size; i++) { 153 cur = h->htable[i]; 154 if (cur) { 155 slots_used++; 156 chain_len = 0; 157 while (cur) { 158 chain_len++; 159 cur = cur->next; 160 } 161 162 if (chain_len > max_chain_len) 163 max_chain_len = chain_len; 164 } 165 } 166 167 info->slots_used = slots_used; 168 info->max_chain_len = max_chain_len; 169 } 170