LXR linux/security/selinux/ss/hashtab.c

   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
  12struct 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
  39int 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
  77void *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
  96void 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
 120int 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
 144void 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