第三章 从动态数组学习设计

3.1 动态数组与双向链表

/*
 * File:    typedef.h
 */

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

#ifndef TYPEDEF_H
#define TYPEDEF_H

typedef enum _Ret
{
	RET_OK,
	RET_OOM,
	RET_STOP,
	RET_INVALID_PARAMS,
	RET_FAIL
}Ret;

typedef void     (*DataDestroyFunc)(void* ctx, void* data);
typedef int      (*DataCompareFunc)(void* ctx, void* data);
typedef Ret      (*DataVisitFunc)(void* ctx, void* data);

#ifdef __cplusplus
#define DECLS_BEGIN extern "C" {
#define DECLS_END   }
#else
#define DECLS_BEGIN
#define DECLS_END
#endif/*__cplusplus*/

#define return_if_fail(p) if(!(p)) \
	{printf("%s:%d Warning: "#p" failed.\n", \
		__func__, __LINE__); return;}
#define return_val_if_fail(p, ret) if(!(p)) \
	{printf("%s:%d Warning: "#p" failed.\n",\
	__func__, __LINE__); return (ret);}

#define SAFE_FREE(p) if(p != NULL) {free(p); p = NULL;}

typedef Ret (*SortFunc)(void** array, size_t nr, DataCompareFunc cmp);

#endif/*TYPEDEF_H*/

/*
 * File:    darray.h
 */

#include <stdio.h>
#include "typedef.h"

#ifndef DARRAY_H
#define DARRAY_H

DECLS_BEGIN

struct _DArray;
typedef struct _DArray DArray;

DArray* darray_create(DataDestroyFunc data_destroy, void* ctx);

Ret    darray_insert(DArray* thiz, size_t index, void* data);
Ret    darray_prepend(DArray* thiz, void* data);
Ret    darray_append(DArray* thiz, void* data);
Ret    darray_delete(DArray* thiz, size_t index);
Ret    darray_get_by_index(DArray* thiz, size_t index, void** data);
Ret    darray_set_by_index(DArray* thiz, size_t index, void* data);
size_t darray_length(DArray* thiz);
int    darray_find(DArray* thiz, DataCompareFunc cmp, void* ctx);
Ret    darray_foreach(DArray* thiz, DataVisitFunc visit, void* ctx);

void darray_destroy(DArray* thiz);

DECLS_END

#endif/*DARRAY_H*/

/*
 * File:    darray.c
 */

#include <stdlib.h>
#include <stdint.h>
#include "darray.h"

struct _DArray
{
	void** data;
	size_t size;
	size_t alloc_size;

	void* data_destroy_ctx;
	DataDestroyFunc data_destroy;
};

static void darray_destroy_data(DArray* thiz, void* data)
{
	if(thiz->data_destroy != NULL)
	{
		thiz->data_destroy(thiz->data_destroy_ctx, data);
	}

	return;
}

DArray* darray_create(DataDestroyFunc data_destroy, void* ctx)
{
	DArray* thiz = malloc(sizeof(DArray));

	if(thiz != NULL)
	{
		thiz->data  = NULL;
		thiz->size  = 0;
		thiz->alloc_size = 0;
		thiz->data_destroy = data_destroy;
		thiz->data_destroy_ctx = ctx;
	}

	return thiz;
}

#define MIN_PRE_ALLOCATE_NR 10
static Ret darray_expand(DArray* thiz, size_t need)
{
	return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS); 

	if((thiz->size + need) > thiz->alloc_size)
	{
		/*  thiz->alloc_size * 1.5 + MIN_PRE_ALLOCATE_NR   */
		size_t alloc_size = thiz->alloc_size + (thiz->alloc_size>>1) + MIN_PRE_ALLOCATE_NR;

		void** data = (void**)realloc(thiz->data, sizeof(void*) * alloc_size);
		if(data != NULL)
		{
			thiz->data = data;
			thiz->alloc_size = alloc_size;
		}
	}

	return ((thiz->size + need) <= thiz->alloc_size) ? RET_OK : RET_FAIL;
}

static Ret darray_shrink(DArray* thiz)
{
	return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS); 

	if((thiz->size < (thiz->alloc_size >> 1)) && (thiz->alloc_size > MIN_PRE_ALLOCATE_NR))
	{
		size_t alloc_size = thiz->size + (thiz->size >> 1);

		void** data = (void**)realloc(thiz->data, sizeof(void*) * alloc_size);
		if(data != NULL)
		{
			thiz->data = data;
			thiz->alloc_size = alloc_size;
		}
	}

	return RET_OK;
}

Ret darray_insert(DArray* thiz, size_t index, void* data)
{
	Ret ret = RET_OOM;
	size_t cursor = index;
	return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS); 

	cursor = cursor < thiz->size ? cursor : thiz->size;

	if(darray_expand(thiz, 1) == RET_OK)
	{
		size_t i = 0;
		for(i = thiz->size; i > cursor; i--)
		{
			thiz->data[i] = thiz->data[i-1];
		}

		thiz->data[cursor] = data;
		thiz->size++;
		
		ret = RET_OK;
	}

	return ret;
}

Ret darray_prepend(DArray* thiz, void* data)
{
	return darray_insert(thiz, 0, data);
}

Ret darray_append(DArray* thiz, void* data)
{
	return darray_insert(thiz, -1, data);
}

Ret darray_delete(DArray* thiz, size_t index)
{
	size_t i = 0;
	Ret ret = RET_OK;

	return_val_if_fail(thiz != NULL && thiz->size > index, RET_INVALID_PARAMS); 

	darray_destroy_data(thiz, thiz->data[index]);
	for(i = index; (i+1) < thiz->size; i++)
	{
		thiz->data[i] = thiz->data[i+1];
	}
	thiz->size--;

	darray_shrink(thiz);

	return RET_OK;
}

Ret darray_get_by_index(DArray* thiz, size_t index, void** data)
{

	return_val_if_fail(thiz != NULL && data != NULL && index < thiz->size, 
		RET_INVALID_PARAMS); 

	*data = thiz->data[index];

	return RET_OK;
}

Ret darray_set_by_index(DArray* thiz, size_t index, void* data)
{
	return_val_if_fail(thiz != NULL && index < thiz->size, 
		RET_INVALID_PARAMS); 

	thiz->data[index] = data;

	return RET_OK;
}

size_t   darray_length(DArray* thiz)
{
	size_t length = 0;
	
	return_val_if_fail(thiz != NULL, 0);

	return thiz->size;
}

Ret darray_foreach(DArray* thiz, DataVisitFunc visit, void* ctx)
{
	size_t i = 0;	
	Ret ret = RET_OK;
	return_val_if_fail(thiz != NULL && visit != NULL, RET_INVALID_PARAMS);

	for(i = 0; i < thiz->size; i++)
	{
		ret = visit(ctx, thiz->data[i]);
	}

	return ret;
}

int      darray_find(DArray* thiz, DataCompareFunc cmp, void* ctx)
{
	size_t i = 0;

	return_val_if_fail(thiz != NULL && cmp != NULL, -1);

	for(i = 0; i < thiz->size; i++)
	{
		if(cmp(ctx, thiz->data[i]) == 0)
		{
			break;
		}
	}

	return i;
}

void darray_destroy(DArray* thiz)
{
	size_t i = 0;
	
	if(thiz != NULL)
	{
		for(i = 0; i < thiz->size; i++)
		{
			darray_destroy_data(thiz, thiz->data[i]);
		}
		
		SAFE_FREE(thiz->data);
		SAFE_FREE(thiz);
	}

	return;
}

#ifdef DARRAY_TEST

#include <assert.h>

static int int_cmp(void* ctx, void* data)
{
	return (int)data - (int)ctx;
}

static Ret print_int(void* ctx, void* data)
{
	printf("%d ", (int)data);

	return RET_OK;
}

static Ret check_and_dec_int(void* ctx, void* data)
{
	int* expected =(int*)ctx;
	assert(*expected == (int)data);

	(*expected)--;

	return RET_OK;
}

static void test_int_darray(void)
{
	//int i = 0;
	//int n = 100;
	//int data = 0;

	intptr_t i = 0;
	intptr_t n = 100;
	intptr_t data = 0;

	DArray* darray = darray_create(NULL, NULL);

	for(i = 0; i < n; i++)
	{
		assert(darray_append(darray, (void*)i) == RET_OK);
		assert(darray_length(darray) == (i + 1));
		assert(darray_get_by_index(darray, i, (void**)&data) == RET_OK);
		assert(data == i);
		assert(darray_set_by_index(darray, i, (void*)(2*i)) == RET_OK);
		assert(darray_get_by_index(darray, i, (void**)&data) == RET_OK);
		assert(data == 2*i);
		assert(darray_set_by_index(darray, i, (void*)i) == RET_OK);
		assert(darray_find(darray, int_cmp, (void*)i) == i);
	}

	for(i = 0; i < n; i++)
	{
		assert(darray_get_by_index(darray, 0, (void**)&data) == RET_OK);
		assert(data == (i));
		assert(darray_length(darray) == (n-i));
		assert(darray_delete(darray, 0) == RET_OK);
		assert(darray_length(darray) == (n-i-1));
		if((i + 1) < n)
		{
			assert(darray_get_by_index(darray, 0, (void**)&data) == RET_OK);
			assert((int)data == (i+1));
		}
	}
	
	assert(darray_length(darray) == 0);

	for(i = 0; i < n; i++)
	{
		assert(darray_prepend(darray, (void*)i) == RET_OK);
		assert(darray_length(darray) == (i + 1));
		assert(darray_get_by_index(darray, 0, (void**)&data) == RET_OK);
		assert(data == i);
		assert(darray_set_by_index(darray, 0, (void*)(2*i)) == RET_OK);
		assert(darray_get_by_index(darray, 0, (void**)&data) == RET_OK);
		assert(data == 2*i);
		assert(darray_set_by_index(darray, 0, (void*)i) == RET_OK);
	}

	i = n - 1;
	assert(darray_foreach(darray, check_and_dec_int, &i) == RET_OK);

	darray_destroy(darray);

	return;
}

static void test_invalid_params(void)
{
	printf("===========Warning is normal begin==============\n");
	assert(darray_length(NULL) == 0);
	assert(darray_prepend(NULL, 0) == RET_INVALID_PARAMS);
	assert(darray_append(NULL, 0) == RET_INVALID_PARAMS);
	assert(darray_delete(NULL, 0) == RET_INVALID_PARAMS);
	assert(darray_insert(NULL, 0, 0) == RET_INVALID_PARAMS);
	assert(darray_set_by_index(NULL, 0, 0) == RET_INVALID_PARAMS);
	assert(darray_get_by_index(NULL, 0, NULL) == RET_INVALID_PARAMS);
	assert(darray_find(NULL, NULL, NULL) < 0);
	assert(darray_foreach(NULL, NULL, NULL) == RET_INVALID_PARAMS);
	printf("===========Warning is normal end==============\n");

	return;
}

static void single_thread_test(void)
{
	test_int_darray();
	test_invalid_params();

	return;
}

int main(int argc, char* argv[])
{
	single_thread_test();

	return 0;
}
#endif

CFILES=darray.c
all:
	gcc -g -shared -fPIC  -lpthread $(CFILES) -o libdarray.so
	gcc -g -DDARRAY_TEST -lpthread $(CFILES)  -o darray_test

clean:
	rm -f *test *.exe *.so

3.2 排序

• 冒泡排序

• 快速排序

  先将元素分成两个区，所有小于某个元素的值在第一个区，其他在第二个区。然后分别对这两个区进行快速排序，直到所分的区只剩下一个元素为止。

• 归并排序

  让左右两部分进行排序，然后把它们合并起来。在排序左右两部分时，同样使用归并排序.

/*
 * File:    typedef.h
 */

#include <stdio.h>
#include <stdint.h>
#include <assert.h>
#include <stdlib.h>

#ifndef TYPEDEF_H
#define TYPEDEF_H

typedef enum _Ret
{
	RET_OK,
	RET_OOM,
	RET_STOP,
	RET_INVALID_PARAMS,
	RET_FAIL
}Ret;

typedef void     (*DataDestroyFunc)(void* ctx, void* data);
typedef intptr_t      (*DataCompareFunc)(void* ctx, void* data);
typedef Ret      (*DataVisitFunc)(void* ctx, void* data);

#ifdef __cplusplus
#define DECLS_BEGIN extern "C" {
#define DECLS_END   }
#else
#define DECLS_BEGIN
#define DECLS_END
#endif/*__cplusplus*/

#define return_if_fail(p) if(!(p)) \
	{printf("%s:%d Warning: "#p" failed.\n", \
		__func__, __LINE__); return;}
#define return_val_if_fail(p, ret) if(!(p)) \
	{printf("%s:%d Warning: "#p" failed.\n",\
	__func__, __LINE__); return (ret);}

#define SAFE_FREE(p) if(p != NULL) {free(p); p = NULL;}

typedef Ret (*SortFunc)(void** array, size_t nr, DataCompareFunc cmp);

#endif/*TYPEDEF_H*/

/*
 * File:    sort.h
 */

#ifndef SORT_H
#define SORT_H

#include "typedef.h"

Ret bubble_sort(void** array, size_t nr, DataCompareFunc cmp);
Ret quick_sort(void** array, size_t nr, DataCompareFunc cmp);
Ret merge_sort(void** array, size_t nr, DataCompareFunc cmp);

#endif/*SORT_H*/

/*
 * File:    sort.c
 */

#include "sort.h"

/*
 *  冒泡排序
 */
Ret bubble_sort(void** p_array, size_t nr, DataCompareFunc cmp)
{
	size_t i     = 0;
	size_t max   = 0;
	size_t right = 0;


	return_val_if_fail(p_array != NULL && cmp != NULL, RET_INVALID_PARAMS);

	if(nr < 2){
		return RET_OK;
	}
	
	intptr_t* array = (intptr_t*)p_array;

	for(right = nr - 1; right > 0; right--){
		for(i = 1, max = 0; i < right; i++){
			if(cmp((void *)(array[i]), (void *)(array[max])) > 0){
				max = i;
			}
		}

		if(cmp((void *)(array[max]), (void *)(array[right])) > 0){
			intptr_t data = array[right];
			array[right] = array[max];
			array[max] = data;
		}
	}

	return RET_OK;
}


/*
 *  快速排序
 */
void quick_sort_impl(void** p_array, size_t left, size_t right, DataCompareFunc cmp)
{
	size_t save_left  = left;
	size_t save_right = right;
	
	intptr_t * array = (intptr_t *) p_array;    	

	intptr_t x = array[left];
	/*这个循环，让小于x的元素在左边，大于x的元素在右边*/
	while(left < right){
		while(cmp((void*)(array[right]), (void *) x) >= 0 && left < right) right--;
		if(left != right){
			array[left] = array[right];
			left++;
		}

		while(cmp((void *)(array[left]), (void *) x) <= 0 && left < right)	left++;
		if(left != right){
			array[right] = array[left];
			right--;
		}
	}
	array[left] = x;

	if(save_left < left){
		quick_sort_impl((void **)array, save_left, left-1, cmp);
	}

	if(save_right > left){
		quick_sort_impl((void **)array, left+1, save_right, cmp);
	}

	return;
}

Ret quick_sort(void** array, size_t nr, DataCompareFunc cmp)
{
	Ret ret = RET_OK;

	return_val_if_fail(array != NULL && cmp != NULL, RET_INVALID_PARAMS);

	if(nr > 1){
		quick_sort_impl(array, 0, nr - 1, cmp);
	}

	return ret;
}

/*
 * 归并排序
 */
static Ret merge_sort_impl(void** p_storage, void** p_array, size_t low, size_t mid, size_t high, DataCompareFunc cmp)
{
	size_t i = low;
	size_t j = low;
	size_t k = mid;

	intptr_t* storage = (intptr_t *) p_storage;
	intptr_t* array = (intptr_t *) p_array;
  
	/* 对左半部分排序 */
	if((low + 1) < mid){
		size_t x = low + ((mid - low) >> 1);
		merge_sort_impl(p_storage, p_array, low, x, mid, cmp);
	}
	
	/* 对右半部分排序 */
	if((mid + 1) < high){
		size_t x = mid + ((high - mid) >> 1);
		merge_sort_impl(p_storage, p_array, mid, x, high, cmp);
	}

	/* 合并两个有序数组 */	
	while(j < mid && k < high){
		if(cmp((void *)(array[j]), (void *)(array[k])) <= 0) {
			storage[i++] = array[j++];
		}
		else{
			storage[i++] = array[k++];
		}
	}

	while(j < mid){
		storage[i++] = array[j++];
	}

	while(k < high){
		storage[i++] = array[k++];
	}

	for(i = low; i < high; i++){
		array[i] = storage[i];
	}

	return RET_OK;
}

Ret merge_sort(void** array, size_t nr, DataCompareFunc cmp)
{
	void** storage = NULL;
	Ret ret = RET_OK;

	return_val_if_fail(array != NULL && cmp != NULL, RET_INVALID_PARAMS);

	if(nr > 1)
	{
		storage = (void**)malloc(sizeof(void*) * nr);
		if(storage != NULL)
		{
			ret = merge_sort_impl(storage, array, 0, nr>>1, nr, cmp);

			free(storage);
		}
	}

	return ret;
}


#ifdef SORT_TEST
#include <assert.h>
intptr_t int_cmp(void* a, void* b)
{
	return (intptr_t)a - (intptr_t)b;
}

intptr_t int_cmp_invert(void* a, void* b)
{
	return (intptr_t)b - (intptr_t)a;
}

static void** create_int_array(intptr_t n)
{
	intptr_t i = 0;
	intptr_t* array = (intptr_t*)malloc(sizeof(intptr_t) * n);
	for(i = 0; i < n; i++)
	{
		array[i] = rand();
	}

	return (void**)array;
}

static void sort_test_one_asc(SortFunc sort, intptr_t n)
{
	intptr_t i = 0;
	void** p_array = create_int_array(n);

	sort(p_array, n, int_cmp);

	intptr_t* array =  (intptr_t *)p_array;
	for(i = 1; i < n; i++)
	{
		assert(array[i] >= array[i-1]);
	}

	free(array);

	return;
}

static void sort_test_one_dec(SortFunc sort, intptr_t n)
{
	intptr_t i = 0;
	void** p_array = create_int_array(n);

	sort((void**)p_array, n, int_cmp_invert);


	intptr_t* array =  (intptr_t *)p_array;
	for(i = 1; i < n; i++)
	{
		assert(array[i] <= array[i-1]);
	}

	free(array);

	return;
}

static void sort_test(SortFunc sort)
{
	intptr_t i = 0;
	for(i = 0; i < 1000; i++) {
		sort_test_one_dec(sort, i);
		sort_test_one_asc(sort, i);
	}
	return ;
}

intptr_t main(intptr_t argc, char* argv[])
{
	srand(100);
	sort_test(bubble_sort); // 冒泡排序 测试
	sort_test(quick_sort);  // 快速排序 测试
	sort_test(merge_sort);  // 归并排序 测试

	return 0;
}
#endif/*SORT_TEST*/

all:
	gcc -g sort.c -DSORT_TEST -o sort_test 

clean:
	rm -f *test *.exe *.so

3.3. 有序数组的两个应用

/*
 * File:    typedef.h
 */

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

#ifndef TYPEDEF_H
#define TYPEDEF_H

typedef enum _Ret
{
	RET_OK,
	RET_OOM,
	RET_STOP,
	RET_INVALID_PARAMS,
	RET_FAIL
}Ret;

typedef void     (*DataDestroyFunc)(void* ctx, void* data);
typedef int      (*DataCompareFunc)(void* ctx, void* data);
typedef Ret      (*DataVisitFunc)(void* ctx, void* data);

#ifdef __cplusplus
#define DECLS_BEGIN extern "C" {
#define DECLS_END   }
#else
#define DECLS_BEGIN
#define DECLS_END
#endif/*__cplusplus*/

#define return_if_fail(p) if(!(p)) \
	{printf("%s:%d Warning: "#p" failed.\n", \
		__func__, __LINE__); return;}
#define return_val_if_fail(p, ret) if(!(p)) \
	{printf("%s:%d Warning: "#p" failed.\n",\
	__func__, __LINE__); return (ret);}

#define SAFE_FREE(p) if(p != NULL) {free(p); p = NULL;}

typedef Ret (*SortFunc)(void** array, size_t nr, DataCompareFunc cmp);

#endif/*TYPEDEF_H*/

/*
 * File : search.c
 */

#include "typedef.h"

int qsearch(void** array, size_t nr, void* data, DataCompareFunc cmp)
{
	int low    = 0;
	int mid    = 0;
	int high   = nr-1;
	int result = 0;

	return_val_if_fail(array != NULL && cmp != NULL, -1);

	while(low <= high)
	{
		mid  = low + ((high - low) >> 1);
		result = cmp(array[mid], data);

		if(result == 0){
			return mid;
		}else if(result < 0){
			low = mid + 1;
		}else{
			high = mid - 1;
		}
	}

	return -1;
}

#ifdef SEARCH_TEST
#include <assert.h>
int int_cmp(void* a, void* b)
{
	return (int)a - (int)b;
}

static void search_test(size_t n)
{
	int i = 0;
	int* array = (int*)malloc(n * sizeof(int));
	
	for(i = 0; i < n; i++){
		array[i] = i;
	}

	for(i = 0; i < n; i++){
		assert(qsearch((void**)array, n, (void*)i, int_cmp) == i);
	}

	free(array);

	return;
}

int main(int argc, char* argv[])
{
	int i = 0;
	for(i = 1; i < 1000; i++){
		search_test(i);
	}

	return 0;
}
#endif/*QSEARCH_TEST*/

/*
 * File:    sort.h
  */

#ifndef SORT_H
#define SORT_H

#include "typedef.h"

DECLS_BEGIN

Ret bubble_sort(void** array, size_t nr, DataCompareFunc cmp);
Ret quick_sort(void** array, size_t nr, DataCompareFunc cmp);
Ret merge_sort(void** array, size_t nr, DataCompareFunc cmp);

DECLS_END

#endif/*SORT_H*/

/*
 * File:    sort.c
 */

#include "sort.h"

Ret bubble_sort(void** array, size_t nr, DataCompareFunc cmp)
{
	size_t i     = 0;
	size_t max   = 0;
	size_t right = 0;

	return_val_if_fail(array != NULL && cmp != NULL, RET_INVALID_PARAMS);

	if(nr < 2) 
	{
		return RET_OK;
	}

	for(right = nr - 1; right > 0; right--)
	{
		for(i = 1, max = 0; i < right; i++)
		{
			if(cmp(array[i], array[max]) > 0)
			{
				max = i;
			}
		}

		if(cmp(array[max], array[right]) > 0)
		{
			void* data = array[right];
			array[right] = array[max];
			array[max] = data;
		}
	}

	return RET_OK;
}

void quick_sort_impl(void** array, size_t left, size_t right, DataCompareFunc cmp)
{
	size_t save_left  = left;
	size_t save_right = right;
	void* x = array[left];

	while(left < right)
	{
		while(cmp(array[right], x) >= 0 && left < right) right--;
		if(left != right)
		{
			array[left] = array[right];
			left++;
		}

		while(cmp(array[left], x) <= 0 && left < right)	left++;
		if(left != right)
		{
			array[right] = array[left];
			right--;
		}
	}
	array[left] = x;

	if(save_left < left)
	{
		quick_sort_impl(array, save_left, left-1, cmp);
	}

	if(save_right > left)
	{
		quick_sort_impl(array, left+1, save_right, cmp);
	}

	return;
}

Ret quick_sort(void** array, size_t nr, DataCompareFunc cmp)
{
	Ret ret = RET_OK;

	return_val_if_fail(array != NULL && cmp != NULL, RET_INVALID_PARAMS);

	if(nr > 1)
	{
		quick_sort_impl(array, 0, nr - 1, cmp);
	}

	return ret;
}

static Ret merge_sort_impl(void** storage, void** array, size_t low, size_t mid, size_t high, DataCompareFunc cmp)
{
	size_t i = low;
	size_t j = low;
	size_t k = mid;

	if((low + 1) < mid)
	{
		size_t x = low + ((mid - low) >> 1);
		merge_sort_impl(storage, array, low, x, mid, cmp);
	}
	
	if((mid + 1) < high)
	{
		size_t x = mid + ((high - mid) >> 1);
		merge_sort_impl(storage, array, mid, x, high, cmp);
	}

	
	while(j < mid && k < high)
	{
		if(cmp(array[j], array[k]) <= 0)
		{
			storage[i++] = array[j++];
		}
		else
		{
			storage[i++] = array[k++];
		}
	}

	while(j < mid)
	{
		storage[i++] = array[j++];
	}

	while(k < high)
	{
		storage[i++] = array[k++];
	}

	for(i = low; i < high; i++)
	{
		array[i] = storage[i];
	}

	return RET_OK;
}

Ret merge_sort(void** array, size_t nr, DataCompareFunc cmp)
{
	void** storage = NULL;
	Ret ret = RET_OK;

	return_val_if_fail(array != NULL && cmp != NULL, RET_INVALID_PARAMS);

	if(nr > 1)
	{
		storage = (void**)malloc(sizeof(void*) * nr);
		if(storage != NULL)
		{
			ret = merge_sort_impl(storage, array, 0, nr>>1, nr, cmp);

			free(storage);
		}
	}

	return ret;
}


#ifdef SORT_TEST
#include <assert.h>
int int_cmp(void* a, void* b)
{
	return (int)a - (int)b;
}

int int_cmp_invert(void* a, void* b)
{
	return (int)b - (int)a;
}

static void** create_int_array(int n)
{
	int i = 0;
	int* array = (int*)malloc(sizeof(int) * n);

	for(i = 0; i < n; i++)
	{
		array[i] = rand();
	}

	return (void**)array;
}

static void sort_test_one_asc(SortFunc sort, int n)
{
	int i = 0;
	void** array = create_int_array(n);

	sort(array, n, int_cmp);

	for(i = 1; i < n; i++)
	{
		assert(array[i] >= array[i-1]);
	}

	free(array);

	return;
}

static void sort_test_one_dec(SortFunc sort, int n)
{
	int i = 0;
	void** array = create_int_array(n);

	sort((void**)array, n, int_cmp_invert);

	for(i = 1; i < n; i++)
	{
		assert(array[i] <= array[i-1]);
	}

	free(array);

	return;
}

static void sort_test(SortFunc sort)
{
	int i = 0;
	for(i = 0; i < 1000; i++)
	{
		sort_test_one_dec(sort, i);
		sort_test_one_asc(sort, i);
	}

	return ;
}

int main(int argc, char* argv[])
{
	srand(100);

	sort_test(quick_sort);
	sort_test(merge_sort);
	sort_test(bubble_sort);

	return 0;
}
#endif/*SORT_TEST*/

/*
 * File:    darray.h
 */

#include <stdio.h>
#include "typedef.h"

#ifndef DARRAY_H
#define DARRAY_H

DECLS_BEGIN

struct _DArray;
typedef struct _DArray DArray;

DArray* darray_create(DataDestroyFunc data_destroy, void* ctx);

Ret    darray_insert(DArray* thiz, size_t index, void* data);
Ret    darray_prepend(DArray* thiz, void* data);
Ret    darray_append(DArray* thiz, void* data);
Ret    darray_delete(DArray* thiz, size_t index);
Ret    darray_get_by_index(DArray* thiz, size_t index, void** data);
Ret    darray_set_by_index(DArray* thiz, size_t index, void* data);
size_t darray_length(DArray* thiz);
int    darray_find(DArray* thiz, DataCompareFunc cmp, void* ctx);
Ret    darray_foreach(DArray* thiz, DataVisitFunc visit, void* ctx);
Ret    darray_sort(DArray* thiz, SortFunc sort, DataCompareFunc cmp);

void darray_destroy(DArray* thiz);

DECLS_END

#endif/*DARRAY_H*/

/*
 * File:    darray.c
 */

#include <stdlib.h>
#include "darray.h"

struct _DArray
{
	void** data;
	size_t size;
	size_t alloc_size;

	void* data_destroy_ctx;
	DataDestroyFunc data_destroy;
};

static void darray_destroy_data(DArray* thiz, void* data)
{
	if(thiz->data_destroy != NULL)
	{
		thiz->data_destroy(thiz->data_destroy_ctx, data);
	}

	return;
}

DArray* darray_create(DataDestroyFunc data_destroy, void* ctx)
{
	DArray* thiz = malloc(sizeof(DArray));

	if(thiz != NULL)
	{
		thiz->data  = NULL;
		thiz->size  = 0;
		thiz->alloc_size = 0;
		thiz->data_destroy = data_destroy;
		thiz->data_destroy_ctx = ctx;
	}

	return thiz;
}

#define MIN_PRE_ALLOCATE_NR 10
static Ret darray_expand(DArray* thiz, size_t need)
{
	return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS); 

	if((thiz->size + need) > thiz->alloc_size)
	{
		size_t alloc_size = thiz->alloc_size + (thiz->alloc_size>>1) + MIN_PRE_ALLOCATE_NR;

		void** data = (void**)realloc(thiz->data, sizeof(void*) * alloc_size);
		if(data != NULL)
		{
			thiz->data = data;
			thiz->alloc_size = alloc_size;
		}
	}

	return ((thiz->size + need) <= thiz->alloc_size) ? RET_OK : RET_FAIL;
}

static Ret darray_shrink(DArray* thiz)
{
	return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS); 

	if((thiz->size < (thiz->alloc_size >> 1)) && (thiz->alloc_size > MIN_PRE_ALLOCATE_NR))
	{
		size_t alloc_size = thiz->size + (thiz->size >> 1);

		void** data = (void**)realloc(thiz->data, sizeof(void*) * alloc_size);
		if(data != NULL)
		{
			thiz->data = data;
			thiz->alloc_size = alloc_size;
		}
	}

	return RET_OK;
}

Ret darray_insert(DArray* thiz, size_t index, void* data)
{
	Ret ret = RET_OOM;
	size_t cursor = index;
	return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS); 

	cursor = cursor < thiz->size ? cursor : thiz->size;

	if(darray_expand(thiz, 1) == RET_OK)
	{
		size_t i = 0;
		for(i = thiz->size; i > cursor; i--)
		{
			thiz->data[i] = thiz->data[i-1];
		}

		thiz->data[cursor] = data;
		thiz->size++;
		
		ret = RET_OK;
	}

	return ret;
}

Ret darray_prepend(DArray* thiz, void* data)
{
	return darray_insert(thiz, 0, data);
}

Ret darray_append(DArray* thiz, void* data)
{
	return darray_insert(thiz, -1, data);
}

Ret darray_delete(DArray* thiz, size_t index)
{
	size_t i = 0;

	return_val_if_fail(thiz != NULL && thiz->size > index, RET_INVALID_PARAMS); 

	darray_destroy_data(thiz, thiz->data[index]);
	for(i = index; (i+1) < thiz->size; i++)
	{
		thiz->data[i] = thiz->data[i+1];
	}
	thiz->size--;

	darray_shrink(thiz);

	return RET_OK;
}

Ret darray_get_by_index(DArray* thiz, size_t index, void** data)
{

	return_val_if_fail(thiz != NULL && data != NULL && index < thiz->size, 
		RET_INVALID_PARAMS); 

	*data = thiz->data[index];

	return RET_OK;
}

Ret darray_set_by_index(DArray* thiz, size_t index, void* data)
{
	return_val_if_fail(thiz != NULL && index < thiz->size, 
		RET_INVALID_PARAMS); 

	thiz->data[index] = data;

	return RET_OK;
}

size_t   darray_length(DArray* thiz)
{
	return_val_if_fail(thiz != NULL, 0);

	return thiz->size;
}

Ret darray_foreach(DArray* thiz, DataVisitFunc visit, void* ctx)
{
	size_t i = 0;	
	Ret ret = RET_OK;
	return_val_if_fail(thiz != NULL && visit != NULL, RET_INVALID_PARAMS);

	for(i = 0; i < thiz->size; i++)
	{
		ret = visit(ctx, thiz->data[i]);
	}

	return ret;
}

int      darray_find(DArray* thiz, DataCompareFunc cmp, void* ctx)
{
	size_t i = 0;

	return_val_if_fail(thiz != NULL && cmp != NULL, -1);

	for(i = 0; i < thiz->size; i++)
	{
		if(cmp(ctx, thiz->data[i]) == 0)
		{
			break;
		}
	}

	return i;
}

void darray_destroy(DArray* thiz)
{
	size_t i = 0;
	
	if(thiz != NULL)
	{
		for(i = 0; i < thiz->size; i++)
		{
			darray_destroy_data(thiz, thiz->data[i]);
		}
		
		SAFE_FREE(thiz->data);
		SAFE_FREE(thiz);
	}

	return;
}

Ret    darray_sort(DArray* thiz, SortFunc sort, DataCompareFunc cmp)
{
	return_val_if_fail(thiz != NULL && sort != NULL && cmp != NULL, RET_INVALID_PARAMS);

	return sort(thiz->data, thiz->size, cmp);
}

#ifdef DARRAY_TEST

#include "sort.h"
#include <assert.h>
#include "test_helper.c"

static void darray_assert_sorted(DArray* thiz, DataCompareFunc cmp)
{
	size_t i = 0;
	for(i = 1; i < thiz->size; i++)
	{
		assert(cmp(thiz->data[i], thiz->data[i-1]) >= 0);
	}

	return;
}

static Ret check_and_dec_int(void* ctx, void* data)
{
	int* expected =(int*)ctx;
	assert(*expected == (int)data);

	(*expected)--;

	return RET_OK;
}

static void test_int_darray(void)
{
	int i = 0;
	int n = 100;
	int data = 0;
	DArray* darray = darray_create(NULL, NULL);

	for(i = 0; i < n; i++)
	{
		assert(darray_append(darray, (void*)i) == RET_OK);
		assert(darray_length(darray) == (i + 1));
		assert(darray_get_by_index(darray, i, (void**)&data) == RET_OK);
		assert(data == i);
		assert(darray_set_by_index(darray, i, (void*)(2*i)) == RET_OK);
		assert(darray_get_by_index(darray, i, (void**)&data) == RET_OK);
		assert(data == 2*i);
		assert(darray_set_by_index(darray, i, (void*)i) == RET_OK);
		assert(darray_find(darray, cmp_int, (void*)i) == i);
	}

	for(i = 0; i < n; i++)
	{
		assert(darray_get_by_index(darray, 0, (void**)&data) == RET_OK);
		assert(data == (i));
		assert(darray_length(darray) == (n-i));
		assert(darray_delete(darray, 0) == RET_OK);
		assert(darray_length(darray) == (n-i-1));
		if((i + 1) < n)
		{
			assert(darray_get_by_index(darray, 0, (void**)&data) == RET_OK);
			assert((int)data == (i+1));
		}
	}
	
	assert(darray_length(darray) == 0);

	for(i = 0; i < n; i++)
	{
		assert(darray_prepend(darray, (void*)i) == RET_OK);
		assert(darray_length(darray) == (i + 1));
		assert(darray_get_by_index(darray, 0, (void**)&data) == RET_OK);
		assert(data == i);
		assert(darray_set_by_index(darray, 0, (void*)(2*i)) == RET_OK);
		assert(darray_get_by_index(darray, 0, (void**)&data) == RET_OK);
		assert(data == 2*i);
		assert(darray_set_by_index(darray, 0, (void*)i) == RET_OK);
	}

	i = n - 1;
	assert(darray_foreach(darray, check_and_dec_int, &i) == RET_OK);

	darray_sort(darray, quick_sort, cmp_int);
	darray_assert_sorted(darray, cmp_int);

	darray_destroy(darray);

	return;
}

static void test_invalid_params(void)
{
	printf("===========Warning is normal begin==============\n");
	assert(darray_length(NULL) == 0);
	assert(darray_prepend(NULL, 0) == RET_INVALID_PARAMS);
	assert(darray_append(NULL, 0) == RET_INVALID_PARAMS);
	assert(darray_delete(NULL, 0) == RET_INVALID_PARAMS);
	assert(darray_insert(NULL, 0, 0) == RET_INVALID_PARAMS);
	assert(darray_set_by_index(NULL, 0, 0) == RET_INVALID_PARAMS);
	assert(darray_get_by_index(NULL, 0, NULL) == RET_INVALID_PARAMS);
	assert(darray_find(NULL, NULL, NULL) < 0);
	assert(darray_foreach(NULL, NULL, NULL) == RET_INVALID_PARAMS);
	printf("===========Warning is normal end==============\n");

	return;
}

static void single_thread_test(void)
{
	test_int_darray();
	test_invalid_params();

	return;
}

int main(int argc, char* argv[])
{
	single_thread_test();

	return 0;
}
#endif

/* 
 * File :  test_helper.c
 */

static int cmp_int(void* ctx, void* data)
{
	return (int)ctx - (int)data;
}

static Ret print_int(void* ctx, void* data)
{
	printf("%d ", (int)data);

	return RET_OK;
}

all:
	gcc -g -m32 -DDARRAY_TEST -lpthread darray.c sort.c -o darray_test
	gcc -g -m32 -Wall -DSORT_TEST sort.c -o sort_test
	gcc -g -m32 -Wall -DSEARCH_TEST search.c -o search_test
	gcc -g -m32 -Wall -DUNIQUE_TEST unique.c darray.c sort.c -o unique_test

clean:
	rm -f *test *.exe *.so