第六章 算法和容器

6.1 容器

1) typedef.h

/*
 * 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);
typedef int       (*DataHashFunc)(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*/

2) darray

/*
 * 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 <assert.h>
#include "test_helper.c"

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_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

gcc -Wall -Wno-unused-function -g -m32 -DDARRAY_TEST darray.c -o darray_test

3) dlist

/*
 * File:    dlist.h
 */

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

#ifndef DLIST_H
#define DLIST_H

DECLS_BEGIN

struct _DList;
typedef struct _DList DList;

DList* dlist_create(DataDestroyFunc data_destroy, void* ctx);

Ret dlist_insert(DList* thiz, size_t index, void* data);
Ret dlist_prepend(DList* thiz, void* data);
Ret dlist_append(DList* thiz, void* data);
Ret dlist_delete(DList* thiz, size_t index);
Ret dlist_get_by_index(DList* thiz, size_t index, void** data);
Ret dlist_set_by_index(DList* thiz, size_t index, void* data);
size_t   dlist_length(DList* thiz);
int      dlist_find(DList* thiz, DataCompareFunc cmp, void* ctx);
Ret      dlist_foreach(DList* thiz, DataVisitFunc visit, void* ctx);

void dlist_destroy(DList* thiz);

DECLS_END

#endif/*DLIST*/

/*
 * File:    dlist.c
 */

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

typedef struct _DListNode
{
	struct _DListNode* prev;
	struct _DListNode* next;

	void* data;
}DListNode;

struct _DList
{
	DListNode* first;
	void* data_destroy_ctx;
	DataDestroyFunc data_destroy;
};

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

	return;
}

static DListNode* dlist_create_node(DList* thiz, void* data)
{
	DListNode* node = malloc(sizeof(DListNode));

	if(node != NULL) {
		node->prev = NULL;
		node->next = NULL;
		node->data = data;
	}

	return node;
}

static void dlist_destroy_node(DList* thiz, DListNode* node)
{
	if(node != NULL) {
		node->next = NULL;
		node->prev = NULL;
		dlist_destroy_data(thiz, node->data);
		SAFE_FREE(node);
	}

	return;
}

DList* dlist_create(DataDestroyFunc data_destroy, void* ctx)
{
	DList* thiz = malloc(sizeof(DList));

	if(thiz != NULL) {
		thiz->first  = NULL;
		thiz->data_destroy = data_destroy;
		thiz->data_destroy_ctx = ctx;
	}

	return thiz;
}

static DListNode* dlist_get_node(DList* thiz, size_t index, int fail_return_last)
{
	DListNode* iter = NULL;
	
	return_val_if_fail(thiz != NULL, NULL); 

	iter = thiz->first;

	while(iter != NULL && iter->next != NULL && index > 0) {
		iter = iter->next;
		index--;
	}

	if(!fail_return_last) {
		iter = index > 0 ? NULL : iter;
	}

	return iter;
}

Ret dlist_insert(DList* thiz, size_t index, void* data)
{
	Ret ret = RET_OK;
	DListNode* node = NULL;
	DListNode* cursor = NULL;

	return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS); 


	do
	{
		if((node = dlist_create_node(thiz, data)) == NULL) {
			ret = RET_OOM;
			break;
		}

		if(thiz->first == NULL) {
			thiz->first = node;
			break;
		}

		cursor = dlist_get_node(thiz, index, 1);
		
		if(index < dlist_length(thiz)) {
			node->next = cursor;
			if(cursor->prev != NULL) {
				cursor->prev->next = node;
			}
			cursor->prev = node;
			if(thiz->first == cursor) {
				thiz->first = node;
			}
		} else {
			cursor->next = node;
			node->prev = cursor;
		}
	}while(0);

	return ret;
}

Ret dlist_prepend(DList* thiz, void* data)
{
	return dlist_insert(thiz, 0, data);
}

Ret dlist_append(DList* thiz, void* data)
{
	return dlist_insert(thiz, -1, data);
}

Ret dlist_delete(DList* thiz, size_t index)
{
	Ret ret = RET_OK;
	DListNode* cursor = NULL;

	return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS); 
	
	cursor = dlist_get_node(thiz, index, 0);

	do
	{
		if(cursor == NULL) {
			ret = RET_INVALID_PARAMS;
			break;
		}

		if(cursor != NULL) {
			if(cursor == thiz->first) {
				thiz->first = cursor->next;
			}

			if(cursor->next != NULL) {
				cursor->next->prev = cursor->prev;
			}

			if(cursor->prev != NULL) {
				cursor->prev->next = cursor->next;
			}

			dlist_destroy_node(thiz, cursor);
		}

	}while(0);

	return RET_OK;
}

Ret dlist_get_by_index(DList* thiz, size_t index, void** data)
{
	DListNode* cursor = NULL;

	return_val_if_fail(thiz != NULL && data != NULL, RET_INVALID_PARAMS); 

	cursor = dlist_get_node(thiz, index, 0);

	if(cursor != NULL) {
		*data = cursor->data;
	}

	return cursor != NULL ? RET_OK : RET_INVALID_PARAMS;
}

Ret dlist_set_by_index(DList* thiz, size_t index, void* data)
{
	DListNode* cursor = NULL;

	return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS);

	
	cursor = dlist_get_node(thiz, index, 0);

	if(cursor != NULL) {
		cursor->data = data;
	}

	return cursor != NULL ? RET_OK : RET_INVALID_PARAMS;
}

size_t dlist_length(DList* thiz)
{
	size_t length = 0;
	DListNode* iter = NULL;

	return_val_if_fail(thiz != NULL, 0);

	iter = thiz->first;

	while(iter != NULL) {
		length++;
		iter = iter->next;
	}

	return length;
}

Ret dlist_foreach(DList* thiz, DataVisitFunc visit, void* ctx)
{
	Ret ret = RET_OK;
	DListNode* iter = NULL;
	
	return_val_if_fail(thiz != NULL && visit != NULL, RET_INVALID_PARAMS);

	iter = thiz->first;

	while(iter != NULL && ret != RET_STOP) {
		ret = visit(ctx, iter->data);

		iter = iter->next;
	}

	return ret;
}

int      dlist_find(DList* thiz, DataCompareFunc cmp, void* ctx)
{
	int i = 0;
	DListNode* iter = NULL;

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

	iter = thiz->first;
	while(iter != NULL) {
		if(cmp(ctx, iter->data) == 0) {
			break;
		}
		i++;
		iter = iter->next;
	}

	return i;
}

void dlist_destroy(DList* thiz)
{
	DListNode* iter = NULL;
	DListNode* next = NULL;
	
	return_if_fail(thiz != NULL);

	iter = thiz->first;
	while(iter != NULL) {
		next = iter->next;
		dlist_destroy_node(thiz, iter);
		iter = next;
	}

	thiz->first = NULL;
	
	SAFE_FREE(thiz);

	return;
}

#ifdef DLIST_TEST

#include <unistd.h>
#include <assert.h>
#include <pthread.h>
#include "test_helper.c"

static void test_int_dlist(void)
{
	int i = 0;
	int n = 100;
	int data = 0;
	DList* dlist = dlist_create(NULL, NULL);

	for(i = 0; i < n; i++) {
		assert(dlist_append(dlist, (void*)i) == RET_OK);
		assert(dlist_length(dlist) == (i + 1));
		assert(dlist_get_by_index(dlist, i, (void**)&data) == RET_OK);
		assert(data == i);
		assert(dlist_set_by_index(dlist, i, (void*)(2*i)) == RET_OK);
		assert(dlist_get_by_index(dlist, i, (void**)&data) == RET_OK);
		assert(data == 2*i);
		assert(dlist_set_by_index(dlist, i, (void*)i) == RET_OK);
		assert(dlist_find(dlist, cmp_int, (void*)i) == i);
	}

	for(i = 0; i < n; i++) {
		assert(dlist_get_by_index(dlist, 0, (void**)&data) == RET_OK);
		assert(data == (i));
		assert(dlist_length(dlist) == (n-i));
		assert(dlist_delete(dlist, 0) == RET_OK);
		assert(dlist_length(dlist) == (n-i-1));
		if((i + 1) < n)
		{
			assert(dlist_get_by_index(dlist, 0, (void**)&data) == RET_OK);
			assert((int)data == (i+1));
		}
	}
	
	assert(dlist_length(dlist) == 0);

	for(i = 0; i < n; i++) {
		assert(dlist_prepend(dlist, (void*)i) == RET_OK);
		assert(dlist_length(dlist) == (i + 1));
		assert(dlist_get_by_index(dlist, 0, (void**)&data) == RET_OK);
		assert(data == i);
		assert(dlist_set_by_index(dlist, 0, (void*)(2*i)) == RET_OK);
		assert(dlist_get_by_index(dlist, 0, (void**)&data) == RET_OK);
		assert(data == 2*i);
		assert(dlist_set_by_index(dlist, 0, (void*)i) == RET_OK);
	}

	i = n - 1;
	assert(dlist_foreach(dlist, check_and_dec_int, &i) == RET_OK);

	dlist_destroy(dlist);

	return;
}

static void test_invalid_params(void)
{
	printf("===========Warning is normal begin==============\n");
	assert(dlist_length(NULL) == 0);
	assert(dlist_prepend(NULL, 0) == RET_INVALID_PARAMS);
	assert(dlist_append(NULL, 0) == RET_INVALID_PARAMS);
	assert(dlist_delete(NULL, 0) == RET_INVALID_PARAMS);
	assert(dlist_insert(NULL, 0, 0) == RET_INVALID_PARAMS);
	assert(dlist_set_by_index(NULL, 0, 0) == RET_INVALID_PARAMS);
	assert(dlist_get_by_index(NULL, 0, NULL) == RET_INVALID_PARAMS);
	assert(dlist_find(NULL, NULL, NULL) < 0);
	assert(dlist_foreach(NULL, NULL, NULL) == RET_INVALID_PARAMS);
	printf("===========Warning is normal end==============\n");

	return;
}

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

	return;
}

#define NR 1000
int main(int argc, char* argv[])
{
	single_thread_test();

	return 0;
}
#endif

gcc -Wall -Wno-unused-function -g -m32 -DDLIST_TEST dlist.c -o dlist_test

4) linear_container_dlist

/*
 * File:    linear_container.h
 */

#ifndef LINEAR_CONTAINER_H
#define LINEAR_CONTAINER_H

#include "typedef.h"

DECLS_BEGIN

struct _LinearContainer;
typedef struct _LinearContainer LinearContainer;

typedef Ret (*LinearContainerInsert)(LinearContainer* thiz, size_t index, void* data);
typedef Ret (*LinearContainerPrepend)(LinearContainer* thiz, void* data);
typedef Ret (*LinearContainerAppend)(LinearContainer* thiz, void* data);
typedef Ret (*LinearContainerDelete)(LinearContainer* thiz, size_t index);
typedef Ret (*LinearContainerGetByIndex)(LinearContainer* thiz, size_t index, void** data);
typedef Ret (*LinearContainerSetByIndex)(LinearContainer* thiz, size_t index, void* data);
typedef size_t (*LinearContainerLength)(LinearContainer* thiz);
typedef int    (*LinearContainerFind)(LinearContainer* thiz, DataCompareFunc cmp, void* ctx);
typedef Ret    (*LinearContainerForeach)(LinearContainer* thiz, DataVisitFunc visit, void* ctx);
typedef void   (*LinearContainerDestroy)(LinearContainer* thiz);

struct _LinearContainer
{
	LinearContainerInsert     insert;
	LinearContainerPrepend    prepend;
	LinearContainerAppend     append;
	LinearContainerDelete     del;
	LinearContainerGetByIndex get_by_index;
	LinearContainerSetByIndex set_by_index;
	LinearContainerLength     length;
	LinearContainerFind       find;
	LinearContainerForeach    foreach;
	LinearContainerDestroy    destroy;

	char priv[0];
};

static inline Ret linear_container_insert(LinearContainer* thiz, size_t index, void* data)
{
	return_val_if_fail(thiz != NULL && thiz->insert != NULL, RET_INVALID_PARAMS);

	return thiz->insert(thiz, index, data);
}

static inline Ret linear_container_prepend(LinearContainer* thiz, void* data)
{
	return_val_if_fail(thiz != NULL && thiz->prepend != NULL, RET_INVALID_PARAMS);

	return thiz->prepend(thiz, data);
}

static inline Ret linear_container_append(LinearContainer* thiz, void* data)
{
	return_val_if_fail(thiz != NULL && thiz->append != NULL, RET_INVALID_PARAMS);

	return thiz->append(thiz, data);
}

static inline Ret linear_container_delete(LinearContainer* thiz, size_t index)
{
	return_val_if_fail(thiz != NULL && thiz->del != NULL, RET_INVALID_PARAMS);

	return thiz->del(thiz, index);
}

static inline Ret linear_container_get_by_index(LinearContainer* thiz, size_t index, void** data)
{
	return_val_if_fail(thiz != NULL && thiz->get_by_index != NULL, RET_INVALID_PARAMS);

	return thiz->get_by_index(thiz, index, data);
}

static inline Ret linear_container_set_by_index(LinearContainer* thiz, size_t index, void* data)
{
	return_val_if_fail(thiz != NULL && thiz->set_by_index != NULL, RET_INVALID_PARAMS);

	return thiz->set_by_index(thiz, index, data);
}

static inline size_t linear_container_length(LinearContainer* thiz)
{
	return_val_if_fail(thiz != NULL && thiz->length != NULL, 0);

	return thiz->length(thiz);
}

static inline int    linear_container_find(LinearContainer* thiz, DataCompareFunc cmp, void* ctx)
{
	return_val_if_fail(thiz != NULL && thiz->find != NULL, -1);

	return thiz->find(thiz, cmp, ctx);
}

static inline Ret    linear_container_foreach(LinearContainer* thiz, DataVisitFunc visit, void* ctx)
{
	return_val_if_fail(thiz != NULL && thiz->foreach != NULL, RET_INVALID_PARAMS);

	return thiz->foreach(thiz, visit, ctx);
}

static inline void   linear_container_destroy(LinearContainer* thiz)
{
	return_if_fail(thiz!= NULL && thiz->destroy != NULL);

	return thiz->destroy(thiz);
}

DECLS_END

#endif/*LINEAR_CONTAINER_H*/

/*
 * File:    linear_container_dlist.h
 */

#ifndef LINEAR_CONTAINER_DLIST_H
#define LINEAR_CONTAINER_DLIST_H

#include "linear_container.h"

DECLS_BEGIN

LinearContainer* linear_container_dlist_create(DataDestroyFunc data_destroy, void* ctx);

DECLS_END

#endif/*LINEAR_CONTAINER_DLIST_H*/

/*
 * File:    linear_container_dlist.c
 */

#include "dlist.h"
#include "linear_container.h"

typedef struct _PrivInfo
{
	DList* dlist;
}PrivInfo;

static Ret linear_container_dlist_insert(LinearContainer* thiz, size_t index, void* data)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	return dlist_insert(priv->dlist, index, data);
}

static Ret linear_container_dlist_prepend(LinearContainer* thiz, void* data)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	return dlist_prepend(priv->dlist, data);
}

static Ret linear_container_dlist_append(LinearContainer* thiz, void* data)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	return dlist_append(priv->dlist, data);
}

static Ret linear_container_dlist_delete(LinearContainer* thiz, size_t index)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	return dlist_delete(priv->dlist, index);
}

static Ret linear_container_dlist_get_by_index(LinearContainer* thiz, size_t index, void** data)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	return dlist_get_by_index(priv->dlist, index, data);
}

static Ret linear_container_dlist_set_by_index(LinearContainer* thiz, size_t index, void* data)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	return dlist_set_by_index(priv->dlist, index, data);
}

static size_t linear_container_dlist_length(LinearContainer* thiz)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	return dlist_length(priv->dlist);
}

static int    linear_container_dlist_find(LinearContainer* thiz, DataCompareFunc cmp, void* ctx)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	return dlist_find(priv->dlist, cmp, ctx);
}

static Ret    linear_container_dlist_foreach(LinearContainer* thiz, DataVisitFunc visit, void* ctx)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	return dlist_foreach(priv->dlist, visit, ctx);
}

static void   linear_container_dlist_destroy(LinearContainer* thiz)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	dlist_destroy(priv->dlist);
	free(thiz);

	return;
}

LinearContainer* linear_container_dlist_create(DataDestroyFunc data_destroy, void* ctx)
{
	LinearContainer* thiz = (LinearContainer*)malloc(sizeof(LinearContainer) + sizeof(PrivInfo));

	if(thiz != NULL) {
		PrivInfo* priv = (PrivInfo*)thiz->priv;
		priv->dlist = dlist_create(data_destroy, ctx);

		thiz->insert        =  linear_container_dlist_insert;
		thiz->prepend       =  linear_container_dlist_prepend;
		thiz->append        =  linear_container_dlist_append;
		thiz->del           =  linear_container_dlist_delete;
		thiz->get_by_index  =  linear_container_dlist_get_by_index;
		thiz->set_by_index  =  linear_container_dlist_set_by_index;
		thiz->length        =  linear_container_dlist_length;
		thiz->find          =  linear_container_dlist_find;
		thiz->foreach       =  linear_container_dlist_foreach;
		thiz->destroy       =  linear_container_dlist_destroy;

		if(priv->dlist == NULL) {
			free(thiz);
			thiz = NULL;
		}
	}
	
	return thiz;
}

5) queue

/*
 * File:    queue.h
 */

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

#ifndef QUEUE_H
#define QUEUE_H

DECLS_BEGIN

struct _Queue;
typedef struct _Queue Queue;

Queue* queue_create(LinearContainer* container);

Ret      queue_head(Queue* thiz, void** data);
Ret      queue_push(Queue* thiz, void* data);
Ret      queue_pop(Queue* thiz);
size_t   queue_length(Queue* thiz);
Ret      queue_foreach(Queue* thiz, DataVisitFunc visit, void* ctx);

void queue_destroy(Queue* thiz);

DECLS_END

#endif/*QUEUE_H*/

/*
 * File:    queue.c
 */

#include "queue.h"
#include "linear_container.h"

struct _Queue
{
	LinearContainer* linear_container;
};

Queue* queue_create(LinearContainer* container)
{
	Queue* thiz = NULL;
	
	return_val_if_fail(container != NULL, NULL);

	thiz = (Queue*)malloc(sizeof(Queue));

	if(thiz != NULL) {
		thiz->linear_container = container;
	}

	return thiz;
}

Ret      queue_head(Queue* thiz, void** data)
{
	return_val_if_fail(thiz != NULL && data != NULL, RET_INVALID_PARAMS);

	return linear_container_get_by_index(thiz->linear_container, 0, data);
}

Ret      queue_push(Queue* thiz, void* data)
{
	return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS);

	return linear_container_append(thiz->linear_container, data);
}

Ret      queue_pop(Queue* thiz)
{
	return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS);

	return linear_container_delete(thiz->linear_container, 0);
}

size_t   queue_length(Queue* thiz)
{
	return_val_if_fail(thiz != NULL, 0);

	return linear_container_length(thiz->linear_container);	
}

Ret      queue_foreach(Queue* thiz, DataVisitFunc visit, void* ctx)
{
	return_val_if_fail(thiz != NULL && visit != NULL, RET_INVALID_PARAMS);

	return linear_container_foreach(thiz->linear_container, visit, ctx);
}

void queue_destroy(Queue* thiz)
{
	if(thiz != NULL) {
		linear_container_destroy(thiz->linear_container);
		thiz->linear_container = NULL;

		free(thiz);
	}

	return;
}

#ifdef QUEUE_TEST
#include "test_helper.c"
#include "linear_container_dlist.h"
int main(int argc, char* argv[])
{
	int i = 0;
	int n = 1000;
	int ret_data = 0;
	Queue* queue = queue_create(linear_container_dlist_create(NULL, NULL));		

	for(i = 0; i < n; i++) {
		assert(queue_push(queue, (void*)i) == RET_OK);
		assert(queue_head(queue, (void**)&ret_data) == RET_OK);
		assert(queue_length(queue) == (i+1));
	}

	queue_foreach(queue, print_int, NULL);

	for(i = 0; i < n; i++) {
		assert(queue_head(queue, (void**)&ret_data) == RET_OK);
		assert(ret_data == i );
		assert(queue_length(queue) == (n - i));
		assert(queue_pop(queue) == RET_OK);
	}

	queue_destroy(queue);
	return 0;
}
#endif/*QUEUE_TEST*/

gcc -Wall -Wno-unused-function -g -m32 -DQUEUE_TEST dlist.c linear_container_dlist.c  queue.c -o queue_test

6) linear_container_darray

/*
 * File:    linear_container_darray.h
 */

#ifndef LINEAR_CONTAINER_DARRAY_H
#define LINEAR_CONTAINER_DARRAY_H

#include "linear_container.h"

DECLS_BEGIN

LinearContainer* linear_container_darray_create(DataDestroyFunc data_destroy, void* ctx);

DECLS_END

#endif/*LINEAR_CONTAINER_DARRAY_H*/

/*
 * File:    linear_container_darray.c
 */

#include "darray.h"
#include "linear_container.h"

typedef struct _PrivInfo
{
	DArray* darray;
}PrivInfo;

static Ret linear_container_darray_insert(LinearContainer* thiz, size_t index, void* data)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	return darray_insert(priv->darray, index, data);
}

static Ret linear_container_darray_prepend(LinearContainer* thiz, void* data)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	return darray_prepend(priv->darray, data);
}

static Ret linear_container_darray_append(LinearContainer* thiz, void* data)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	return darray_append(priv->darray, data);
}

static Ret linear_container_darray_delete(LinearContainer* thiz, size_t index)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	return darray_delete(priv->darray, index);
}

static Ret linear_container_darray_get_by_index(LinearContainer* thiz, size_t index, void** data)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	return darray_get_by_index(priv->darray, index, data);
}

static Ret linear_container_darray_set_by_index(LinearContainer* thiz, size_t index, void* data)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	return darray_set_by_index(priv->darray, index, data);
}

static size_t linear_container_darray_length(LinearContainer* thiz)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	return darray_length(priv->darray);
}

static int    linear_container_darray_find(LinearContainer* thiz, DataCompareFunc cmp, void* ctx)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	return darray_find(priv->darray, cmp, ctx);
}

static Ret    linear_container_darray_foreach(LinearContainer* thiz, DataVisitFunc visit, void* ctx)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	return darray_foreach(priv->darray, visit, ctx);
}

static void   linear_container_darray_destroy(LinearContainer* thiz)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;

	darray_destroy(priv->darray);
	free(thiz);

	return;
}

LinearContainer* linear_container_darray_create(DataDestroyFunc data_destroy, void* ctx)
{
	LinearContainer* thiz = (LinearContainer*)malloc(sizeof(LinearContainer) + sizeof(PrivInfo));

	if(thiz != NULL)
	{
		PrivInfo* priv = (PrivInfo*)thiz->priv;
		priv->darray = darray_create(data_destroy, ctx);

		thiz->insert        =  linear_container_darray_insert;
		thiz->prepend       =  linear_container_darray_prepend;
		thiz->append        =  linear_container_darray_append;
		thiz->del           =  linear_container_darray_delete;
		thiz->get_by_index  =  linear_container_darray_get_by_index;
		thiz->set_by_index  =  linear_container_darray_set_by_index;
		thiz->length        =  linear_container_darray_length;
		thiz->find          =  linear_container_darray_find;
		thiz->foreach       =  linear_container_darray_foreach;
		thiz->destroy       =  linear_container_darray_destroy;
	}
	
	return thiz;
}

/*
 * linear_container_test.c
 */

#include <assert.h>
#include "linear_container.h"
#include "test_helper.c"
#include "linear_container_dlist.h"
#include "linear_container_darray.h"

static void test_int_linear_container(LinearContainer* linear_container)
{
	int i = 0;
	int n = 100;
	int data = 0;

	for(i = 0; i < n; i++)
	{
		assert(linear_container_append(linear_container, (void*)i) == RET_OK);
		assert(linear_container_length(linear_container) == (i + 1));
		assert(linear_container_get_by_index(linear_container, i, (void**)&data) == RET_OK);
		assert(data == i);
		assert(linear_container_set_by_index(linear_container, i, (void*)(2*i)) == RET_OK);
		assert(linear_container_get_by_index(linear_container, i, (void**)&data) == RET_OK);
		assert(data == 2*i);
		assert(linear_container_set_by_index(linear_container, i, (void*)i) == RET_OK);
		assert(linear_container_find(linear_container, cmp_int, (void*)i) == i);
	}

	for(i = 0; i < n; i++)
	{
		assert(linear_container_get_by_index(linear_container, 0, (void**)&data) == RET_OK);
		assert(data == (i));
		assert(linear_container_length(linear_container) == (n-i));
		assert(linear_container_delete(linear_container, 0) == RET_OK);
		assert(linear_container_length(linear_container) == (n-i-1));
		if((i + 1) < n)
		{
			assert(linear_container_get_by_index(linear_container, 0, (void**)&data) == RET_OK);
			assert((int)data == (i+1));
		}
	}
	
	assert(linear_container_length(linear_container) == 0);

	for(i = 0; i < n; i++)
	{
		assert(linear_container_prepend(linear_container, (void*)i) == RET_OK);
		assert(linear_container_length(linear_container) == (i + 1));
		assert(linear_container_get_by_index(linear_container, 0, (void**)&data) == RET_OK);
		assert(data == i);
		assert(linear_container_set_by_index(linear_container, 0, (void*)(2*i)) == RET_OK);
		assert(linear_container_get_by_index(linear_container, 0, (void**)&data) == RET_OK);
		assert(data == 2*i);
		assert(linear_container_set_by_index(linear_container, 0, (void*)i) == RET_OK);
	}

	i = n - 1;
	assert(linear_container_foreach(linear_container, check_and_dec_int, &i) == RET_OK);

	linear_container_destroy(linear_container);

	return;
}

static void test_invalid_params(void)
{
	printf("===========Warning is normal begin==============\n");
	assert(linear_container_length(NULL) == 0);
	assert(linear_container_prepend(NULL, 0) == RET_INVALID_PARAMS);
	assert(linear_container_append(NULL, 0) == RET_INVALID_PARAMS);
	assert(linear_container_delete(NULL, 0) == RET_INVALID_PARAMS);
	assert(linear_container_insert(NULL, 0, 0) == RET_INVALID_PARAMS);
	assert(linear_container_set_by_index(NULL, 0, 0) == RET_INVALID_PARAMS);
	assert(linear_container_get_by_index(NULL, 0, NULL) == RET_INVALID_PARAMS);
	assert(linear_container_find(NULL, NULL, NULL) < 0);
	assert(linear_container_foreach(NULL, NULL, NULL) == RET_INVALID_PARAMS);
	printf("===========Warning is normal end==============\n");

	return;
}

static void single_thread_test(void)
{
	LinearContainer* linear_container = linear_container_darray_create(NULL, NULL);
	test_int_linear_container(linear_container);
	linear_container = linear_container_dlist_create(NULL, NULL);
	test_int_linear_container(linear_container);
	test_invalid_params();

	return;
}

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

	return 0;
}

all:
	# -Wno-unused-function  发现不使用的函数不警告
	#  darray_test
	gcc -Wall -Wno-unused-function -g -m32 -DDARRAY_TEST darray.c -o darray_test
	#  dlist_test
	gcc -Wall -Wno-unused-function -g -m32 -DDLIST_TEST dlist.c -o dlist_test
	#  queue_test
	gcc -Wall -Wno-unused-function -g -m32 -DQUEUE_TEST dlist.c linear_container_dlist.c  queue.c -o queue_test
	# container_test
	gcc -Wall -Wno-unused-function -g -m32 -shared darray.c  dlist.c  linear_container_darray.c linear_container_dlist.c queue.c -o libcontainer.so
	gcc -Wall -Wno-unused-function -g -m32 linear_container_test.c -L./ -lcontainer -o container_test
clean:
	rm *test *.so

6.2 迭代器

/*
 * File : invert_ng.c
 */

#include "linear_container.h"

Ret invert(LinearContainer* linear_container)
{
	int i = 0;
	int j = 0;
	void* data1 = NULL;
	void* data2 = NULL;

	return_val_if_fail(linear_container != NULL, RET_INVALID_PARAMS);

	j = linear_container_length(linear_container) - 1;
	for(; i < j; i++, j--)
	{
		linear_container_get_by_index(linear_container, i, &data1);
		linear_container_get_by_index(linear_container, j, &data2);
		linear_container_set_by_index(linear_container, i, data2);
		linear_container_set_by_index(linear_container, j, data1);
	}

	return RET_OK;
}

#ifdef INVERT_TEST
#include "test_helper.c"
#include "linear_container_dlist.h"

int main(int argc, char* argv[])
{
	int i = 0;
	int n = 101;

	LinearContainer* linear_container = linear_container_dlist_create(NULL, NULL);
	for(i = 0; i < n; i++)
	{
		linear_container_append(linear_container, (void*)i);
	}
	invert(linear_container);
	i--;
	linear_container_foreach(linear_container, check_and_dec_int, &i); 
	linear_container_destroy(linear_container);

	return 0;
}
#endif/*INVERT_TEST*/

#ifndef ITERATOR_H
#define ITERATOR_H

#include "typedef.h"

DECLS_BEGIN

struct _Iterator;
typedef struct _Iterator Iterator;

typedef Ret  (*IteratorSetFunc)(Iterator* thiz, void* data);
typedef Ret  (*IteratorGetFunc)(Iterator* thiz, void** data);
typedef Ret  (*IteratorNextFunc)(Iterator* thiz);
typedef Ret  (*IteratorPrevFunc)(Iterator* thiz);
typedef Ret  (*IteratorAdvanceFunc)(Iterator* thiz, int offset);
typedef int  (*IteratorOffsetFunc)(Iterator* thiz);
typedef Ret  (*IteratorCloneFunc)(Iterator* thiz, Iterator** cloned);
typedef void (*IteratorDestroyFunc)(Iterator* thiz);

struct _Iterator
{
	IteratorSetFunc     set;
	IteratorGetFunc     get;
	IteratorNextFunc    next;
	IteratorPrevFunc    prev;
	IteratorAdvanceFunc advance;
	IteratorCloneFunc   clone;
	IteratorOffsetFunc  offset;
	IteratorDestroyFunc destroy;

	char priv[0];
};

static inline Ret  iterator_set(Iterator* thiz, void* data)
{
	return_val_if_fail(thiz != NULL && thiz->set != NULL, RET_INVALID_PARAMS);

	return thiz->set(thiz, data);
}

static inline Ret  iterator_get(Iterator* thiz, void** data)
{
	return_val_if_fail(thiz != NULL && thiz->get != NULL, RET_INVALID_PARAMS);

	return thiz->get(thiz, data);
}

static inline Ret  iterator_next(Iterator* thiz)
{
	return_val_if_fail(thiz != NULL && thiz->next != NULL, RET_INVALID_PARAMS);

	return thiz->next(thiz);
}

static inline Ret  iterator_prev(Iterator* thiz)
{
	return_val_if_fail(thiz != NULL && thiz->prev != NULL, RET_INVALID_PARAMS);

	return thiz->prev(thiz);
}

static inline Ret  iterator_advance(Iterator* thiz, int offset)
{
	return_val_if_fail(thiz != NULL && thiz->advance != NULL, RET_INVALID_PARAMS);

	return thiz->advance(thiz, offset);
}

static inline int  iterator_offset(Iterator* thiz)
{
	return_val_if_fail(thiz != NULL && thiz->offset != NULL, -1);

	return thiz->offset(thiz);
}

static inline Ret  iterator_clone(Iterator* thiz, Iterator** cloned)
{
	return_val_if_fail(thiz != NULL && thiz->clone != NULL, RET_INVALID_PARAMS);

	return thiz->clone(thiz, cloned);
}

static inline void iterator_destroy(Iterator* thiz)
{
	return_if_fail(thiz != NULL && thiz->destroy != NULL);

	return thiz->destroy(thiz);
}

DECLS_END

#endif/*ITERATOR_H*/

/*
 * File : dlist_iterator.h
 */

#ifndef DLIST_ITERATOR_H
#define DLIST_ITERATOR_H

#include "dlist.h"
#include "iterator.h"

DECLS_BEGIN

Iterator* dlist_iterator_create(DList* dlist);

DECLS_END

#endif/*DLIST_ITERATOR_H*/

/*
 * File : dlist_iterator.c
 */

#include <string.h>
#include "dlist_iterator.h"

typedef struct _PrivInfo
{
	DList* dlist;
	DListNode* cursor;
	int offset;
}PrivInfo;

static Ret  dlist_iterator_set(Iterator* thiz, void* data)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;
	return_val_if_fail(priv->cursor != NULL && priv->dlist != NULL, RET_INVALID_PARAMS);

	priv->cursor->data = data;

	return RET_OK;
}

static Ret  dlist_iterator_get(Iterator* thiz, void** data)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;
	return_val_if_fail(priv->cursor != NULL && priv->dlist != NULL && data != NULL, RET_INVALID_PARAMS);

	*data = priv->cursor->data;

	return RET_OK;
}

static Ret  dlist_iterator_next(Iterator* thiz)
{
	Ret ret = RET_FAIL;
	PrivInfo* priv = (PrivInfo*)thiz->priv;
	return_val_if_fail(priv->cursor != NULL && priv->dlist != NULL, RET_INVALID_PARAMS);

	if(priv->cursor->next != NULL)
	{
		priv->cursor = priv->cursor->next;
		priv->offset++;

		ret = RET_OK;
	}

	return ret;
}

static Ret  dlist_iterator_prev(Iterator* thiz)
{
	Ret ret = RET_FAIL;
	PrivInfo* priv = (PrivInfo*)thiz->priv;
	return_val_if_fail(priv->cursor != NULL && priv->dlist != NULL, RET_INVALID_PARAMS);

	if(priv->cursor->prev != NULL)
	{
		priv->cursor = priv->cursor->prev;
		priv->offset--;

		ret = RET_OK;
	}

	return RET_OK;
}

static Ret  dlist_iterator_advance(Iterator* thiz, int offset)
{
	int n   = offset;
	Ret ret = RET_FAIL;
	DListNode* iter = NULL;
	PrivInfo*  priv = (PrivInfo*)thiz->priv;
	return_val_if_fail(priv->cursor != NULL && priv->dlist != NULL, RET_INVALID_PARAMS);

	iter = priv->cursor;
	if(offset > 0)
	{
		for(n = offset; n > 0 && iter != NULL; n--)
		{
			iter = iter->next;
		}
	}
	else
	{
		for(n = -offset; n > 0 && iter != NULL; n--)
		{
			iter = iter->prev;
		}
	}

	if(iter != NULL)
	{
		priv->cursor = iter;
		priv->offset += offset;

		ret = RET_OK;
	}

	return ret;
}

static int  dlist_iterator_offset(Iterator* thiz)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;
	return_val_if_fail(priv->cursor != NULL && priv->dlist != NULL, RET_INVALID_PARAMS);

	return priv->offset;
}

static Ret  dlist_iterator_clone(Iterator* thiz, Iterator** cloned)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;
	return_val_if_fail(priv->cursor != NULL && priv->dlist != NULL, RET_INVALID_PARAMS);

	*cloned = (Iterator*)malloc(sizeof(Iterator) + sizeof(PrivInfo));
	if(*cloned != NULL)
	{
		memcpy(*cloned, thiz, sizeof(Iterator) + sizeof(PrivInfo));
	}

	return *cloned != NULL ? RET_OK : RET_FAIL;
}

static void dlist_iterator_destroy(Iterator* thiz)
{
	if(thiz != NULL)
	{
		free(thiz);
	}

	return;
}

Iterator* dlist_iterator_create(DList* dlist)
{
	Iterator* thiz = NULL;
	return_val_if_fail(dlist != NULL, NULL);

	if((thiz = malloc(sizeof(Iterator) + sizeof(PrivInfo))) != NULL)
	{
		PrivInfo* priv = (PrivInfo*)thiz->priv;

		thiz->set      =  dlist_iterator_set;
		thiz->get      =  dlist_iterator_get;
		thiz->next     =  dlist_iterator_next;
		thiz->prev     =  dlist_iterator_prev;
		thiz->advance  =  dlist_iterator_advance;
		thiz->clone    =  dlist_iterator_clone;
		thiz->offset   =  dlist_iterator_offset;
		thiz->destroy  =  dlist_iterator_destroy;

		priv->dlist  = dlist;
		priv->cursor = dlist->first;
		priv->offset = 0;
	}

	return thiz;
}

/*
 * File : darray_iterator.h
 */

#ifndef DARRAY_ITERATOR_H
#define DARRAY_ITERATOR_H

#include "darray.h"
#include "iterator.h"

DECLS_BEGIN

Iterator* darray_iterator_create(DArray* darray);

DECLS_END

#endif/*DARRAY_ITERATOR_H*/

/*
 * File : darray_iterator.c
 */

#include <string.h>
#include "darray_iterator.h"

typedef struct _PrivInfo
{
	DArray* darray;
	int offset;
}PrivInfo;

static Ret  darray_iterator_set(Iterator* thiz, void* data)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;
	return_val_if_fail(priv->darray != NULL, RET_INVALID_PARAMS);

	return darray_set_by_index(priv->darray, priv->offset, data);
}

static Ret  darray_iterator_get(Iterator* thiz, void** data)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;
	return_val_if_fail(priv->darray != NULL && data != NULL, RET_INVALID_PARAMS);

	return darray_get_by_index(priv->darray, priv->offset, data);
}

static Ret  darray_iterator_next(Iterator* thiz)
{
	Ret ret = RET_FAIL;
	PrivInfo* priv = (PrivInfo*)thiz->priv;
	return_val_if_fail(priv->darray != NULL, RET_INVALID_PARAMS);

	if((priv->offset + 1) < priv->darray->size)
	{
		priv->offset++;
		ret = RET_OK;
	}

	return ret;
}

static Ret  darray_iterator_prev(Iterator* thiz)
{
	Ret ret = RET_FAIL;
	PrivInfo* priv = (PrivInfo*)thiz->priv;
	return_val_if_fail(priv->darray != NULL, RET_INVALID_PARAMS);

	if(priv->offset > 0)
	{
		priv->offset--;

		ret = RET_OK;
	}

	return RET_OK;
}

static Ret  darray_iterator_advance(Iterator* thiz, int offset)
{
	int new_offset = 0;
	Ret ret = RET_FAIL;
	PrivInfo*  priv = (PrivInfo*)thiz->priv;
	return_val_if_fail(priv->darray != NULL, RET_INVALID_PARAMS);

	new_offset = priv->offset + offset;
	if(new_offset >= 0 && new_offset < priv->darray->size)
	{
		priv->offset = new_offset;
	}

	return ret;
}

static int  darray_iterator_offset(Iterator* thiz)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;
	return_val_if_fail(priv->darray != NULL, RET_INVALID_PARAMS);

	return priv->offset;
}

static Ret  darray_iterator_clone(Iterator* thiz, Iterator** cloned)
{
	PrivInfo* priv = (PrivInfo*)thiz->priv;
	return_val_if_fail(priv->darray != NULL, RET_INVALID_PARAMS);

	*cloned = (Iterator*)malloc(sizeof(Iterator) + sizeof(PrivInfo));
	if(*cloned != NULL)
	{
		memcpy(*cloned, thiz, sizeof(Iterator) + sizeof(PrivInfo));
	}

	return *cloned != NULL ? RET_OK : RET_FAIL;
}

static void darray_iterator_destroy(Iterator* thiz)
{
	if(thiz != NULL)
	{
		free(thiz);
	}

	return;
}

Iterator* darray_iterator_create(DArray* darray)
{
	Iterator* thiz = NULL;
	return_val_if_fail(darray != NULL, NULL);

	if((thiz = malloc(sizeof(Iterator) + sizeof(PrivInfo))) != NULL)
	{
		PrivInfo* priv = (PrivInfo*)thiz->priv;

		thiz->set      =  darray_iterator_set;
		thiz->get      =  darray_iterator_get;
		thiz->next     =  darray_iterator_next;
		thiz->prev     =  darray_iterator_prev;
		thiz->advance  =  darray_iterator_advance;
		thiz->clone    =  darray_iterator_clone;
		thiz->offset   =  darray_iterator_offset;
		thiz->destroy  =  darray_iterator_destroy;

		priv->darray  = darray;
		priv->offset = 0;
	}

	return thiz;
}

/*
 * File : invert.c
 */

#include "iterator.h"

Ret invert(Iterator* forward, Iterator* backward)
{
	void* data1 = NULL;
	void* data2 = NULL;
	return_val_if_fail(forward != NULL && backward != NULL, RET_INVALID_PARAMS);

	for(; iterator_offset(forward) < iterator_offset(backward); iterator_next(forward), iterator_prev(backward))
	{
		iterator_get(forward, &data1);
		iterator_get(backward, &data2);
		iterator_set(forward, data2);
		iterator_set(backward, data1);
	}

	return RET_OK;
}

#ifdef INVERT_TEST
#include "dlist.h"
#include "dlist_iterator.h"
#include "test_helper.c"

int main(int argc, char* argv[])
{
	int i = 0;
	int n = 101;
	int last = n - 1;
	DList* dlist = dlist_create(NULL, NULL);

	for(i = 0; i < n; i++)
	{
		dlist_append(dlist, (void*)i);
	}

	Iterator* forward = dlist_iterator_create(dlist);
	Iterator* backward = dlist_iterator_create(dlist);

	iterator_advance(backward, last);
	invert(forward, backward);
	dlist_foreach(dlist, check_and_dec_int, &last);
	iterator_destroy(forward);
	iterator_destroy(backward);
	dlist_destroy(dlist);

	return 0;
}
#endif/*INVERT_TEST*/

all:
	gcc -Wall -m32 -g -DDARRAY_TEST darray.c -o darray_test
	gcc -Wall -m32 -g -DDLIST_TEST dlist.c -o dlist_test
	gcc -Wall -m32 -g -shared darray.c  dlist.c  linear_container_darray.c linear_container_dlist.c -o libcontainer.so
	gcc -Wall -m32 -g linear_container_test.c -L./ -lcontainer -o container_test
	gcc -Wall -m32 -g invert_ng.c -DINVERT_TEST -L./ -lcontainer -o invert_ng_test
	gcc -Wall -m32 -g invert.c -DINVERT_TEST -L./ -lcontainer -o invert_test
clean:
	rm *test *.so

6.3 动态绑定

/*
 * File : call_cos.c
 */

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

int main(int argc, char **argv)
{
	void *handle = NULL;
	double (*cosine)(double) = NULL;
	/*加载共享库*/
	handle = dlopen("libm.so", RTLD_LAZY);
	/*通过函数名找到函数指针*/
	*(void **) (&cosine) = dlsym(handle, "cos");
	/*调用函数*/
	printf("%f\n", (*cosine)(2.0));
	/*卸载共享库*/
	dlclose(handle);

	return 0;
}

/*
 * File:    module.h
 */

#ifndef MODULE_H
#define MODULE_H
#include "typedef.h"

DECLS_BEGIN

struct _Module;
typedef struct _Module Module;

typedef enum _ModuleFlags
{
	MODULE_FLAGS_NONE,
	MODULE_FLAGS_DELAY = 1
}ModuleFlags;

Module* module_create(const char* file_name, ModuleFlags flags);
void*   module_sym(Module* thiz, const char* func_name);
void    module_destroy(Module* thiz);

DECLS_END

#endif/*MODULE_H*/

/*
 * File:    module_linux.h
 */

#include <dlfcn.h>
#include "module.h"

struct _Module
{
	void* handle;
};

Module* module_create(const char* file_name, ModuleFlags flags)
{
	Module* thiz = NULL;
	return_val_if_fail(file_name != NULL, NULL);
	
	if((thiz = malloc(sizeof(Module))) != NULL)
	{
		thiz->handle = dlopen(file_name, flags & MODULE_FLAGS_DELAY ? RTLD_LAZY : RTLD_NOW);
		if(thiz->handle == NULL)
		{
			free(thiz);
			thiz = NULL;
			printf("%s\n", dlerror());
		}
	}

	return thiz;
}

void*   module_sym(Module* thiz, const char* func_name)
{
	return_val_if_fail(thiz != NULL && thiz->handle != NULL && func_name != NULL, NULL);

	dlerror();
	return dlsym(thiz->handle, func_name);
}

void    module_destroy(Module* thiz)
{
	if(thiz != NULL)
	{
		if(thiz->handle != NULL)
		{
			dlclose(thiz->handle);
		}
		
		free(thiz);
	}
	
	return;
}

/*
 * File : module_test.c
 */

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

int main(int argc, char* argv[])
{
	if(argc != 3) {
		printf("%s module function\n", argv[0]);

		return 0;
	}

	Module* module = module_create(argv[1], 0);
	if(module != NULL) {
		void* func = module_sym(module, argv[2]);
		printf("func=%p\n", func);
		module_destroy(module);
	} else {
		printf("load %s failed\n", argv[1]);
	}

	return 0;
}

all:
	gcc -Wall -m32 -g -DDARRAY_TEST darray.c -o darray_test
	gcc -Wall -m32 -g -DDLIST_TEST dlist.c -o dlist_test
	gcc -Wall -m32 -g -shared darray.c  dlist.c  linear_container_darray.c linear_container_dlist.c queue.c -o libcontainer.so
	gcc -Wall -m32 -g linear_container_test.c -L./ -lcontainer -o container_test
	gcc -Wall -m32 -g queue.c linear_container_dlist.c dlist.c -DQUEUE_TEST -o queue_test
	gcc -Wall -m32 -g module_linux.c module_test.c -ldl -o module_test
	gcc -Wall -m32 -g module_linux.c queue.c queue_test.c -ldl -o queue_dynamic_test
	gcc -m32 -g call_cos.c -ldl -o call_cos

clean:
	rm *test *.so call_cos