[C] explode()

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>

struct v {
void *p;
size_t n;
};

struct v **explode(const void *p, const void *q, size_t pn, size_t qn, size_t size);
void *memmem(const void *p, const void *q, size_t pn, size_t qn, size_t size);
void *memdup(const void *p, size_t n);

int main(void) {
struct v **p = explode("a b", " ", 3, 1, 1);
struct v **q = p;
if(p == NULL) {
perror(NULL);
return EXIT_FAILURE;
}
while(*p) {
fwrite((*p)->p, 1, (*p)->n, stdout);
putchar(' ');
p++;
}
putchar('\n');
p = q;
while(*p != NULL) {
free((*p)->p);
free(*p++);
}
free(q);
return 0;
}

struct v **explode(const void *p, const void *q, size_t pn, size_t qn, size_t size) {
void *tmp;
struct v **rv = NULL;
size_t i;
ptrdiff_t j;
pn *= size;
qn *= size;
for(i = 0;; i++) {
while(pn >= qn && memcmp(p, q, qn) == 0) {
p = (char *)p + qn;
pn -= qn;
}
if((tmp = realloc(rv, (i + 1) * sizeof *rv)) == NULL) {
while(i--) {
free(rv[i]->p);
free(rv[i]);
}
free(rv);
return NULL;
}
rv = tmp;
rv[i] = NULL;
if(pn == 0) break;
if((rv[i] = malloc(sizeof **rv)) == NULL) {
while(i--) {
free(rv[i]->p);
free(rv[i]);
}
free(rv);
return NULL;
}
if((tmp = memmem(p, q, pn, qn, size)) == NULL) {
if((rv[i]->p = memdup(p, pn)) == NULL) {
while(i--) {
free(rv[i]->p);
free(rv[i]);
}
free(rv);
return NULL;
}
rv[i]->n = pn;
break;
}
else {
j = (char *)tmp - (char *)p;
if((tmp = memdup(p, j)) == NULL) {
while(i--) {
free(rv[i]->p);
free(rv[i]);
}
free(rv);
return NULL;
}
rv[i]->p = tmp;
rv[i]->n = j;
p = (char *)p + j;
pn -= j;
}
}
if(rv[i] != NULL) {
if((tmp = realloc(rv, (i + 2) * sizeof *rv)) == NULL) {
i++;
while(i--) {
free(rv[i]->p);
free(rv[i]);
}
free(rv);
return NULL;
}
rv[i + 1] = NULL;
}
return rv;
}

void *memdup(const void *p, size_t n) {
void *rv = NULL;
if((rv = malloc(n)) != NULL) memcpy(rv, p, n);
return rv;
}

void *memmem(const void *p, const void *q, size_t pn, size_t qn, size_t size) {
for(; pn >= qn; p = (unsigned char *)p + 1, pn -= size)
if(memcmp(p, q, qn) == 0) return p;
return NULL;
}

>>13
for(i = 0;; i++) {
It's quadratic in the number of fragments.
i is the number of rv blocks, and it tries to grow the array of rv pointers by only 1 each time, realloc() potentially has to move and copy the memory if it can't expand the current block.

Even if you fix it to a geometric progression, it's still way too many allocations and deallocations, should run through p once and record all the offsets of where it should be split into an index array, then allocate entire rv once and then copy the fragments there using the index array.
Two passes through p, but I reckon it's way better than allocating and reallocing all the time.