Added the interfaces for json state output.
diff --git a/hex.c b/hex.c
index cc42430..d12daf2 100644
--- a/hex.c
+++ b/hex.c
@@ -1,24 +1,25 @@
#include "hex.h"
#include <stdio.h>
-hexdmp_error_t stderr_hexdmp(const char * description, const unsigned char * data_ptr, size_t datasz){
- if(description) {
- fprintf(stderr,"%s:\n", description);
+hexdmp_error_t stderr_hexdmp(const char* description,
+ const unsigned char* data_ptr, size_t datasz) {
+ if (description) {
+ fprintf(stderr, "%s:\n", description);
}
- if(datasz == 0) {
- fprintf(stderr,"No Data, Size is 0");
+ if (datasz == 0) {
+ fprintf(stderr, "No Data, Size is 0");
return HEXDMP_OK;
}
- if(!data_ptr) {
- fprintf(stderr,"No data pointer");
+ if (!data_ptr) {
+ fprintf(stderr, "No data pointer");
return HEXDMP_ERROR;
}
- for(size_t i = 0; i < datasz; i += 16) {
+ for (size_t i = 0; i < datasz; i += 16) {
// First print the offset.
- fprintf(stderr, "%08x", (unsigned) i);
+ fprintf(stderr, "%08x", (unsigned)i);
// Now print the next (at most) 16 characters.
- for(size_t j = 0; (j < 16) && (i+j) < datasz; j++) {
- fprintf(stderr, " %02x", data_ptr[i+j]);
+ for (size_t j = 0; (j < 16) && (i + j) < datasz; j++) {
+ fprintf(stderr, " %02x", data_ptr[i + j]);
}
// Print a newline.
fprintf(stderr, "\n");
diff --git a/hex.h b/hex.h
index d47281e..432ca26 100644
--- a/hex.h
+++ b/hex.h
@@ -1,11 +1,12 @@
#ifndef __MEDIAN_HEX_H_INCLUDED__
#define __MEDIAN_HEX_H_INCLUDED__
-#include <strings.h> // size_t
+#include <strings.h> // size_t
typedef int hexdmp_error_t;
static const hexdmp_error_t HEXDMP_OK = 0;
static const hexdmp_error_t HEXDMP_ERROR = -1;
// The function produces an output to stderr similar to the "hexdump"
// application. Useful in debugging things.
-hexdmp_error_t stderr_hexdmp(const char * description, const unsigned char * data_ptr, size_t datasz);
-#endif // __MEDIAN_HEX_H_INCLUDED__
+hexdmp_error_t stderr_hexdmp(const char* description,
+ const unsigned char* data_ptr, size_t datasz);
+#endif // __MEDIAN_HEX_H_INCLUDED__
diff --git a/median.c b/median.c
index 1162fbd..e47bb61 100644
--- a/median.c
+++ b/median.c
@@ -1,10 +1,10 @@
#include "median.h"
+#include <pthread.h> // pthread_mutex_*
+#include <stdio.h> // fprintf
+#include <stdlib.h> // qsort
+#include <string.h> // memcpy
+#include <strings.h> // size_t
#include "hex.h"
-#include <strings.h> // size_t
-#include <stdio.h> // fprintf
-#include <stdlib.h> // qsort
-#include <string.h> // memcpy
-#include <pthread.h> // pthread_mutex_*
// The structure of the data buffer is this:
// ----------------------------------------------------------------------------
@@ -14,107 +14,125 @@
// is stored in Metadata as well.
// The buffer is cast into this struct.
-
// ----------------------------------------------------------------------------
// The block header.
// ----------------------------------------------------------------------------
-typedef struct blockdata {
- unsigned int id; // Block identity.
- size_t level; // The level of this buffer.
- size_t occupancy; // Number of occupants for this buffer.
- unsigned char data[0]; // Start of the data block, cast as unsigned char.
- median_data_t median_data[0]; // The data for this buffer cast as median_data_t.
-} blockdata_t;
+struct blockdata {
+ unsigned int id; // Block identity.
+ size_t level; // The level of this buffer.
+ size_t occupancy; // Number of occupants for this buffer.
+ unsigned char data[0]; // Start of the data block, cast as unsigned char.
+ median_data_t
+ median_data[0]; // The data for this buffer cast as median_data_t.
+};
// ----------------------------------------------------------------------------
// The overall header
// ----------------------------------------------------------------------------
-typedef struct metadata {
- pthread_mutex_t mutex_ptr[0]; // Pointer to the mutex.
- pthread_mutex_t mutex; // The mutex for this median counter.
- unsigned int gid; // The next available global id
- size_t nLevels; // Number of buffers available.
- size_t nMembers; // The number of members in each block.
- size_t currentBufferIdx; // The index of the currently active buffer.
- unsigned char data[0]; // The start of the data.
- blockdata_t block_data[0]; // Makes the code cleaner and avoids unnecessary casting.
-} metadata_t;
+struct metadata {
+ pthread_mutex_t mutex_ptr[0]; // Pointer to the mutex.
+ pthread_mutex_t mutex; // The mutex for this median counter.
+ unsigned int gid; // The next available global id
+ size_t nLevels; // Number of buffers available.
+ size_t nMembers; // The number of members in each block.
+ size_t currentBufferIdx; // The index of the currently active buffer.
+ unsigned char data[0]; // The start of the data.
+ struct blockdata block_data[0]; // Makes the code cleaner and avoids
+ // unnecessary casting.
+};
+
+// ----------------------------------------------------------------------------
+// These structs are used internally for algorithmic work.
+//
+//
// ----------------------------------------------------------------------------
// The record used for sorting the output
// ----------------------------------------------------------------------------
-typedef struct sortrec {
- median_data_t d; // The data point.
- size_t sz; // The leveled size of the point.
-} sortrec_t;
+struct sortrec {
+ median_data_t d; // The data point.
+ size_t sz; // The leveled size of the point.
+};
// ----------------------------------------------------------------------------
-// The spare buffer space header.
+// The spare buffer header.
// ----------------------------------------------------------------------------
-typedef struct spare_buffer {
- size_t spareSize; // Size in bytes of the spare block.
- unsigned char data[0]; // Start of the data block.
- sortrec_t sortrec_data[0]; // The same point cast as a sortrec
- median_data_t median_data[0]; // The same point cast as a median datum
- size_t size_data[0]; // The same point case as size_t
-} spare_buffer_t;
+struct spare_buffer {
+ size_t spareSize; // Size in bytes of the spare block.
+ unsigned char data[0]; // Start of the data block.
+ struct sortrec sortrec_data[0]; // The same point cast as a sortrec
+ median_data_t median_data[0]; // The same point cast as a median datum
+ size_t size_data[0]; // The same point case as size_t
+};
+// ----------------------------------------------------------------------------
+// This is the struct used to hold a JSON output string.
+// ----------------------------------------------------------------------------
+// A buffer to hold the output string.
+// ----------------------------------------------------------------------------
+struct output_buffer {
+ size_t outputBufferSize; // The buffer size in char
+ char mesg[0]; // The message.
+};
// ----------------------------------------------------------------------------
// Helper functions.
//
// This turns epsilon into a suggested size for each block.
size_t calculate_nMembers(double epsilon) {
- return (size_t) ((1.0 / epsilon) + 1);
+ return (size_t)((1.0 / epsilon) + 1);
}
// This turns maxN into the number of levels needed. It's ceiling(log2(maxN)).
size_t calculate_nLevels(size_t maxN) {
size_t nLevels = 1;
- while((maxN = (maxN >> 1))) nLevels++;
+ while ((maxN = (maxN >> 1))) nLevels++;
return nLevels;
}
// This returns the blocksize in bytes.
-// The blocksize is the header plus m->nMembers many
+// The blocksize is the header plus m->nMembers many
// data points, each of type median_data_t
-size_t blocksize(metadata_t * m) {
- return sizeof(blockdata_t) + m->nMembers * sizeof(median_data_t);
+size_t blocksize(struct metadata *m) {
+ return sizeof(struct blockdata) + m->nMembers * sizeof(median_data_t);
}
// This return the start of the next block given
-// a pointer to a block. The easiest way is to jump
+// a pointer to a block. The easiest way is to jump
// m->nMembers median_data_t items away.
-blockdata_t * nextblock(blockdata_t * blk, metadata_t * m) {
- return (blockdata_t *) (blk->median_data + m->nMembers);
+struct blockdata *nextblock(struct blockdata *blk, struct metadata *m) {
+ return (struct blockdata *)(blk->median_data + m->nMembers);
}
// This returns the size of the entire buffer in bytes.
// The size of the metadata block, plus m->nLevels many
// blocks each of size blocksize(m)
-size_t buffersize(metadata_t * m) {
- return sizeof(metadata_t) + m->nLevels * blocksize(m);
+size_t buffersize(struct metadata *m) {
+ return sizeof(struct metadata) + m->nLevels * blocksize(m);
}
// Returns the first byte address which is too high to start a block regardless
// of size.. One blockdata worth less than the actual end of the buffer plus
-// one. The computation is done in byte units and then cast as a blockdata_t
-// pointer.
-blockdata_t * out_of_bounds(metadata_t * m) {
- return (blockdata_t *) (m->data + buffersize(m) - sizeof(metadata_t) - blocksize(m));
+// one. The computation is done in byte units and then cast as a struct
+// blockdata pointer.
+struct blockdata *out_of_bounds(struct metadata *m) {
+ return (struct blockdata *)(m->data + buffersize(m) -
+ sizeof(struct metadata) - blocksize(m));
}
// Get the current block.
-// The computation is done in bytes, and then cast as a blockdata_t pointer.
-blockdata_t * get_current_block(metadata_t *m) {
+// The computation is done in bytes, and then cast as a struct blockdata
+// pointer.
+struct blockdata *get_current_block(struct metadata *m) {
size_t offset = m->currentBufferIdx * blocksize(m);
- return (blockdata_t *)(m->data + offset);
+ return (struct blockdata *)(m->data + offset);
}
// This function inserts data into the current block if possible.
// Otherwise, it returns false.
-unsigned int insert_into_current_block_if_possible(metadata_t *m, median_data_t data) {
- blockdata_t * b = get_current_block(m);
+unsigned int insert_into_current_block_if_possible(struct metadata *m,
+ median_data_t data) {
+ struct blockdata *b = get_current_block(m);
if (b->occupancy < m->nMembers) {
b->median_data[b->occupancy++] = data;
return 1;
@@ -124,10 +142,11 @@
// Check if there is space in some block and if there is, then
// make that block the current block.
-unsigned int occupy_available_empty_block(metadata_t * m) {
+unsigned int occupy_available_empty_block(struct metadata *m) {
// Iterate over the blocks.
- for(blockdata_t * b = m->block_data; b < out_of_bounds(m); b = nextblock(b,m)) {
- if(b->occupancy < m->nMembers) {
+ for (struct blockdata *b = m->block_data; b < out_of_bounds(m);
+ b = nextblock(b, m)) {
+ if (b->occupancy < m->nMembers) {
// Empty block found!
m->currentBufferIdx = b->id;
return 1;
@@ -138,20 +157,21 @@
}
// A simple compare operator for the qsort routine.
-int compare_data(const void *a, const void *b){
- median_data_t * i = (median_data_t *)a;
- median_data_t * j = (median_data_t *)b;
- return (*i < *j)?-1:+1;
+int compare_data(const void *a, const void *b) {
+ median_data_t *i = (median_data_t *)a;
+ median_data_t *j = (median_data_t *)b;
+ return (*i < *j) ? -1 : +1;
}
-unsigned int merge_blocks(metadata_t *m,blockdata_t *i,blockdata_t *j, median_scratch_buffer_t spare){
+unsigned int merge_blocks(struct metadata *m, struct blockdata *i,
+ struct blockdata *j, median_scratch_buffer_t spare) {
// Prepare an array for the data.
- unsigned char * d = spare->data;
+ unsigned char *d = spare->data;
size_t datasz = m->nMembers * sizeof(median_data_t);
- if (2*datasz > spare->spareSize) {
+ if (2 * datasz > spare->spareSize) {
return 0;
}
- bzero(d, 2*datasz);
+ bzero(d, 2 * datasz);
// This is the size of the data.
// Copy the data to where it needs to be.
@@ -165,7 +185,8 @@
// be consuming level 0 buffers, I have left this
// inefficiency in.
// But we should fix it.
- qsort(spare->median_data,2*m->nMembers,sizeof(median_data_t),&compare_data);
+ qsort(spare->median_data, 2 * m->nMembers, sizeof(median_data_t),
+ &compare_data);
// Now interleave the sorted buffer.
// We should track parity and take the
@@ -176,8 +197,8 @@
// zero or one.
// However, this does make the routine somewhat non
// deterministic, but offers some extra accuracy.
- for(size_t idx = 0; idx < 2*m->nMembers; idx+=2){
- i->median_data[idx/2] = spare->median_data[idx];
+ for (size_t idx = 0; idx < 2 * m->nMembers; idx += 2) {
+ i->median_data[idx / 2] = spare->median_data[idx];
}
// Update the metadata. i is full, j is empty.
@@ -194,7 +215,8 @@
}
// Find the smallest level such that there are two blocks at the same level.
-unsigned int identify_qualified_level(metadata_t *m, size_t *lvl, median_scratch_buffer_t spare) {
+unsigned int identify_qualified_level(struct metadata *m, size_t *lvl,
+ median_scratch_buffer_t spare) {
// Zero out the count buffer after validating the
// spare space buffer.
size_t datasz = m->nLevels * sizeof(size_t);
@@ -203,21 +225,22 @@
}
// Prepare the size array.
- size_t * levelcount = spare->size_data;
+ size_t *levelcount = spare->size_data;
bzero(levelcount, datasz);
// Count up the level population.
- for(blockdata_t * b = m->block_data; b < out_of_bounds(m); b = nextblock(b,m)) {
+ for (struct blockdata *b = m->block_data; b < out_of_bounds(m);
+ b = nextblock(b, m)) {
levelcount[b->level]++;
}
// Look for a level where the count is at least 2.
- for(size_t idx = 0; idx < m->nLevels; idx++) {
- if(levelcount[idx] > 1) {
- // Found one, return it.
- *lvl = idx;
- return 1;
- }
+ for (size_t idx = 0; idx < m->nLevels; idx++) {
+ if (levelcount[idx] > 1) {
+ // Found one, return it.
+ *lvl = idx;
+ return 1;
+ }
}
// There is no such thing.
@@ -225,11 +248,14 @@
}
// This identifies the pair of blocks to merge.
-unsigned int identify_compatible_block_pair(metadata_t *m, blockdata_t ** i, blockdata_t ** j, median_scratch_buffer_t spare) {
+unsigned int identify_compatible_block_pair(struct metadata *m,
+ struct blockdata **i,
+ struct blockdata **j,
+ median_scratch_buffer_t spare) {
// The qualified level will reside here.
// Find the qualified level.
size_t qualified_level = 0;
- if (!identify_qualified_level(m,&qualified_level,spare)) {
+ if (!identify_qualified_level(m, &qualified_level, spare)) {
return 0;
}
@@ -239,48 +265,52 @@
// State machine to find the two buffers.
// Iterate over the blocks.
- for(blockdata_t * b = m->block_data; b < out_of_bounds(m); b = nextblock(b,m)) {
+ for (struct blockdata *b = m->block_data; b < out_of_bounds(m);
+ b = nextblock(b, m)) {
if (!(*i) && (b->level == qualified_level)) {
- *i = b; continue; // Found the first one.
+ *i = b;
+ continue; // Found the first one.
}
if (!(*j) && (b->level == qualified_level)) {
- *j = b; return 1; // Found the second one.
+ *j = b;
+ return 1; // Found the second one.
}
}
// Loop should not exit before the two are found.
return 0;
}
-
// THis routine creates an empty block by merging two available blocks into a
// single block. Consequently this frees up one of them.
// If two compatible blocks cannot be found, then this routine returns 0.
// It also returns 0 if for some reason the two blocks cannot be merged.
-unsigned int create_empty_block(metadata_t * m, median_scratch_buffer_t spare) {
- blockdata_t *i,*j;
- if(!identify_compatible_block_pair(m, &i, &j, spare)){
+unsigned int create_empty_block(struct metadata *m,
+ median_scratch_buffer_t spare) {
+ struct blockdata *i, *j;
+ if (!identify_compatible_block_pair(m, &i, &j, spare)) {
return 0;
}
- return merge_blocks(m,i,j,spare);
+ return merge_blocks(m, i, j, spare);
}
// Shift the current block. If there is an empty block, great!
// If not, then empty a block by merging two blocks and then occupy the
// freed up block.
-unsigned int shift_current_block(metadata_t * m, median_scratch_buffer_t spare) {
- if(!occupy_available_empty_block(m)) {
- if(create_empty_block(m,spare)) { // Now there should be an empty block!
- if(!occupy_available_empty_block(m)) {
- return 0; // Stuck we are. Empty block is not, even though create it we did.
+unsigned int shift_current_block(struct metadata *m,
+ median_scratch_buffer_t spare) {
+ if (!occupy_available_empty_block(m)) {
+ if (create_empty_block(m, spare)) { // Now there should be an empty block!
+ if (!occupy_available_empty_block(m)) {
+ return 0; // Stuck we are. Empty block is not, even though create it we
+ // did.
}
} else {
- return 0; // Stuck we are. Block not.
+ return 0; // Stuck we are. Block not.
}
}
- return 1; // Occupy a block we did.
+ return 1; // Occupy a block we did.
}
-
// ----------------------------------------------------------------------------
// Implementation of the interface functions (specified in median.h).
// ----------------------------------------------------------------------------
@@ -288,19 +318,22 @@
// ----------------------------------------------------------------------------
// Suggest the size of the buffer needed for a fixed epsilon and maxN.
// ----------------------------------------------------------------------------
-median_error_t median_suggest_buffer_size(double epsilon, size_t maxN, size_t *suggested_size){
+median_error_t median_suggest_buffer_size(double epsilon, size_t maxN,
+ size_t *suggested_size) {
// First check for sane parameters.
// Check that maxN is not zero.
if (maxN <= 0) return MEDIAN_ERROR_INVALID_PARAMETERS;
- // If n is too large, (i.e. epsilon is too small), you are looking for too fine an approximation.
- // This is not the right algorithm. Maybe consider random sampling instead.
- if (calculate_nMembers(epsilon) > 100000) return MEDIAN_ERROR_INVALID_PARAMETERS;
+ // If n is too large, (i.e. epsilon is too small), you are looking for too
+ // fine an approximation. This is not the right algorithm. Maybe consider
+ // random sampling instead.
+ if (calculate_nMembers(epsilon) > 100000)
+ return MEDIAN_ERROR_INVALID_PARAMETERS;
// Calculate the required buffer size for the right nLevels and nMembers
// value.
- metadata_t m;
+ struct metadata m;
m.nLevels = calculate_nLevels(maxN);
m.nMembers = calculate_nMembers(epsilon);
@@ -308,7 +341,7 @@
// and outputing. If we have many ongoing buffers, we can do with a single
// spare space buffer. We can figure out that optimization later.
// Ideally, this will be done by keeping a pointer to the global spare space
- // within the metadata_t block. I prefer keeping this data structure
+ // within the struct metadata block. I prefer keeping this data structure
// relocatable and serializable. So we may need to think about what the
// alternatives are.
*suggested_size = buffersize(&m);
@@ -320,25 +353,42 @@
// ----------------------------------------------------------------------------
// Suggest a buffer size for the scratch buffer.
// ----------------------------------------------------------------------------
-median_error_t median_suggest_scratch_buffer_size(median_buffer_t m, size_t *suggested_size){
- *suggested_size = m->nLevels * m->nMembers * sizeof(sortrec_t) + sizeof(spare_buffer_t);
+median_error_t median_suggest_scratch_buffer_size(median_buffer_t m,
+ size_t *suggested_size) {
+ *suggested_size = m->nLevels * m->nMembers * sizeof(struct sortrec) +
+ sizeof(struct spare_buffer);
+ return MEDIAN_OK;
+}
+
+// ----------------------------------------------------------------------------
+// Suggest a size of the output buffer.
+// ----------------------------------------------------------------------------
+median_error_t median_suggest_json_string_size(median_buffer_t m,
+ size_t *suggested_size) {
+ // ToDo improve this estimate.
+ *suggested_size = 256 * 1024; // Constant size of 256K for now.
return MEDIAN_OK;
}
// ----------------------------------------------------------------------------
// Initialize an allocated buffer.
// ----------------------------------------------------------------------------
-median_error_t median_init_buffer(void * buffer, size_t buffer_size, double epsilon, size_t maxN, median_buffer_t *initialized_buffer){
+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;
+ 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;
+ // Cast the buffer as struct metadata so that we can initialize the metadata
+ // block.
+ struct metadata *m = (struct metadata *)buffer;
// Initialize the mutex.
pthread_mutex_init(m->mutex_ptr, NULL);
// Initialize the metadata block.
@@ -348,14 +398,15 @@
m->currentBufferIdx = 0;
// Zero all the data following the metadata block.
// Strictly this should not be necessary, but I'm a coward!
- bzero(m->data, buffersize(m) - sizeof(metadata_t));
+ bzero(m->data, buffersize(m) - sizeof(struct metadata));
- // cast the data part as an array of blockdata_t fronted blocks.
+ // cast the data part as an array of struct blockdata fronted blocks.
// and initialize each of the blocks.
// Iterate over the blocks.
- for(blockdata_t * b = m->block_data; b < out_of_bounds(m); b = nextblock(b,m)) {
+ for (struct blockdata *b = m->block_data; b < out_of_bounds(m);
+ b = nextblock(b, m)) {
b->id = (m->gid)++;
- b->level = 0;
+ b->level = 0;
b->occupancy = 0;
}
@@ -370,33 +421,52 @@
return MEDIAN_OK;
}
+// Nothing to do, yet!
+median_error_t median_deinit_scratch_buffer(median_scratch_buffer_t s) {
+ return MEDIAN_OK;
+}
+
+// Nothing to do, yet!
+median_error_t median_deinit_json_string(median_json_string_t o) {
+ return MEDIAN_OK;
+}
// ----------------------------------------------------------------------------
// Initialize the scratch buffer.
// ----------------------------------------------------------------------------
-median_error_t median_init_scratch_buffer(void * buffer, size_t buffer_size, median_buffer_t m, median_scratch_buffer_t * initialized_buffer){
+median_error_t median_init_scratch_buffer(
+ void *buffer, size_t buffer_size, median_buffer_t m,
+ median_scratch_buffer_t *initialized_buffer) {
median_scratch_buffer_t s = buffer;
- s->spareSize = buffer_size - sizeof(spare_buffer_t);
+ s->spareSize = buffer_size - sizeof(struct spare_buffer);
*initialized_buffer = s;
return MEDIAN_OK;
}
+median_error_t median_init_json_string(void *buffer, size_t buffer_size,
+ median_buffer_t m,
+ median_json_string_t *output_buffer) {
+ median_json_string_t o = buffer;
+ o->outputBufferSize = buffer_size - sizeof(struct output_buffer);
+ *output_buffer = o;
+ return MEDIAN_OK;
+}
+
// ----------------------------------------------------------------------------
// Insert data into the buffer.
// ----------------------------------------------------------------------------
// Unprotected function.
-median_error_t _median_insert_data(median_buffer_t m,
- median_data_t data,
- median_scratch_buffer_t scratch){
+median_error_t _median_insert_data(median_buffer_t m, median_data_t data,
+ median_scratch_buffer_t scratch) {
// If there is space in the current block..
- if(!insert_into_current_block_if_possible(m,data)) {
+ if (!insert_into_current_block_if_possible(m, data)) {
// Shift
- if(!shift_current_block(m,scratch)) {
+ if (!shift_current_block(m, scratch)) {
return MEDIAN_ERROR_MAX_N_EXCEEDED;
}
// Try to insert again, this should work because
// we just shifted.
- if(!insert_into_current_block_if_possible(m,data)) {
+ if (!insert_into_current_block_if_possible(m, data)) {
return MEDIAN_ERROR_BUG;
}
}
@@ -404,13 +474,12 @@
}
// Locked function.
-median_error_t median_insert_data(median_buffer_t m,
- median_data_t data,
- median_scratch_buffer_t scratch){
+median_error_t median_insert_data(median_buffer_t m, median_data_t data,
+ median_scratch_buffer_t scratch) {
// Lock.
pthread_mutex_lock(m->mutex_ptr);
// Call the unprotected routine.
- median_error_t ret = _median_insert_data(m,data,scratch);
+ median_error_t ret = _median_insert_data(m, data, scratch);
// Unlock
pthread_mutex_unlock(m->mutex_ptr);
// return
@@ -420,8 +489,8 @@
// ----------------------------------------------------------------------------
// Compare two sort records.
// ----------------------------------------------------------------------------
-int compare_sortrec(const void * a, const void *b) {
- return ((sortrec_t *)a)->d < ((sortrec_t*)b)->d?-1:1;
+int compare_sortrec(const void *a, const void *b) {
+ return ((struct sortrec *)a)->d < ((struct sortrec *)b)->d ? -1 : 1;
}
// ----------------------------------------------------------------------------
@@ -430,37 +499,38 @@
// Unprotected implementation.
median_error_t _median_output_median(const median_buffer_t m,
- median_data_t *approximate_median,
- median_scratch_buffer_t scratch){
+ median_data_t *approximate_median,
+ median_scratch_buffer_t scratch) {
// Initialize the data buffer to zero.
- size_t datasz = m->nMembers * m->nLevels * sizeof(sortrec_t);
- if(datasz > scratch->spareSize) {
+ size_t datasz = m->nMembers * m->nLevels * sizeof(struct sortrec);
+ if (datasz > scratch->spareSize) {
return MEDIAN_ERROR_BUFFER_TOO_SMALL;
}
- sortrec_t * s = scratch->sortrec_data;
+ struct sortrec *s = scratch->sortrec_data;
bzero(s, datasz);
// Initialize the count and weight values.
size_t count = 0;
size_t weight = 0;
// First construct the sort buffer.
- for(blockdata_t * b = m->block_data; b < out_of_bounds(m); b = nextblock(b,m)) {
- for(size_t i = 0; i < b->occupancy; i++) {
+ for (struct blockdata *b = m->block_data; b < out_of_bounds(m);
+ b = nextblock(b, m)) {
+ for (size_t i = 0; i < b->occupancy; i++) {
s->d = b->median_data[i];
s->sz = (1 << b->level);
weight += s->sz;
- s++; count++;
+ s++;
+ count++;
}
}
- qsort(scratch->sortrec_data,count,sizeof(sortrec_t),&compare_sortrec);
+ qsort(scratch->sortrec_data, count, sizeof(struct sortrec), &compare_sortrec);
// This is the weight at which the median will be found.
- weight = weight/2;
+ weight = weight / 2;
// We now need to pick out the
// median.
- for(s = scratch->sortrec_data;
- weight > s->sz;
- weight -= (s++)->sz);
+ for (s = scratch->sortrec_data; weight > s->sz; weight -= (s++)->sz)
+ ;
*approximate_median = s->d;
return MEDIAN_OK;
@@ -469,27 +539,44 @@
// Locked call.
median_error_t median_output_median(const median_buffer_t m,
median_data_t *approximate_median,
- median_scratch_buffer_t scratch){
+ median_scratch_buffer_t scratch) {
pthread_mutex_lock(m->mutex_ptr);
median_error_t ret = _median_output_median(m, approximate_median, scratch);
pthread_mutex_unlock(m->mutex_ptr);
return ret;
}
+
+median_error_t _median_output_json(const median_buffer_t m,
+ median_json_string_t output) {
+ return MEDIAN_OK;
+}
+median_error_t median_output_json(const median_buffer_t m,
+ median_json_string_t output) {
+ pthread_mutex_lock(m->mutex_ptr);
+ median_error_t ret = _median_output_json(m, output);
+ pthread_mutex_unlock(m->mutex_ptr);
+ return ret;
+}
// ----------------------------------------------------------------------------
// Dump the state to stderr.
// ----------------------------------------------------------------------------
// Unprotected call.
-median_error_t _median_dump_stderr(const median_buffer_t m){
+median_error_t _median_dump_stderr(const median_buffer_t m) {
// First print out all the metadata.
- blockdata_t * current = get_current_block(m);
- fprintf(stderr, "Metadata:\n Next GID:%d\n nMembers:%d\n nLevels:%d\n CurrentBlock:%d\n",m->gid,(unsigned)m->nMembers,(unsigned)m->nLevels, current->id);
+ struct blockdata *current = get_current_block(m);
+ fprintf(
+ stderr,
+ "Metadata:\n Next GID:%d\n nMembers:%d\n nLevels:%d\n CurrentBlock:%d\n",
+ m->gid, (unsigned)m->nMembers, (unsigned)m->nLevels, current->id);
- for(blockdata_t * b = m->block_data; b < out_of_bounds(m); b = nextblock(b,m)) {
- // Now dump the blocks.
- fprintf(stderr, "Block:%d\n Level:%d\n Occupancy:%d\n", b->id,(unsigned)b->level,(unsigned)b->occupancy);
+ for (struct blockdata *b = m->block_data; b < out_of_bounds(m);
+ b = nextblock(b, m)) {
+ // Now dump the blocks.
+ fprintf(stderr, "Block:%d\n Level:%d\n Occupancy:%d\n", b->id,
+ (unsigned)b->level, (unsigned)b->occupancy);
// For every block, dump the first 8 keys in the block.
- stderr_hexdmp("Data:",b->data,8*sizeof(median_data_t));
+ stderr_hexdmp("Data:", b->data, 8 * sizeof(median_data_t));
}
// Done, return MEDIAN_OK.
@@ -497,7 +584,7 @@
}
// Protected call.
-median_error_t median_dump_stderr(const median_buffer_t m){
+median_error_t median_dump_stderr(const median_buffer_t m) {
pthread_mutex_lock(m->mutex_ptr);
median_error_t ret = _median_dump_stderr(m);
pthread_mutex_unlock(m->mutex_ptr);
diff --git a/median.h b/median.h
index 5e02bf8..d4a83a2 100644
--- a/median.h
+++ b/median.h
@@ -1,7 +1,7 @@
#ifndef __MONITORING_MEDIAN_H_INCLUDED__
#define __MONITORING_MEDIAN_H_INCLUDED__
-#include <stdint.h>
#include <stddef.h>
+#include <stdint.h>
// ------------------------------------------------------------------------
// The core phylosophy of the interface is this.
@@ -19,14 +19,12 @@
// The ErrorCode returned by all
// functions in this file.
typedef int32_t median_error_t;
-
-struct metadata_t;
-struct spare_buffer_t;
// A buffer which contains all the state held
// within an approximate median calculator.
// And another type for scratch data.
-typedef struct metadata * median_buffer_t;
-typedef struct spare_buffer * median_scratch_buffer_t;
+typedef struct metadata *median_buffer_t;
+typedef struct spare_buffer *median_scratch_buffer_t;
+typedef struct output_buffer *median_json_string_t;
// A single data element. For now this is defined
// to be a 64 bit integer. But in principle this could be
@@ -42,59 +40,74 @@
static const median_error_t MEDIAN_ERROR_INVALID_PARAMETERS = -1;
// The buffer allocated is too small for the parameters requested.
-static const 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 const median_error_t MEDIAN_ERROR_MAX_N_EXCEEDED = -3;
+static const median_error_t MEDIAN_ERROR_MAX_N_EXCEEDED = -3;
// This is returned when some invariant is broken.
// It should not happen in normal operation.
-static const median_error_t MEDIAN_ERROR_BUG = -1000;
+static const median_error_t MEDIAN_ERROR_BUG = -1000;
// Indicates that the size of the largest possible dataset is not known.
static const size_t MEDIAN_MAX_N_UNKNOWN = 0;
// The default size of the largest possible dataset.
-static const 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.
// maxN is the largest dataset that we anticipate. If maxN is set to
-// MEDIAN_MAX_N_UNKNOWN (or zero), then we assume MEDIAN_MAX_N_DEFAULT to be the value of
-// maxN. The value return parameter is conventionally the last one. In this
-// case, it contains the suggested_size of the buffer, assuming that the return
-// value is MEDIAN_ERROR_OK.
-// In all reasonable calls, the returned value will be
-// MEDIAN_ERROR_OK.
-median_error_t median_suggest_buffer_size(double epsilon, size_t maxN, size_t *suggested_size);
+// MEDIAN_MAX_N_UNKNOWN (or zero), then we assume MEDIAN_MAX_N_DEFAULT to be the
+// value of maxN. The value return parameter is conventionally the last one. In
+// this case, it contains the suggested_size of the buffer, assuming that the
+// return value is MEDIAN_ERROR_OK. In all reasonable calls, the returned value
+// will be MEDIAN_ERROR_OK.
+median_error_t median_suggest_buffer_size(double epsilon, size_t maxN,
+ size_t *suggested_size);
// Suggest a size of the buffer for scratch space. This is needed
// so that the buffer is not corrupted by the output and merge steps.
-median_error_t median_suggest_scratch_buffer_size(median_buffer_t m, size_t *suggested_size);
+median_error_t median_suggest_scratch_buffer_size(median_buffer_t m,
+ size_t *suggested_size);
+// Suggest a size of a buffer to output a JSON description of the median status.
+// This is the function that is used to serialize out the result when needed.
+median_error_t median_suggest_json_string_size(median_buffer_t m,
+ size_t *suggested_size);
// This routine will init the buffer. It will check if the buffer meets the
// size restriction returned by #median_suggest_buffer_size(). If not, it will
// exit with MEDIAN_ERROR_BUFFER_TOO_SMALL.
// The method can also exit with MEDIAN_ERR)R_INVALID_PARAMETERS in case there
// are some meaningless parameters passed in the call.
-// We assume that a buffer of length buffer_size (in bytes) has been allocated and is
-// available at the pointer specified by buffer.
-// The parameters to median_suggest_buffer_size are passed into the data
-// initialization routine, and the init routine will store them inside the data
-// structure, so that the values can be used during the operation
-// of the data structure.
-// The value return parameter initialized_buffer is identical to the buffer
-// variable (i.e. *initialized_buffer == buffer), but is appropriately cast
-// to indicate that it is initialized.
-// In all reasonable calls, the returned value will be
+// We assume that a buffer of length buffer_size (in bytes) has been allocated
+// and is available at the pointer specified by buffer. The parameters to
+// median_suggest_buffer_size are passed into the data initialization routine,
+// and the init routine will store them inside the data structure, so that the
+// values can be used during the operation of the data structure. The value
+// return parameter initialized_buffer is identical to the buffer variable (i.e.
+// *initialized_buffer == buffer), but is appropriately cast to indicate that it
+// is initialized. In all reasonable calls, the returned value will be
// 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);
+median_error_t median_init_buffer(void *buffer, size_t buffer_size,
+ double epsilon, size_t maxN,
+ median_buffer_t *initialized_buffer);
// This frees up any internal resource consumed with the buffer, including
// mutex locks and other provisioned resources.
median_error_t median_deinit_buffer(median_buffer_t m);
// Initialize the scratch buffer.
// This function is similar in behaviour to the
// init function for the main buffer.
-median_error_t median_init_scratch_buffer(void * buffer, size_t buffer_size, median_buffer_t m, median_scratch_buffer_t * initialized_buffer);
+median_error_t median_init_scratch_buffer(
+ void *buffer, size_t buffer_size, median_buffer_t m,
+ median_scratch_buffer_t *initialized_buffer);
+// De-init the scratch buffer.
+median_error_t median_deinit_scratch_buffer(median_scratch_buffer_t s);
+// Initialize the output buffer.
+median_error_t median_init_json_string(
+ void *buffer, size_t buffer_size, median_buffer_t m,
+ median_json_string_t *initialized_buffer);
+// De-init the output buffer.
+median_error_t median_deinit_json_string(median_json_string_t b);
// This routine inserts a data point into the median computation. It's
// implemented to be really cheap. However, it is not always constant time.
@@ -111,7 +124,8 @@
// then MEDIAN_ERROR_INVALID_PARAMETERS will be returned.
// In all reasonable calls, the returned value will be
// MEDIAN_ERROR_OK.
-median_error_t median_insert_data(median_buffer_t buffer, median_data_t data, median_scratch_buffer_t scratch_buffer);
+median_error_t median_insert_data(median_buffer_t buffer, median_data_t data,
+ median_scratch_buffer_t scratch_buffer);
// This routine returns the approximate median of the data seen thusfar.
// This is implemented to be really cheap as well, but not as cheap as the
@@ -126,9 +140,14 @@
// return an error.
// If it does return an error, the error will be
// MEDIAN_ERROR_INVALID_PARAMETERS
-median_error_t median_output_median(const median_buffer_t buffer, median_data_t *approximate_median, median_scratch_buffer_t scratch_buffer);
-
-// This hexdumps the state of the buffer to stderr so that it can help debug if needed.
+median_error_t median_output_median(const median_buffer_t buffer,
+ median_data_t *approximate_median,
+ median_scratch_buffer_t scratch_buffer);
+// Output the JSON representation of the median buffer state.
+median_error_t median_output_json(const median_buffer_t buffer,
+ median_json_string_t output);
+// This hexdumps the state of the buffer to stderr so that it can help debug if
+// needed.
median_error_t median_dump_stderr(const median_buffer_t buffer);
-#endif // ._MONITORING_MEDIAN>H_INCLUDED__
+#endif // ._MONITORING_MEDIAN>H_INCLUDED__
diff --git a/median.main.c b/median.main.c
index 32beae4..15cbb36 100644
--- a/median.main.c
+++ b/median.main.c
@@ -1,34 +1,36 @@
-#include <stdio.h> // fprintf, stderr
-#include <stdlib.h> // size_t
-#include <assert.h> // assert
-#include "median.h"
+#include <assert.h> // assert
+#include <stdio.h> // fprintf, stderr
+#include <stdlib.h> // size_t
#include "hex.h"
+#include "median.h"
-#define TEST_SIZE 1024*1024*256 // 256M
+#define TEST_SIZE 1024 * 1024 * 256 // 256M
// 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[]) {
+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;
// Allocate the buffer of the required size. And then
// initialize it (median_init_buffer).
- assert(median_suggest_buffer_size(.001, TEST_SIZE , &n) == MEDIAN_OK);
- void * b = malloc(n);
+ assert(median_suggest_buffer_size(.001, TEST_SIZE, &n) == MEDIAN_OK);
+ void* b = malloc(n);
+ assert(b);
median_buffer_t buf;
assert(median_init_buffer(b, n, .001, TEST_SIZE, &buf) == MEDIAN_OK);
// Initialize the spare buffer.
assert(median_suggest_scratch_buffer_size(buf, &n) == MEDIAN_OK);
- void * s = malloc(n);
+ void* s = malloc(n);
+ assert(s);
median_scratch_buffer_t scratch;
- assert(median_init_scratch_buffer(s,n,buf,&scratch) == MEDIAN_OK);
+ assert(median_init_scratch_buffer(s, n, buf, &scratch) == MEDIAN_OK);
// Insert some data.
- for(median_data_t i = 1; i < TEST_SIZE; i++) { // 1G
- assert(median_insert_data(buf,i,scratch) == MEDIAN_OK);
+ for (median_data_t i = 1; i < TEST_SIZE; i++) { // 1G
+ assert(median_insert_data(buf, i, scratch) == MEDIAN_OK);
}
// Dump the buffer.
@@ -36,15 +38,24 @@
median_data_t median;
assert(median_output_median(buf, &median, scratch) == MEDIAN_OK);
-
fprintf(stderr, "And the median is %x\n", (unsigned)median);
+ size_t obs = 0;
+ assert(median_suggest_json_string_size(buf, &obs) == MEDIAN_OK);
+ void* ob = malloc(obs);
+ assert(ob);
+ median_json_string_t mob;
+ assert(median_init_json_string(ob, obs, buf, &mob) == MEDIAN_OK);
+
// Free up the resources.
assert(median_deinit_buffer(buf) == MEDIAN_OK);
+ assert(median_deinit_scratch_buffer(scratch) == MEDIAN_OK);
+ assert(median_deinit_json_string(mob) == MEDIAN_OK);
// Free up the malloc'd space.
free(b);
free(s);
+ free(ob);
// All done, return 0
return 0;
