src/testbed/testbed_api_sd.c

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