listライブラリ

Cでstlのリストっぽいことをやってみた。
Nextと対照的にprevを実装すべきだが、とりあえずってことで。
今のところ格納しているのはintに決め打ちだがvoid *で持てば、汎用的に保持できる。
しかし、デストラクタがめんどい。

list.h

#ifndef LIST_H__
#define LIST_H__

/* Listコンテナライブラリ */

/* List構造体宣言 */
/* 実装詳細を隠蔽するため名前のみ公開 */
/* とりあえず格納するのはint */
typedef struct List List;

/* Listコンストラクタ */
List *ListCreate(void);

/* Listデストラクタ */
void ListDispose(List *pList);

/* Listダンプ */
void ListDump(List *pList);


/* ListIterator構造体宣言 */
/* 実装詳細を隠蔽するため名前のみ公開 */
typedef struct ListIterator ListIterator;

/* ListIteratorコンストラクタ */
ListIterator *ListIteratorCreate(List *pList);

/* ListIteratorデストラクタ */
void ListIteratorDispose(ListIterator *pIte);

/* Next可能か？ */
/* Next可能なら1, 不可なら0を返す */
int ListIteratorHasNext(ListIterator *pIte);

/* Nextしてオブジェクト(int)を返す */
int ListIteratorNext(ListIterator *pIte);

/* pIteの次にdataを格納したノードを追加する。 */
void ListIteratorInsertNext(ListIterator *pIte, int data);

/* pIteが指しているノードを切り離し、格納していた値を返す。 */
/* ノードは開放される。pIteがは元のノードのprevを指すようになる。 */
int ListIteratorErase(ListIterator *pIte);

#endif	/* LIST_H__ */

list.c

#include <stdio.h>
#include <stdlib.h>
#include "list.h"


/* Listコンテナライブラリ */

/* Node構造体 */
/* 非公開構造体 */
typedef struct M_Node {
	struct M_Node *pPrev;
	struct M_Node *pNext;
	int data;
} M_Node;

/* List構造体宣言 */
/* とりあえず格納するのはint */
struct List {
	M_Node dummyNode;	/* リストの先頭、最後尾を指すダミーノード */
};

/* Listコンストラクタ */
List *ListCreate(void)
{
	List *p = malloc(sizeof(List));
	
	if (p) {
		/* ダミーノードなので牛の死体を置いておく*/
		p->dummyNode.data = 0xdeadbeef;
		
		/* ダミーノードを始点終点として循環させる。 */
		p->dummyNode.pPrev = &p->dummyNode;
		p->dummyNode.pNext = &p->dummyNode;
	}
	
	return p;
}

/* Listデストラクタ */
void ListDispose(List *pList)
{
	M_Node *pTmp, *pDelete;
	
	/* 引数チェック */
	if (pList == NULL) {
		return;
	}
	
	/* リストの各ノードを開放 */
	pTmp = pList->dummyNode.pNext;
	while (pTmp != &pList->dummyNode) {
		/* 切り離すノードを保持 */
		pDelete = pTmp;
		
		/* ノードをすすめる */
		pTmp = pTmp->pNext;
		
		/* ノードを切り離す */
		pDelete->pNext = pDelete->pPrev = NULL;
		
		/* ノード開放 */
		free(pDelete);
	}
	
	/* リストを開放 */
	free(pList);
}

/* Listダンプ */
void ListDump(List *pList)
{
	int i = 0;
	/* イテレータ生成 */
	ListIterator *pIte = ListIteratorCreate(pList);
	
	printf("==== Dump List ====\n");
	
	if (pIte) {
		while (ListIteratorHasNext(pIte)) {
			printf("%d: %d\n", ++i, ListIteratorNext(pIte));
		}
	}
	
	/* イテレータ開放 */
	ListIteratorDispose(pIte);
}


/* ListIterator構造体宣言 */
/* 実装詳細を隠蔽するため名前のみ公開 */
struct ListIterator {
	List *pList;		/* リストを保持 */
	M_Node *pNode;		/* 現時点のノードを保持 */
};

/* ListIteratorコンストラクタ */
ListIterator *ListIteratorCreate(List *pList)
{
	ListIterator *pIte = malloc(sizeof(ListIterator));
	
	/* 引数チェック */
	if (pList == NULL) {
		return NULL;
	}
	
	if (pIte) {
		pIte->pList = pList;
		pIte->pNode = &pList->dummyNode;
	}
	
	return pIte;
}

/* ListIteratorデストラクタ */
void ListIteratorDispose(ListIterator *pIte)
{
	free(pIte);
}

/* Next可能か？ */
/* Next可能なら1, 不可なら0を返す */
int ListIteratorHasNext(ListIterator *pIte)
{
	if (pIte == NULL) {
		return 0;
	}
	
	if (pIte->pNode->pNext != &pIte->pList->dummyNode) {
		return 1;
	} else {
		return 0;
	}
}

/* Nextしてオブジェクト(int)を返す */
int ListIteratorNext(ListIterator *pIte)
{
	pIte->pNode = pIte->pNode->pNext;
	
	return pIte->pNode->data;
}


/* pIteの次にdataを格納したノードを追加する。 */
void ListIteratorInsertNext(ListIterator *pIte, int data)
{
	M_Node *pNewNode = malloc(sizeof(M_Node));
	
	if (pNewNode) {
		pNewNode->data = data;
		
		/* ノードをつなぐ */
		pNewNode->pPrev = pIte->pNode;
		pNewNode->pNext = pIte->pNode->pNext;
		
		pIte->pNode->pNext = pNewNode;
		pNewNode->pNext->pPrev = pNewNode;
	}
}


/* pIteが指しているノードを切り離し、格納していた値を返す。 */
/* ノードは開放される。pIteがは元のノードのprevを指すようになる。 */
/* 切り離しに失敗したら0が返る */
int ListIteratorErase(ListIterator *pIte)
{
	M_Node *pPrev, *pNext;
	int rtn;
	
	if (pIte == NULL) {
		return 0;
	}
	
	if (pIte->pNode == &pIte->pList->dummyNode) {
		/* ダミーノードは切り離せない */
		return 0;
	}
	
	pPrev = pIte->pNode->pPrev;
	pNext = pIte->pNode->pNext;
	
	/* 前と後ろをつなげる */
	pPrev->pNext = pNext;
	pNext->pPrev = pPrev;
	
	rtn = pIte->pNode->data;
	
	/* Node開放 */
	free(pIte->pNode);
	
	/* イテレータはひとつ前を指す */
	pIte->pNode = pPrev;
	
	return rtn;
}

main.c

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

int main(void)
{
	List *pList;
	ListIterator *pIte;
	
	pList = ListCreate();
	pIte = ListIteratorCreate(pList);
	
	/* リストに挿入 */
	ListIteratorInsertNext(pIte, 0);
	ListIteratorInsertNext(pIte, 1);
	ListIteratorInsertNext(pIte, 2);
	ListIteratorInsertNext(pIte, 3);
	ListIteratorInsertNext(pIte, 4);
	ListIteratorInsertNext(pIte, 5);

	/* リストダンプ */
	ListDump(pList);

	/* 2つすすめる */
	ListIteratorNext(pIte);
	ListIteratorNext(pIte);
	
	/* リストに挿入 */
	ListIteratorInsertNext(pIte, 10);
	ListIteratorInsertNext(pIte, 11);
	ListIteratorInsertNext(pIte, 12);
	
	/* リストダンプ */
	ListDump(pList);

	/* 5つすすめる */
	ListIteratorNext(pIte);
	ListIteratorNext(pIte);
	ListIteratorNext(pIte);
	ListIteratorNext(pIte);
	ListIteratorNext(pIte);
	
	/* 3つリストから削除 */
	ListIteratorErase(pIte);
	ListIteratorErase(pIte);
	ListIteratorErase(pIte);
	
	/* リストダンプ */
	ListDump(pList);

	/* イテレータ開放 */
	ListIteratorDispose(pIte);
	/* リスト開放 */
	ListDispose(pList);
	
	return 0;
}