Suppose you were to delete all of the array like this. One moves forward in the array, and at every data, tests if it should be deleted: yes. It will move all the array back one spot every time. The running time to delete n objects is n(n+1)/2 which is O(n^2).
We could do better by having a lazy delete operation which remembers the spot but doesn't delete until it absolutely has to. This runs in one pass O(n).
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <assert.h>
struct inventory {
char name[128];
uint64_t amount;
uint32_t cent_price;
};
static const size_t max_size_of_strings = sizeof ((struct inventory *)0)->name;
struct database {
struct inventory data[32];
size_t size;
} db;
static const size_t max_size_of_arrays = sizeof db.data / sizeof *db.data;
typedef int (*predicate_fn)(const struct inventory *, const void *);
static void keep_if(const predicate_fn keep, const void *const param) {
struct inventory *erase = 0, *i, *retain = 0, *end;
int keep0 = 1, keep1 = 0;
assert(keep);
for(i = db.data, end = i + db.size; i < end; keep0 = keep1, i++) {
keep1 = !!keep(i, param);
if(!(keep0 ^ keep1)) continue; /* Not a falling/rising edge. */
if(keep1) { /* Rising edge. */
assert(erase && !retain);
retain = i;
} else if(erase) { /* Falling edge. */
size_t n = (size_t)(i - retain);
assert(erase < retain && retain < i);
memmove(erase, retain, sizeof *i * n);
erase += n;
retain = 0;
} else { /* Falling edge, (first time only.) */
erase = i;
}
}
if(!erase) return; /* All elements were kept. */
if(keep1) { /* Delayed move when the iteration ended; repeat. */
size_t n = (size_t)(i - retain);
assert(retain && erase < retain && retain < i);
memmove(erase, retain, sizeof *i * n);
erase += n;
}
/* Adjust the size. */
assert((size_t)(erase - db.data) <= db.size);
db.size = (size_t)(erase - db.data);
}
static int strcmp_name(const struct inventory *item, const void *const vname) {
const char *const name = vname;
return strcmp(name, item->name);
}
int main(void) {
size_t i;
strcpy(db.data[0].name, "A"); db.data[0].amount = 0;
strcpy(db.data[1].name, "B"); db.data[1].amount = 1;
strcpy(db.data[2].name, "A"); db.data[2].amount = 2;
strcpy(db.data[3].name, "B"); db.data[3].amount = 3;
strcpy(db.data[4].name, "A"); db.data[4].amount = 4;
strcpy(db.data[5].name, "B"); db.data[5].amount = 5;
strcpy(db.data[6].name, "C"); db.data[6].amount = 6;
strcpy(db.data[7].name, "B"); db.data[7].amount = 7;
strcpy(db.data[8].name, "B"); db.data[8].amount = 8;
strcpy(db.data[9].name, "B"); db.data[9].amount = 9;
strcpy(db.data[10].name, "B"); db.data[10].amount = 10;
strcpy(db.data[11].name, "B"); db.data[11].amount = 11;
strcpy(db.data[12].name, "B"); db.data[12].amount = 12;
strcpy(db.data[13].name, "A"); db.data[13].amount = 13;
strcpy(db.data[14].name, "C"); db.data[14].amount = 14;
db.size = 15;
keep_if(&strcmp_name, "B"); /* strcmp returns false if matched */
for(i = 0; i < db.size; i++) {
const struct inventory *const item = db.data + i;
printf("%llu, %d, %s\n", item->amount, item->cent_price, item->name);
}
return 0;
}
I've simplified the code with a struct so all the data is in one object. (I assume the second MAX_SIZE_OF_ARRAYS in INVENTORY_NAMES_ARRAY should be MAX_SIZE_OF_STRINGS.)
mallocwhich are pointers not arrays). So if your array was defined asxpto[4]it will always have 4 elements. You can however keep a count of active elements...int xpto[4] = {1, 2, 3, 4}, active_xpto = 4; ... xpto[2] = 4; active_xpto = 3; ...