/*
This file is part of GNUnet
(C) 2008--2013 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
*/
#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 */