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