C言語で可変長配列を作った

JavaのArrayListを参考にしつつ、2種類作った。
　

mallocしたメモリの先頭アドレスの配列を保持するパターン

voidポインタの配列。
配列の個数+1回mallocする。
charとか小さいものだと無駄がありそう。（特に64bitOSの場合）
配列の数が足らなくなったら、voidポインタの配列のサイズをreallocする。
　

vararr.h

#ifndef VARARR_H
#define VARARR_H

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

typedef void (*VARARR_DELETE_FUNC)(void*);

typedef struct {
	void **values;
	unsigned int size;
	unsigned int allocsize;
	VARARR_DELETE_FUNC delete_func;
} VARARR;

extern VARARR* vararr_new(unsigned int size);
extern void vararr_delete(VARARR* arr);

#define vararr_push(arr, item) \
	if (arr->allocsize <= arr->size) { \
		if (arr->allocsize==0) { \
			arr->allocsize = 32; \
		} else { \
			arr->allocsize <<= 1; \
		} \
		/* printf("vararr_push realloc: %p %u\n", arr, arr->allocsize); */ \
		arr->values = (void**)realloc(arr->values, arr->allocsize * sizeof(void*)); \
	} \
	arr->values[arr->size] = item; \
	arr->size++;

#define vararr_push_int(arr, item) \
	int *value = (int*)malloc(sizeof(int)); \
	*value = (item); \
	vararr_push(hash_arr, value);

#define vararr_remove(arr, i, do_delete) \
	if (arr) { \
		if (0<=i && i<arr->size && arr->values[i]) { \
			if (arr->delete_func && do_delete) { \
				arr->delete_func(arr->values[i]); \
			} \
			arr->size--; \
			if (i < arr->size) { \
				arr->values[i] = arr->values[arr->size]; \
				/* memmove(&arr->values[i], &arr->values[i+1], (arr->size-i)*sizeof(void*)); */ \
			} \
			arr->values[arr->size] = NULL; \
		} \
	}

#endif

vararr.c

#include "vararr.h"


// 生成
VARARR* vararr_new(unsigned int size)
{
	VARARR *arr;
	arr = (VARARR*)malloc(sizeof(VARARR));
	if (0<size) {
		arr->allocsize = size;
	} else {
		arr->allocsize = 1;
	}
	arr->values = (void**)malloc(arr->allocsize * sizeof(void*));
	arr->size = 0;
	arr->delete_func = (VARARR_DELETE_FUNC)free;
	return arr;
}

// 開放
void vararr_delete(VARARR* arr)
{
	unsigned int i;
	if (arr) {
		if (arr->delete_func) {
			for (i=0; i<arr->size; i++) {
				arr->delete_func(arr->values[i]);
			}
		}
		free(arr->values);
		free(arr);
	}
}

配列の個数分の長さをmallocしたメモリの先頭アドレスを保持するパターン

mallocは1回だけ。
奇妙なキャストをしてバイト数で無理やりアクセス。
配列の数が足らなくなったら、voidポインタの指す先をまるごとreallocする。
大きな構造体の配列とかだと無駄がありそう。
　

vararr.h

#ifndef VARARR_H
#define VARARR_H

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



/* VARARR */

typedef void (*VARARR_DELETE_FUNC)(void*);

typedef struct {
	void *values;
	unsigned int size;
	unsigned int allocsize;
	unsigned int onesize;
	VARARR_DELETE_FUNC delete_func;
} VARARR;


extern VARARR* vararr_new(unsigned int allocsize, unsigned int onesize);
extern void vararr_delete(VARARR *arr);


#define vararr_getp(arr, i) \
	/* ((i)<arr->allocsize ? (void*)&((char(*)[arr->onesize])arr->values)[i] : NULL) */ \
	((i)<arr->allocsize ? (void*)(((char*)arr->values) + (i) * arr->onesize) : NULL)

#define vararr_get(arr, i, type) \
	((i)<arr->allocsize ? ((type*)arr->values)[i] : 0)

#define vararr_realloc(arr, i) \
	if (arr->allocsize<=(i)) { \
		while (arr->allocsize<=(i)) { \
			arr->allocsize <<= 1; \
		} \
		printf("vararr_realloc: %p %u\n", arr, arr->allocsize); \
		arr->values = realloc(arr->values, arr->allocsize * arr->onesize); \
	}

#define vararr_put(arr, i, value, type) \
	if ((i)<arr->allocsize) { \
		((type*)arr->values)[i] = value; \
	}

#define vararr_push(arr, value, type) \
	vararr_realloc(arr, arr->size); \
	vararr_put(arr, arr->size, value, type); \
	arr->size++;

#define vararr_remove(arr, i, type) \
	if ((i)<arr->size) { \
		if (arr->delete_func) { \
			arr->delete_func(vararr_getp(arr, i)); \
		} \
		arr->size--; \
		if ((i)<arr->size) { \
			((type*)arr->values)[i] = ((type*)arr->values)[arr->size]; \
		} \
	}



/* CHARS */

#define chars_new(allocsize, onesize) \
	vararr_new(allocsize, onesize)

#define chars_get(arr, i) \
	((char*)vararr_getp(arr, i))

#define chars_put(arr, i, str) \
	if ((i)<arr->size) { \
		strcpy(&((char*)arr->values)[(i) * arr->onesize], str); \
	}

#define chars_push(arr, str) \
	vararr_realloc(arr, arr->size); \
	chars_put(arr, arr->size, str); \
	arr->size++;

#define chars_delete(arr) \
	vararr_delete(arr)



/* UINTS */

#define uints_new(allocsize) \
	vararr_new(allocsize, sizeof(unsigned int))

#define uints_get(arr, i) \
	vararr_get(arr, i, unsigned int)

#define uints_put(arr, i, value) \
	vararr_put(arr, i, value, unsigned int)

#define uints_push(arr, value) \
	vararr_push(arr, value, unsigned int)

#define uints_remove(arr, i) \
	vararr_remove(arr, i, unsigned int)

#endif

vararr.c

#include "vararr.h"

VARARR* vararr_new(unsigned int allocsize, unsigned int onesize)
{
	VARARR *arr;
	arr = (VARARR*)malloc(sizeof(VARARR));
	arr->values = (void*)malloc(allocsize * onesize);
	arr->size = 0;
	arr->allocsize = allocsize;
	arr->onesize = onesize;
	arr->delete_func = NULL;
	return arr;
}

void vararr_delete(VARARR *arr)
{
	unsigned int i;
	if (arr) {
		if (arr->delete_func) {
			for (i=0; i<arr->size; i++) {
				arr->delete_func(vararr_getp(arr, i));
			}
		}
		free(arr->values);
		free(arr);
	}
}

速度

構造体を扱う場合は、前者の方が1.25倍位速かった。
　
マルチバイト文字列を1文字ずつに分割する処理は、後者の方が1.65倍位速かった。
でもなぜかVARARRとは全く関係ない箇所が遅くなっていて、全体の速度は下がった。（なぜ？）
　
名前が被らないようにして2つを併用してみたら、どっこいどっこいか若干遅いか位。
当然だけど、実行ファイルのサイズが大きくなった。
　
後者だけを使った場合、なんとなく遅い。
　
よく解らないから、前者だけを使おうと思う。