fork(1) download
copy 
  1. /*
  2.  * HashTable - ハッシュテーブル。
  3.  *
  4.  * Date: 2014-04-10
  5.  * Author: Leonardone
  6.  */
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9. #include <string.h>
  10.  
  11. #define DEBUG_FLAG 1
  12.  
  13. #if DEBUG_FLAG
  14. #  define DebugDo(d) d
  15. #else
  16. #  define DebugDo(d)
  17. #endif
  18.  
  19. /* --- hashtable.h --- */
  20.  
  21. #define MINIMUM_HASHTABLESIZE (0x0002)
  22. #define MAXIMUM_HASHTABLESIZE (0x7FFF)
  23.  
  24. struct _hashtable;
  25. struct _tabledata;
  26.  
  27. typedef struct _hashtable HashTable, *LPHashTable;
  28. typedef struct _tabledata TableData, *LPTableData;
  29.  
  30. extern LPHashTable newHashTable(int tablesize);
  31. extern void releaseHashTable(LPHashTable htable);
  32. extern int addDataIntoHashTable(LPHashTable htable, const char *key, const void *data, const int size);
  33. extern int getDataFromHashTable(const LPHashTable htable, const char *key, void *data, const int size);
  34. extern int removeDataFromHashTable(LPHashTable htable, const char *key);
  35. extern int existKeyInHashTable(LPHashTable htable, const char *key);
  36. extern int setDataIntoHashTable(LPHashTable htable, const char *key, const void *data, const int size);
  37. extern int countDataInHashTable(LPHashTable htable);
  38. extern int getAllKeysInHashTable(const LPHashTable htable, int (*func)(const char *key));
  39.  
  40. struct _hashtable {
  41. 	int count;
  42. 	int tablesize;
  43. 	LPTableData *table;
  44. };
  45.  
  46. struct _tabledata {
  47. 	char *key;
  48. 	void *data;
  49. 	int size;
  50. 	LPTableData next;
  51. };
  52.  
  53. /* --- hashtable_static.h --- */
  54.  
  55. #define HASH_DEEP (5)
  56.  
  57. static int hash(const char *key, const int tablesize);
  58. static LPTableData *searchPlace(const LPHashTable htable, const char *key);
  59. static void releaseTableData(LPTableData ptbdata, int chain);
  60.  
  61. /* --- test.c --- */
  62.  
  63. int addIntIntoHashTable(LPHashTable htable, const char *key, const int value) {
  64. 	return addDataIntoHashTable(htable, key, &value, sizeof(int));
  65. }
  66.  
  67. int getIntFromHashTable(const LPHashTable htable, const char *key, int *value) {
  68. 	return getDataFromHashTable(htable, key, (void*)value, sizeof(int));
  69. }
  70.  
  71. int setIntIntoHashTable(LPHashTable htable, const char *key, const int value) {
  72. 	return setDataIntoHashTable(htable, key, &value, sizeof(int));
  73. }
  74.  
  75. int func1(const char* key) {
  76. 	printf("key: %s\n", key);
  77. 	return 0;
  78. }
  79.  
  80. int main(void) {
  81.  
  82. 	LPHashTable htable = newHashTable(1024);
  83. 	int v = 0;
  84.  
  85. 	addIntIntoHashTable(htable, "foo", 111);
  86. 	addIntIntoHashTable(htable, "bar", 222);
  87. 	addIntIntoHashTable(htable, "baz", 333);
  88. 	addIntIntoHashTable(htable, "fuga", 987);
  89. 	addIntIntoHashTable(htable, "piyo", 654);
  90.  
  91.  
  92. 	printf("cnt: %d\n", htable->count);
  93. 	printf("cnt: %d\n", countDataInHashTable(htable));
  94.  
  95. 	addIntIntoHashTable(htable, "hoge", 123);
  96. 	addIntIntoHashTable(htable, "hoge", 345);
  97. 	getIntFromHashTable(htable, "hoge", &v);
  98. 	printf("get: %d\n", v);
  99.  
  100. 	printf("cnt: %d\n", countDataInHashTable(htable));
  101.  
  102. 	setIntIntoHashTable(htable, "hoge", 345);
  103. 	setIntIntoHashTable(htable, "foobar", 999);
  104. 	getIntFromHashTable(htable, "hoge", &v);
  105. 	printf("get: %d\n", v);
  106.  
  107. 	printf("cnt: %d\n", countDataInHashTable(htable));
  108.  
  109. 	getAllKeysInHashTable(htable, func1);
  110.  
  111. 	removeDataFromHashTable(htable, "baz");
  112. 	removeDataFromHashTable(htable, "baz");
  113. 	removeDataFromHashTable(htable, "test");
  114.  
  115. 	printf("cnt: %d\n", countDataInHashTable(htable));
  116.  
  117. 	printf("sch: %d\n", searchPlace(htable, "hoge"));
  118. 	printf("sch: %d\n", searchPlace(htable, "abc"));
  119. 	printf("*sch: %d\n", *searchPlace(htable, "hoge"));
  120. 	printf("*sch: %d\n", *searchPlace(htable, "abc"));
  121. 	printf("*sch-d: %d\n", *(int*)(*searchPlace(htable, "hoge"))->data);
  122. 	printf("*sch-d: %d\n", *(int*)(*searchPlace(htable, "bar"))->data);
  123.  
  124. 	printf("ext: %d\n", existKeyInHashTable(htable, "hoge"));
  125. 	printf("ext: %d\n", existKeyInHashTable(htable, "abc"));
  126. 	printf("ext: %d\n", existKeyInHashTable(htable, "foo"));
  127. 	printf("ext: %d\n", existKeyInHashTable(htable, "baz"));
  128. 	printf("ext: %d\n", existKeyInHashTable(htable, "fuga"));
  129. 	printf("ext: %d\n", existKeyInHashTable(htable, "piyo"));
  130.  
  131. 	releaseHashTable(htable);
  132.  
  133. 	return 0;
  134. }
  135.  
  136. /* --- hashtable.c --- */
  137.  
  138. /* +++ extern functions +++ */
  139.  
  140. /**
  141.  * 新しいHashTableを作る。
  142.  * @param tablesize
  143.  * @return
  144.  */
  145. LPHashTable newHashTable(const int tablesize) {
  146. 	/* calloc は 0 で初期化される */
  147. 	LPHashTable htable;
  148. 	if (tablesize < MINIMUM_HASHTABLESIZE || tablesize > MAXIMUM_HASHTABLESIZE) {
  149. 		return NULL; /* 引数エラー */ 
  150. 	}
  151. 	htable = (LPHashTable)calloc(1, sizeof(HashTable));
  152. 	if (htable == NULL) {
  153. 		return NULL; /* メモリ確保失敗 */
  154. 	}
  155. 	htable->table = (LPTableData *)calloc(tablesize, sizeof(LPTableData));
  156. 	if (htable->table == NULL) {
  157. 		free(htable);
  158. 		return NULL; /* メモリ確保失敗 */
  159. 	}
  160. 	htable->tablesize = tablesize;
  161. 	DebugDo(printf("init HashTable(%d)\n", tablesize));
  162. 	return htable;
  163. }
  164.  
  165. /**
  166.  * HashTableをメモリから解放する。
  167.  * @param htable
  168.  */
  169. void releaseHashTable(LPHashTable htable) {
  170. 	int i;
  171. 	int tablesize;
  172. 	LPTableData *ptbdata;
  173. 	if (htable == NULL) {
  174. 		return; /* ぬるぽ */
  175. 	}
  176. 	tablesize = htable->tablesize;
  177. 	for (i = 0; i < tablesize; ++i) {
  178. 		ptbdata = htable->table + i;
  179. 		if (*ptbdata != NULL) {
  180. 			releaseTableData(*ptbdata, 1);
  181. 		}
  182. 	}
  183. 	free(htable->table);
  184. 	free(htable);
  185. 	DebugDo(printf("release HashTable(%d)\n", tablesize));
  186. }
  187.  
  188. /**
  189.  * HashTableにデータを追加する。既にキー名が存在する場合は失敗する。
  190.  * @param htable
  191.  * @param key
  192.  * @param data
  193.  * @param size
  194.  * @return
  195.  */
  196. int addDataIntoHashTable(LPHashTable htable, const char *key, const void *data, const int size) {
  197. 	int len;
  198. 	LPTableData *ptbdata;
  199. 	if (htable == NULL || key == NULL || data == NULL || size < 1) {
  200. 		return 0; /* 引数エラー */
  201. 	}
  202. 	ptbdata = searchPlace(htable, key);
  203. 	if (*ptbdata == NULL) {
  204. 		*ptbdata = (LPTableData)calloc(1, sizeof(TableData));
  205. 		if (*ptbdata == NULL) {
  206. 			return 0; /* メモリ確保失敗 */
  207. 		}
  208. 		(*ptbdata)->key = (char *)calloc(len, sizeof(char));
  209. 		if ((*ptbdata)->key == NULL) {
  210. 			free(*ptbdata);
  211. 			*ptbdata = NULL;
  212. 			return 0; /* メモリ確保失敗 */
  213. 		}
  214. 		(*ptbdata)->data = calloc(size, 1);
  215. 		if ((*ptbdata)->data == NULL) {
  216. 			free((*ptbdata)->key);
  217. 			free(*ptbdata);
  218. 			*ptbdata = NULL;
  219. 			return 0; /* メモリ確保失敗 */
  220. 		}
  221. 		len = strlen(key) + 1;
  222. 		memcpy((*ptbdata)->key, key, len);
  223. 		memcpy((*ptbdata)->data, data, size);
  224. 		(*ptbdata)->size = size;
  225. 		++(htable->count);
  226. 		DebugDo(printf("add(success): %s\n", key));
  227. 		return 1;
  228. 	}
  229. 	DebugDo(printf("add(failure): %s\n", key));
  230. 	return 2;
  231. }
  232.  
  233. /**
  234.  * HashTableからキー名のデータを取得する。
  235.  * @param htable
  236.  * @param key
  237.  * @param data
  238.  * @param size
  239.  * @return
  240.  */
  241. int getDataFromHashTable(const LPHashTable htable, const char *key, void *data, const int size) {
  242. 	int minsize;
  243. 	LPTableData tbdata;
  244. 	if (htable == NULL || key == NULL || data == NULL || size < 1) {
  245. 		return 0; /* 引数エラー */
  246. 	}
  247. 	tbdata = *searchPlace(htable, key);
  248. 	if (tbdata != NULL) {
  249. 		if (strcmp(tbdata->key, key) == 0) {
  250. 			minsize = tbdata->size < size ? tbdata->size : size;
  251. 			memcpy(data, tbdata->data, minsize);
  252. 			DebugDo(printf("get(success): %s\n", key));
  253. 			return minsize;
  254. 		}
  255. 		tbdata = tbdata->next;
  256. 	}
  257. 	DebugDo(printf("get(failure): %s\n", key));
  258. 	return 0;
  259. }
  260.  
  261. /**
  262.  * HashTableにデータを書き込む。既にキー名のデータがある場合は上書きする。
  263.  * @param htable
  264.  * @param key
  265.  * @param data
  266.  * @param size
  267.  * @return
  268.  */
  269. int setDataIntoHashTable(LPHashTable htable, const char *key, const void *data, const int size) {
  270. 	int len;
  271. 	int ret = 1;
  272. 	void *temp;
  273. 	LPTableData *ptbdata;
  274. 	if (htable == NULL || key == NULL || data == NULL || size < 1) {
  275. 		return 0; /* 引数エラー */
  276. 	}
  277. 	ptbdata = searchPlace(htable, key);
  278. 	if (*ptbdata == NULL) {
  279. 		*ptbdata = (LPTableData)calloc(1, sizeof(TableData));
  280. 		if (*ptbdata == NULL) {
  281. 			return 0; /* メモリ確保失敗 */
  282. 		}
  283. 		(*ptbdata)->key = (char *)calloc(len, sizeof(char));
  284. 		if ((*ptbdata)->key == NULL) {
  285. 			free(*ptbdata);
  286. 			*ptbdata = NULL;
  287. 			return 0; /* メモリ確保失敗 */
  288. 		}
  289. 		(*ptbdata)->data = calloc(size, 1);
  290. 		if ((*ptbdata)->data == NULL) {
  291. 			free((*ptbdata)->key);
  292. 			free(*ptbdata);
  293. 			*ptbdata = NULL;
  294. 			return 0; /* メモリ確保失敗 */
  295. 		}
  296. 		len = strlen(key) + 1;
  297. 		memcpy((*ptbdata)->key, key, len);
  298. 		(*ptbdata)->size = size;
  299. 		++(htable->count);
  300. 		DebugDo(printf("set/new(success): %s\n", key));
  301. 	} else {
  302. 		if ((*ptbdata)->size != size) {
  303. 			temp = realloc((*ptbdata)->data, size);
  304. 			if (temp == NULL) {
  305. 				return 0; /* メモリ確保失敗 */
  306. 			}
  307. 			(*ptbdata)->data = temp;
  308. 			(*ptbdata)->size = size;
  309. 		}
  310. 		ret = 2;
  311. 		DebugDo(printf("set/update(success): %s\n", key));
  312. 	}
  313. 	memcpy((*ptbdata)->data, data, size);
  314. 	return ret;
  315. }
  316.  
  317. /**
  318.  * HashTable内の指定キー名のデータを削除する。
  319.  * @param htable HashTable。
  320.  * @param key    キー名。
  321.  * @return 削除できたら(1)、失敗したら(0)。
  322.  */
  323. int removeDataFromHashTable(LPHashTable htable, const char *key) {
  324. 	LPTableData *ptbdata;
  325. 	LPTableData tbdata;
  326. 	if (htable == NULL || key == NULL) {
  327. 		return 0; /* ぬるぽ */
  328. 	}
  329. 	ptbdata = searchPlace(htable, key);
  330. 	if (*ptbdata != NULL) {
  331. 		tbdata = *ptbdata;
  332. 		*ptbdata = tbdata->next;
  333. 		releaseTableData(tbdata, 0);
  334. 		--(htable->count);
  335. 		DebugDo(printf("remove(success): %s\n", key));
  336. 		return 1;
  337. 	}
  338. 	DebugDo(printf("remove(failure): %s\n", key));
  339. 	return 0;
  340. }
  341.  
  342. /**
  343.  * HashTable内にキー名のデータが存在するか書くにする。
  344.  * @param htable HashTable。
  345.  * @param key    探すキー名。
  346.  * @return 存在すれば(1)、存在しなければ(0)。
  347.  */
  348. int existKeyInHashTable(LPHashTable htable, const char *key) {
  349. 	if (htable == NULL || key == NULL) {
  350. 		return 0; /* ぬるぽ */
  351. 	}
  352. 	return *searchPlace(htable, key) != NULL;
  353. }
  354.  
  355. /**
  356.  * HashTable内のデータ数を返す。
  357.  * @param htable HashTable。
  358.  * @return データ数。
  359.  */
  360. int countDataInHashTable(LPHashTable htable) {
  361. 	if (htable == NULL) {
  362. 		return 0; /* ぬるぽ */
  363. 	}
  364. 	return htable->count;
  365. }
  366.  
  367. /**
  368.  * HashTable内のキー名を全て取得する。
  369.  * @param htable
  370.  * @param func
  371.  * @return
  372.  */
  373. int getAllKeysInHashTable(const LPHashTable htable, int (*func)(const char *key)) {
  374. 	int i;
  375. 	int ret;
  376. 	int tablesize;
  377. 	LPTableData *ptbdata;
  378. 	LPTableData tbdata;
  379. 	if (htable == NULL || func == NULL) {
  380. 		return 0;
  381. 	}
  382. 	DebugDo(printf("allkey(start)\n"));
  383. 	ptbdata = htable->table;
  384. 	tablesize = htable->tablesize;
  385. 	for (i = 0; i < tablesize; ++i) {
  386. 		tbdata = *ptbdata;
  387. 		while (tbdata != NULL) {
  388. 			ret = (*func)(tbdata->key);
  389. 			if (ret) {
  390. 				DebugDo(printf("allkey(stop)\n"));
  391. 				return 2;
  392. 			}
  393. 			tbdata = tbdata->next;
  394. 		}
  395. 		++ptbdata;
  396. 	}
  397. 	DebugDo(printf("allkey(done)\n"));
  398. 	return 1;
  399. }
  400.  
  401. /* +++ static functions +++ */
  402.  
  403. /**
  404.  * ハッシュ関数。キー名からハッシュ値を生成する。
  405.  * @param key        キー名。
  406.  * @param tablesize  ハッシュ値の制限値。
  407.  * @return ハッシュ値。
  408.  */
  409. int hash(const char *key, const int tablesize) {
  410. 	int i;
  411. 	int v = (int)*key;
  412. 	for (i = 0; i < HASH_DEEP && *key != '\0'; i++) {
  413. 		v ^= (int)(*key) * (int)(*(key + 1));
  414. 		++key;
  415. 	}
  416. 	return v % tablesize;
  417. }
  418.  
  419. /**
  420.  * HashTableからキー名のデータを格納する場所(アドレス)を探す。
  421.  * @param htable キー名を探すHashTable。
  422.  * @param key    探すキー名。
  423.  * @return 格納されてる場所(アドレス)。
  424.  */
  425. LPTableData *searchPlace(const LPHashTable htable, const char *key) {
  426. 	int h = hash(key, htable->tablesize);
  427. 	LPTableData *ptbdata = htable->table + h;
  428. 	while (*ptbdata != NULL) {
  429. 		if (strcmp((*ptbdata)->key, key) == 0) {
  430. 			break;
  431. 		}
  432. 		ptbdata = &(*ptbdata)->next;
  433. 	}
  434. 	DebugDo(printf("hash(%d): %s\n", h, key));
  435. 	return ptbdata;
  436. }
  437.  
  438. /**
  439.  * TableDataをメモリから解放する。
  440.  * @param ptbdata 解放するデータ。
  441.  * @param chain   nextにあるTableDataも解放する(1)かしない(0)か。
  442.  */
  443. void releaseTableData(LPTableData tbdata, int chain) {
  444. 	if (tbdata == NULL) {
  445. 		return;
  446. 	}
  447. 	if (chain) {
  448. 		releaseTableData(tbdata->next, chain);
  449. 	}
  450. 	DebugDo(printf("release TableData: %s\n", tbdata->key));
  451. 	free(tbdata->key);
  452. 	free(tbdata->data);
  453. 	free(tbdata);
  454. }
Success #stdin #stdout 0s 2384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
init HashTable(1024)
hash(125): foo
add(success): foo
hash(626): bar
add(success): bar
hash(890): baz
add(success): baz
hash(748): fuga
add(success): fuga
hash(86): piyo
add(success): piyo
cnt: 5
cnt: 5
hash(378): hoge
add(success): hoge
hash(378): hoge
add(failure): hoge
hash(378): hoge
get(success): hoge
get: 123
cnt: 6
hash(378): hoge
set/update(success): hoge
hash(19): foobar
set/new(success): foobar
hash(378): hoge
get(success): hoge
get: 345
cnt: 7
allkey(start)
key: foobar
key: piyo
key: foo
key: hoge
key: bar
key: fuga
key: baz
allkey(done)
hash(890): baz
release TableData: baz
remove(success): baz
hash(890): baz
remove(failure): baz
hash(243): test
remove(failure): test
cnt: 6
hash(378): hoge
sch: 137057792
hash(165): abc
sch: 137056940
hash(378): hoge
*sch: 137060664
hash(165): abc
*sch: 0
hash(378): hoge
*sch-d: 345
hash(626): bar
*sch-d: 222
hash(378): hoge
ext: 1
hash(165): abc
ext: 0
hash(125): foo
ext: 1
hash(890): baz
ext: 0
hash(748): fuga
ext: 1
hash(86): piyo
ext: 1
release TableData: foobar
release TableData: piyo
release TableData: foo
release TableData: hoge
release TableData: bar
release TableData: fuga
release HashTable(1024)
https://ideone.com/UClFxU
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!