Advertisement
NyteOwlDave

Hash Table in C

Sep 7th, 2022
981
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.97 KB | Software | 0 0
  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5.  
  6. #define NUMBER_OF_BUCKETS 3
  7.  
  8. typedef struct _node {
  9.     char* key;
  10.     void* value; // Most hash tables have a value in each node too
  11.     struct _node* next;
  12. } NODE, *PNODE;
  13.  
  14. // Create an unattached node and initialize it
  15. PNODE create_node(char* key, void* value) {
  16.     PNODE pnode = (PNODE)malloc(sizeof (NODE));
  17.     pnode->key = strdup(key);
  18.     pnode->value = value;
  19.     pnode->next = NULL;
  20.     return pnode;
  21. }
  22.  
  23. // Destroy a dynamically allocated node
  24. PNODE destroy_node(PNODE pnode) {
  25.     if (pnode) {
  26.         if (pnode->key) free(pnode->key);
  27.         free(pnode);
  28.     }
  29. }
  30.  
  31. // Simple hashing function
  32. // (Sum of character codes in key, modulo # of buckets)
  33. int calc_hash(char* key) {
  34.     int bucket = 0;
  35.     while (*key) {
  36.         bucket += (int)(*key);
  37.         key++;
  38.     }
  39.     return (bucket % NUMBER_OF_BUCKETS);
  40. }
  41.  
  42. // Insert dynamic node into table
  43. // NOTE: Static nodes will seg fault during cleanup
  44. void insert_node(PNODE* table, PNODE pnode) {
  45.     int bucket = calc_hash(pnode->key);
  46.     pnode->next = table[bucket];
  47.     table[bucket] = pnode;
  48. }
  49.  
  50. // Returns node ptr, or NULL if not found
  51. PNODE find_node(PNODE* table, char* key) {
  52.     int bucket = calc_hash(key);
  53.     PNODE pnode = table[bucket];
  54.     while (pnode) {
  55.         if (strcmp(pnode->key, key) ==0) return pnode;
  56.         pnode = pnode->next;
  57.     }
  58.     // Not found
  59.     return NULL;
  60. }
  61.  
  62. // Locate node by key, then print key if found
  63. void print_node(PNODE* table, char* key) {
  64.     PNODE pnode = find_node(table, key);
  65.     if (pnode) {
  66.         printf("Found: %s\n", key);      
  67.     } else {
  68.         printf("Not found: %s\n", key);
  69.     }
  70. }
  71.  
  72. // Walk the entire table and print all found nodes
  73. void print_all_nodes(PNODE* table) {
  74.     for (int bucket=0; bucket<NUMBER_OF_BUCKETS; bucket++) {
  75.         PNODE pnode = table[bucket];
  76.         while (pnode) {
  77.             printf("Found %s\n", pnode->key);
  78.             pnode = pnode->next;
  79.         }
  80.     }
  81. }
  82.  
  83. // Deallocate all nodes in the table
  84. void destroy_all_nodes(PNODE* table) {
  85.     for (int bucket=0; bucket<NUMBER_OF_BUCKETS; bucket++) {
  86.         PNODE pnode = table[bucket];
  87.         if (pnode) {
  88.             while (pnode->next) {
  89.                 PNODE pnext = pnode->next;
  90.                 pnode->next = pnode->next->next;
  91.                 destroy_node(pnext);
  92.             }
  93.             destroy_node(pnode);
  94.             table[bucket] = NULL;
  95.         }
  96.     }
  97. }
  98.  
  99. int main(void) {
  100.     PNODE table[NUMBER_OF_BUCKETS];
  101.     // Clear the table!
  102.     memset(table, 0, NUMBER_OF_BUCKETS * sizeof (PNODE));
  103.     PNODE pnode = create_node("Anant", NULL);
  104.     insert_node(table, pnode);
  105.     pnode = create_node("Param", NULL);
  106.     insert_node(table, pnode);
  107.     pnode = create_node("Heisenberg", NULL);
  108.     insert_node(table, pnode);
  109.     // What have we got?
  110.     print_all_nodes(table);
  111.     // Clean up dynamic memory
  112.     destroy_all_nodes(table);
  113.     return 0;
  114. }
  115.  
  116.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement