Remove all spaces

remove_all_spaces.c

// cc -std=c99 -g -O0 -Wall remove_all_spaces.c -o remove_all_spaces && gdb -ex r -ex q ./remove_all_spaces
// cc -DENABLE_BENCHMARK -std=c99 -O3 -Wall remove_all_spaces.c -o remove_all_spaces && ./remove_all_spaces | gnuplot -p -

#include <assert.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

static char* remove_char(char* st, const size_t pos, const size_t maxlen);
static char* remove_first_space(char* st, const size_t maxlen);
char* remove_all_spaces_quadratic(char* st, const size_t maxlen);
char* remove_all_spaces_linear(char* st, const size_t maxlen);

typedef char* (*pfunction)(char*, const size_t);

#define TEST_STRING "12 34 56 78 90 "
#define TEST_STRING_SIZE 15
#define MIN(x, y) ((x < y) ? (x) : (y))

void test_helpers();
void test(pfunction remove_all_spaces);

static char* make_input(const size_t len);
void benchmark(pfunction remove_all_spaces);

static char* remove_char(char* st, const size_t pos, const size_t maxlen)
{
    size_t i;
    for (i = pos; i < maxlen - 1 && st[i] != '\0'; i++)
    {
        st[i] = st[i + 1];
    }
    return st;
}

static char* remove_first_space(char* st, const size_t maxlen)
{
    size_t i;
    for (i = 0; i < maxlen && st[i] != '\0'; i++)
    {
        if (isspace(st[i]))
        {
            return remove_char(st, i, maxlen);
        }
    }
    return st;
}

char* remove_all_spaces_quadratic(char* st, const size_t maxlen)
{
    size_t i = 0;
    while (i < maxlen)
    {
        if (isspace(st[i]))
        {
            (void) remove_char(st, i, maxlen);
        }
        else
        {
            i++;
        }
    }
    return st;
}

char* remove_all_spaces_linear(char* st, const size_t maxlen)
{
    size_t r = 0;
    size_t w = 0;

    while (r < maxlen)
    {
        if (!isspace(st[r]))
        {
            st[w] = st[r];
            w++;
        }

        if (st[r] == '\0')
        {
            break;
        }

        r++;
    }

    return st;
}

void test_helpers()
{
    {
        #define SIZE 12
        char input[SIZE] = "hello world";
        char output[SIZE] = "helloworld";
        char* our = remove_char(input, 5, SIZE);
        assert(strncmp(our, output, SIZE) == 0);
        #undef SIZE
    }
    {
        #define SIZE 12
        char input[SIZE] = "hello world";
        char output[SIZE] = "hello worl";
        char* our = remove_char(input, 10, SIZE);
        assert(strncmp(our, output, SIZE) == 0);
        #undef SIZE
    }
    {
        #define SIZE 24
        char input[SIZE] = "hello world blab blabla";
        char output[SIZE] = "helloworld blab blabla";
        char* our = remove_first_space(input, SIZE);
        assert(strncmp(our, output, SIZE) == 0);
        #undef SIZE
    }
    {
        #define SIZE 15
        char* input = make_input(SIZE);
        assert(strncmp(input, "12 34 56 78 90", SIZE) == 0);
        free(input);
        #undef SIZE
    }
    {
        #define SIZE 20
        char* input = make_input(SIZE);
        assert(strncmp(input, "12 34 56 78 90 12 3", SIZE) == 0);
        free(input);
        #undef SIZE
    }
}

void test(pfunction remove_all_spaces)
{
    {
        #define SIZE 24
        char input[SIZE] = "hello world blab blabla";
        char output[SIZE] = "helloworldblabblabla";
        char* our = remove_all_spaces(input, SIZE);
        assert(strncmp(our, output, SIZE) == 0);
        #undef SIZE
    }
    {
        #define SIZE 35
        char input[SIZE] = "hello world   blab blabla bla  bla";
        char output[SIZE] = "helloworldblabblablablabla";
        char* our = remove_all_spaces(input, SIZE);
        assert(strncmp(our, output, SIZE) == 0);
        #undef SIZE
    }
    {
        #define SIZE 37
        char input[SIZE] = "hello world   blab blabla bla  bla  ";
        char output[SIZE] = "helloworldblabblablablabla";
        char* our = remove_all_spaces(input, SIZE);
        assert(strncmp(our, output, SIZE) == 0);
        #undef SIZE
    }
    {
        #define SIZE 38
        char input[SIZE] = "   hello world   blab blabla bla  bla";
        char output[SIZE] = "helloworldblabblablablabla";
        char* our = remove_all_spaces(input, SIZE);
        assert(strncmp(our, output, SIZE) == 0);
        #undef SIZE
    }
}

static char* make_input(const size_t len)
{
    assert(len > 0);

    char* input = (char*) malloc(len * sizeof(char));

    size_t pos = 0;
    while (pos < len)
    {
        memcpy(input + pos, TEST_STRING, MIN(TEST_STRING_SIZE, len - pos - 1));
        pos += TEST_STRING_SIZE;
    }

    input[len - 1] = '\0';

    return input;
}

void benchmark(pfunction remove_all_spaces)
{
    size_t len = 10;

    while (len < 5000ULL)
    {
        char* input = make_input(len);

        const clock_t start = clock();
        remove_all_spaces(input, len);
        const clock_t end = clock();
        const clock_t dt = end - start;
        const double dt_seconds = dt / (double) CLOCKS_PER_SEC;
        printf("%lu,%lf\n", (unsigned long) len, dt_seconds);

        free(input);

        len += 10;
    }
}

int main()
{
    test_helpers();
    test(remove_all_spaces_linear);
    test(remove_all_spaces_quadratic);

#ifdef ENABLE_BENCHMARK
    printf("set xlabel 'input length'; set ylabel 'time in seconds'; set datafile separator ','; plot '-' with lines, '-' with lines\n");
    benchmark(remove_all_spaces_linear);
    printf("e\n");
    benchmark(remove_all_spaces_quadratic);
    printf("e\n");
    fflush(stdout);
#endif

    return 0;
}