src/testbed/testbed_api_sd.c

   1 /*
   2       This file is part of GNUnet
   3       (C) 2008--2013 Christian Grothoff (and other contributing authors)
   4
   5       GNUnet is free software; you can redistribute it and/or modify
   6       it under the terms of the GNU General Public License as published
   7       by the Free Software Foundation; either version 3, or (at your
   8       option) any later version.
   9
  10       GNUnet is distributed in the hope that it will be useful, but
  11       WITHOUT ANY WARRANTY; without even the implied warranty of
  12       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13       General Public License for more details.
  14
  15       You should have received a copy of the GNU General Public License
  16       along with GNUnet; see the file COPYING.  If not, write to the
  17       Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18       Boston, MA 02111-1307, USA.
  19  */
  20
  21 /**
  22  * @file testbed/testbed_api_sd.c
  23  * @brief functions to calculate standard deviation
  24  * @author Sree Harsha Totakura <sreeharsha@totakura.in>
  25  */
  26
  27 #include "platform.h"
  28 #include "gnunet_util_lib.h"
  29 #include "testbed_api_sd.h"
  30
  31 /**
  32  * An entry to hold data which will be used to calculate SD
  33  */
  34 struct SDEntry
  35 {
  36   /**
  37    * DLL next pointer
  38    */
  39   struct SDEntry *next;
  40
  41   /**
  42    * DLL prev pointer
  43    */
  44   struct SDEntry *prev;
  45
  46   /**
  47    * The value to store
  48    */
  49   unsigned int amount;
  50 };
  51
  52
  53 /**
  54  * Opaque handle for calculating SD
  55  */
  56 struct SDHandle
  57 {
  58   /**
  59    * DLL head for storing entries
  60    */
  61   struct SDEntry *head;
  62
  63   /**
  64    * DLL tail for storing entries
  65    */
  66   struct SDEntry *tail;
  67
  68   /**
  69    * Squared sum of data values
  70    */
  71   unsigned long long sqsum;
  72
  73   /**
  74    * Sum of the data values
  75    */
  76   unsigned long sum;
  77
  78   /**
  79    * The average of data amounts
  80    */
  81   float avg;
  82
  83   /**
  84    * The variance
  85    */
  86   double vr;
  87
  88   /**
  89    * Number of data values; also the length of DLL containing SDEntries
  90    */
  91   unsigned int cnt;
  92
  93   /**
  94    * max number of entries we can have in the DLL
  95    */
  96   unsigned int max_cnt;
  97 };
  98
  99
 100 /**
 101  * Initialize standard deviation calculation handle
 102  *
 103  * @param max_cnt the maximum number of readings to keep
 104  * @return the initialized handle
 105  */
 106 struct SDHandle *
 107 GNUNET_TESTBED_SD_init_ (unsigned int max_cnt)
 108 {
 109   struct SDHandle *h;
 110
 111   GNUNET_assert (1 < max_cnt);
 112   h = GNUNET_new (struct SDHandle);
 113   h->max_cnt = max_cnt;
 114   return h;
 115 }
 116
 117
 118 /**
 119  * Frees the memory allocated to the SD handle
 120  *
 121  * @param h the SD handle
 122  */
 123 void
 124 GNUNET_TESTBED_SD_destroy_ (struct SDHandle *h)
 125 {
 126   struct SDEntry *entry;
 127
 128   while (NULL != (entry = h->head))
 129   {
 130     GNUNET_CONTAINER_DLL_remove (h->head, h->tail, entry);
 131     GNUNET_free (entry);
 132   }
 133   GNUNET_free (h);
 134 }
 135
 136
 137 /**
 138  * Add a reading to SD
 139  *
 140  * @param h the SD handle
 141  * @param amount the reading value
 142  */
 143 void
 144 GNUNET_TESTBED_SD_add_data_ (struct SDHandle *h, unsigned int amount)
 145 {
 146   struct SDEntry *entry;
 147   double sqavg;
 148   double sqsum_avg;
 149
 150   entry = NULL;
 151   if (h->cnt == h->max_cnt)
 152   {
 153     entry = h->head;
 154     GNUNET_CONTAINER_DLL_remove (h->head, h->tail, entry);
 155     h->sum -= entry->amount;
 156     h->sqsum -=
 157         ((unsigned long) entry->amount) * ((unsigned long) entry->amount);
 158     h->cnt--;
 159   }
 160   GNUNET_assert (h->cnt < h->max_cnt);
 161   if (NULL == entry)
 162     entry = GNUNET_new (struct SDEntry);
 163   entry->amount = amount;
 164   GNUNET_CONTAINER_DLL_insert_tail (h->head, h->tail, entry);
 165   h->sum += amount;
 166   h->cnt++;
 167   h->avg = ((float) h->sum) / ((float) h->cnt);
 168   h->sqsum += ((unsigned long) amount) * ((unsigned long) amount);
 169   sqsum_avg = ((double) h->sqsum) / ((double) h->cnt);
 170   sqavg = ((double) h->avg) * ((double) h->avg);
 171   h->vr = sqsum_avg - sqavg;
 172 }
 173
 174
 175 /**
 176  * Calculates the factor by which the given amount differs
 177  *
 178  * @param h the SDhandle
 179  * @param amount the value for which the deviation is returned
 180  * @param factor the factor by which the given amont differs
 181  * @return GNUNET_SYSERR if the deviation cannot
 182  *   be calculated; GNUNET_OK if the deviation is returned through factor
 183  */
 184 int
 185 GNUNET_TESTBED_SD_deviation_factor_ (struct SDHandle *h, unsigned int amount,
 186                                      int *factor)
 187 {
 188   double diff;
 189   int f;
 190   int n;
 191
 192   if (h->cnt < 2)
 193     return GNUNET_SYSERR;
 194   if (((float) amount) > h->avg)
 195   {
 196     diff = ((float) amount) - h->avg;
 197     f = 1;
 198   }
 199   else
 200   {
 201     diff = h->avg - ((float) amount);
 202     f = -1;
 203   }
 204   diff *= diff;
 205   for (n = 1; n < 4; n++)
 206     if (diff < (((double) (n * n)) * h->vr))
 207       break;
 208   *factor = f * n;
 209   return GNUNET_OK;
 210 }
 211
 212 /* end of testbed_api_sd.c */