HASH - C

SUBMITTED BY: bitcoinsachen

DATE: Dec. 14, 2016, 9:44 p.m.

UPDATED: Dec. 14, 2016, 9:52 p.m.

FORMAT: Text only

SIZE: 11.8 kB

History Raw Download

HITS: 409

Report
  1. #ifndef HEADER_H_INCLUDED
  2. #define HEADER_H_INCLUDED
  3. #include <string.h>
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. typedef struct hashentry__s
  7. {
  8. char songtitle[256], interpreter[256];
  9. } hashentry_t;
  11. typedef struct hasharray__s
  12. {
  13. hashentry_t *entries;
  14. long num_entries;
  15. } hasharray_t;
  17. typedef struct hashcontainer__s
  18. {
  19. hasharray_t *harrays;
  20. long hashsize;
  21. } hashcontainer_t;
  23. long hash_key(char songtitle[], char interpreter[], long hash_max);
  24. hashcontainer_t *create_hash(long hashsize);
  25. void delete_hash(hashcontainer_t *hashcontainer);
  26. void insert_entry(hashcontainer_t *hashcontainer, char songtitle[], char interpreter[]);
  27. hashentry_t *search_entry(hashcontainer_t *hashcontainer, char songtitle[], char interpreter[]);
  28. void delete_entry(hashcontainer_t *hashcontainer, char songtitle[], char interpreter[]);
  29. void print_hash(hashcontainer_t *hashcontainer);
  30. long count_entries(hashcontainer_t *hashcontainer);
  31. long count_entries_with_songtitle(hashcontainer_t *hashcontainer, char songtitle[]);
  32. void insert_entry_ext_exp(hashcontainer_t *hashcontainer, char songtitle[], char interpreter[], long(*hashkey_gen)(hashentry_t *entry, long hash_max));
  33. void insert_entry_ext(hashcontainer_t *hashcontainer, hashentry_t *hashentry, long(*hashkey_gen)(hashentry_t *entry, long hash_max));
  34. long hashkey_gen1(hashentry_t *entry, long hash_max);
  35. long hashkey_gen2(hashentry_t *entry, long hash_max);
  36. void rehash1(hashcontainer_t *hashcontainer, long(*hashkey_gen)(hashentry_t *entry, long hash_max), long hash_max);
  37. void rehash2(hashcontainer_t *hashcontainer, long(*hashkey_gen)(hashentry_t *entry, long hash_max), long hash_max);
  39. #endif // HEADER_H_INCLUDED
  41. #include "header.h"
  43. long hash_key(char songtitle[], char interpreter[], long hash_max)
  44. {
  45. unsigned long i, index = 0;
  46. for (i = 0; i < strlen(songtitle); ++i)
  47. index = 64 * index + (long)(songtitle[i]);
  48. for (i = 0; i < strlen(interpreter); ++i)
  49. index = 64 * index + (long)(interpreter[i]);
  50. return index % hash_max;
  51. }
  53. long hashkey_gen1(hashentry_t *entry, long hash_max)
  54. {
  55. unsigned long i, index = 0;
  56. for (i = 0; i < strlen(entry->songtitle); ++i)
  57. index = 64 * index + (long)(entry->songtitle[i]);
  58. for (i = 0; i < strlen(entry->interpreter); ++i)
  59. index = 64 * index + (long)(entry->interpreter[i]);
  60. return index % hash_max;
  61. }
  63. hashcontainer_t *create_hash(long hashsize)
  64. {
  65. unsigned long i;
  66. hashcontainer_t *new = 0;
  67. if (!(new = malloc(sizeof(hashcontainer_t))))
  68. {
  69. fprintf(stderr, "Memory allocation error in create_hash()");
  70. exit(-1);
  71. }
  73. if (!(new->harrays = calloc(hashsize, sizeof(hasharray_t))))
  74. {
  75. fprintf(stderr, "Memory allocation error in create_hash()");
  76. exit(-1);
  77. }
  78. new->hashsize = hashsize;
  79. for (i = 0; i < hashsize; i++)
  80. {
  81. new->harrays[i];
  82. }
  83. return new;
  84. }
  86. void delete_hash(hashcontainer_t *hashcontainer)
  87. {
  88. unsigned long i;
  89. for (i = 0; i < hashcontainer->hashsize; i++)
  90. {
  91. if (hashcontainer->harrays[i].entries)
  92. {
  93. free(hashcontainer->harrays[i].entries);
  94. hashcontainer->harrays[i].entries = 0;
  95. hashcontainer->harrays[i].num_entries = 0;
  96. }
  98. }
  100. free(hashcontainer->harrays);
  101. hashcontainer->harrays = 0;
  102. hashcontainer->hashsize = 0;
  103. }
  106. void insert_entry(hashcontainer_t *hashcontainer, char songtitle[], char interpreter[])
  107. {
  108. unsigned long index = hash_key(songtitle, interpreter, hashcontainer->hashsize);
  109. hashcontainer->harrays[index].num_entries++;
  110. hashcontainer->harrays[index].entries = realloc(hashcontainer->harrays[index].entries, hashcontainer->harrays[index].num_entries * sizeof(hashentry_t));
  111. strcpy(hashcontainer->harrays[index].entries[hashcontainer->harrays[index].num_entries - 1].songtitle, songtitle);
  112. strcpy(hashcontainer->harrays[index].entries[hashcontainer->harrays[index].num_entries - 1].interpreter, interpreter);
  113. }
  115. hashentry_t *search_entry(hashcontainer_t *hashcontainer, char songtitle[], char interpreter[])
  116. {
  117. unsigned long index = hash_key(songtitle, interpreter, hashcontainer->hashsize);
  118. unsigned long len = hashcontainer->harrays[index].num_entries, i;
  119. for (i = 0; i < len; i++)
  120. {
  121. if ((strcmp(hashcontainer->harrays[index].entries[i].interpreter, interpreter) == 0) && (strcmp(hashcontainer->harrays[index].entries[i].songtitle, songtitle) == 0))
  122. return (hashcontainer->harrays[index].entries)+i;
  123. }
  124. return 0;
  125. }
  127. void delete_entry(hashcontainer_t *hashcontainer, char songtitle[], char interpreter[])
  128. {
  129. unsigned long index = hash_key(songtitle, interpreter, hashcontainer->hashsize);
  130. unsigned long len = hashcontainer->harrays[index].num_entries, i;
  131. for (i = 0; i < len; i++)
  132. {
  133. if ((strcmp(hashcontainer->harrays[index].entries[i].interpreter, interpreter) == 0) && (strcmp(hashcontainer->harrays[index].entries[i].songtitle, songtitle) == 0))
  134. {
  135. if (i == 0 && len == 1)
  136. {
  137. free(hashcontainer->harrays[index].entries);
  138. hashcontainer->harrays[index].entries = 0;
  139. hashcontainer->harrays[index].num_entries = 0;
  140. }
  141. else
  142. {
  143. if (i != len - 1)
  144. memcpy(hashcontainer->harrays[index].entries + i, hashcontainer->harrays[index].entries + i + 1, (len - i - 1)* sizeof(hashentry_t));
  145. hashcontainer->harrays[index].entries = realloc(hashcontainer->harrays[index].entries, --hashcontainer->harrays[index].num_entries * sizeof(hashentry_t));
  146. }
  147. }
  148. }
  149. }
  152. void print_hash(hashcontainer_t *hashcontainer)
  153. {
  154. unsigned long i, j;
  155. for (i = 0; i < hashcontainer->hashsize; i++)
  156. {
  157. fprintf(stdout, "Hash index %ld\n", i);
  158. for (j = 0; j < hashcontainer->harrays[i].num_entries; j++)
  159. {
  160. fprintf(stdout, "%s\t%s\n", hashcontainer->harrays[i].entries[j].songtitle, hashcontainer->harrays[i].entries[j].interpreter);
  161. }
  162. fprintf(stdout, "\n");
  163. }
  164. }
  166. long count_entries(hashcontainer_t *hashcontainer)
  167. {
  168. unsigned long i, j, count = 0;
  169. for (i = 0; i < hashcontainer->hashsize; i++)
  170. {
  171. for (j = 0; j < hashcontainer->harrays[i].num_entries; j++)
  172. {
  173. count++;
  174. }
  175. }
  176. return count;
  177. }
  179. long count_entries_with_songtitle(hashcontainer_t *hashcontainer, char songtitle[])
  180. {
  181. unsigned long i, j, count = 0;
  182. for (i = 0; i < hashcontainer->hashsize; i++)
  183. {
  184. for (j = 0; j < hashcontainer->harrays[i].num_entries; j++)
  185. {
  186. if (strcmp(hashcontainer->harrays[i].entries[j].songtitle, songtitle) == 0)
  187. count++;
  188. }
  189. }
  190. return count;
  191. }
  193. void insert_entry_ext_exp(hashcontainer_t *hashcontainer, char songtitle[], char interpreter[], long(*hashkey_gen)(hashentry_t *entry, long hash_max))
  194. {
  195. hashentry_t *new = malloc(sizeof(hashentry_t));
  196. strcpy(new->songtitle, songtitle);
  197. strcpy(new->interpreter, interpreter);
  198. unsigned long index = hashkey_gen(new, hashcontainer->hashsize);
  199. hashcontainer->harrays[index].num_entries++;
  200. hashcontainer->harrays[index].entries = realloc(hashcontainer->harrays[index].entries, hashcontainer->harrays[index].num_entries * sizeof(hashentry_t));
  201. memcpy(hashcontainer->harrays[index].entries + hashcontainer->harrays[index].num_entries - 1, new, sizeof(hashentry_t));
  202. }
  204. void insert_entry_ext(hashcontainer_t *hashcontainer, hashentry_t *new, long(*hashkey_gen)(hashentry_t *entry, long hash_max))
  205. {
  206. unsigned long index = hashkey_gen(new, hashcontainer->hashsize);
  207. hashcontainer->harrays[index].num_entries++;
  208. hashcontainer->harrays[index].entries = realloc(hashcontainer->harrays[index].entries, hashcontainer->harrays[index].num_entries * sizeof(hashentry_t));
  209. memcpy(hashcontainer->harrays[index].entries + hashcontainer->harrays[index].num_entries - 1, new, sizeof(hashentry_t));
  210. }
  212. hashentry_t *search_entry_ext(hashcontainer_t *hashcontainer, char songtitle[], char interpreter[], long(*hashkey_gen)(hashentry_t *entry, long hash_max))
  213. {
  214. hashentry_t *new = malloc(sizeof(hashentry_t));
  215. strcpy(new->songtitle, songtitle);
  216. strcpy(new->interpreter, interpreter);
  217. unsigned long index = hashkey_gen(new, hashcontainer->hashsize);
  218. unsigned long i;
  219. for (i = 0; i < hashcontainer->harrays[index].num_entries; i++)
  220. {
  221. if ((strcmp(hashcontainer->harrays[index].entries[i].interpreter, interpreter) == 0) && (strcmp(hashcontainer->harrays[index].entries[i].songtitle, songtitle) == 0))
  222. return (hashcontainer->harrays[index].entries)+i;
  223. }
  224. return 0;
  225. }
  227. void rehash1(hashcontainer_t *hashcontainer, long(*hashkey_gen)(hashentry_t *entry, long hash_max), long hash_max)
  228. {
  229. hashcontainer_t *new = create_hash(hash_max);
  230. unsigned long i, j;
  231. for (i = 0; i < hashcontainer->hashsize; i++)
  232. {
  233. for (j = 0; j < hashcontainer->harrays[i].num_entries; j++)
  234. {
  235. insert_entry_ext(new, hashcontainer->harrays[i].entries + j, hashkey_gen);
  236. }
  237. }
  238. delete_hash(hashcontainer);
  239. hashcontainer->harrays = new->harrays;
  240. hashcontainer->hashsize = new->hashsize;
  241. }
  244. void rehash2(hashcontainer_t *hashcontainer, long(*hashkey_gen)(hashentry_t *entry, long hash_max), long hash_max)
  245. {
  246. unsigned long i, j, count = 0, len = count_entries(hashcontainer);
  247. hashentry_t temp[len];
  248. for (i = 0; i < hashcontainer->hashsize; i++)
  249. {
  250. for (j = 0; j < hashcontainer->harrays[i].num_entries; j++)
  251. {
  252. strcpy(temp[count].songtitle, hashcontainer->harrays[i].entries[j].songtitle);
  253. strcpy(temp[count].interpreter, hashcontainer->harrays[i].entries[j].interpreter);
  254. count++;
  255. }
  256. }
  257. delete_hash(hashcontainer);
  258. hashcontainer_t *new = create_hash(hash_max);
  259. for (i = 0; i < len; i++)
  260. {
  261. insert_entry_ext(new, &temp[i], hashkey_gen);
  262. }
  263. hashcontainer->harrays = new->harrays;
  264. hashcontainer->hashsize = new->hashsize;
  265. free(new);
  266. }
  268. #include "source.c"
  270. int main()
  271. {
  272. hashcontainer_t *container = create_hash(3);
  273. insert_entry_ext_exp(container, "Title1", "Inter1", hashkey_gen1);
  274. insert_entry_ext_exp(container, "Title2", "Inter2", hashkey_gen1);
  275. insert_entry_ext_exp(container, "Title2", "Inter2", hashkey_gen1);
  276. insert_entry_ext_exp(container, "Title3", "Inter3", hashkey_gen1);
  277. insert_entry_ext_exp(container, "Title3", "Inter3", hashkey_gen1);
  278. insert_entry_ext_exp(container, "Title3", "Inter3", hashkey_gen1);
  279. insert_entry_ext_exp(container, "Title3", "Inter3", hashkey_gen1);
  280. insert_entry_ext_exp(container, "Title4", "Inter4", hashkey_gen1);
  281. insert_entry_ext_exp(container, "Title7", "Inter7", hashkey_gen1);
  282. insert_entry_ext_exp(container, "Title7", "Inter7", hashkey_gen1);
  283. delete_entry(container, "Title7", "Inter7");
  285. print_hash(container);
  286. fprintf(stdout, "\nRehashing...\n\n");
  287. rehash1(container, hashkey_gen1, 11);
  288. print_hash(container);
  289. hashentry_t *temp = search_entry_ext(container, "Title7", "Inter7", hashkey_gen1);
  290. if (temp)
  291. fprintf(stdout, "%s\t%s\n", temp->songtitle, temp->interpreter);
  292. else
  293. fprintf(stdout, "Not found.\n");
  294. fprintf(stdout, "%ld entries found.", count_entries(container));
  295. delete_hash(container);
  296. free(container);
  297. return 0;
  298. }
comments powered by Disqus