fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. #define TABLE_SIZE (102400)
  6. #define HASH_TABLE_SIZE (32)
  7.  
  8. void initHashTable();
  9.  
  10. /*
  11.  * ハッシュテーブル。
  12.  *
  13.  * 各テーブルはリスト構造によって構築。
  14.  */
  15.  
  16. /* テーブル上のデータにint型サイズでアクセスするためのもの */
  17. union U {
  18. 	int *addr;
  19. 	char *ptr;
  20. };
  21.  
  22. char table[TABLE_SIZE]; /* 全てのデータの格納 */
  23. union U freeptr; /* データの追加ポイントへの参照 */
  24.  
  25. /* テーブルの先頭アドレスの取得 */
  26. char *getTableHeadPtr() {
  27. 	return &table[0] + sizeof(int);
  28. }
  29.  
  30. /* データの追加場所のアドレスを登録 */
  31. void setFreePtr(char *ptr) {
  32. 	*freeptr.addr = (int)ptr;
  33. }
  34.  
  35. /* データの追加場所のアドレスの移動 */
  36. char *moveFreePtr(int add) {
  37. 	*freeptr.addr += add;
  38. 	return (char*)*freeptr.addr;
  39. }
  40.  
  41. /* データの追加場所のアドレスの取得 */
  42. char *getFreePtr() {
  43. 	return (char*)*freeptr.addr;
  44. }
  45.  
  46. /* ハッシュ関数 */
  47. int hash(char *str) {
  48. 	int h = 0;
  49. 	int i;
  50. 	for (i = 0; (*str != '\0') && (i < 10); ++i) {
  51. 		h += (str[0]) * (str[1]);
  52. 		++str;
  53. 	}
  54. 	return h % HASH_TABLE_SIZE;
  55. }
  56.  
  57. /* ハッシュテーブルの初期化 */
  58. void initHashTable() {
  59. 	union U u;
  60. 	int i;
  61.  
  62. 	/* テーブルの初期化 */
  63. 	u.ptr = getTableHeadPtr();
  64. 	for (i = 0; i < HASH_TABLE_SIZE; ++i) {
  65. 		*u.addr = (int)NULL;
  66. 		u.ptr += sizeof(int);
  67. 	}
  68.  
  69. 	/* データの追加場所を記録する場所はテーブルの先頭 */
  70. 	freeptr.ptr = &table[0];
  71.  
  72. 	/* データの追加場所の指定 */
  73. 	setFreePtr(u.ptr);
  74. }
  75.  
  76. /* テーブルへのデータの追加 */
  77. void addHashTable(const char *key, const void *data, const int size) {
  78. 	union U u, v;
  79. 	int h = hash(key);
  80. 	int len;
  81. 	char *p;
  82.  
  83. 	/* リストの先頭アドレスの取得 */
  84. 	u.ptr = getTableHeadPtr() + h * sizeof(int);
  85.  
  86. 	/* リスト上のデータ追加する場所を探す */
  87. 	if (*u.addr != (int)NULL) {
  88. 		do {
  89. 			u.ptr = (char*)*u.addr;
  90. 			p = u.ptr + sizeof(int);
  91. 			if (strcmp(p, key) == 0) {
  92. 				printf("invalid key: %s\n", key); /* キー重複面倒 */
  93. 				return;
  94. 			}
  95. 		} while (*u.addr != (int)NULL);
  96. 	}
  97.  
  98. 	/* 新しいデータのアドレス格納 */
  99. 	*u.addr = (int)getFreePtr();
  100.  
  101. 	/* ここから新しいデータの編集 */
  102.  
  103. 	/* 次のデータへのポインタを0(NULL)で初期化 */
  104. 	v.ptr = getFreePtr();
  105. 	*v.addr = (int)NULL;
  106. 	moveFreePtr(sizeof(int));
  107.  
  108. 	/* キーの登録 */
  109. 	len = strlen(key) + 1;
  110. 	memcpy(getFreePtr(), key, len);
  111. 	moveFreePtr(len);
  112.  
  113. 	/* データサイズの登録 */
  114. 	/* 不精なのでunion Uを代用 */
  115. 	v.ptr = getFreePtr();
  116. 	*v.addr = size;
  117. 	moveFreePtr(sizeof(int));
  118.  
  119. 	/* データの登録 */
  120. 	memcpy(getFreePtr(), data, size);
  121. 	moveFreePtr(size);
  122. }
  123.  
  124. void getAllData(void (*func)(const char*, const void*, const int)) {
  125. 	union U u, v, w;
  126. 	int i, len;
  127. 	char *p;
  128. 	u.ptr = getTableHeadPtr();
  129. 	for (i = 0; i < HASH_TABLE_SIZE; ++i) {
  130. 		if (*u.addr != (int)NULL) {
  131. 			v = u;
  132. 			do {
  133. 				v.ptr = (char*)*v.addr;
  134. 				p = v.ptr + sizeof(int);
  135. 				len = strlen(p);
  136. 				w.ptr = p + len + 1;
  137. 				(*func)(p, w.ptr + sizeof(int), *w.addr);
  138. 			} while (*v.addr != (int)NULL);
  139. 		}
  140. 		u.ptr += sizeof(int);
  141. 	}
  142. }
  143.  
  144. void myfunc(const char* key, const void* data, const int size) {
  145. 	printf("key: %s, size: %d, data address: %d\n", key, size, data);
  146. }
  147.  
  148. int main(void) {
  149. 	int v = 0xABCDEF12;
  150.  
  151. 	initHashTable();
  152.  
  153. 	addHashTable("abcde", &v, sizeof(v));
  154. 	addHashTable("abcde", &v, sizeof(v));
  155. 	addHashTable("abcde", &v, sizeof(v));
  156.  
  157. 	v = 0xAABBCC;
  158. 	addHashTable("XYZ", &v, sizeof(v));
  159.  
  160. 	v = 0x112233;
  161. 	addHashTable("ABCDE", &v, sizeof(v));
  162.  
  163. 	getAllData(myfunc);
  164.  
  165. 	for (v = 0; v < 256; ++v) {
  166. 		if (v % 8 == 0) {
  167. 			if (v % 16 == 0) {
  168. 				printf("\n%04X: ", v);
  169. 			} else {
  170. 				printf(" ");
  171. 			}
  172. 		}
  173. 		printf("%02x ", 0xFF & table[v]);
  174. 	}
  175.  
  176. 	return 0;
  177. }
  178.  
Success #stdin #stdout 0s 2392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
invalid key: abcde
invalid key: abcde
key: XYZ, size: 4, data address: 134520418
key: abcde, size: 4, data address: 134520402
key: ABCDE, size: 4, data address: 134520436

0000: 78 9e 04 08 00 00 00 00  00 00 00 00 56 9e 04 08 
0010: 00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00 
0020: 00 00 00 00 44 9e 04 08  00 00 00 00 00 00 00 00 
0030: 00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00 
0040: 00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00 
0050: 00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00 
0060: 00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00 
0070: 00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00 
0080: 00 00 00 00 66 9e 04 08  61 62 63 64 65 00 04 00 
0090: 00 00 12 ef cd ab 00 00  00 00 58 59 5a 00 04 00 
00A0: 00 00 cc bb aa 00 00 00  00 00 41 42 43 44 45 00 
00B0: 04 00 00 00 33 22 11 00  00 00 00 00 00 00 00 00 
00C0: 00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00 
00D0: 00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00 
00E0: 00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00 
00F0: 00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00
https://ideone.com/XJkS5V
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

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!