arrlist.c

#include "arrlist.h"

#include <math.h>
#include <stdlib.h>
#include <string.h>

#define EXTRA_CAPACITY 4
#define RESZ_NUMER 5
#define RESZ_DENOM 3
#define MAX(x, y) ((x) > (y) ? (x) : (y))

static void arLsResize(ArrList*, int capacity);

ArrList arLsNew(size_t size, int len_hint) {
	ArrList list;

	list.size = size;
	list.length = 0;
	list.extra_cap = EXTRA_CAPACITY;
	list.capacity = len_hint + list.extra_cap;
	list.resz_numer = RESZ_NUMER;
	list.resz_denom = RESZ_DENOM;
	list.data = malloc(list.size * list.capacity);
	return list;
}

ArrList arLsCopy(size_t size, void* arr, int len) {
	ArrList list = arLsNew(size, len);

	list.length = len;
	memcpy(list.data, arr, list.size * list.length);
	return list;
}

void arLsFree(ArrList* list) {
	free(list->data);
	memset(list, 0, sizeof(ArrList));
}

void arLsCalibrate(ArrList* list, int extra, int n, int d) {
	list->extra_cap = extra;
	list->resz_numer = n;
	list->resz_denom = d;
}

void arLsShrinkToFit(ArrList* list) {
	arLsResize(list, list->length);
}

void* arLsGet(const ArrList* list, int index) {
	return &((char*)list->data)[list->size * index];
}

void* arLsFind(const ArrList* list, void* data, cmp_func cmp) {
	for (int i = 0; i < list->length; i++){
		void* item = (char*)list->data + list->size * i;
		if (cmp(item, data) == 0)
			return item;
	}
	return NULL;
}

int arLsIndexOf(const ArrList* list, const void* item) {
	int index = ((char*)item - (char*)list->data) / list->size;
	
	if (index >= 0 && index < list->length)
		return index;
	else
		return -1;
}

void arLsAppend(ArrList* list, void* data) {
	if (list->length == list->capacity)
		arLsResize(list, list->capacity + MAX(list->extra_cap, 1));
	memcpy((char*)list->data + list->size * list->length, data, list->size);
	list->length++;
}

void arLsInsert(ArrList* list, void* data, int index) {
	if (list->length == list->capacity)
		arLsResize(list, list->capacity + MAX(list->extra_cap, 1));
	for (int i = list->length - 1; i >= index; i--)
		memcpy(
			(char*)list->data + list->size * (i + 1),
			(char*)list->data + list->size * i,
			list->size
		);
	memcpy((char*)list->data + list->size * index, data, list->size);
	list->length++;
}

void arLsOrderedInsert(ArrList* list, void* data, cmp_func cmp) {
	int i;
	if (list->length == list->capacity)
		arLsResize(list, list->capacity + MAX(list->extra_cap, 1));
	for (
		i = list->length;
		i >= 1 && cmp((char*)list->data + list->size * (i - 1), data) > 0;
		i--
	)
		memcpy(
			(char*)list->data + list->size * i,
			(char*)list->data + list->size * (i - 1),
			list->size
		);
	memcpy((char*)list->data + list->size * i, data, list->size);
	list->length++;
}

void arLsRemove(ArrList* list, int index) {
	for (int i = index; i < list->length - 1; i++)
		memcpy(
			(char*)list->data + list->size * i,
			(char*)list->data + list->size * (i + 1),
			list->size
		);
	list->length--;
	if (
		(list->capacity - list->length) > list->length &&
		list->resz_denom * (list->capacity - list->length) >
		list->resz_numer * list->extra_cap
	)
		arLsResize(list, list->length + MAX(list->extra_cap, 1));
}

void arLsResize(ArrList* list, int capacity) {
	list->data = realloc(list->data, list->size * capacity);
	list->capacity = capacity;
}

arrlist.h

#ifndef ARRLIST_H
#define ARRLIST_H

#include <stddef.h>

typedef int(*cmp_func)(const void*, const void*);

typedef struct arLs {
	void* data;
	size_t size;
	int
		length,
		capacity,
		extra_cap, resz_numer, resz_denom;
} ArrList;

ArrList arLsNew(size_t, int len_hint);
ArrList arLsCopy(size_t, void*, int len);
void arLsFree(ArrList*);
void arLsCalibrate(ArrList*, int extra, int n, int d);
void arLsShrinkToFit(ArrList*);
void* arLsGet(const ArrList*, int index);
void* arLsFind(const ArrList*, void*, cmp_func);
int arLsIndexOf(const ArrList*, const void*);
void arLsAppend(ArrList*, void*);
void arLsInsert(ArrList*, void*, int index);
void arLsOrderedInsert(ArrList*, void*, cmp_func);
void arLsRemove(ArrList*, int index);
//void arLsSort(ArrList*, cmp_func);

#endif