median.c

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

// The buffer is cast into this struct.
typedef struct metadata {
  size_t bufferSize;      // Number of bytes available for use.
  size_t nLevels;          // Number of buffers available.
  size_t currentBufferIdx; // The index of the currently active buffer.
  unsigned char data[0];   // The start of the data.
} metadata_t;

typedef uint32_t parity_t;

typedef struct bufferdata {
  parity_t parity;           // The parity of this buffer.
  size_t level;              // The level of this buffer.
  size_t occupancy;          // Number of occupants for this buffer.
} bufferdata_t;


static const parity_t PARITY_NONE  = 0; // The parity is none.
static const parity_t PARITY_LEFT  = 1; // The buffer has LEFT parity.
static const parity_t PARITY_RIGHT = 2; // The buffer has RIGHT parity.

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++;

  // This is the total bytes needed.
  // One metadata block. nLevels bufferdata_t blockes.
  // and n * nLevels median_data_t elements.
  *suggested_size = n * nLevels * sizeof(median_data_t) + nLevels * sizeof(bufferdata_t) + sizeof(metadata_t);

  // Things worked. Return MEDIAN_OK
  return MEDIAN_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 expectedSize = 0;
  median_error_t error = MEDIAN_OK;

  // First run median_suggest_buffer_size
  if ((error = median_suggest_buffer_size(epsilon,maxN,&expectedSize)) != MEDIAN_OK) return error;
  // Ensure that the buffer is large enough.
  if (expectedSize > buffer_size) return MEDIAN_ERROR_BUFFER_TOO_SMALL;

  // Cast the buffer as metadata_t so that we can initialize the metadata block.
  metadata_t * m = (metadata_t *)buffer;
  // Initialize the metadata block.
  m->bufferSize = buffer_size - sizeof(metadata_t);
  m->nLevels = m->bufferSize/((maxN * sizeof(median_data_t)) + sizeof(bufferdata_t));
  m->currentBufferIdx = 0;
  bzero(m->data, m->bufferSize);

  // cast the data part as an array of bufferdata_t blocks.
  // and initialize each of the blocks.
  bufferdata_t * t = (bufferdata_t *) m->data;
  for(size_t i = 0; i < m->nLevels; i++) {
    t[i].parity = PARITY_NONE;
    t[i].level  = 0;
    t[i].occupancy = 0;
  }

  // Populate the return value.
  *initialized_buffer = (median_buffer_t)buffer;
  return error;
}

median_error_t median_insert_data(median_buffer_t buffer, median_data_t data){
  // First locate the empty buffer.
  return MEDIAN_OK;
}

median_error_t median_output_median(median_buffer_t buffer, median_data_t *approximate_median){
  return MEDIAN_OK;
}