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 "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 = kzalloc(sizeof(*p), GFP_KERNEL);
  19         if (p == NULL)
  20                 return p;
  21
  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
  57         newnode = kzalloc(sizeof(*newnode), GFP_KERNEL);
  58         if (newnode == NULL)
  59                 return -ENOMEM;
  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 }