src/sn_hashtable.c

   1 /**
   2  * \file sn_hashtable.c
   3  * \brief A hash table for counting the number of sort networks.
   4  *
   5  * This is more details about what this file does.
   6  *
   7  * \verbatim
   8  * libsortnetwork - src/sn_hashtable.c
   9  * Copyright (C) 2011  Florian octo Forster
  10  *
  11  * This library is free software; you can redistribute it and/or modify it
  12  * under the terms of the GNU Lesser General Public License as published by
  13  * the Free Software Foundation; either version 2.1 of the License, or (at
  14  * your option) any later version.
  15  *
  16  * This library is distributed in the hope that it will be useful, but WITHOUT
  17  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  18  * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
  19  * for more details.
  20  *
  21  * You should have received a copy of the GNU Lesser General Public License
  22  * along with this library; if not, write to the Free Software Foundation,
  23  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  24  *
  25  * Authors:
  26  *   Florian octo Forster <ff at octo.it>
  27  * \endverbatim
  28  **/
  29
  30 #include <stdlib.h>
  31 #include <stdio.h>
  32 #include <stdint.h>
  33 #include <inttypes.h>
  34 #include <string.h>
  35 #include <math.h>
  36 #include <errno.h>
  37 #include <assert.h>
  38
  39 #include "sn_hashtable.h"
  40
  41 struct sn_hashtable_s
  42 {
  43   uint64_t collisions_num;
  44   uint64_t networks_num;
  45
  46   uint8_t ****data;
  47 };
  48
  49 sn_hashtable_t *sn_hashtable_create (void) /* {{{ */
  50 {
  51   sn_hashtable_t *ht;
  52
  53   ht = malloc (sizeof (*ht));
  54   if (ht == NULL)
  55     return (NULL);
  56   memset (ht, 0, sizeof (*ht));
  57
  58   ht->data = NULL;
  59
  60   return (ht);
  61 } /* }}} sn_hashtable_t *sn_hashtable_create */
  62
  63 void sn_hashtable_destroy (sn_hashtable_t *ht) /* {{{ */
  64 {
  65   if (ht == NULL)
  66     return;
  67
  68   if (ht->data != NULL)
  69   {
  70     int i;
  71
  72     for (i = 0; i < 65536; i++)
  73     {
  74       int j;
  75
  76       if (ht->data[i] == NULL)
  77         continue;
  78
  79       for (j = 0; j < 256; j++)
  80       {
  81         int k;
  82
  83         if (ht->data[i][j] == NULL)
  84           continue;
  85
  86         for (k = 0; k < 256; k++)
  87           free (ht->data[i][j][k]);
  88
  89         free (ht->data[i][j]);
  90       }
  91
  92       free (ht->data[i]);
  93     }
  94
  95     free (ht->data);
  96   }
  97
  98   free (ht);
  99 } /* }}} void sn_hashtable_destroy */
 100
 101 int sn_hashtable_account (sn_hashtable_t *ht, const sn_network_t *n) /* {{{ */
 102 {
 103   uint64_t hash;
 104   uint16_t h0;
 105   uint8_t h1;
 106   uint8_t h2;
 107   uint8_t h3;
 108
 109   if ((ht == NULL) || (n == NULL))
 110     return (EINVAL);
 111
 112   hash = sn_network_get_hashval (n);
 113
 114   h0 = (uint16_t) (hash >> 24);
 115   h1 = (uint8_t)  (hash >> 16);
 116   h2 = (uint8_t)  (hash >>  8);
 117   h3 = (uint8_t)   hash;
 118
 119   if (ht->data == NULL)
 120     ht->data = calloc (65536, sizeof (ht->data[0]));
 121
 122   if (ht->data[h0] == NULL)
 123     ht->data[h0] = calloc (256, sizeof (ht->data[h0][0]));
 124
 125   if (ht->data[h0][h1] == NULL)
 126     ht->data[h0][h1] = calloc (256, sizeof (ht->data[h0][h1][0]));
 127
 128   if (ht->data[h0][h1][h2] == NULL)
 129     ht->data[h0][h1][h2] = calloc (256, sizeof (ht->data[h0][h1][h2][0]));
 130
 131   assert (sizeof (ht->data[h0][h1][h2][0]) == sizeof (uint8_t));
 132
 133   if (ht->data[h0][h1][h2][h3] == 0)
 134     ht->networks_num++;
 135   else
 136     ht->collisions_num++;
 137
 138   if (ht->data[h0][h1][h2][h3] < UINT8_MAX)
 139     ht->data[h0][h1][h2][h3]++;
 140
 141   return (0);
 142 } /* }}} int sn_hashtable_account */
 143
 144 _Bool sn_hashtable_check_collision (sn_hashtable_t *ht, const sn_network_t *n) /* {{{ */
 145 {
 146   uint64_t hash;
 147   uint16_t h0;
 148   uint8_t h1;
 149   uint8_t h2;
 150   uint8_t h3;
 151
 152   if ((ht == NULL) || (n == NULL))
 153     return (0);
 154
 155   hash = sn_network_get_hashval (n);
 156
 157   h0 = (uint16_t) (hash >> 24);
 158   h1 = (uint8_t)  (hash >> 16);
 159   h2 = (uint8_t)  (hash >>  8);
 160   h3 = (uint8_t)   hash;
 161
 162   if (ht->data == NULL)
 163     return (0);
 164
 165   if (ht->data[h0] == NULL)
 166     return (0);
 167
 168   if (ht->data[h0][h1] == NULL)
 169     return (0);
 170
 171   if (ht->data[h0][h1][h2] == NULL)
 172     return (0);
 173
 174   assert (sizeof (ht->data[h0][h1][h2][0]) == sizeof (uint8_t));
 175
 176   if (ht->data[h0][h1][h2][h3] == 0)
 177     return (0);
 178   else
 179     return (1);
 180 } /* }}} _Bool sn_hashtable_check_collision */
 181
 182 uint64_t sn_hashtable_get_collisions (sn_hashtable_t *ht) /* {{{ */
 183 {
 184   if (ht == NULL)
 185     return (0);
 186
 187   return (ht->collisions_num);
 188 } /* }}} uint64_t sn_hashtable_get_collisions */
 189
 190 double sn_hashtable_get_collisions_pct (sn_hashtable_t *ht) /* {{{ */
 191 {
 192   if (ht == NULL)
 193     return (NAN);
 194
 195   return (100.0 * ((double) ht->collisions_num)
 196       / ((double) (ht->collisions_num + ht->networks_num)));
 197 } /* }}} double sn_hashtable_get_collisions_pct */
 198
 199 uint64_t sn_hashtable_get_networks (sn_hashtable_t *ht) /* {{{ */
 200 {
 201   if (ht == NULL)
 202     return (0);
 203
 204   return (ht->networks_num);
 205 } /* }}} uint64_t sn_hashtable_get_networks */
 206
 207 double sn_hashtable_get_networks_pct (sn_hashtable_t *ht) /* {{{ */
 208 {
 209   if (ht == NULL)
 210     return (NAN);
 211
 212   return (100.0 * ((double) ht->networks_num)
 213       / ((double) (ht->collisions_num + ht->networks_num)));
 214 } /* }}} double sn_hashtable_get_networks_pct */
 215
 216 uint64_t sn_hashtable_get_total (sn_hashtable_t *ht) /* {{{ */
 217 {
 218   if (ht == NULL)
 219     return (0);
 220
 221   return (ht->collisions_num + ht->networks_num);
 222 } /* }}} uint64_t sn_hashtable_get_total */
 223
 224 /* vim: set sw=2 sts=2 et fdm=marker : */