fork download
copy 
  1. /*-----------------------------------------------------------------------------
  2. 	このコードの利用に際して：
  3. 		自己責任でお願いします。
  4.  
  5. 	List
  6. 	作成中：2013/10/ 現在
  7.  
  8. 	ListEntry entry を初期化せずに関数を使用した場合、警告を出してプログラムを終了します。
  9. 	ListEntry entry のdatasizeが０以下の時に関数を使用した場合、警告を出してプログラムを終了します。
  10. 	datasize にリストのノードに格納するデータのbyte数を指定してください。 
  11. 	例１：
  12.  		ListEntry integerList = { sizeof(int), };
  13. 	例２：
  14. 		ListEntry integerList = {};
  15. 		integerList.datasize = sizeof(int);
  16.  
  17. 	未定義の動作：
  18. 		初期化フラグのみを初期化した場合、動作は未定義です
  19. 		例：
  20. 			ListEntry intList;
  21. 			intList.__isinited = 0;
  22.  
  23. 		定数を引数に渡したとき、動作は未定義です
  24. 		変数のアドレスを渡してください
  25. 		例：
  26. 			ListEntry intList = { sizeof(int), };
  27. 			List_PushBack( 10 );// error
  28.  
  29. 		違う型のデータをリストに格納した時の動作は未定義です。
  30. 		例：
  31. 			ListEntry intList = { sizeof(int), };
  32. 			double data = 0.0;
  33. 			List_PushBack( &intList, &data );
  34.  
  35. 		ListEntry型変数同士の演算は未定義です。
  36. 		例：
  37. 			entry1 = entry2
  38.   ---------------------------------------------------------------------------*/
  39.  
  40. // ---------------------------------------------------------------------------------------------------------- List.h
  41. #ifndef __LIST_H__
  42. #define __LIST_H__
  43.  
  44. #include <stdio.h>
  45. #include <stdlib.h>
  46. #include <string.h>
  47.  
  48. typedef struct tagListEntry	ListEntry;
  49. typedef struct tagListNode	ListNode;
  50.  
  51. struct tagListEntry {
  52. 	int			datasize;	// ノードに格納するdataのbyte数。ユーザ定義。
  53. 	int			__nodesum;	// リストが持つノードの数
  54. 	int			__isinited;	// リストが初期化されているかどうか。値が０なら初期化済みと見なす。
  55. 	ListNode	*headnode;	// 先頭ノード
  56. 	ListNode	*tailnode;	// 末尾ノード
  57. };
  58.  
  59. extern void  List_Init		(ListEntry *list, int datasize);
  60. extern void  List_Clear		(ListEntry *list);
  61. extern int   List_Size		(ListEntry *list);
  62. extern int   List_Empty		(ListEntry *list);
  63. extern void  List_PushBack	(ListEntry *list, void *data);
  64. extern void  List_PushFront	(ListEntry *list, void *data);
  65. extern void* List_Back		(ListEntry *list);
  66. extern void* List_Front		(ListEntry *list);
  67. extern void  List_PopBack	(ListEntry *list);
  68. extern void  List_PopFront	(ListEntry *list);
  69. extern void  List_Swap		(ListEntry *list, ListEntry *target);
  70. extern void* List_Search	(ListEntry *list, const void *key, int (*compar)(const void *val1, const void *val2));
  71.  
  72. #endif//__LIST_H__
  73.  
  74. // --------------------------------------------------------------------- List.c
  75.  
  76. /*-----------------------------------------------------------------------------
  77.   List.c: 静的なデータ宣言
  78.   ---------------------------------------------------------------------------*/
  79. struct tagListNode {
  80. 	struct tagListNode	*prev;
  81. 	struct tagListNode	*next;
  82. 	void				*data;
  83. };
  84.  
  85. /*-----------------------------------------------------------------------------
  86.   List.c: 静的な広域変数の実体
  87.   ---------------------------------------------------------------------------*/
  88. static const int debug = 0;// 0でデバッグ表示をオフ
  89.  
  90. /*-----------------------------------------------------------------------------
  91.   List.c: 静的な広域関数のプロトタイプ宣言
  92.   ---------------------------------------------------------------------------*/
  93. static void			Error   (ListEntry *list, const char *errmsg);
  94. static int			IsValid (ListEntry *list);
  95. static ListNode*	GetNode (ListEntry *list, void *data);
  96. static void			Remove  (ListEntry *list, ListNode *targetnode);
  97.  
  98. /*-----------------------------------------------------------------------------
  99.   List.c: 静的な広域関数の実体
  100.   ---------------------------------------------------------------------------*/
  101. static void Error(ListEntry *list, const char *errmsg)
  102. {
  103. 	fprintf(stderr, "error: List address: %d: %s\n", (unsigned int)list, errmsg);
  104. 	exit(2);
  105. }
  106.  
  107. /**
  108.  * リストが有効かを調べる。
  109.  * @ret 有効でなければ０。有効ならそれ以外。
  110.  */
  111. static int IsValid(ListEntry *list)
  112. {
  113. 	if (list == NULL) {
  114. 		return 0;
  115. 	} else if (list->__isinited != 0) {
  116. 		Error(list, "IsValid: エントリーを初期化してください。");
  117. 		return 0;
  118. 	} else if (list->datasize <= 0) {
  119. 		Error(list, "IsValid: データサイズを設定してください。");
  120. 		return 0;
  121. 	}
  122. 	return 1;
  123. }
  124.  
  125. /**
  126.  * ノードとノード内データのメモリを確保して、データをコピーし、そのノードを返す
  127.  */
  128. static ListNode* GetNode(ListEntry *list, void *data)
  129. {
  130. 	ListNode *addnode;
  131.  
  132. 	addnode = (ListNode*)malloc(sizeof(ListNode));// ノードのメモリを確保
  133. 	if (addnode == NULL)
  134. 		Error(list, "PushBack: addnode is null.");
  135.  
  136. 	if (debug) printf("\tin List: malloc data size: addnode: %d byte: address: %d\n",
  137. 						sizeof(*addnode), (unsigned int)addnode);
  138.  
  139. 	addnode->data = malloc(list->datasize);// データのメモリを確保
  140. 	if (addnode->data == NULL)
  141. 		Error(list, "PushBack: addnode->data is null.");
  142.  
  143. 	if (debug) printf("\tin List: malloc data size: addnode->data: %d byte: address: %d\n",
  144. 						list->datasize, (unsigned int)&(addnode->data));
  145. 	// メンバ変数を初期化
  146. 	memmove(addnode->data, data, list->datasize);
  147. 	addnode->prev = NULL;
  148. 	addnode->next = NULL;
  149. 	// ノードの数を更新
  150. 	list->__nodesum++;
  151.  
  152. 	return addnode;
  153. }
  154.  
  155. /**
  156.  * リストからノードを削除
  157.  */
  158. static void Remove(ListEntry *list, ListNode *targetnode)
  159. {
  160. 	if (targetnode == NULL)
  161. 		return;
  162. 	ListNode *delnode, *prevnode, *nextnode;
  163.  
  164. 	list->__nodesum--;// ノードの数を更新
  165.  
  166. 	delnode  = targetnode;
  167. 	prevnode = targetnode->prev;
  168. 	nextnode = targetnode->next;
  169.  
  170. 	// リスト内にノードが一つしかない場合(孤立してる場合)
  171. 	if (prevnode == NULL && nextnode == NULL)
  172. 	{
  173. 		free(delnode->data);
  174. 		delnode->data = NULL;
  175. 		free(delnode);
  176. 		delnode = NULL;
  177. 		list->headnode = list->tailnode = NULL;
  178. 		return;
  179. 	}
  180. 	// リスト先頭のノードの場合
  181. 	else if (prevnode == NULL) {
  182. 		nextnode->prev = NULL;
  183. 		list->headnode = nextnode;// 先頭ノードの更新
  184. 	}
  185. 	// リスト中間にあるノードの場合
  186. 	else if (prevnode != NULL && nextnode != NULL) {
  187. 		prevnode->next = nextnode;
  188. 		nextnode->prev = prevnode;
  189. 	}
  190. 	// リスト末尾のノードの場合
  191. 	else if (nextnode == NULL) {
  192. 		prevnode->next = NULL;
  193. 		list->tailnode = prevnode;// 末尾ノードの更新
  194. 	} else {
  195. 		Error(list, "Remove: illegal exception error.\n");
  196. 	}
  197. 	free(delnode->data);
  198. 	delnode->data = NULL;
  199. 	free(delnode);
  200. 	delnode = NULL;
  201. }
  202.  
  203. /*-----------------------------------------------------------------------------
  204.   List.c: 外部に公開する広域関数
  205.   ---------------------------------------------------------------------------*/
  206. /**
  207.  * リストを初期化
  208.  * @param *list		ListEntry
  209.  * @param datasize	リストが扱うデータ型のbyte数
  210.  */
  211. extern void List_Init(ListEntry *list, int datasize)
  212. {
  213. 	list->datasize   = datasize;
  214. 	list->__nodesum  = 0;
  215. 	list->__isinited = 0;
  216. 	list->headnode   = 0;
  217. 	list->tailnode   = 0;
  218. }
  219.  
  220. /**
  221.  * リストが持つノード（要素）数を返す
  222.  * @param *list		ListEntry
  223.  */
  224. extern int List_Size(ListEntry *list)
  225. {
  226. 	if (! IsValid(list))
  227. 		return -1;
  228. 	return list->__nodesum;
  229. }
  230.  
  231. /**
  232.  * リストから目的のデータを探す。
  233.  * @ret		(void *)data	見つけたデータへのアドレス。見つからなければNULL。
  234.  * @param	*list			ListEntry
  235.  * @param	*key			目的のデータ
  236.  * @param	*compar			比較用の関数ポインタ（ユーザ定義）
  237.  * compar関数のルール(bsearch関数を参考)
  238.  *	val1 が val2 よりも小さい場合 : 0 より小さい値を返す
  239.  *	val1 が val2 と一致する場合   : 0 を返す
  240.  *	val1 が val2 よりも大きい場合 : 0 より大きい値を返す
  241.  */
  242. extern void* List_Search(ListEntry *list, const void *key, int (*compar)(const void *val1, const void *val2))
  243. {
  244. 	if (! IsValid(list))
  245. 		return NULL;
  246. 	ListNode *thisnode;
  247.  
  248. 	for (thisnode = list->headnode; thisnode != NULL; thisnode = thisnode->next)
  249. 	{
  250. 		if ( (*compar)(key, thisnode->data) == 0 )
  251. 			return thisnode->data;
  252. 	}
  253. 	return NULL;
  254. }
  255.  
  256. /**
  257.  * リストが空なら真を返す。
  258.  * @param *list		ListEntry
  259.  */
  260. extern int List_Empty(ListEntry *list)
  261. {
  262. 	return (list->headnode == NULL && list->tailnode == NULL);
  263. }
  264.  
  265. /**
  266.  * リストの末尾に、データを格納したノードを追加する。
  267.  * @param *list		ListEntry
  268.  * @param *data		ノードに格納するデータ
  269.  */
  270. extern void List_PushBack(ListEntry *list, void *data)
  271. {
  272. 	if (! IsValid(list))
  273. 		return;
  274.  
  275. 	ListNode *addnode;
  276.  
  277. 	addnode = GetNode(list, data);
  278.  
  279. 	if (list->tailnode == NULL) {
  280. 		list->headnode = list->tailnode = addnode;
  281. 	} else {
  282. 		addnode->prev		 = list->tailnode;
  283. 		list->tailnode->next = addnode;
  284. 		list->tailnode		 = addnode;
  285. 	}
  286.  
  287. 	if (debug) printf("\tin List: PushBack: addnode: address: %d\n",
  288. 						(unsigned int)addnode);
  289. }
  290.  
  291. /**
  292.  * リストの先頭にデータを格納したノードを追加する。
  293.  * @param *list		ListEntry
  294.  * @param *data		ノードに格納するデータ
  295.  */
  296. extern void List_PushFront(ListEntry *list, void *data)
  297. {
  298. 	if (! IsValid(list))
  299. 		return;
  300.  
  301. 	ListNode *addnode;
  302.  
  303. 	addnode = GetNode(list, data);
  304.  
  305. 	if (list->tailnode == NULL) {
  306. 		list->headnode = list->tailnode = addnode;
  307. 	} else {
  308. 		addnode->next		 = list->headnode;
  309. 		list->headnode->prev = addnode;
  310. 		list->headnode		 = addnode;
  311. 	}
  312. }
  313.  
  314. /**
  315.  * リスト末尾のノードを削除する
  316.  * @param *list		ListEntry
  317.  */
  318. extern void List_PopBack(ListEntry *list)
  319. {
  320. 	if (! IsValid(list))
  321. 		return;
  322. 	Remove(list, list->tailnode);
  323. }
  324.  
  325. /**
  326.  * リスト先頭のノードを削除する
  327.  * @param *list		ListEntry
  328.  */
  329. extern void List_PopFront(ListEntry *list)
  330. {
  331. 	if (! IsValid(list))
  332. 		return;
  333. 	Remove(list, list->headnode);
  334. }
  335.  
  336. /**
  337.  * リストの末尾のノードからデータを返す
  338.  * @param *list		ListEntry
  339.  */
  340. extern void* List_Back(ListEntry *list)
  341. {
  342. 	if (! IsValid(list))
  343. 		return NULL;
  344. 	if (List_Empty(list))
  345. 		return NULL;
  346. 	return list->tailnode->data;
  347. }
  348.  
  349. /**
  350.  * リストの先頭のノードからデータを返す
  351.  * @param *list		ListEntry
  352.  */
  353. extern void* List_Front(ListEntry *list)
  354. {
  355. 	if (! IsValid(list))
  356. 		return NULL;
  357. 	if (List_Empty(list))
  358. 		return NULL;
  359. 	return list->headnode->data;
  360. }
  361.  
  362. /**
  363.  * リストをクリア。リスト内のノードをすべて開放。
  364.  * @param *list		ListEntry
  365.  */
  366. extern void List_Clear(ListEntry *list)
  367. {
  368. 	if (! IsValid(list))
  369. 		return;
  370.  
  371. 	ListNode *thisnode, *remnode;
  372.  
  373. 	for (thisnode = list->headnode; thisnode != NULL; )
  374. 	{
  375. 		remnode = thisnode;
  376. 		if (debug) printf("\tin List: remnode: %d\n", (unsigned int)remnode);//debug
  377.  
  378. 		thisnode = thisnode->next;
  379. 		free(remnode->data);
  380. 		remnode->data = NULL;
  381. 		free(remnode);
  382. 		remnode = NULL;
  383. 	}
  384. 	list->headnode = list->tailnode = NULL;	// ポインタをクリア
  385. 	list->__nodesum = 0;					// ノードの数を更新
  386. }
  387.  
  388. /**
  389.  * リストをスワップ
  390.  * @param *list   スワップする ListEntry*
  391.  * @param *target スワップする ListEntry*
  392.  */
  393. extern void List_Swap(ListEntry *list, ListEntry *target)
  394. {
  395. 	if (list == NULL || target == NULL)
  396. 		return;
  397. 	ListEntry temp;
  398.  
  399. 	temp = *list;
  400. 	*list = *target;
  401. 	*target = temp;
  402. }
  403.  
  404. // ----------------------------------------------------------------------------------------------------- ListTest.c
  405. static int Compar(const int *val1, const int *val2)
  406. {
  407. 	if ( *val1 < *val2 )
  408. 		return -1;
  409. 	else if ( *val1 == *val2 )
  410. 		return 0;
  411. 	else
  412. 		return 1;
  413. }
  414.  
  415. int main()
  416. {
  417. 	ListEntry 	ageList = {sizeof(int)},
  418. 				weightList = {sizeof(double)};
  419. 	int 		i, age, *find;
  420. 	double 		weight;
  421.  
  422. 	/* リストにデータを格納 */
  423. 	for (i = 0; i < 10; i++) {
  424. 		age = 20 + i;
  425. 		List_PushBack(&ageList, &age);
  426. 	}
  427. 	for (i = 0; i < 5; i++) {
  428. 		weight = rand()%500*0.10+40;
  429. 		List_PushFront(&weightList, &weight);
  430. 	}
  431. 	printf("ageList    size: %d\n", List_Size(&ageList));
  432. 	printf("weightList size: %d\n", List_Size(&weightList));
  433.  
  434.  
  435. 	/* リスト内からデータを探索 */
  436. 	age = 25;
  437. 	find = (int *)List_Search(&ageList, &age,
  438. 		(int (*)(const void*, const void*))Compar
  439. 	);
  440. 	if (find == NULL)
  441. 		printf("not found.\n");
  442. 	else
  443. 		printf("found age: %2d\n", *find);
  444.  
  445. 	/* リストからデータを取得＆削除 */
  446. 	while (! List_Empty(&ageList)) {
  447. 		age = *(int*)List_Back(&ageList);
  448. 		printf("age: %2d\n", age);
  449. 		List_PopBack(&ageList);
  450. 	}
  451. 	while (! List_Empty(&weightList)) {
  452. 		weight = *(double*)List_Front(&weightList);
  453. 		printf("weight: %.2f kg\n", weight);
  454. 		List_PopFront(&weightList);
  455. 	}
  456.  
  457. 	/* リストをクリア */
  458. 	List_Clear(&ageList);
  459. 	List_Clear(&weightList);
  460. 	return 0;
  461. }
Success #stdin #stdout 0s 2384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
ageList    size: 10
weightList size: 5
found age: 25
age: 29
age: 28
age: 27
age: 26
age: 25
age: 24
age: 23
age: 22
age: 21
age: 20
weight: 69.30 kg
weight: 81.50 kg
weight: 67.70 kg
weight: 78.60 kg
weight: 78.30 kg
https://ideone.com/2gVP0V
language:
C (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!