SAFE public projects git trees. - safe/jmp/linux-2.6/blob - 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 void *hashtab_search(struct hashtab *h, void *key)
  77 {
  78         u32 hvalue;
  79         struct hashtab_node *cur;
  80
  81         if (!h)
  82                 return NULL;
  83
  84         hvalue = h->hash_value(h, key);
  85         cur = h->htable[hvalue];
  86         while (cur != NULL && h->keycmp(h, key, cur->key) > 0)
  87                 cur = cur->next;
  88
  89         if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
  90                 return NULL;
  91
  92         return cur->datum;
  93 }
  94
  95 void hashtab_destroy(struct hashtab *h)
  96 {
  97         u32 i;
  98         struct hashtab_node *cur, *temp;
  99
 100         if (!h)
 101                 return;
 102
 103         for (i = 0; i < h->size; i++) {
 104                 cur = h->htable[i];
 105                 while (cur != NULL) {
 106                         temp = cur;
 107                         cur = cur->next;
 108                         kfree(temp);
 109                 }
 110                 h->htable[i] = NULL;
 111         }
 112
 113         kfree(h->htable);
 114         h->htable = NULL;
 115
 116         kfree(h);
 117 }
 118
 119 int hashtab_map(struct hashtab *h,
 120                 int (*apply)(void *k, void *d, void *args),
 121                 void *args)
 122 {
 123         u32 i;
 124         int ret;
 125         struct hashtab_node *cur;
 126
 127         if (!h)
 128                 return 0;
 129
 130         for (i = 0; i < h->size; i++) {
 131                 cur = h->htable[i];
 132                 while (cur != NULL) {
 133                         ret = apply(cur->key, cur->datum, args);
 134                         if (ret)
 135                                 return ret;
 136                         cur = cur->next;
 137                 }
 138         }
 139         return 0;
 140 }
 141
 142
 143 void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
 144 {
 145         u32 i, chain_len, slots_used, max_chain_len;
 146         struct hashtab_node *cur;
 147
 148         slots_used = 0;
 149         max_chain_len = 0;
 150         for (slots_used = max_chain_len = i = 0; i < h->size; i++) {
 151                 cur = h->htable[i];
 152                 if (cur) {
 153                         slots_used++;
 154                         chain_len = 0;
 155                         while (cur) {
 156                                 chain_len++;
 157                                 cur = cur->next;
 158                         }
 159
 160                         if (chain_len > max_chain_len)
 161                                 max_chain_len = chain_len;
 162                 }
 163         }
 164
 165         info->slots_used = slots_used;
 166         info->max_chain_len = max_chain_len;
 167 }