security/selinux/ss/hashtab.c

   1 /*
   2  * Implementation of the hash table type.
   3  *
   4  * Author : Stephen Smalley, <sds@tycho.nsa.gov>
   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
  12 struct 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)
  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_array(size, sizeof(*p->htable), GFP_KERNEL);
  28         if (!p->htable) {
  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         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)
  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
  77 void *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 || (h->keycmp(h, key, cur->key) != 0))
  91                 return NULL;
  92
  93         return cur->datum;
  94 }
  95
  96 void 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
 120 int 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
 144 void 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 }