src/sn_hashtable.[ch]: Add module for counting sort networks.

diff --git a/src/Makefile.am b/src/Makefile.am
index ae4e12f..7306d6e 100644 (file)
--- 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 (file)
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 <ff at octo.it>
+ * \endverbatim
+ **/
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdint.h>
+#include <inttypes.h>
+#include <string.h>
+#include <math.h>
+#include <errno.h>
+#include <assert.h>
+
+#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 (file)
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 <ff at octo.it>
+ * \endverbatim
+ **/
+
+#ifndef SN_HASHTABLE_H
+#define SN_HASHTABLE_H 1
+
+#include <stdint.h>
+#include <inttypes.h>
+
+#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 : */