Merging two arrays of integers in C

Inspired by TDWTF’s “Cheaters Never Prosper” story, I decided to put together an example in C.

Given that we’ll be dealing with arrays of int and we’ll have to pass size information around, first, I declare a struct that holds a pointer to the array and the current size:

struct int_array_with_size {
    size_t size;
    int *ary;
};

This is mostly to avoid longish argument lists. Besides, it’s good to keep related information together.

Next, we need a way of creating such arrays:

static struct int_array_with_size *
new_int_array_with_size(
        size_t n_elem
        )
{
    struct int_array_with_size *p = malloc(sizeof(*p));
    if (!p) {
        return NULL;
    }

    p->ary = malloc(n_elem * (sizeof(*(p->ary))));
    if (!p->ary) {
        return NULL;
    }

    p->size = n_elem;
    return p;
}

We’d end up writing a lot of extra lines without a simple function to free such a struct:

static void free_int_array_with_size(
        struct int_array_with_size **p
        )
{
    free((*p)->ary);
    (*p)->ary = NULL;
    free(*p);
    *p = NULL;
    return;
}

A function to fill such an array with a bunch of integers is useful as well:

static void
fill_int_array(
        struct int_array_with_size *p,
        int start,
        int delta
        )
{
    size_t i;
    size_t k = p->size;

    for (i = 0; i < k; i += 1) {
        (p->ary)[i] = start;
        start += delta;
    }
    return;
}

And, of course, we might want to print the contents, too:

static void
print_int_array(
        const struct int_array_with_size *p
        )
{
    size_t i;
    size_t k = p->size;

    printf("[ ");
    for (i = 0; i < (k - 1); i += 1) {
        printf("%d, ", (p->ary)[i]);
    }
    printf("%d ]\n", (p->ary)[i]);

    return;
}

And, of course, we’ll need min and max:

static size_t min_size_t(const size_t x, const size_t y)
{
    return (x < y) ? x : y;
}

static size_t max_size_t(const size_t x, const size_t y)
{
    return (x > y) ? x : y;
}

Sure, you can define a generic macro, but I am allergic to macros that evaluate expressions more than once.

The algorithm for merging is quite simple: Allocate a similar array that can hold all the elements of the arrays to be merged. Then, fill in the even indexed elements from the first array, and the odd-indexed elements from the second array, until you reach the end of the shorter one. Then, fill in the rest of the elements from the longer one:

struct int_array_with_size *
merge_int_arrays(
        const struct int_array_with_size *x,
        const struct int_array_with_size *y
        )
{
    int *end = NULL;
    int *dest = NULL;
    int *src = NULL;
    size_t limit = 0;
    size_t remainder_size = 0;

    struct int_array_with_size *r = malloc(sizeof(*r));
    if (!r) {
        return NULL;
    }

    r->size = x->size + y->size;
    r->ary = malloc(r->size * sizeof(*(r->ary)));

    if (!r->ary) {
        free(r);
        return NULL;
    }

    limit = min_size_t(x->size, y->size);
    src = x->ary;
    end = r->ary + 2 * limit;

    for (dest = r->ary; dest < end; dest += 2) {
        *dest = *src;
        src += 1;
    }

    src = y->ary;
    for (dest = (1 + r->ary); dest < end; dest += 2) {
        *dest = *src;
        src += 1;
    }

    dest = end;
    remainder_size = sizeof(*(r->ary)) *
        (max_size_t(x->size, y->size) - limit);

    src = (x->size > y->size) ? x->ary : y->ary;
    src += limit;
    memcpy(dest, src, remainder_size);

    return r;
}

Note the one bit of premature optimization where instead of having a single for loop that copies elements from both arrays in one go, I first fill in the even-indexed elements and then the odd-indexed elements based on the assumption that not jumping between memory locations is going to be faster. No, I didn’t measure anything … just wrote it that way at first and later thought about why I did that ;-)

Finally, here’s a short main as proof that code works for some values of “works”:

int main(void) {
    struct int_array_with_size *r;
    struct int_array_with_size *x = new_int_array_with_size(3);
    struct int_array_with_size *y = new_int_array_with_size(5);

    if (!x || !y) {
        return EXIT_FAILURE;
    }

    fill_int_array(x, 1, 3);
    print_int_array(x);

    fill_int_array(y, 1000, 10);
    print_int_array(y);

    r = merge_int_arrays(x, y);
    if (!r) {
        return EXIT_FAILURE;
    }

    print_int_array(r);

    free_int_array_with_size(&r);
    free_int_array_with_size(&y);
    free_int_array_with_size(&x);

    return EXIT_SUCCESS;
}

Of course, what would we do without a Perl version?

#!/usr/bin/env perl

use 5.014;
use strict;
use warnings;

sub make_iterator {
    my $array = shift;
    return sub {
        state $i = 0;
        return $i <= $#$array ? $array->[$i++] : ();
    };
}

sub make_merger {
    my $iterators = shift;
    return sub { map $_->(), @$iterators };
}

my @iterators = map make_iterator($_), [1 .. 3], [5 .. 10];
my $merger = make_merger(\@iterators);

my @merged;
while (my @stripe = $merger->()) {
    push @merged, @stripe;
}

say "[ @merged ]";

OK, now I am being silly. That handles an arbitrary number of arrays as well as data types.