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 = 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 int hashtab_remove(struct hashtab *h, void *key,
  77                    void (*destroy)(void *k, void *d, void *args),
  78                    void *args)
  79 {
  80         u32 hvalue;
  81         struct hashtab_node *cur, *last;
  82
  83         if (!h)
  84                 return -EINVAL;
  85
  86         hvalue = h->hash_value(h, key);
  87         last = NULL;
  88         cur = h->htable[hvalue];
  89         while (cur != NULL && h->keycmp(h, key, cur->key) > 0) {
  90                 last = cur;
  91                 cur = cur->next;
  92         }
  93
  94         if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
  95                 return -ENOENT;
  96
  97         if (last == NULL)
  98                 h->htable[hvalue] = cur->next;
  99         else
 100                 last->next = cur->next;
 101
 102         if (destroy)
 103                 destroy(cur->key, cur->datum, args);
 104         kfree(cur);
 105         h->nel--;
 106         return 0;
 107 }
 108
 109 int hashtab_replace(struct hashtab *h, void *key, void *datum,
 110                     void (*destroy)(void *k, void *d, void *args),
 111                     void *args)
 112 {
 113         u32 hvalue;
 114         struct hashtab_node *prev, *cur, *newnode;
 115
 116         if (!h)
 117                 return -EINVAL;
 118
 119         hvalue = h->hash_value(h, key);
 120         prev = NULL;
 121         cur = h->htable[hvalue];
 122         while (cur != NULL && h->keycmp(h, key, cur->key) > 0) {
 123                 prev = cur;
 124                 cur = cur->next;
 125         }
 126
 127         if (cur && (h->keycmp(h, key, cur->key) == 0)) {
 128                 if (destroy)
 129                         destroy(cur->key, cur->datum, args);
 130                 cur->key = key;
 131                 cur->datum = datum;
 132         } else {
 133                 newnode = kmalloc(sizeof(*newnode), GFP_KERNEL);
 134                 if (newnode == NULL)
 135                         return -ENOMEM;
 136                 memset(newnode, 0, sizeof(*newnode));
 137                 newnode->key = key;
 138                 newnode->datum = datum;
 139                 if (prev) {
 140                         newnode->next = prev->next;
 141                         prev->next = newnode;
 142                 } else {
 143                         newnode->next = h->htable[hvalue];
 144                         h->htable[hvalue] = newnode;
 145                 }
 146         }
 147
 148         return 0;
 149 }
 150
 151 void *hashtab_search(struct hashtab *h, void *key)
 152 {
 153         u32 hvalue;
 154         struct hashtab_node *cur;
 155
 156         if (!h)
 157                 return NULL;
 158
 159         hvalue = h->hash_value(h, key);
 160         cur = h->htable[hvalue];
 161         while (cur != NULL && h->keycmp(h, key, cur->key) > 0)
 162                 cur = cur->next;
 163
 164         if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
 165                 return NULL;
 166
 167         return cur->datum;
 168 }
 169
 170 void hashtab_destroy(struct hashtab *h)
 171 {
 172         u32 i;
 173         struct hashtab_node *cur, *temp;
 174
 175         if (!h)
 176                 return;
 177
 178         for (i = 0; i < h->size; i++) {
 179                 cur = h->htable[i];
 180                 while (cur != NULL) {
 181                         temp = cur;
 182                         cur = cur->next;
 183                         kfree(temp);
 184                 }
 185                 h->htable[i] = NULL;
 186         }
 187
 188         kfree(h->htable);
 189         h->htable = NULL;
 190
 191         kfree(h);
 192 }
 193
 194 int hashtab_map(struct hashtab *h,
 195                 int (*apply)(void *k, void *d, void *args),
 196                 void *args)
 197 {
 198         u32 i;
 199         int ret;
 200         struct hashtab_node *cur;
 201
 202         if (!h)
 203                 return 0;
 204
 205         for (i = 0; i < h->size; i++) {
 206                 cur = h->htable[i];
 207                 while (cur != NULL) {
 208                         ret = apply(cur->key, cur->datum, args);
 209                         if (ret)
 210                                 return ret;
 211                         cur = cur->next;
 212                 }
 213         }
 214         return 0;
 215 }
 216
 217
 218 void hashtab_map_remove_on_error(struct hashtab *h,
 219                                  int (*apply)(void *k, void *d, void *args),
 220                                  void (*destroy)(void *k, void *d, void *args),
 221                                  void *args)
 222 {
 223         u32 i;
 224         int ret;
 225         struct hashtab_node *last, *cur, *temp;
 226
 227         if (!h)
 228                 return;
 229
 230         for (i = 0; i < h->size; i++) {
 231                 last = NULL;
 232                 cur = h->htable[i];
 233                 while (cur != NULL) {
 234                         ret = apply(cur->key, cur->datum, args);
 235                         if (ret) {
 236                                 if (last)
 237                                         last->next = cur->next;
 238                                 else
 239                                         h->htable[i] = cur->next;
 240
 241                                 temp = cur;
 242                                 cur = cur->next;
 243                                 if (destroy)
 244                                         destroy(temp->key, temp->datum, args);
 245                                 kfree(temp);
 246                                 h->nel--;
 247                         } else {
 248                                 last = cur;
 249                                 cur = cur->next;
 250                         }
 251                 }
 252         }
 253         return;
 254 }
 255
 256 void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
 257 {
 258         u32 i, chain_len, slots_used, max_chain_len;
 259         struct hashtab_node *cur;
 260
 261         slots_used = 0;
 262         max_chain_len = 0;
 263         for (slots_used = max_chain_len = i = 0; i < h->size; i++) {
 264                 cur = h->htable[i];
 265                 if (cur) {
 266                         slots_used++;
 267                         chain_len = 0;
 268                         while (cur) {
 269                                 chain_len++;
 270                                 cur = cur->next;
 271                         }
 272
 273                         if (chain_len > max_chain_len)
 274                                 max_chain_len = chain_len;
 275                 }
 276         }
 277
 278         info->slots_used = slots_used;
 279         info->max_chain_len = max_chain_len;
 280 }