Advertisement
Guest User

Hash map in C

a guest
Nov 27th, 2023
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 4.89 KB | Fixit | 0 0
  1. #ifdef __STDC_LIB_EXT1__
  2.     #define __STDC_WANT_LIB_EXT1__ 1
  3.     #define scanf scanf_s // Bit hacky ngl.
  4. #endif
  5.  
  6. #include <stddef.h>  // size_t, NULL
  7. #include <stdint.h>  // uint64_t
  8. #include <stdbool.h> // bool
  9. #include <stdio.h>   // scanf()/scanf_s(), puts()
  10. #include <stdlib.h>  // malloc(), calloc(), free()
  11. #include <string.h>  // memset(), strcmp()
  12.  
  13. typedef struct {
  14.     unsigned short year;
  15.     unsigned char month, day;
  16.     char *name;
  17. } User;
  18.  
  19. typedef struct Bucket {
  20.     User user;
  21.     struct Bucket *collision;
  22.     bool valid: 1;
  23. } Bucket;
  24.  
  25. #define FNV1A_OFFSET 0xCBF29CE484222325
  26. #define FNV1A_PRIME  0x00000100000001B3
  27.  
  28. static inline uint64_t fnv1a_hash_user(User user) {
  29.     uint64_t hash = FNV1A_OFFSET;
  30.     hash = (hash ^ user.year)  * FNV1A_PRIME;
  31.     hash = (hash ^ user.month) * FNV1A_PRIME;
  32.     hash = (hash ^ user.day)   * FNV1A_PRIME;
  33.     while (*user.name)
  34.         hash = (hash ^ *user.name++) * FNV1A_PRIME;
  35.     return hash;
  36. }
  37.  
  38. #define HASHMAP_HEAP
  39. #ifdef HASHMAP_HEAP
  40.     #define HASHMAP_SIZE 10000000 / sizeof(Bucket) // RAM is limited to 35 MB. God and virtual memmory, please save me.
  41. #else
  42.     #define HASHMAP_SIZE 10000000 / sizeof(Bucket) // RAM is limited to 35 MB. God and virtual memmory, please save me.
  43. #endif
  44.  
  45. int main() {
  46. #ifdef HASHMAP_HEAP
  47.     Bucket *hashmap = (Bucket *) calloc(HASHMAP_SIZE, sizeof(Bucket)); // false == 0, NULL == 0
  48. #else
  49.     Bucket hashmap[HASHMAP_SIZE];
  50.     memset(&hashmap, 0, sizeof(hashmap)); // false == 0, NULL == 0
  51. #endif
  52.     char operation;
  53.     User user;
  54.     while (5 == scanf(" %c : %hu %hhu %hhu %m[^\n]",
  55.         &operation,
  56.         &user.year,
  57.         &user.month,
  58.         &user.day,
  59.         &user.name)) {
  60.         Bucket *bucket = &hashmap[fnv1a_hash_user(user) % HASHMAP_SIZE], *prev_bucket = NULL;
  61.         switch (operation) {
  62.             case 'S': store: {
  63.                 if (!bucket->valid) {
  64.                     bucket->user      = user;
  65.                     bucket->collision = NULL;
  66.                     bucket->valid     = true;
  67.                     if (prev_bucket)
  68.                         prev_bucket->collision = bucket;
  69.                     puts("Stored");
  70.                 }
  71.                 else if (bucket->user.year  == user.year  &&
  72.                     bucket->user.month      == user.month &&
  73.                     bucket->user.day        == user.day   &&
  74.                     !strcmp(bucket->user.name, user.name))
  75.                     puts("Already stored");
  76.                 else if (!bucket->collision) {
  77.                     prev_bucket = bucket;
  78.                     prev_bucket->collision = bucket = bucket->collision = malloc(sizeof(Bucket));
  79.                     bucket->user      = user;
  80.                     bucket->collision = NULL;
  81.                     bucket->valid     = true;
  82.                     puts("Stored");
  83.                 }
  84.                 else {
  85.                     prev_bucket = bucket;
  86.                     bucket = bucket->collision;
  87.                     goto store;
  88.                 }
  89.             }
  90.             break;
  91.             case 'F': find: {
  92.                 if (!bucket->valid)
  93.                     puts("Not found");
  94.                 else if (bucket->user.year  == user.year  &&
  95.                     bucket->user.month      == user.month &&
  96.                     bucket->user.day        == user.day   &&
  97.                     !strcmp(bucket->user.name, user.name))
  98.                     puts("Found");
  99.                 else if (!bucket->collision)
  100.                     puts("Not found");
  101.                 else {
  102.                     // prev_bucket = bucket;
  103.                     bucket = bucket->collision;
  104.                     goto find;
  105.                 }
  106.             }
  107.             break;
  108.             case 'D': delete: {
  109.                 if (!bucket->valid)
  110.                     puts("Not found");
  111.                 else if (bucket->user.year  == user.year  &&
  112.                     bucket->user.month      == user.month &&
  113.                     bucket->user.day        == user.day   &&
  114.                     !strcmp(bucket->user.name, user.name)) {
  115.                         prev_bucket = bucket->collision;
  116.                         bucket->valid = false;
  117.                         free(bucket->user.name);
  118.                         puts("Deleted");
  119.                     }
  120.                 else if (!bucket->collision)
  121.                     puts("Not found");
  122.                 else {
  123.                     prev_bucket = bucket;
  124.                     bucket = bucket->collision;
  125.                     goto delete;
  126.                 }
  127.             }
  128.             break;
  129.         }
  130.     }
  131.     for (size_t idx = 0; HASHMAP_SIZE > idx; idx++)
  132.         if (hashmap[idx].valid) {
  133.             free(hashmap[idx].user.name);
  134.             Bucket *collision = &hashmap[idx];
  135.             while ((collision = collision->collision))
  136.                 free(collision);
  137.         }
  138. #ifdef HASHMAP_HEAP
  139.     free(hashmap);
  140. #endif
  141. }
  142.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement