Circular Buffer with fast search

buffer.c

#include <stdio.h>
#include <string.h>
#include <malloc.h>

#include <math.h>
#include <limits.h>
#include <assert.h>

#include "buffer.h"

/*!
 * Circular Buffer Example (Keep one slot open)
 * Compile: gcc cbuf.c -o cbuf.exe
 */
 
/**< Init Circular Buffer */
Buffer* 
BufferInit(unsigned size)
{
    Buffer *self = (Buffer*) malloc(sizeof(Buffer));
    if (self)
    {
        self->size=size;
        self->head = 0;
        self->tail  = 0;
        self->keys = malloc(sizeof(TYPE) * size);
        if (!self->keys)
        {
            free(self);
            self = NULL;
        }
    }
    return self;
}

void 
BufferDestroy(Buffer *self)
{
    free(self->keys);
    free(self);
}
 
inline int 
BufferIsFull(Buffer* self)
{
    return (((self->head + 1) % self->size) == self->tail);
}
 
inline int 
BufferIsEmpty(Buffer* self)
{
    return (self->head == self->tail);
}

inline TYPE *
BufferFirst (Buffer *self)
{
    if (BufferIsEmpty(self)) return NULL;
    return &self->keys[self->tail];
}

inline TYPE *
BufferLast (Buffer *self)
{
    if (BufferIsEmpty(self)) return NULL;
    return &self->keys[self->head - 1];
}

inline void 
BufferEnque(Buffer* self, double k)
{
    if (BufferIsFull(self))
    {        
        BufferDeque(self, NULL);
    }
    self->keys[self->head] = k;
    self->head++;
    self->head %= self->size;
}

inline void 
BufferDeque(Buffer* self, TYPE *k)
{
    if (!BufferIsEmpty(self))
    {        
        if (k)
        {
            *k = self->keys[self->tail];
        }
        self->tail++;
        self->tail %= self->size;
    }
}

unsigned BufferSearch (Buffer *self, TYPE k)
{
    unsigned a, b;
    for (b = self->head;b != self->tail && self->keys[a] >= k;b = a)
    {
        a = b > 0 ? b - 1 : self->size - 1;
    }
    return b;
}

unsigned 
BufferFastSearch (Buffer *self, TYPE k)
{
    unsigned a = self->head, b = self->tail, l, c;
    if (k > self->keys[a]) return a;
    do
    {
        l = (self->size + a - b) % self->size;
        c = (b + (unsigned)floor(l / 2.0)) % self->size;

        if (k > self->keys[c])
        {
            b = c;
        }
        else
        {
            a = c;
        }
    } while (l > 1);
    return a;
}

int 
BufferInsert(Buffer *self, double k)
{
    if (BufferIsFull(self))
    {        
        BufferDeque(self, NULL);
    }
    unsigned a, b;
    
    for (b = self->head;b != self->tail && self->keys[b] != k;b = a)
    {
        a = b > 0 ? b - 1 : self->size - 1;
        if (self->keys[a] > k)
        {
            self->keys[b] = self->keys[a];
        }
        else
        {
            break;
        }
    }
    self->keys[b] = k;

    self->head++;
    self->head %= self->size;

    return self->head;
}

int
BufferFastInsert(Buffer *self, double k)
{
    unsigned a = self->head, b = self->tail, l, c, i;
    
    do
    {
        l = (self->size + a - b) % self->size;
        c = (b + (unsigned)ceil(l / 2.0)) % self->size;

        if (k > self->keys[c])
        {
            b = c;
        }
        else
        {
            a = c;
        }
    } while (l > 1);
    
    i = k < self->keys[b] ? b : a;
    
    TYPE temp;
    
    if (BufferIsFull(self))
    {        
        BufferDeque(self, NULL);
    }
    
    if (i == self->head)
    {
        BufferEnque(self, k);
    }
    else
    {
        while (i != self->head)
        {
            temp = self->keys[i];
            self->keys[i] = k;
            k = temp;
            i++;
            i %= self->size;
        }
        self->keys[i] = k;
        self->head++;
        self->head %= self->size;
    }

    return 0;
}

int BufferPrint(Buffer* self)
{
    unsigned i = self->tail;
    while (i != self->head)
    {
        printf("%3.3f\t", self->keys[i]);
        i++;
        i %= self->size;
    }
    printf("\n");
    return 0;
}

int BufferPrint2(Buffer* self)
{
    unsigned i = 0;
    for (i = 0;i < self->size;i++)
    {
        printf("%3u: ", i);
        if (i >= self->tail && (i < self->head || self->head <= self->tail))
        {
            printf("%3.3f\t", self->keys[i]); 
        }
        else if (i < self->tail && i < self->head)
        {
            printf("%3.3f\t", self->keys[i]); 
        }
        else if (i == self->head)
        {
            printf(" X    \t");
        }
        else
        {
            printf(" O    \t"); 
        }
    }
    printf("\n");
    return 0;
}

int BufferPrintReverse(Buffer* self)
{
    unsigned i = self->head;
    while (i != self->tail)
    {
        i = i > 0 ? i - 1 : self->size - 1;
        printf("%3.3f\t", self->keys[i]);
    }
    printf("\n");
    return 0;
}

buffer.h

#define TYPE double
#define BUFFER_ELEMENT_TYPE double
#define BUFFER_MAX_SIZE (UINT_MAX / sizeof(BUFFER_ELEMENT_TYPE))

typedef struct
{
    long head;
    long tail;
    size_t size;
    double *keys;
    int written;
} Buffer;

/* reader remembers what has been read */
typedef struct
{
    unsigned first;
    unsigned last;
    unsigned head;
    unsigned tail;
} BufferReader;

Buffer* BufferInit(unsigned);
void BufferDestroy(Buffer *);
inline int BufferIsFull(Buffer *);
inline int BufferIsEmpty(Buffer *);
inline void BufferEnque(Buffer *, double);
inline void BufferDeque(Buffer *, double *);
unsigned BufferSearch (Buffer *self, double);
unsigned BufferFastSearch (Buffer *, double);
int BufferInsert(Buffer *self, double);
int BufferFastInsert(Buffer *, double);
int BufferPrint(Buffer *);
int BufferPrint2(Buffer *);
int BufferPrintReverse(Buffer *);

buffer_test.c

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <unistd.h>
#include <assert.h>

#include "buffer.h"

#define BUFFER_SIZE 10000
#define BUFFER_TESTS 33333

int main(int argc, char *argv[])
{
    int o;
    clock_t start, diff[10];
    unsigned c, t;
    unsigned b_sz = BUFFER_SIZE, b_tests = BUFFER_TESTS, distribution = 0;
    double *values;
    Buffer *b;
    
    unsigned *results[2];
    
    while ((o = getopt (argc, argv, "s:t:l")) != EOF)
    {
        switch (o)
        {
            case 's':
                b_sz = atoi(optarg);
                break;
            case 't':
                b_tests = atoi(optarg);
                break;
            case 'l':
                distribution = 1;
            default:
                break;
        }
    }

    /* create random values */
    values = malloc(b_tests * sizeof(TYPE));
    assert(values);
    
    /* set seed for pseudo random number generator */
    srand(time(0));
    
    for (t = 0;t < b_tests;t++)
    {
        switch (distribution)
        {
            case 1:
                values[t] = t < 1 ? (rand() % 10000000) * 0.001 : 
                    values[t - 1] + (rand() % 100000) * 0.001;
                break;
            default:
                values[t] = (rand() % 10000000) * 0.001;
                break;
        }
    }
    
    for (c = 0;c <= 4;c++)
    {
        b = BufferInit(b_sz);
        
        switch (c)
        {
            case 3:
            case 4:
                results[c % 2] = malloc(b_tests * sizeof(unsigned));
                break;
            default:
                break;
        }
        
        /* start time measuring */
        start = clock(); 
        
        for (t = 0;t < b_tests;t++)
        {
            switch (c)
            {
                case 0:
                    BufferEnque(b, values[t]);
                    break;
                case 1:
                    BufferInsert(b, values[t]);
                    break;
                case 2:
                    BufferFastInsert(b, values[t]);
                    break;
                case 3:
                    results[c % 2][t] = BufferSearch(b, values[t]);
                    break;
                case 4:
                    results[c % 2][t] = BufferFastSearch(b, values[t]);
                    break;
                case 5:
                    if (results[0][t] != results[1][t])
                    {
                        printf("Error in search for %.3f. (%u != %u)\n", 
                            values[t], results[0][t], results[1][t]);
                        BufferPrint2(b);
                    }
                default:
                    break;
            }
        }
        
        /* calculate time difference */
        diff[c] = clock() - start;
        
        BufferDestroy(b);
    }

    printf("Enque took %.5f seconds.\n", ((double)(diff[0])) / CLOCKS_PER_SEC);
    
    printf("Insertion took %.5f seconds.\n", 
        ((double)(diff[1])) / CLOCKS_PER_SEC);
    printf("Fast Insertion took %.5f seconds.\n", 
        ((double)(diff[2])) / CLOCKS_PER_SEC);
    
    printf("Search took %.5f seconds.\n", 
        ((double)(diff[3])) / CLOCKS_PER_SEC);
    printf("Fast Search took %.5f seconds.\n", 
        ((double)(diff[4])) / CLOCKS_PER_SEC);

    return 0;
}