hash.c

   1 /*
   2  * hash.c - hashing routines mainly used for caching key details.
   3  *
   4  * Copyright 2000-2002 Jonathan McDowell <noodles@earth.li>
   5  *
   6  * This program is free software: you can redistribute it and/or modify it
   7  * under the terms of the GNU General Public License as published by the Free
   8  * Software Foundation; version 2 of the License.
   9  *
  10  * This program is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12  * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
  13  * more details.
  14  *
  15  * You should have received a copy of the GNU General Public License along with
  16  * this program.  If not, see <https://www.gnu.org/licenses/>.
  17  */
  18
  19 #include <stdio.h>
  20 #include <stdlib.h>
  21 #include <string.h>
  22
  23 #include "hash.h"
  24 #include "keystructs.h"
  25 #include "ll.h"
  26 #include "mem.h"
  27 #include "stats.h"
  28
  29 /**
  30  *      hashtable - the hash table array.
  31  */
  32 static struct ll *hashtable[HASHSIZE];
  33
  34 /**
  35  *      elements - the number of elements in the hash table.
  36  */
  37 static unsigned long elements;
  38
  39 /**
  40  *      free_statskey - free an stats key structure.
  41  *      @key: The key to free.
  42  *
  43  *      Takes a stats key and frees the memory used by it and the linked list
  44  *      of sigs under it. Doesn't recurse into the list as it's assumed all the
  45  *      objects referenced also exist in the hash.
  46  */
  47 static void free_statskey(struct stats_key *key)
  48 {
  49         if (key != NULL) {
  50                 if (key->sigs != NULL) {
  51                         llfree(key->sigs, NULL);
  52                         key->sigs = NULL;
  53                 }
  54                 if (key->signs != NULL) {
  55                         llfree(key->signs, NULL);
  56                         key->signs = NULL;
  57                 }
  58                 free(key);
  59         }
  60 }
  61
  62 /**
  63  *      inithash - Initialize the hash ready for use.
  64  */
  65 void inithash(void)
  66 {
  67         unsigned int i;
  68
  69         for (i = 0; i < HASHSIZE; i++) {
  70                 hashtable[i] = NULL;
  71         }
  72         elements = 0;
  73 }
  74
  75 /**
  76  *      destroyhash - Clean up the hash after use.
  77  *
  78  *      This function destroys the hash after use, freeing any memory that was
  79  *      used during its lifetime.
  80  */
  81 void destroyhash(void)
  82 {
  83         int i;
  84         struct ll *curll = NULL;
  85
  86         for (i = 0; i < HASHSIZE; i++) {
  87                 curll = hashtable[i];
  88                 /*
  89                  * TODO: The problem is the object has pointers that
  90                  * need freed too.
  91                  */
  92                 llfree(curll, (void (*)(void *)) free_statskey);
  93                 hashtable[i] = NULL;
  94         }
  95         elements = 0;
  96 }
  97
  98 /**
  99  *      addtohash - Adds a key to the hash.
 100  *      @key: The key to add.
 101  *
 102  *      Takes a key and stores it in the hash.
 103  */
 104 void addtohash(struct stats_key *key)
 105 {
 106         ++elements;
 107         hashtable[key->keyid & HASHMASK]=
 108                 lladd(hashtable[key->keyid & HASHMASK], key);
 109 }
 110
 111 /**
 112  *      createandaddtohash - Creates a key and adds it to the hash.
 113  *      @keyid: The key to create and add.
 114  *
 115  *      Takes a key, checks if it exists in the hash and if not creates it
 116  *      and adds it to the hash. Returns the key from the hash whether it
 117  *      already existed or we just created it.
 118  */
 119 struct stats_key *createandaddtohash(uint64_t keyid)
 120 {
 121         struct stats_key *tmpkey;
 122
 123         /*
 124          * Check if the key already exists and if not create and add it.
 125          */
 126         tmpkey = findinhash(keyid);
 127         if (tmpkey == NULL) {
 128                 tmpkey = malloc(sizeof(*tmpkey));
 129                 memset(tmpkey, 0, sizeof(*tmpkey));
 130                 tmpkey->keyid = keyid;
 131                 addtohash(tmpkey);
 132         }
 133         return tmpkey;
 134 }
 135
 136 static int stats_key_cmp(struct stats_key *key, uint64_t *keyid)
 137 {
 138         return !(key != NULL && key->keyid == *keyid);
 139 }
 140
 141 struct stats_key *findinhash(uint64_t keyid)
 142 {
 143         int (*p)();
 144         struct ll *found;
 145
 146         p = stats_key_cmp;
 147         if ((found = llfind(hashtable[keyid & HASHMASK], &keyid, p))==NULL) {
 148                 return NULL;
 149         }
 150         return found->object;
 151 }
 152
 153 unsigned long hashelements(void)
 154 {
 155         return elements;
 156 }
 157
 158 struct ll *gethashtableentry(unsigned int entry)
 159 {
 160         return hashtable[entry];
 161 }