第一章 从双向链表学习设计

1.3 Wirte once, run anywhere (WORA)

• 让C++可以调用

# ifdef __cplusplus
extern "C" {
#endif

//.....

# ifdef __cplusplus
}
#endif

1.4 拥抱变化

/*
 * File:    dlist.h
 */

#ifndef DLIST_H
#define DLIST_H

#ifdef __cplusplus
extern "C" {
#endif/*__cplusplus*/

typedef enum _DListRet
{
	DLIST_RET_OK,
	DLIST_RET_OOM,
	DLIST_RET_STOP,
	DLIST_RET_PARAMS,
	DLIST_RET_FAIL
}DListRet;

struct _DList;
typedef struct _DList DList;

typedef DListRet (*DListDataPrintFunc)(void* data);

DList* dlist_create(void);

DListRet dlist_insert(DList* thiz, size_t index, void* data);
DListRet dlist_prepend(DList* thiz, void* data);
DListRet dlist_append(DList* thiz, void* data);
DListRet dlist_delete(DList* thiz, size_t index);
DListRet dlist_get_by_index(DList* thiz, size_t index, void** data);
DListRet dlist_set_by_index(DList* thiz, size_t index, void* data);
size_t   dlist_length(DList* thiz);
DListRet dlist_print(DList* thiz, DListDataPrintFunc print);

void dlist_destroy(DList* thiz);

#ifdef __cplusplus
}
#endif/*__cplusplus*/

#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;
};

static DListNode* dlist_node_create(void* data)
{
	DListNode* node = malloc(sizeof(DListNode));

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

	return node;
}

static void dlist_node_destroy(DListNode* node)
{
	if(node != NULL) {
		node->next = NULL;
		node->prev = NULL;
		free(node);
	}
	return;
}

DList* dlist_create(void)
{
	DList* thiz = malloc(sizeof(DList));

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

	return thiz;
}

static DListNode* dlist_get_node(DList* thiz, size_t index, int fail_return_last)
{
	DListNode* 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;
}

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

	if((node = dlist_node_create(data)) == NULL) {
		return DLIST_RET_OOM; 
	}

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

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

	return DLIST_RET_OK;
}

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

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

DListRet dlist_delete(DList* thiz, size_t index)
{
	DListNode* cursor = dlist_get_node(thiz, index, 0);

	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_node_destroy(cursor);
	}

	return DLIST_RET_OK;
}

DListRet dlist_get_by_index(DList* thiz, size_t index, void** data)
{
	DListNode* cursor = dlist_get_node(thiz, index, 0);

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

	return cursor != NULL ? DLIST_RET_OK : DLIST_RET_FAIL;
}

DListRet dlist_set_by_index(DList* thiz, size_t index, void* data)
{
	DListNode* cursor = dlist_get_node(thiz, index, 0);

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

	return cursor != NULL ? DLIST_RET_OK : DLIST_RET_FAIL;
}

size_t   dlist_length(DList* thiz)
{
	size_t length = 0;
	DListNode* iter = thiz->first;

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

	return length;
}

DListRet dlist_print(DList* thiz, DListDataPrintFunc print)
{
	DListRet ret = DLIST_RET_OK;
	DListNode* iter = thiz->first;

	while(iter != NULL){
		print(iter->data);
		iter = iter->next;
	}

	return ret;
}

void dlist_destroy(DList* thiz)
{
	DListNode* iter = thiz->first;
	DListNode* next = NULL;

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

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

	return;
}

/*
* 1.4 拥抱拜变化 
*/

/* 
 * File:    dlist.c
 */

#include <stdio.h>
#include <assert.h>
#include "dlist.h"

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

	return DLIST_RET_OK;
}

int main(int argc, char* argv[])
{
	int i = 0;
	int n = 100;
	DList* dlist = dlist_create();

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

	dlist_print(dlist, print_int);
	printf("\n");

	dlist_destroy(dlist);

	return 0;
}

all:
	gcc -g -m32 dlist.c main.c -o demo
clean:
	rm -f demo

1.5 Don't Repeat Yourself(DRY)

需求描述

• 对一个存放整数的的双向链表，找出链表中的最大值.
• 对一个存放整数的的双向链表，累加链表中的所有整数.

/*
 * File:    dlist.h
 */


#ifndef DLIST_H
#define DLIST_H

#ifdef __cplusplus
extern "C" {
#endif/*__cplusplus*/

typedef enum _DListRet
{
	DLIST_RET_OK,
	DLIST_RET_OOM,
	DLIST_RET_STOP,
	DLIST_RET_PARAMS,
	DLIST_RET_FAIL
}DListRet;

struct _DList;
typedef struct _DList DList;

typedef int (*DListDataCompareFunc)(void* ctx, void* data);
typedef DListRet (*DListDataVisitFunc)(void* ctx, void* data);

DList* dlist_create(void);

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

void dlist_destroy(DList* thiz);

#ifdef __cplusplus
}
#endif/*__cplusplus*/

#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;
};

static DListNode* dlist_node_create(void* data)
{
	DListNode* node = malloc(sizeof(DListNode));

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

	return node;
}

static void dlist_node_destroy(DListNode* node)
{
	if(node != NULL) {
		node->next = NULL;
		node->prev = NULL;
		free(node);
	}

	return;
}

DList* dlist_create(void)
{
	DList* thiz = malloc(sizeof(DList));

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

	return thiz;
}

static DListNode* dlist_get_node(DList* thiz, size_t index, int fail_return_last)
{
	DListNode* 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;
}

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

	if((node = dlist_node_create(data)) == NULL){
		return DLIST_RET_OOM; 
	}

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

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

	return DLIST_RET_OK;
}

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

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

DListRet dlist_delete(DList* thiz, size_t index)
{
	DListNode* cursor = dlist_get_node(thiz, index, 0);

	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_node_destroy(cursor);
	}

	return DLIST_RET_OK;
}

DListRet dlist_get_by_index(DList* thiz, size_t index, void** data)
{
	DListNode* cursor = dlist_get_node(thiz, index, 0);

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

	return cursor != NULL ? DLIST_RET_OK : DLIST_RET_FAIL;
}

DListRet dlist_set_by_index(DList* thiz, size_t index, void* data)
{
	DListNode* cursor = dlist_get_node(thiz, index, 0);

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

	return cursor != NULL ? DLIST_RET_OK : DLIST_RET_FAIL;
}

size_t   dlist_length(DList* thiz)
{
	size_t length = 0;
	DListNode* iter = thiz->first;

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

	return length;
}

DListRet dlist_foreach(DList* thiz, DListDataVisitFunc visit, void* ctx)
{
	DListRet ret = DLIST_RET_OK;
	DListNode* iter = thiz->first;

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

	return ret;
}

int   dlist_find(DList* thiz, DListDataCompareFunc cmp, void* ctx)
{
	int i = 0;
	DListNode* 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 = thiz->first;
	DListNode* next = NULL;

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

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

	return;
}

/*
 * File:    main.c
 */

#include <stdio.h>
#include "dlist.h"
#include <assert.h>

static DListRet sum_cb(void* ctx, void* data)
{
	long long* result = ctx;
	*result += (int)data;

	return DLIST_RET_OK;
}

typedef struct _MaxCtx
{
	int is_first;
	int max;
}MaxCtx;

static DListRet max_cb(void* ctx, void* data)
{
	MaxCtx* max_ctx = ctx;
	if(max_ctx->is_first) {
		max_ctx->is_first = 0;
		max_ctx->max = (int)data;
	}else if(max_ctx->max < (int)data){
		max_ctx->max = (int)data;
	}

	return DLIST_RET_OK;
}

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

	return DLIST_RET_OK;
}

int main(int argc, char* argv[])
{
	int i = 0;
	int n = 100;
	long long sum = 0;
	MaxCtx max_ctx = {.is_first = 1, 0};
	DList* dlist = dlist_create();

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

	dlist_foreach(dlist, print_int, NULL);
	dlist_foreach(dlist, max_cb, &max_ctx);
	dlist_foreach(dlist, sum_cb, &sum);

	printf("\nsum=%lld max=%d\n", sum, max_ctx.max);
	dlist_destroy(dlist);

	return 0;
}

all:
	gcc -g -m32 dlist.c main.c -o demo

clean:
	rm -f demo

1.6 你的数据放在哪里

需求描述

对一个存放字符串的双向链表,把存放在其中的字符串转换成大写字母.

---

/*
 * File: dlist_toupper.c
 */

#include "dlist.h"
#include <string.h>
#include <stdio.h>
#include <ctype.h>

static DListRet str_toupper(void* ctx, void* data)
{
	char* p = (char*)data;
	if(p != NULL){
		while(*p != '\0'){
			if(islower((*p))){
				*p = toupper(*p);
			}
			p++;
		}
	}

	return DLIST_RET_OK;
}

static DListRet str_print(void* ctx, void* data)
{
	printf("%s\n", (char *)data);
	
	return DLIST_RET_OK;
}

/* 双向链表中存放常量字符串，转换时出现段错误*/
static void demo_const(void)
{
	DList* dlist = dlist_create(NULL, NULL);
	dlist_append(dlist, "It");
	dlist_append(dlist, "is");
	dlist_append(dlist, "OK");
	dlist_append(dlist, "!");
	dlist_foreach(dlist, str_toupper, NULL);
	dlist_destroy(dlist);

	return ;
}

/* 双向链表中存放的是临时变量，转换后发现所有字符串都一样*/
static void demo_temp(void)
{
	char str[256] = {0};
	DList* dlist = dlist_create(NULL, NULL);
	strcpy(str, "It");
	dlist_append(dlist, str);
	strcpy(str, "is");
	dlist_append(dlist, str);
	strcpy(str, "OK");
	dlist_append(dlist, str);
	strcpy(str, "!");
	dlist_append(dlist, str);
	dlist_foreach(dlist, str_toupper, NULL);
	dlist_foreach(dlist, str_print, NULL);
	dlist_destroy(dlist);

	return ;
}

static void data_free(void* ctx, void* data)
{
	free(data);

	return;
}

/*存放时，复制了数据，但没有释放所分配的内存*/
static void demo_heap(void)
{
	DList* dlist = dlist_create(data_free, NULL);
	dlist_append(dlist, strdup("It"));
	dlist_append(dlist, strdup("is"));
	dlist_append(dlist, strdup("OK"));
	dlist_append(dlist, strdup("!"));
	dlist_foreach(dlist, str_toupper, NULL);
	dlist_foreach(dlist, str_print, NULL);
	dlist_destroy(dlist);

	return ;
}

int main(int argc, char* argv[])
{
	demo_temp();
	demo_heap();
	demo_const();

	return 0;
}

/* 
 * bss.c 
 * */

/* 未初始化的全局变量(.bss段) */
int bss_array[1024 * 1024];

int main(int argc, char* argv[])
{
	return 0;
}

/*
 * data.c
 */

/* 初始化过的全局变量(.data段) */
int data_array[1024 * 1024] = {1};

int main(int argc, char* argv[])
{
	return 0;
}

/*
 * File: heap_error.c
 */
 
#include <stdlib.h>
#include <string.h>

/*# valgrind --tool=memcheck --leak-check=full ./heap_error */

int main(int argc, char* argv[])
{
	/*memory leak and buffer overflow.*/
	char* str = malloc(10);
	strcpy(str, "123456788900");

	return 0;
}

ARCH=-m32
all:
	gcc -g ${ARCH} toupper.c -o toupper_test
	gcc -g ${ARCH} dlist.c dlist_toupper.c -o dlist_toupper_test
	gcc -g ${ARCH} bss.c -o bss.exe
	gcc -g ${ARCH} data.c -o data.exe
	gcc -g ${ARCH} heap_error.c -o heap_error_test
clean:
	rm -f *test *.exe