Blame src/array.c

8535a3
8535a3
#include "private.h"
8535a3
8535a3
8535a3
void heliPairInit(HeliPair *p) {
8535a3
	p->key = p->value = NULL;
8535a3
	p->freeKey = p->freeValue = NULL;
8535a3
}
8535a3
8535a3
void heliPairDestroy(HeliPair *p) {
8eb855
	HeliPair pp;
8eb855
	memcpy(&pp, p, sizeof(pp));
8535a3
	heliPairInit(p);
8eb855
	if (pp.key && pp.freeKey) pp.freeKey(pp.key);
8eb855
	if (pp.value && pp.freeValue) pp.freeValue(pp.value);
8535a3
}
8535a3
07b70f
void heliArrayInit(HeliArray *a) {
8535a3
	a->items = NULL;
8535a3
	a->count = a->allocated = 0;
8535a3
}
8535a3
07b70f
void heliArrayDestroy(HeliArray *a) {
8535a3
	heliArrayClear(a);
8535a3
	free(a->items);
8535a3
	heliArrayInit(a);
8535a3
}
8535a3
8535a3
HeliPair* heliArrayGet(HeliArray *a, int i)
8535a3
	{ return i >= 0 && i < a->count ? &a->items[i] : NULL; }
8535a3
8535a3
void* heliArrayGetKey(HeliArray *a, int i) {
8535a3
	HeliPair *item = heliArrayGet(a, i);
8535a3
	return item ? item->key : NULL;
8535a3
}
8535a3
8535a3
void* heliArrayGetValue(HeliArray *a, int i) {
8535a3
	HeliPair *item = heliArrayGet(a, i);
8535a3
	return item ? item->value : NULL;
8535a3
}
8535a3
8eb855
HeliPair* heliArrayInsertPair(HeliArray *a, int i, void *k, HeliFreeCallback fk, void *v, HeliFreeCallback fv) {
8535a3
	if (i < 0 || i > a->count)
8535a3
		i = a->count;
8535a3
	if (a->allocated < a->count + 1) {
8535a3
		a->allocated += a->allocated/4 + 32;
07b70f
		a->items = realloc(a->items, a->allocated*sizeof(a->items[0]));
8535a3
		memset(&a->items[a->count], 0, (a->allocated - a->count)*sizeof(a->items[0]));
8535a3
	}
8535a3
	if (i < a->count) {
8535a3
		memmove(&a->items[i+1], &a->items[i], (a->count-i)*sizeof(a->items[0]));
8535a3
		memset(&a->items[i], 0, sizeof(a->items[0]));
8535a3
	}
8535a3
	++a->count;
8535a3
	
8535a3
	HeliPair *item = &a->items[i];
8535a3
	item->key = k;
8535a3
	item->value = v;
8535a3
	item->freeKey = fk;
8535a3
	item->freeValue = fv;
8535a3
	return item;
8535a3
}
8535a3
8535a3
HeliPair* heliArrayInsert(HeliArray *a, int i, void *v, HeliFreeCallback fv)
8eb855
	{ return heliArrayInsertPair(a, i, NULL, NULL, v, fv); }
8535a3
8535a3
void heliArrayRemove(HeliArray *a, int i) {
8535a3
	if (i < 0 || i >= a->count) return;
8eb855
	HeliPair item;
8eb855
	memcpy(&item, &a->items[i], sizeof(item));
8535a3
	memmove(&a->items[i], &a->items[i+1], (a->count-i-1)*sizeof(a->items[0]));
8535a3
	--a->count;
8535a3
	memset(&a->items[a->count], 0, sizeof(a->items[0]));
8eb855
	heliPairDestroy(&item);
8535a3
}
8535a3
8535a3
void heliArrayClear(HeliArray *a) {
8535a3
	while(a->count > 0)
87fe10
		heliArrayRemove(a, 0);
8535a3
}
8535a3
8eb855
8eb855
HeliPair* heliMapFind(HeliArray *a, const void *k, HeliCompareCallback cmp, int *gtOrEqIndex) {
8535a3
	int i0 = 0;
8535a3
	int i1 = a->count - 1;
8eb855
	int c = i0 < a->count ? cmp(a->items[i0].key, k) : -1;
8eb855
	if (c >= 0) {
8535a3
		if (gtOrEqIndex) *gtOrEqIndex = i0;
8eb855
		return c ? NULL : &a->items[i0];
8535a3
	}
8eb855
	if (i1 > i0) c = cmp(a->items[i1].key, k);
8eb855
	if (c < 0) {
8535a3
		if (gtOrEqIndex) *gtOrEqIndex = a->count;
d1f083
		return NULL;
d1f083
	}
8eb855
	if (c == 0) {
d1f083
		if (gtOrEqIndex) *gtOrEqIndex = i1;
d1f083
		return &a->items[i1];
8535a3
	}
8535a3
	
8535a3
	while(i0 + 1 < i1) {
8535a3
		int i = (i0 + i1)/2;
8eb855
		c = cmp(a->items[i].key, k);
8eb855
		if (c == 0) {
8535a3
			if (gtOrEqIndex) *gtOrEqIndex = i;
8535a3
			return &a->items[i];
8535a3
		}
8eb855
		if (c < 0) i0 = i; else i1 = i;
8535a3
	}
8535a3
	if (gtOrEqIndex) *gtOrEqIndex = i1;
8535a3
	return NULL;
8535a3
}
8535a3
8eb855
HeliPair* heliMapGet(HeliArray *a, const void *k, HeliCompareCallback cmp)
8eb855
	{ return heliMapFind(a, k, cmp, NULL); }
8535a3
8eb855
HeliPair* heliMapAdd(
8eb855
	HeliArray *a, const void *k, HeliCompareCallback cmp,
8eb855
	HeliCloneCallback ck, HeliFreeCallback fk,
8eb855
	void *v, HeliFreeCallback fv )
8eb855
{
8535a3
	int i;
8eb855
	HeliPair *item = heliMapFind(a, k, cmp, &i);
8535a3
	if (item) {
8eb855
		if (item->value != v) {
8eb855
			void *vv = item->value;
8eb855
			HeliFreeCallback ffvv = item->freeValue;
8eb855
			item->value = v;
8eb855
			item->freeValue = fv;
8eb855
			if (vv && ffvv) ffvv(vv);
8eb855
		}
8535a3
	} else {
8eb855
		item = heliArrayInsertPair(a, i, ck(k), fk, v, fv);
8535a3
	}
8535a3
	return item;
8535a3
}
8535a3
8eb855
int heliMapRemove(HeliArray *a, const void *k, HeliCompareCallback cmp) {
8535a3
	int i;
8eb855
	if (heliMapFind(a, k, cmp, &i)) {
8535a3
		heliArrayRemove(a, i);
8535a3
		return TRUE;
8535a3
	}
8535a3
	return FALSE;
8535a3
}
8535a3
909bc2
static int uintCompare(size_t a, size_t b)
909bc2
	{ return a < b ? -1 : (a > b ? 1: 0); }
909bc2
static size_t uintClone(size_t a)
909bc2
	{ return a; }
909bc2
HeliPair* heliUIntFind(HeliArray *a, size_t k, int *gtOrEqIndex)
909bc2
	{ return heliMapFind(a, (const void*)k, (HeliCompareCallback)&uintCompare, gtOrEqIndex); }
909bc2
HeliPair* heliUIntGet(HeliArray *a, size_t k)
909bc2
	{ return heliUIntFind(a, k, NULL); }
909bc2
HeliPair* heliUIntAdd(HeliArray *a, size_t k, void *v, HeliFreeCallback fv)
909bc2
	{ return heliMapAdd(a, (const void*)k, (HeliCompareCallback)&uintCompare, (HeliCloneCallback)&uintClone, NULL, v, fv); }
909bc2
int heliUIntRemove(HeliArray *a, size_t k)
909bc2
	{ return heliMapRemove(a, (const void*)k, (HeliCompareCallback)&uintCompare); }
8eb855
8eb855
HeliPair* heliStringmapFind(HeliArray *a, const char *k, int *gtOrEqIndex)
8eb855
	{ return heliMapFind(a, k, (HeliCompareCallback)&strcmp, gtOrEqIndex); }
8eb855
HeliPair* heliStringmapGet(HeliArray *a, const char *k)
8eb855
	{ return heliStringmapFind(a, k, NULL); }
8eb855
HeliPair* heliStringmapAdd(HeliArray *a, const char *k, void *v, HeliFreeCallback fv)
8eb855
	{ return heliMapAdd(a, k, (HeliCompareCallback)&strcmp, (HeliCloneCallback)&heliStringCopy, &free, v, fv); }
8eb855
int heliStringmapRemove(HeliArray *a, const char *k)
8eb855
	{ return heliMapRemove(a, k, (HeliCompareCallback)&strcmp); }
8eb855