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