Branch data     Line data    Source code

       1                 :            : // SPDX-License-Identifier: GPL-2.0
       2                 :            : /*
       3                 :            :  * Implementation of the hash table type.
       4                 :            :  *
       5                 :            :  * Author : Stephen Smalley, <sds@tycho.nsa.gov>
       6                 :            :  */
       7                 :            : #include <linux/kernel.h>
       8                 :            : #include <linux/slab.h>
       9                 :            : #include <linux/errno.h>
      10                 :            : #include <linux/sched.h>
      11                 :            : #include "hashtab.h"
      12                 :            : 
      13                 :            : static struct kmem_cache *hashtab_node_cachep;
      14                 :            : 
      15                 :          0 : struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, const void *key),
      16                 :            :                                int (*keycmp)(struct hashtab *h, const void *key1, const void *key2),
      17                 :            :                                u32 size)
      18                 :            : {
      19                 :          0 :         struct hashtab *p;
      20                 :          0 :         u32 i;
      21                 :            : 
      22                 :          0 :         p = kzalloc(sizeof(*p), GFP_KERNEL);
      23         [ #  # ]:          0 :         if (!p)
      24                 :            :                 return p;
      25                 :            : 
      26                 :          0 :         p->size = size;
      27                 :          0 :         p->nel = 0;
      28                 :          0 :         p->hash_value = hash_value;
      29                 :          0 :         p->keycmp = keycmp;
      30                 :          0 :         p->htable = kmalloc_array(size, sizeof(*p->htable), GFP_KERNEL);
      31         [ #  # ]:          0 :         if (!p->htable) {
      32                 :          0 :                 kfree(p);
      33                 :          0 :                 return NULL;
      34                 :            :         }
      35                 :            : 
      36         [ #  # ]:          0 :         for (i = 0; i < size; i++)
      37                 :          0 :                 p->htable[i] = NULL;
      38                 :            : 
      39                 :            :         return p;
      40                 :            : }
      41                 :            : 
      42                 :          0 : int hashtab_insert(struct hashtab *h, void *key, void *datum)
      43                 :            : {
      44                 :          0 :         u32 hvalue;
      45                 :          0 :         struct hashtab_node *prev, *cur, *newnode;
      46                 :            : 
      47                 :          0 :         cond_resched();
      48                 :            : 
      49   [ #  #  #  # ]:          0 :         if (!h || h->nel == HASHTAB_MAX_NODES)
      50                 :            :                 return -EINVAL;
      51                 :            : 
      52                 :          0 :         hvalue = h->hash_value(h, key);
      53                 :          0 :         prev = NULL;
      54                 :          0 :         cur = h->htable[hvalue];
      55   [ #  #  #  # ]:          0 :         while (cur && h->keycmp(h, key, cur->key) > 0) {
      56                 :          0 :                 prev = cur;
      57                 :          0 :                 cur = cur->next;
      58                 :            :         }
      59                 :            : 
      60   [ #  #  #  # ]:          0 :         if (cur && (h->keycmp(h, key, cur->key) == 0))
      61                 :            :                 return -EEXIST;
      62                 :            : 
      63                 :          0 :         newnode = kmem_cache_zalloc(hashtab_node_cachep, GFP_KERNEL);
      64         [ #  # ]:          0 :         if (!newnode)
      65                 :            :                 return -ENOMEM;
      66                 :          0 :         newnode->key = key;
      67                 :          0 :         newnode->datum = datum;
      68         [ #  # ]:          0 :         if (prev) {
      69                 :          0 :                 newnode->next = prev->next;
      70                 :          0 :                 prev->next = newnode;
      71                 :            :         } else {
      72                 :          0 :                 newnode->next = h->htable[hvalue];
      73                 :          0 :                 h->htable[hvalue] = newnode;
      74                 :            :         }
      75                 :            : 
      76                 :          0 :         h->nel++;
      77                 :          0 :         return 0;
      78                 :            : }
      79                 :            : 
      80                 :          0 : void *hashtab_search(struct hashtab *h, const void *key)
      81                 :            : {
      82                 :          0 :         u32 hvalue;
      83                 :          0 :         struct hashtab_node *cur;
      84                 :            : 
      85         [ #  # ]:          0 :         if (!h)
      86                 :            :                 return NULL;
      87                 :            : 
      88                 :          0 :         hvalue = h->hash_value(h, key);
      89                 :          0 :         cur = h->htable[hvalue];
      90   [ #  #  #  # ]:          0 :         while (cur && h->keycmp(h, key, cur->key) > 0)
      91                 :          0 :                 cur = cur->next;
      92                 :            : 
      93   [ #  #  #  # ]:          0 :         if (!cur || (h->keycmp(h, key, cur->key) != 0))
      94                 :          0 :                 return NULL;
      95                 :            : 
      96                 :          0 :         return cur->datum;
      97                 :            : }
      98                 :            : 
      99                 :          0 : void hashtab_destroy(struct hashtab *h)
     100                 :            : {
     101                 :          0 :         u32 i;
     102                 :          0 :         struct hashtab_node *cur, *temp;
     103                 :            : 
     104         [ #  # ]:          0 :         if (!h)
     105                 :            :                 return;
     106                 :            : 
     107         [ #  # ]:          0 :         for (i = 0; i < h->size; i++) {
     108                 :          0 :                 cur = h->htable[i];
     109         [ #  # ]:          0 :                 while (cur) {
     110                 :          0 :                         temp = cur;
     111                 :          0 :                         cur = cur->next;
     112                 :          0 :                         kmem_cache_free(hashtab_node_cachep, temp);
     113                 :            :                 }
     114                 :          0 :                 h->htable[i] = NULL;
     115                 :            :         }
     116                 :            : 
     117                 :          0 :         kfree(h->htable);
     118                 :          0 :         h->htable = NULL;
     119                 :            : 
     120                 :          0 :         kfree(h);
     121                 :            : }
     122                 :            : 
     123                 :          0 : int hashtab_map(struct hashtab *h,
     124                 :            :                 int (*apply)(void *k, void *d, void *args),
     125                 :            :                 void *args)
     126                 :            : {
     127                 :          0 :         u32 i;
     128                 :          0 :         int ret;
     129                 :          0 :         struct hashtab_node *cur;
     130                 :            : 
     131         [ #  # ]:          0 :         if (!h)
     132                 :            :                 return 0;
     133                 :            : 
     134         [ #  # ]:          0 :         for (i = 0; i < h->size; i++) {
     135                 :          0 :                 cur = h->htable[i];
     136         [ #  # ]:          0 :                 while (cur) {
     137                 :          0 :                         ret = apply(cur->key, cur->datum, args);
     138         [ #  # ]:          0 :                         if (ret)
     139                 :          0 :                                 return ret;
     140                 :          0 :                         cur = cur->next;
     141                 :            :                 }
     142                 :            :         }
     143                 :            :         return 0;
     144                 :            : }
     145                 :            : 
     146                 :            : 
     147                 :          0 : void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
     148                 :            : {
     149                 :          0 :         u32 i, chain_len, slots_used, max_chain_len;
     150                 :          0 :         struct hashtab_node *cur;
     151                 :            : 
     152                 :          0 :         slots_used = 0;
     153                 :          0 :         max_chain_len = 0;
     154         [ #  # ]:          0 :         for (i = 0; i < h->size; i++) {
     155                 :          0 :                 cur = h->htable[i];
     156         [ #  # ]:          0 :                 if (cur) {
     157                 :          0 :                         slots_used++;
     158                 :          0 :                         chain_len = 0;
     159         [ #  # ]:          0 :                         while (cur) {
     160                 :          0 :                                 chain_len++;
     161                 :          0 :                                 cur = cur->next;
     162                 :            :                         }
     163                 :            : 
     164                 :          0 :                         if (chain_len > max_chain_len)
     165                 :            :                                 max_chain_len = chain_len;
     166                 :            :                 }
     167                 :            :         }
     168                 :            : 
     169                 :          0 :         info->slots_used = slots_used;
     170                 :          0 :         info->max_chain_len = max_chain_len;
     171                 :          0 : }
     172                 :            : 
     173                 :         13 : void __init hashtab_cache_init(void)
     174                 :            : {
     175                 :         13 :                 hashtab_node_cachep = kmem_cache_create("hashtab_node",
     176                 :            :                         sizeof(struct hashtab_node),
     177                 :            :                         0, SLAB_PANIC, NULL);
     178                 :         13 : }