From 41a304ffa32d46f12921e19e10bce093d48cfbd9 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Thu, 13 Jan 2011 12:57:16 +0100 Subject: [PATCH] src/sn_hashtable.[ch]: Add module for counting sort networks. --- src/Makefile.am | 3 +- src/sn_hashtable.c | 186 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/sn_hashtable.h | 53 +++++++++++++++ 3 files changed, 241 insertions(+), 1 deletion(-) create mode 100644 src/sn_hashtable.c create mode 100644 src/sn_hashtable.h diff --git a/src/Makefile.am b/src/Makefile.am index ae4e12f..7306d6e 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -12,7 +12,8 @@ bin_PROGRAMS = sn-apply \ libsortnetwork_la_SOURCES = sn_network.c sn_network.h \ sn_stage.c sn_stage.h \ sn_comparator.c sn_comparator.h \ - sn_random.c sn_random.h + sn_random.c sn_random.h \ + sn_hashtable.c sn_hashtable.h libsortnetwork_la_LDFLAGS = -version-info 0:0:0 sn_apply_SOURCES = sn-apply.c diff --git a/src/sn_hashtable.c b/src/sn_hashtable.c new file mode 100644 index 0000000..0656644 --- /dev/null +++ b/src/sn_hashtable.c @@ -0,0 +1,186 @@ +/** + * \file sn_hashtable.c + * \brief A hash table for counting the number of sort networks. + * + * This is more details about what this file does. + * + * \verbatim + * libsortnetwork - src/sn_hashtable.c + * Copyright (C) 2011 Florian octo Forster + * + * This library is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License as published by + * the Free Software Foundation; either version 2.1 of the License, or (at + * your option) any later version. + * + * This library is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License + * for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this library; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + * + * Authors: + * Florian octo Forster + * \endverbatim + **/ + +#include +#include +#include +#include +#include +#include +#include +#include + +#include "sn_hashtable.h" + +struct sn_hashtable_s +{ + uint64_t collisions_num; + uint64_t networks_num; + + uint8_t ****data; +}; + +sn_hashtable_t *sn_hashtable_create (void) /* {{{ */ +{ + sn_hashtable_t *ht; + + ht = malloc (sizeof (*ht)); + if (ht == NULL) + return (NULL); + memset (ht, 0, sizeof (*ht)); + + ht->data = NULL; + + return (ht); +} /* }}} sn_hashtable_t *sn_hashtable_create */ + +void sn_hashtable_destroy (sn_hashtable_t *ht) /* {{{ */ +{ + if (ht == NULL) + return; + + if (ht->data != NULL) + { + int i; + + for (i = 0; i < 256; i++) + { + int j; + + if (ht->data[i] == NULL) + continue; + + for (j = 0; j < 256; j++) + { + int k; + + if (ht->data[i][j] == NULL) + continue; + + for (k = 0; k < 256; k++) + free (ht->data[i][j][k]); + + free (ht->data[i][j]); + } + + free (ht->data[i]); + } + + free (ht->data); + } + + free (ht); +} /* }}} void sn_hashtable_destroy */ + +int sn_hashtable_account (sn_hashtable_t *ht, const sn_network_t *n) /* {{{ */ +{ + uint32_t hash; + uint8_t h0; + uint8_t h1; + uint8_t h2; + uint8_t h3; + + if ((ht == NULL) || (n == NULL)) + return (EINVAL); + + hash = sn_network_get_hashval (n); + + h0 = (uint8_t) (hash >> 24); + h1 = (uint8_t) (hash >> 16); + h2 = (uint8_t) (hash >> 8); + h3 = (uint8_t) hash; + + if (ht->data == NULL) + ht->data = calloc (256, sizeof (ht->data[0])); + + if (ht->data[h0] == NULL) + ht->data[h0] = calloc (256, sizeof (ht->data[h0][0])); + + if (ht->data[h0][h1] == NULL) + ht->data[h0][h1] = calloc (256, sizeof (ht->data[h0][h1][0])); + + if (ht->data[h0][h1][h2] == NULL) + ht->data[h0][h1][h2] = calloc (256, sizeof (ht->data[h0][h1][h2][0])); + + assert (sizeof (ht->data[h0][h1][h2][0]) == sizeof (uint8_t)); + + if (ht->data[h0][h1][h2][h3] == 0) + ht->networks_num++; + else + ht->collisions_num++; + + if (ht->data[h0][h1][h2][h3] < UINT8_MAX) + ht->data[h0][h1][h2][h3]++; + + return (0); +} /* }}} int sn_hashtable_account */ + +uint64_t sn_hashtable_get_collisions (sn_hashtable_t *ht) /* {{{ */ +{ + if (ht == NULL) + return (0); + + return (ht->collisions_num); +} /* }}} uint64_t sn_hashtable_get_collisions */ + +double sn_hashtable_get_collisions_pct (sn_hashtable_t *ht) /* {{{ */ +{ + if (ht == NULL) + return (NAN); + + return (100.0 * ((double) ht->collisions_num) + / ((double) (ht->collisions_num + ht->networks_num))); +} /* }}} double sn_hashtable_get_collisions_pct */ + +uint64_t sn_hashtable_get_networks (sn_hashtable_t *ht) /* {{{ */ +{ + if (ht == NULL) + return (0); + + return (ht->networks_num); +} /* }}} uint64_t sn_hashtable_get_networks */ + +double sn_hashtable_get_networks_pct (sn_hashtable_t *ht) /* {{{ */ +{ + if (ht == NULL) + return (NAN); + + return (100.0 * ((double) ht->networks_num) + / ((double) (ht->collisions_num + ht->networks_num))); +} /* }}} double sn_hashtable_get_networks_pct */ + +uint64_t sn_hashtable_get_total (sn_hashtable_t *ht) /* {{{ */ +{ + if (ht == NULL) + return (0); + + return (ht->collisions_num + ht->networks_num); +} /* }}} uint64_t sn_hashtable_get_total */ + +/* vim: set sw=2 sts=2 et fdm=marker : */ diff --git a/src/sn_hashtable.h b/src/sn_hashtable.h new file mode 100644 index 0000000..3871646 --- /dev/null +++ b/src/sn_hashtable.h @@ -0,0 +1,53 @@ +/** + * \file sn_hashtable.h + * \brief A hash table for counting the number of sort networks. + * + * This is more details about what this file does. + * + * \verbatim + * libsortnetwork - src/sn_hashtable.h + * Copyright (C) 2011 Florian octo Forster + * + * This library is free software; you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License as published by + * the Free Software Foundation; either version 2.1 of the License, or (at + * your option) any later version. + * + * This library is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License + * for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this library; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + * + * Authors: + * Florian octo Forster + * \endverbatim + **/ + +#ifndef SN_HASHTABLE_H +#define SN_HASHTABLE_H 1 + +#include +#include + +#include "sn_network.h" + +struct sn_hashtable_s; +typedef struct sn_hashtable_s sn_hashtable_t; + +sn_hashtable_t *sn_hashtable_create (void); +void sn_hashtable_destroy (sn_hashtable_t *ht); + +int sn_hashtable_account (sn_hashtable_t *ht, const sn_network_t *n); + +uint64_t sn_hashtable_get_collisions (sn_hashtable_t *ht); +double sn_hashtable_get_collisions_pct (sn_hashtable_t *ht); +uint64_t sn_hashtable_get_networks (sn_hashtable_t *ht); +double sn_hashtable_get_networks_pct (sn_hashtable_t *ht); +uint64_t sn_hashtable_get_total (sn_hashtable_t *ht); + +#endif /* SN_HASHTABLE_H */ +/* vim: set sw=2 sts=2 et fdm=marker : */ -- 2.11.0