median.c

#include "median.h"
#include <strings.h>

typedef struct metadata {
  size_t buffer_size;
  size_t nLevels;
  unsigned char data[0];
} metadata_t;

median_error_t median_suggest_buffer_size(double epsilon, size_t maxN, size_t *suggested_size){
  // First check for sane parameters.
  if (maxN <= 0) return MEDIAN_ERROR_INVALID_PARAMETERS;
  // First compute the size of each buffer.
  size_t n = (1.0/epsilon)+ 1;
  // If n is too large, you are looking for too fine an approximation.
  // This is not the right algorithm. Maybe consider random sampling instead.
  if (n > 100000) return MEDIAN_ERROR_INVALID_PARAMETERS;
  // Compute the log of maxN using a divide by 2 loop.
  // There is no need to make this more complicated at this stage. It's not
  // a deep loop function.
  size_t nLevels = 1;
  while(maxN = (maxN >> 1)) nLevels++;
  // What is the size of the metadata structure
  size_t extra = sizeof(metadata_t);
  // This is the total.
  *suggested_size = n * nLevels + extra;

  return MEDIAN_ERROR_OK;
}
median_error_t median_init_buffer(void * buffer, size_t buffer_size, double epsilon, size_t maxN, median_buffer_t *initialized_buffer){
  // Initialize.
  size_t expected_size = 0;
  median_error_t error = MEDIAN_ERROR_OK;;
  // First run median_suggest_buffer_size
  if ((error = median_suggest_buffer_size(epsilon,maxN,&expected_size)) != MEDIAN_ERROR_OK) return error;
  // Ensure that the buffer is large enough.
  if (expected_size > buffer_size) return MEDIAN_ERROR_BUFFER_TOO_SMALL;
  metadata_t * m = (metadata_t *)buffer;

  m->buffer_size = buffer_size - sizeof(metadata_t);
  m->nLevels = m->buffer_size/(maxN * sizeof(median_data_t));
  bzero(m->data, m->buffer_size);

  return error;
}