/*-----------------------------------------------------------------------------
このコードの利用に際して:
自己責任でお願いします。
List
作成中:2013/10/ 現在
ListEntry entry を初期化せずに関数を使用した場合、警告を出してプログラムを終了します。
ListEntry entry のdatasizeが0以下の時に関数を使用した場合、警告を出してプログラムを終了します。
datasize にリストのノードに格納するデータのbyte数を指定してください。
例1:
ListEntry integerList = { sizeof(int), };
例2:
ListEntry integerList = {};
integerList.datasize = sizeof(int);
未定義の動作:
初期化フラグのみを初期化した場合、動作は未定義です
例:
ListEntry intList;
intList.__isinited = 0;
定数を引数に渡したとき、動作は未定義です
変数のアドレスを渡してください
例:
ListEntry intList = { sizeof(int), };
List_PushBack( 10 );// error
違う型のデータをリストに格納した時の動作は未定義です。
例:
ListEntry intList = { sizeof(int), };
double data = 0.0;
List_PushBack( &intList, &data );
ListEntry型変数同士の演算は未定義です。
例:
entry1 = entry2
---------------------------------------------------------------------------*/
// ---------------------------------------------------------------------------------------------------------- List.h
#ifndef __LIST_H__
#define __LIST_H__
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct tagListEntry ListEntry;
typedef struct tagListNode ListNode;
struct tagListEntry {
int datasize; // ノードに格納するdataのbyte数。ユーザ定義。
int __nodesum; // リストが持つノードの数
int __isinited; // リストが初期化されているかどうか。値が0なら初期化済みと見なす。
ListNode *headnode; // 先頭ノード
ListNode *tailnode; // 末尾ノード
};
extern void List_Init (ListEntry *list, int datasize);
extern void List_Clear (ListEntry *list);
extern int List_Size (ListEntry *list);
extern int List_Empty (ListEntry *list);
extern void List_PushBack (ListEntry *list, void *data);
extern void List_PushFront (ListEntry *list, void *data);
extern void* List_Back (ListEntry *list);
extern void* List_Front (ListEntry *list);
extern void List_PopBack (ListEntry *list);
extern void List_PopFront (ListEntry *list);
extern void List_Swap (ListEntry *list, ListEntry *target);
extern void* List_Search (ListEntry *list, const void *key, int (*compar)(const void *val1, const void *val2));
#endif//__LIST_H__
// --------------------------------------------------------------------- List.c
/*-----------------------------------------------------------------------------
List.c: 静的なデータ宣言
---------------------------------------------------------------------------*/
struct tagListNode {
struct tagListNode *prev;
struct tagListNode *next;
void *data;
};
/*-----------------------------------------------------------------------------
List.c: 静的な広域変数の実体
---------------------------------------------------------------------------*/
static const int debug = 0;// 0でデバッグ表示をオフ
/*-----------------------------------------------------------------------------
List.c: 静的な広域関数のプロトタイプ宣言
---------------------------------------------------------------------------*/
static void Error (ListEntry *list, const char *errmsg);
static int IsValid (ListEntry *list);
static ListNode* GetNode (ListEntry *list, void *data);
static void Remove (ListEntry *list, ListNode *targetnode);
/*-----------------------------------------------------------------------------
List.c: 静的な広域関数の実体
---------------------------------------------------------------------------*/
static void Error(ListEntry *list, const char *errmsg)
{
fprintf(stderr
, "error: List address: %d: %s\n", (unsigned int)list
, errmsg
); }
/**
* リストが有効かを調べる。
* @ret 有効でなければ0。有効ならそれ以外。
*/
static int IsValid(ListEntry *list)
{
if (list == NULL) {
return 0;
} else if (list->__isinited != 0) {
Error(list, "IsValid: エントリーを初期化してください。");
return 0;
} else if (list->datasize <= 0) {
Error(list, "IsValid: データサイズを設定してください。");
return 0;
}
return 1;
}
/**
* ノードとノード内データのメモリを確保して、データをコピーし、そのノードを返す
*/
static ListNode* GetNode(ListEntry *list, void *data)
{
ListNode *addnode;
addnode
= (ListNode
*)malloc(sizeof(ListNode
));// ノードのメモリを確保 if (addnode == NULL)
Error(list, "PushBack: addnode is null.");
if (debug
) printf("\tin List: malloc data size: addnode: %d byte: address: %d\n", sizeof(*addnode), (unsigned int)addnode);
addnode
->data
= malloc(list
->datasize
);// データのメモリを確保 if (addnode->data == NULL)
Error(list, "PushBack: addnode->data is null.");
if (debug
) printf("\tin List: malloc data size: addnode->data: %d byte: address: %d\n", list->datasize, (unsigned int)&(addnode->data));
// メンバ変数を初期化
memmove(addnode
->data
, data
, list
->datasize
); addnode->prev = NULL;
addnode->next = NULL;
// ノードの数を更新
list->__nodesum++;
return addnode;
}
/**
* リストからノードを削除
*/
static void Remove(ListEntry *list, ListNode *targetnode)
{
if (targetnode == NULL)
return;
ListNode *delnode, *prevnode, *nextnode;
list->__nodesum--;// ノードの数を更新
delnode = targetnode;
prevnode = targetnode->prev;
nextnode = targetnode->next;
// リスト内にノードが一つしかない場合(孤立してる場合)
if (prevnode == NULL && nextnode == NULL)
{
delnode->data = NULL;
delnode = NULL;
list->headnode = list->tailnode = NULL;
return;
}
// リスト先頭のノードの場合
else if (prevnode == NULL) {
nextnode->prev = NULL;
list->headnode = nextnode;// 先頭ノードの更新
}
// リスト中間にあるノードの場合
else if (prevnode != NULL && nextnode != NULL) {
prevnode->next = nextnode;
nextnode->prev = prevnode;
}
// リスト末尾のノードの場合
else if (nextnode == NULL) {
prevnode->next = NULL;
list->tailnode = prevnode;// 末尾ノードの更新
} else {
Error(list, "Remove: illegal exception error.\n");
}
delnode->data = NULL;
delnode = NULL;
}
/*-----------------------------------------------------------------------------
List.c: 外部に公開する広域関数
---------------------------------------------------------------------------*/
/**
* リストを初期化
* @param *list ListEntry
* @param datasize リストが扱うデータ型のbyte数
*/
extern void List_Init(ListEntry *list, int datasize)
{
list->datasize = datasize;
list->__nodesum = 0;
list->__isinited = 0;
list->headnode = 0;
list->tailnode = 0;
}
/**
* リストが持つノード(要素)数を返す
* @param *list ListEntry
*/
extern int List_Size(ListEntry *list)
{
if (! IsValid(list))
return -1;
return list->__nodesum;
}
/**
* リストから目的のデータを探す。
* @ret (void *)data 見つけたデータへのアドレス。見つからなければNULL。
* @param *list ListEntry
* @param *key 目的のデータ
* @param *compar 比較用の関数ポインタ(ユーザ定義)
* compar関数のルール(bsearch関数を参考)
* val1 が val2 よりも小さい場合 : 0 より小さい値を返す
* val1 が val2 と一致する場合 : 0 を返す
* val1 が val2 よりも大きい場合 : 0 より大きい値を返す
*/
extern void* List_Search(ListEntry *list, const void *key, int (*compar)(const void *val1, const void *val2))
{
if (! IsValid(list))
return NULL;
ListNode *thisnode;
for (thisnode = list->headnode; thisnode != NULL; thisnode = thisnode->next)
{
if ( (*compar)(key, thisnode->data) == 0 )
return thisnode->data;
}
return NULL;
}
/**
* リストが空なら真を返す。
* @param *list ListEntry
*/
extern int List_Empty(ListEntry *list)
{
return (list->headnode == NULL && list->tailnode == NULL);
}
/**
* リストの末尾に、データを格納したノードを追加する。
* @param *list ListEntry
* @param *data ノードに格納するデータ
*/
extern void List_PushBack(ListEntry *list, void *data)
{
if (! IsValid(list))
return;
ListNode *addnode;
addnode = GetNode(list, data);
if (list->tailnode == NULL) {
list->headnode = list->tailnode = addnode;
} else {
addnode->prev = list->tailnode;
list->tailnode->next = addnode;
list->tailnode = addnode;
}
if (debug
) printf("\tin List: PushBack: addnode: address: %d\n", (unsigned int)addnode);
}
/**
* リストの先頭にデータを格納したノードを追加する。
* @param *list ListEntry
* @param *data ノードに格納するデータ
*/
extern void List_PushFront(ListEntry *list, void *data)
{
if (! IsValid(list))
return;
ListNode *addnode;
addnode = GetNode(list, data);
if (list->tailnode == NULL) {
list->headnode = list->tailnode = addnode;
} else {
addnode->next = list->headnode;
list->headnode->prev = addnode;
list->headnode = addnode;
}
}
/**
* リスト末尾のノードを削除する
* @param *list ListEntry
*/
extern void List_PopBack(ListEntry *list)
{
if (! IsValid(list))
return;
Remove(list, list->tailnode);
}
/**
* リスト先頭のノードを削除する
* @param *list ListEntry
*/
extern void List_PopFront(ListEntry *list)
{
if (! IsValid(list))
return;
Remove(list, list->headnode);
}
/**
* リストの末尾のノードからデータを返す
* @param *list ListEntry
*/
extern void* List_Back(ListEntry *list)
{
if (! IsValid(list))
return NULL;
if (List_Empty(list))
return NULL;
return list->tailnode->data;
}
/**
* リストの先頭のノードからデータを返す
* @param *list ListEntry
*/
extern void* List_Front(ListEntry *list)
{
if (! IsValid(list))
return NULL;
if (List_Empty(list))
return NULL;
return list->headnode->data;
}
/**
* リストをクリア。リスト内のノードをすべて開放。
* @param *list ListEntry
*/
extern void List_Clear(ListEntry *list)
{
if (! IsValid(list))
return;
ListNode *thisnode, *remnode;
for (thisnode = list->headnode; thisnode != NULL; )
{
remnode = thisnode;
if (debug
) printf("\tin List: remnode: %d\n", (unsigned int)remnode
);//debug
thisnode = thisnode->next;
remnode->data = NULL;
remnode = NULL;
}
list->headnode = list->tailnode = NULL; // ポインタをクリア
list->__nodesum = 0; // ノードの数を更新
}
/**
* リストをスワップ
* @param *list スワップする ListEntry*
* @param *target スワップする ListEntry*
*/
extern void List_Swap(ListEntry *list, ListEntry *target)
{
if (list == NULL || target == NULL)
return;
ListEntry temp;
temp = *list;
*list = *target;
*target = temp;
}
// ----------------------------------------------------------------------------------------------------- ListTest.c
static int Compar(const int *val1, const int *val2)
{
if ( *val1 < *val2 )
return -1;
else if ( *val1 == *val2 )
return 0;
else
return 1;
}
int main()
{
ListEntry ageList = {sizeof(int)},
weightList = {sizeof(double)};
int i, age, *find;
double weight;
/* リストにデータを格納 */
for (i = 0; i < 10; i++) {
age = 20 + i;
List_PushBack(&ageList, &age);
}
for (i = 0; i < 5; i++) {
weight
= rand()%500*0.10+40; List_PushFront(&weightList, &weight);
}
printf("ageList size: %d\n", List_Size
(&ageList
)); printf("weightList size: %d\n", List_Size
(&weightList
));
/* リスト内からデータを探索 */
age = 25;
find = (int *)List_Search(&ageList, &age,
(int (*)(const void*, const void*))Compar
);
if (find == NULL)
else
printf("found age: %2d\n", *find
);
/* リストからデータを取得&削除 */
while (! List_Empty(&ageList)) {
age = *(int*)List_Back(&ageList);
List_PopBack(&ageList);
}
while (! List_Empty(&weightList)) {
weight = *(double*)List_Front(&weightList);
printf("weight: %.2f kg\n", weight
); List_PopFront(&weightList);
}
/* リストをクリア */
List_Clear(&ageList);
List_Clear(&weightList);
return 0;
}