3 * \brief A hash table for counting the number of sort networks.
5 * This is more details about what this file does.
8 * libsortnetwork - src/sn_hashtable.c
9 * Copyright (C) 2011 Florian octo Forster
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.
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
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
26 * Florian octo Forster <ff at octo.it>
39 #include "sn_hashtable.h"
43 uint64_t collisions_num;
44 uint64_t networks_num;
49 sn_hashtable_t *sn_hashtable_create (void) /* {{{ */
53 ht = malloc (sizeof (*ht));
56 memset (ht, 0, sizeof (*ht));
61 } /* }}} sn_hashtable_t *sn_hashtable_create */
63 void sn_hashtable_destroy (sn_hashtable_t *ht) /* {{{ */
72 for (i = 0; i < 256; i++)
76 if (ht->data[i] == NULL)
79 for (j = 0; j < 256; j++)
83 if (ht->data[i][j] == NULL)
86 for (k = 0; k < 256; k++)
87 free (ht->data[i][j][k]);
89 free (ht->data[i][j]);
99 } /* }}} void sn_hashtable_destroy */
101 int sn_hashtable_account (sn_hashtable_t *ht, const sn_network_t *n) /* {{{ */
109 if ((ht == NULL) || (n == NULL))
112 hash = (uint32_t) sn_network_get_hashval (n);
114 h0 = (uint8_t) (hash >> 24);
115 h1 = (uint8_t) (hash >> 16);
116 h2 = (uint8_t) (hash >> 8);
119 if (ht->data == NULL)
120 ht->data = calloc (256, sizeof (ht->data[0]));
122 if (ht->data[h0] == NULL)
123 ht->data[h0] = calloc (256, sizeof (ht->data[h0][0]));
125 if (ht->data[h0][h1] == NULL)
126 ht->data[h0][h1] = calloc (256, sizeof (ht->data[h0][h1][0]));
128 if (ht->data[h0][h1][h2] == NULL)
129 ht->data[h0][h1][h2] = calloc (256, sizeof (ht->data[h0][h1][h2][0]));
131 assert (sizeof (ht->data[h0][h1][h2][0]) == sizeof (uint8_t));
133 if (ht->data[h0][h1][h2][h3] == 0)
136 ht->collisions_num++;
138 if (ht->data[h0][h1][h2][h3] < UINT8_MAX)
139 ht->data[h0][h1][h2][h3]++;
142 } /* }}} int sn_hashtable_account */
144 uint64_t sn_hashtable_get_collisions (sn_hashtable_t *ht) /* {{{ */
149 return (ht->collisions_num);
150 } /* }}} uint64_t sn_hashtable_get_collisions */
152 double sn_hashtable_get_collisions_pct (sn_hashtable_t *ht) /* {{{ */
157 return (100.0 * ((double) ht->collisions_num)
158 / ((double) (ht->collisions_num + ht->networks_num)));
159 } /* }}} double sn_hashtable_get_collisions_pct */
161 uint64_t sn_hashtable_get_networks (sn_hashtable_t *ht) /* {{{ */
166 return (ht->networks_num);
167 } /* }}} uint64_t sn_hashtable_get_networks */
169 double sn_hashtable_get_networks_pct (sn_hashtable_t *ht) /* {{{ */
174 return (100.0 * ((double) ht->networks_num)
175 / ((double) (ht->collisions_num + ht->networks_num)));
176 } /* }}} double sn_hashtable_get_networks_pct */
178 uint64_t sn_hashtable_get_total (sn_hashtable_t *ht) /* {{{ */
183 return (ht->collisions_num + ht->networks_num);
184 } /* }}} uint64_t sn_hashtable_get_total */
186 /* vim: set sw=2 sts=2 et fdm=marker : */