fork download
copy 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4.  
  5. // www.cse.yorku.ca/~oz/hash.html
  6. unsigned long stringHash(const char *str, unsigned long modulinho)
  7. {
  8.     unsigned long hash = 5381;
  9.     int c;
  10.  
  11.     while ((c = (unsigned char)*str++))
  12.         hash = ((hash << 5) + hash) + c;
  13.  
  14.     return hash % modulinho;
  15. }
  16.  
  17.  
  18. struct Bucket {
  19.     char *key;
  20.     char *value;
  21.     struct Bucket *next;
  22. };
  23.  
  24. struct Bucket *createBucket(const char *key, const char *value)
  25. {
  26.     if (!key || !value) {
  27.         return NULL;
  28.     }
  29.  
  30.     struct Bucket *bucket = malloc(sizeof(struct Bucket));
  31.     if (!bucket) {
  32.         return NULL;
  33.     }
  34.  
  35.     bucket->key = malloc(strlen(key) + 1);
  36.     if (!bucket->key) {
  37.         free(bucket);
  38.         return NULL;
  39.     }
  40.     bucket->value = malloc(strlen(value) + 1);
  41.     if (!bucket->value) {
  42.         free(bucket->key);
  43.         free(bucket);
  44.         return NULL;
  45.     }
  46.  
  47.     strcpy(bucket->key, key);
  48.     strcpy(bucket->value, value);
  49.  
  50.     bucket->next = NULL;
  51.     return bucket;
  52. }
  53.  
  54. void freeBucketList(struct Bucket *bucket)
  55. {
  56.     if (!bucket) {
  57.         return;
  58.     }
  59.  
  60.     free(bucket->key);
  61.     free(bucket->value);
  62.  
  63.     if (bucket->next) {
  64.         freeBucketList(bucket->next);
  65.     }
  66.  
  67.     free(bucket);
  68. }
  69.  
  70.  
  71. struct Bucket *addBucketToList(struct Bucket *head, const char *key, const char *value)
  72. {
  73.     struct Bucket *newBucket = createBucket(key, value);
  74.     if (!newBucket) {
  75.         return NULL;
  76.     }
  77.  
  78.     if (head) {
  79.         struct Bucket *lastBucket = head;
  80.         while (lastBucket->next) {
  81.             lastBucket = lastBucket->next;
  82.         }
  83.         lastBucket->next = newBucket;
  84.         return head;
  85.     }
  86.  
  87.     return newBucket;  // new head
  88. }
  89.  
  90. struct Bucket *findBucket(struct Bucket *head, const char *key)
  91. {
  92.     while (head) {
  93.         if (!strcmp(head->key, key)) {
  94.             return head;
  95.         }
  96.         head = head->next;
  97.     }
  98.  
  99.     return NULL;
  100. }
  101.  
  102. int replaceBucketValue(struct Bucket *bucket, const char *value)
  103. {
  104.     if (!bucket) {
  105.         return 0;
  106.     }
  107.  
  108.     char *newValue = malloc(strlen(value) + 1);
  109.     if (!newValue) {
  110.         return 0;
  111.     }
  112.  
  113.     strcpy(newValue, value);
  114.     free(bucket->value);
  115.     bucket->value = newValue;
  116.  
  117.     return 1;
  118. }
  119.  
  120. struct HashMap {
  121.     unsigned long bucketsSize;
  122.     struct Bucket **buckets;
  123. };
  124.  
  125. struct HashMap *createHashMap(unsigned long bucketsSize)
  126. {
  127.     struct HashMap *map = malloc(sizeof(struct HashMap));
  128.     if (!map) {
  129.         return NULL;
  130.     }
  131.  
  132.     map->bucketsSize = bucketsSize;
  133.     map->buckets = calloc(bucketsSize, sizeof(struct Bucket*));
  134.     if (!map->buckets) {
  135.         free(map);
  136.         return NULL;
  137.     }
  138.  
  139.     return map;
  140. }
  141.  
  142. void freeHashMap(struct HashMap *map)
  143. {
  144.     if (!map) {
  145.         return;
  146.     }
  147.  
  148.     for (unsigned long i = 0; i < map->bucketsSize; i++) {
  149.         freeBucketList(map->buckets[i]);
  150.     }
  151.  
  152.     free(map);
  153. }
  154.  
  155. int mapAddKeyValue(struct HashMap *map, const char *key, const char *value)
  156. {
  157.     if (!map) {
  158.         return 0;
  159.     }
  160.  
  161.     unsigned long hash = stringHash(key, map->bucketsSize);
  162.     struct Bucket *existingBucket = findBucket(map->buckets[hash], key);
  163.     if (existingBucket) {
  164.         return replaceBucketValue(existingBucket, value);
  165.     } else {
  166.         struct Bucket *newHead = addBucketToList(map->buckets[hash], key, value);
  167.         if (!newHead) {
  168.             return 0;
  169.         }
  170.         map->buckets[hash] = newHead;
  171.     }
  172.  
  173.     return 1;
  174. }
  175.  
  176. const char *mapGetValue(struct HashMap *map, const char *key)
  177. {
  178.     if (!map) {
  179.         return NULL;
  180.     }
  181.  
  182.     unsigned long hash = stringHash(key, map->bucketsSize);
  183.     struct Bucket *bucket = map->buckets[hash];
  184.  
  185.     if (!bucket) {
  186.         return NULL;
  187.     }
  188.  
  189.     if (!bucket->next) {
  190.         return bucket->value;
  191.     }
  192.  
  193.     bucket = findBucket(bucket, key);
  194.     if (bucket) {
  195.         return bucket->value;
  196.     } else {
  197.         return NULL;
  198.     }
  199. }
  200.  
  201. int main()
  202. {
  203.     struct HashMap *map = createHashMap(100);
  204.     if (!map) {
  205.         printf("Map creating failed\n");
  206.         return EXIT_FAILURE;
  207.     }
  208.  
  209.     const char *pairs[2][2] = { {"govno", "shit"}, {"kod", "code"} };
  210.  
  211.     for (unsigned int i = 0; i < 2; i++) {
  212.         mapAddKeyValue(map, pairs[i][0], pairs[i][1]);
  213.     }
  214.  
  215.     for (unsigned int i = 0; i < 2; i++) {
  216.         printf("map[%s] = %s\n", pairs[i][0], mapGetValue(map, pairs[i][0]));
  217.     }
  218.  
  219.     freeHashMap(map);
  220.     return EXIT_SUCCESS;
  221. }
Success #stdin #stdout 0s 9424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
map[govno] = shit
map[kod] = code
https://ideone.com/3v5Urq
language:
C99 (gcc 8.3)
created:
7 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!