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;