fork download
  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
stdin
Standard input is empty
stdout
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