Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | |
James Morris | 89d155e | 2005-10-30 14:59:21 -0800 | [diff] [blame] | 18 | p = kzalloc(sizeof(*p), GFP_KERNEL); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 19 | if (p == NULL) |
| 20 | return p; |
| 21 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | |
| 38 | int 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 | |
James Morris | 89d155e | 2005-10-30 14:59:21 -0800 | [diff] [blame] | 57 | newnode = kzalloc(sizeof(*newnode), GFP_KERNEL); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 58 | if (newnode == NULL) |
| 59 | return -ENOMEM; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | |
| 74 | void *hashtab_search(struct hashtab *h, 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 != NULL && 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 | |
| 93 | void 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 != NULL) { |
| 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 | |
| 117 | int 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 != NULL) { |
| 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 | |
| 141 | void 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 | } |