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