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 | |
| 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 | } |