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