11da177e4SLinus Torvalds /* 21da177e4SLinus Torvalds * Implementation of the hash table type. 31da177e4SLinus Torvalds * 41da177e4SLinus Torvalds * Author : Stephen Smalley, <sds@epoch.ncsc.mil> 51da177e4SLinus Torvalds */ 61da177e4SLinus Torvalds #include <linux/kernel.h> 71da177e4SLinus Torvalds #include <linux/slab.h> 81da177e4SLinus Torvalds #include <linux/errno.h> 91da177e4SLinus Torvalds #include "hashtab.h" 101da177e4SLinus Torvalds 111da177e4SLinus Torvalds struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, void *key), 121da177e4SLinus Torvalds int (*keycmp)(struct hashtab *h, void *key1, void *key2), 131da177e4SLinus Torvalds u32 size) 141da177e4SLinus Torvalds { 151da177e4SLinus Torvalds struct hashtab *p; 161da177e4SLinus Torvalds u32 i; 171da177e4SLinus Torvalds 181da177e4SLinus Torvalds p = kmalloc(sizeof(*p), GFP_KERNEL); 191da177e4SLinus Torvalds if (p == NULL) 201da177e4SLinus Torvalds return p; 211da177e4SLinus Torvalds 221da177e4SLinus Torvalds memset(p, 0, sizeof(*p)); 231da177e4SLinus Torvalds p->size = size; 241da177e4SLinus Torvalds p->nel = 0; 251da177e4SLinus Torvalds p->hash_value = hash_value; 261da177e4SLinus Torvalds p->keycmp = keycmp; 271da177e4SLinus Torvalds p->htable = kmalloc(sizeof(*(p->htable)) * size, GFP_KERNEL); 281da177e4SLinus Torvalds if (p->htable == NULL) { 291da177e4SLinus Torvalds kfree(p); 301da177e4SLinus Torvalds return NULL; 311da177e4SLinus Torvalds } 321da177e4SLinus Torvalds 331da177e4SLinus Torvalds for (i = 0; i < size; i++) 341da177e4SLinus Torvalds p->htable[i] = NULL; 351da177e4SLinus Torvalds 361da177e4SLinus Torvalds return p; 371da177e4SLinus Torvalds } 381da177e4SLinus Torvalds 391da177e4SLinus Torvalds int hashtab_insert(struct hashtab *h, void *key, void *datum) 401da177e4SLinus Torvalds { 411da177e4SLinus Torvalds u32 hvalue; 421da177e4SLinus Torvalds struct hashtab_node *prev, *cur, *newnode; 431da177e4SLinus Torvalds 441da177e4SLinus Torvalds if (!h || h->nel == HASHTAB_MAX_NODES) 451da177e4SLinus Torvalds return -EINVAL; 461da177e4SLinus Torvalds 471da177e4SLinus Torvalds hvalue = h->hash_value(h, key); 481da177e4SLinus Torvalds prev = NULL; 491da177e4SLinus Torvalds cur = h->htable[hvalue]; 501da177e4SLinus Torvalds while (cur && h->keycmp(h, key, cur->key) > 0) { 511da177e4SLinus Torvalds prev = cur; 521da177e4SLinus Torvalds cur = cur->next; 531da177e4SLinus Torvalds } 541da177e4SLinus Torvalds 551da177e4SLinus Torvalds if (cur && (h->keycmp(h, key, cur->key) == 0)) 561da177e4SLinus Torvalds return -EEXIST; 571da177e4SLinus Torvalds 581da177e4SLinus Torvalds newnode = kmalloc(sizeof(*newnode), GFP_KERNEL); 591da177e4SLinus Torvalds if (newnode == NULL) 601da177e4SLinus Torvalds return -ENOMEM; 611da177e4SLinus Torvalds memset(newnode, 0, sizeof(*newnode)); 621da177e4SLinus Torvalds newnode->key = key; 631da177e4SLinus Torvalds newnode->datum = datum; 641da177e4SLinus Torvalds if (prev) { 651da177e4SLinus Torvalds newnode->next = prev->next; 661da177e4SLinus Torvalds prev->next = newnode; 671da177e4SLinus Torvalds } else { 681da177e4SLinus Torvalds newnode->next = h->htable[hvalue]; 691da177e4SLinus Torvalds h->htable[hvalue] = newnode; 701da177e4SLinus Torvalds } 711da177e4SLinus Torvalds 721da177e4SLinus Torvalds h->nel++; 731da177e4SLinus Torvalds return 0; 741da177e4SLinus Torvalds } 751da177e4SLinus Torvalds 761da177e4SLinus Torvalds void *hashtab_search(struct hashtab *h, void *key) 771da177e4SLinus Torvalds { 781da177e4SLinus Torvalds u32 hvalue; 791da177e4SLinus Torvalds struct hashtab_node *cur; 801da177e4SLinus Torvalds 811da177e4SLinus Torvalds if (!h) 821da177e4SLinus Torvalds return NULL; 831da177e4SLinus Torvalds 841da177e4SLinus Torvalds hvalue = h->hash_value(h, key); 851da177e4SLinus Torvalds cur = h->htable[hvalue]; 861da177e4SLinus Torvalds while (cur != NULL && h->keycmp(h, key, cur->key) > 0) 871da177e4SLinus Torvalds cur = cur->next; 881da177e4SLinus Torvalds 891da177e4SLinus Torvalds if (cur == NULL || (h->keycmp(h, key, cur->key) != 0)) 901da177e4SLinus Torvalds return NULL; 911da177e4SLinus Torvalds 921da177e4SLinus Torvalds return cur->datum; 931da177e4SLinus Torvalds } 941da177e4SLinus Torvalds 951da177e4SLinus Torvalds void hashtab_destroy(struct hashtab *h) 961da177e4SLinus Torvalds { 971da177e4SLinus Torvalds u32 i; 981da177e4SLinus Torvalds struct hashtab_node *cur, *temp; 991da177e4SLinus Torvalds 1001da177e4SLinus Torvalds if (!h) 1011da177e4SLinus Torvalds return; 1021da177e4SLinus Torvalds 1031da177e4SLinus Torvalds for (i = 0; i < h->size; i++) { 1041da177e4SLinus Torvalds cur = h->htable[i]; 1051da177e4SLinus Torvalds while (cur != NULL) { 1061da177e4SLinus Torvalds temp = cur; 1071da177e4SLinus Torvalds cur = cur->next; 1081da177e4SLinus Torvalds kfree(temp); 1091da177e4SLinus Torvalds } 1101da177e4SLinus Torvalds h->htable[i] = NULL; 1111da177e4SLinus Torvalds } 1121da177e4SLinus Torvalds 1131da177e4SLinus Torvalds kfree(h->htable); 1141da177e4SLinus Torvalds h->htable = NULL; 1151da177e4SLinus Torvalds 1161da177e4SLinus Torvalds kfree(h); 1171da177e4SLinus Torvalds } 1181da177e4SLinus Torvalds 1191da177e4SLinus Torvalds int hashtab_map(struct hashtab *h, 1201da177e4SLinus Torvalds int (*apply)(void *k, void *d, void *args), 1211da177e4SLinus Torvalds void *args) 1221da177e4SLinus Torvalds { 1231da177e4SLinus Torvalds u32 i; 1241da177e4SLinus Torvalds int ret; 1251da177e4SLinus Torvalds struct hashtab_node *cur; 1261da177e4SLinus Torvalds 1271da177e4SLinus Torvalds if (!h) 1281da177e4SLinus Torvalds return 0; 1291da177e4SLinus Torvalds 1301da177e4SLinus Torvalds for (i = 0; i < h->size; i++) { 1311da177e4SLinus Torvalds cur = h->htable[i]; 1321da177e4SLinus Torvalds while (cur != NULL) { 1331da177e4SLinus Torvalds ret = apply(cur->key, cur->datum, args); 1341da177e4SLinus Torvalds if (ret) 1351da177e4SLinus Torvalds return ret; 1361da177e4SLinus Torvalds cur = cur->next; 1371da177e4SLinus Torvalds } 1381da177e4SLinus Torvalds } 1391da177e4SLinus Torvalds return 0; 1401da177e4SLinus Torvalds } 1411da177e4SLinus Torvalds 1421da177e4SLinus Torvalds 1431da177e4SLinus Torvalds void hashtab_stat(struct hashtab *h, struct hashtab_info *info) 1441da177e4SLinus Torvalds { 1451da177e4SLinus Torvalds u32 i, chain_len, slots_used, max_chain_len; 1461da177e4SLinus Torvalds struct hashtab_node *cur; 1471da177e4SLinus Torvalds 1481da177e4SLinus Torvalds slots_used = 0; 1491da177e4SLinus Torvalds max_chain_len = 0; 1501da177e4SLinus Torvalds for (slots_used = max_chain_len = i = 0; i < h->size; i++) { 1511da177e4SLinus Torvalds cur = h->htable[i]; 1521da177e4SLinus Torvalds if (cur) { 1531da177e4SLinus Torvalds slots_used++; 1541da177e4SLinus Torvalds chain_len = 0; 1551da177e4SLinus Torvalds while (cur) { 1561da177e4SLinus Torvalds chain_len++; 1571da177e4SLinus Torvalds cur = cur->next; 1581da177e4SLinus Torvalds } 1591da177e4SLinus Torvalds 1601da177e4SLinus Torvalds if (chain_len > max_chain_len) 1611da177e4SLinus Torvalds max_chain_len = chain_len; 1621da177e4SLinus Torvalds } 1631da177e4SLinus Torvalds } 1641da177e4SLinus Torvalds 1651da177e4SLinus Torvalds info->slots_used = slots_used; 1661da177e4SLinus Torvalds info->max_chain_len = max_chain_len; 1671da177e4SLinus Torvalds } 168