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 < 65536; 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 = sn_network_get_hashval (n);
114 h0 = (uint16_t) (hash >> 24);
115 h1 = (uint8_t) (hash >> 16);
116 h2 = (uint8_t) (hash >> 8);
119 if (ht->data == NULL)
120 ht->data = calloc (65536, 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 _Bool sn_hashtable_check_collision (sn_hashtable_t *ht, const sn_network_t *n) /* {{{ */
152 if ((ht == NULL) || (n == NULL))
155 hash = sn_network_get_hashval (n);
157 h0 = (uint16_t) (hash >> 24);
158 h1 = (uint8_t) (hash >> 16);
159 h2 = (uint8_t) (hash >> 8);
162 if (ht->data == NULL)
165 if (ht->data[h0] == NULL)
168 if (ht->data[h0][h1] == NULL)
171 if (ht->data[h0][h1][h2] == NULL)
174 assert (sizeof (ht->data[h0][h1][h2][0]) == sizeof (uint8_t));
176 if (ht->data[h0][h1][h2][h3] == 0)
180 } /* }}} _Bool sn_hashtable_check_collision */
182 uint64_t sn_hashtable_get_collisions (sn_hashtable_t *ht) /* {{{ */
187 return (ht->collisions_num);
188 } /* }}} uint64_t sn_hashtable_get_collisions */
190 double sn_hashtable_get_collisions_pct (sn_hashtable_t *ht) /* {{{ */
195 return (100.0 * ((double) ht->collisions_num)
196 / ((double) (ht->collisions_num + ht->networks_num)));
197 } /* }}} double sn_hashtable_get_collisions_pct */
199 uint64_t sn_hashtable_get_networks (sn_hashtable_t *ht) /* {{{ */
204 return (ht->networks_num);
205 } /* }}} uint64_t sn_hashtable_get_networks */
207 double sn_hashtable_get_networks_pct (sn_hashtable_t *ht) /* {{{ */
212 return (100.0 * ((double) ht->networks_num)
213 / ((double) (ht->collisions_num + ht->networks_num)));
214 } /* }}} double sn_hashtable_get_networks_pct */
216 uint64_t sn_hashtable_get_total (sn_hashtable_t *ht) /* {{{ */
221 return (ht->collisions_num + ht->networks_num);
222 } /* }}} uint64_t sn_hashtable_get_total */
224 /* vim: set sw=2 sts=2 et fdm=marker : */