Intermediate commit.
Intermediate commit. Not complete yet.
diff --git a/Makefile b/Makefile
index 29ea20d..d124a2e 100644
--- a/Makefile
+++ b/Makefile
@@ -4,14 +4,15 @@
MAINO = $(patsubst %.c,%.o,$(MAIN))
DEPS = $(patsubst %.c,%.d,$(SRCS) $(MAIN))
EXECS = $(patsubst %.c,%,$(MAIN))
+FLAGS = -std=c99 -Wall
all : $(EXECS)
clean :
- rm -f $(OBJS) $(DEPS) $(MAINO)
+ rm -f $(OBJS) $(DEPS) $(MAINO) $(EXECS)
%.o : %.c
- gcc -MD -c $<
+ gcc $(FLAGS) -MD -c $<
%.d : %.c
- gcc -MD -c $<
+ gcc $(FLAGS) -MD -c $<
%.main : %.main.o $(OBJS)
- gcc $< $(OBJS) -o $@
+ gcc $(FLAGS) $< $(OBJS) -o $@
-include $(DEPS)
diff --git a/median.c b/median.c
index face1ef..3cc991a 100644
--- a/median.c
+++ b/median.c
@@ -1,48 +1,89 @@
#include "median.h"
#include <strings.h>
+// The buffer is cast into this struct.
typedef struct metadata {
- size_t buffer_size;
- size_t nLevels;
- unsigned char data[0];
+ 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++;
- // What is the size of the metadata structure
- size_t extra = sizeof(metadata_t);
- // This is the total.
- *suggested_size = n * nLevels + extra;
+ while((maxN = (maxN >> 1))) nLevels++;
- return MEDIAN_ERROR_OK;
+ // 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 expected_size = 0;
- median_error_t error = MEDIAN_ERROR_OK;;
+ size_t expectedSize = 0;
+ median_error_t error = MEDIAN_OK;
+
// First run median_suggest_buffer_size
- if ((error = median_suggest_buffer_size(epsilon,maxN,&expected_size)) != MEDIAN_ERROR_OK) return error;
+ if ((error = median_suggest_buffer_size(epsilon,maxN,&expectedSize)) != MEDIAN_OK) return error;
// Ensure that the buffer is large enough.
- if (expected_size > buffer_size) return MEDIAN_ERROR_BUFFER_TOO_SMALL;
+ 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);
- m->buffer_size = buffer_size - sizeof(metadata_t);
- m->nLevels = m->buffer_size/(maxN * sizeof(median_data_t));
- bzero(m->data, m->buffer_size);
+ // 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;
+}
diff --git a/median.h b/median.h
index 90a3650..0ea0495 100644
--- a/median.h
+++ b/median.h
@@ -31,23 +31,23 @@
// All the error codes.
// No Error.
-static median_error_t MEDIAN_ERROR_OK = 0;
+static const median_error_t MEDIAN_OK = 0;
// The parameters are meaningless (for example, asking for neg values
// for epsilon).
-static median_error_t MEDIAN_ERROR_INVALID_PARAMETERS = -1;
+static const median_error_t MEDIAN_ERROR_INVALID_PARAMETERS = -1;
// The buffer allocated is too small for the parameters requested.
-static median_error_t MEDIAN_ERROR_BUFFER_TOO_SMALL = -2;
+static const median_error_t MEDIAN_ERROR_BUFFER_TOO_SMALL = -2;
// Overflow because MaxN has been exceeded.
-static median_error_t MEDIAN_ERROR_MAX_N_EXCEEDED = -3;
+static const median_error_t MEDIAN_ERROR_MAX_N_EXCEEDED = -3;
// Indicates that the size of the largest possible dataset is not known.
-static size_t MEDIAN_MAX_N_UNKNOWN = 0;
+static const size_t MEDIAN_MAX_N_UNKNOWN = 0;
// The default size of the largest possible dataset.
-static size_t MEDIAN_MAX_N_DEFAULT = 1024*1024*1024; // 1G.
+static const size_t MEDIAN_MAX_N_DEFAULT = 1024*1024*1024; // 1G.
// This routine returns a suggested size for a buffer to hold all the
// state needed for a median calculation. Here epsilon is the permissible error.
diff --git a/median.main.c b/median.main.c
index 4879c04..59c8a53 100644
--- a/median.main.c
+++ b/median.main.c
@@ -1,9 +1,25 @@
#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
#include "median.h"
+// A sinple main routine meant as an example,
+// and also to unit test most of the intersting
+// functions of the median module.
int main(int argc, char * argv[]) {
+ // Call suggest buffer size to determine the size of the buffer
+ // we need to build the data structure.
size_t n = 0;
- median_suggest_buffer_size(.001, 1000, &n);
+ assert(median_suggest_buffer_size(.001, 1000, &n) == MEDIAN_OK);
+ // Print the number out.
printf("%ld\n", n);
+
+ // Allocate the buffer of the required size. And then
+ // initialize it (median_init_buffer).
+ void * b = malloc(n);
+ median_buffer_t buf;
+ assert(median_init_buffer(b, n, .001, 1000, &buf) == MEDIAN_OK);
+
+ // All done, return 0
return 0;
}
