separate SD calculations

1 files changed, 204 insertions, 0 deletions

diff --git a/src/testbed/testbed_api_sd.c b/src/testbed/testbed_api_sd.c
new file mode 100644
index 000000000..f6710774d
--- /dev/null
+++ b/src/testbed/testbed_api_sd.c
@@ -0,0 +1,204 @@
+/*
+      This file is part of GNUnet
+      (C) 2008--2012 Christian Grothoff (and other contributing authors)
+
+      GNUnet is free software; you can redistribute it and/or modify
+      it under the terms of the GNU General Public License as published
+      by the Free Software Foundation; either version 3, or (at your
+      option) any later version.
+
+      GNUnet 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
+      General Public License for more details.
+
+      You should have received a copy of the GNU General Public License
+      along with GNUnet; see the file COPYING.  If not, write to the
+      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+      Boston, MA 02111-1307, USA.
+ */
+
+/**
+ * @file testbed/testbed_api_sd.c
+ * @brief functions to calculate standard deviation
+ * @author Sree Harsha Totakura <sreeharsha@totakura.in> 
+ */
+
+#include "platform.h"
+#include "gnunet_util_lib.h"
+#include "testbed_api_sd.h"
+
+/**
+ * An entry to hold data which will be used to calculate SD
+ */
+struct SDEntry
+{
+  /**
+   * DLL next pointer
+   */
+  struct SDEntry *next;
+
+  /**
+   * DLL prev pointer
+   */
+  struct SDEntry *prev;
+
+  /**
+   * The value to store
+   */
+  unsigned int amount;
+};
+
+
+/**
+ * Opaque handle for calculating SD
+ */
+struct SDHandle
+{
+  /**
+   * DLL head for storing entries
+   */
+  struct SDEntry *head;
+
+  /**
+   * DLL tail for storing entries
+   */
+  struct SDEntry *tail;
+
+  /**
+   * Squared sum of data values
+   */
+  unsigned long long sqsum;
+
+  /**
+   * Sum of the data values
+   */
+  unsigned long sum;
+
+  /**
+   * The average of data amounts
+   */
+  float avg;
+
+  /**
+   * The variance
+   */
+  double vr;
+
+  /**
+   * Number of data values; also the length of DLL containing SDEntries
+   */
+  unsigned int cnt;
+
+  /**
+   * max number of entries we can have in the DLL
+   */
+  unsigned int max_cnt;
+};
+
+
+/**
+ * Initialize standard deviation calculation handle
+ *
+ * @param max_cnt the maximum number of readings to keep
+ * @return the initialized handle
+ */
+struct SDHandle *
+GNUNET_TESTBED_SD_init_ (unsigned int max_cnt)
+{
+  struct SDHandle *h;
+
+  GNUNET_assert (1 < max_cnt);
+  h = GNUNET_malloc (sizeof (struct SDHandle));
+  h->max_cnt = max_cnt;
+  return h;
+}
+
+
+/**
+ * Frees the memory allocated to the SD handle
+ *
+ * @param h the SD handle
+ */
+void
+GNUNET_TESTBED_SD_destroy_ (struct SDHandle *h)
+{
+  struct SDEntry *entry;
+
+  while (NULL != (entry = h->head))
+  {
+    GNUNET_CONTAINER_DLL_remove (h->head, h->tail, entry);
+    GNUNET_free (entry);
+  }
+  GNUNET_free (h);
+}
+
+
+/**
+ * Add a reading to SD
+ *
+ * @param h the SD handle
+ * @param amount the reading value
+ */
+void
+GNUNET_TESTBED_SD_add_data_ (struct SDHandle *h, unsigned int amount)
+{
+  struct SDEntry *entry;
+  double sqavg;
+  double sqsum_avg;
+
+  entry = NULL;
+  if (h->cnt == h->max_cnt)
+  {
+    entry = h->head;
+    GNUNET_CONTAINER_DLL_remove (h->head, h->tail, entry);
+    h->sum -= entry->amount;
+    h->sqsum -=
+        ((unsigned long) entry->amount) * ((unsigned long) entry->amount);
+    h->cnt--;
+  }
+  GNUNET_assert (h->cnt < h->max_cnt);
+  if (NULL == entry)
+    entry = GNUNET_malloc (sizeof (struct SDEntry));
+  entry->amount = amount;
+  GNUNET_CONTAINER_DLL_insert_tail (h->head, h->tail, entry);
+  h->sum += amount;
+  h->cnt++;
+  h->avg = ((float) h->sum) / ((float) h->cnt);
+  h->sqsum += ((unsigned long) amount) * ((unsigned long) amount);
+  sqsum_avg = ((double) h->sqsum) / ((double) h->cnt);
+  sqavg = ((double) h->avg) * ((double) h->avg);
+  h->vr = sqsum_avg - sqavg;
+}
+
+
+/**
+ * Returns the factor by which the given amount differs from the standard deviation
+ *
+ * @param h the SDhandle
+ * @param amount the value for which the deviation is returned
+
+ * @return the deviation from the average; GNUNET_SYSERR if the deviation cannot
+ *           be calculated OR 0 if the deviation is less than the average; a
+ *           maximum of 4 is returned for deviations equal to or larger than 4
+ */
+int
+GNUNET_TESTBED_SD_deviation_factor_ (struct SDHandle *h, unsigned int amount)
+{
+  double diff;
+  unsigned int n;
+
+  if (h->cnt < 2)
+    return GNUNET_SYSERR;
+  if (((float) amount) > h->avg)
+    diff = ((float) amount) - h->avg;
+  else
+    return 0;                   //diff = h->avg - ((float) amount);
+  diff *= diff;
+  for (n = 1; n < 4; n++)
+    if (diff < (((double) (n * n)) * h->vr))
+      break;
+  return n;
+}
+
+/* end of testbed_api_sd.c */