daily pastebin goal
63%
SHARE
TWEET

Untitled

a guest May 17th, 2018 111 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * A very simple dynamically-resized HashTable implementation in C.
  3.  */
  4.  
  5. #include <assert.h>
  6. #include <stdint.h>
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9.  
  10. #define GROWTH_FACTOR 3
  11. #define INITIAL_BUCKET_AMOUNT 50
  12. #define LOAD_FACTOR_THRESHOLD 0.75
  13.  
  14. typedef int (*ComparisonFunction)(const void *, const void *);
  15. typedef uint64_t Hash;
  16.  
  17. struct BucketNode {
  18.     const void *key;
  19.     void *value;
  20.  
  21.     Hash key_hash;
  22.  
  23.     struct BucketNode *previous;
  24. };
  25.  
  26. struct HashTable {
  27.     // public
  28.     size_t entries;
  29.  
  30.     // private
  31.     size_t bucket_amount;
  32.     struct BucketNode **buckets;
  33.     ComparisonFunction cmp_func;
  34. };
  35.  
  36. struct HashTable *hashtable_new(ComparisonFunction cmp_func) {
  37.     struct HashTable *ht = malloc(sizeof *ht);
  38.     ht->entries = 0;
  39.     ht->bucket_amount = INITIAL_BUCKET_AMOUNT;
  40.     ht->buckets = calloc(ht->bucket_amount, sizeof(struct BucketNode *));
  41.     ht->cmp_func = cmp_func;
  42.     return ht;
  43. }
  44.  
  45. static int should_grow(struct HashTable *ht) {
  46.     double load_factor = ((double)(ht->entries)) / ((double)(ht->bucket_amount));
  47.     return load_factor >= LOAD_FACTOR_THRESHOLD;
  48. }
  49.  
  50. static void prune(struct HashTable *ht) {
  51.     (void)(ht);
  52.     // TODO: Remove all useless entries in the hash-table.
  53. }
  54.  
  55. static void grow(struct HashTable *ht) {
  56.     // XXX: This is a very dumb growing algorithm.
  57.     prune(ht);
  58.     size_t new_bucket_amount = ht->bucket_amount * GROWTH_FACTOR;
  59.     struct BucketNode **new_buckets =
  60.         calloc(new_bucket_amount, sizeof(struct BucketNode *));
  61.  
  62.     for (size_t old_index = 0; old_index < ht->bucket_amount; ++old_index) {
  63.         struct BucketNode *bucket = ht->buckets[old_index];
  64.         if (!bucket)
  65.             continue;
  66.  
  67.         size_t new_index = bucket->key_hash % new_bucket_amount;
  68.  
  69.         struct BucketNode *previous;
  70.         while (bucket) {
  71.             previous = bucket->previous;
  72.             bucket->previous = new_buckets[new_index];
  73.             new_buckets[new_index] = bucket;
  74.             bucket = previous;
  75.         }
  76.     }
  77.  
  78.     ht->bucket_amount = new_bucket_amount;
  79.     ht->buckets = new_buckets;
  80. }
  81.  
  82. void hashtable_set(struct HashTable *ht, const void *key, Hash key_hash,
  83.         void *value) {
  84.     if (should_grow(ht)) {
  85.         grow(ht);
  86.     }
  87.  
  88.     size_t bucket_index = key_hash % ht->bucket_amount;
  89.     struct BucketNode *previous_bucket = ht->buckets[bucket_index];
  90.     struct BucketNode *bucket = malloc(sizeof *bucket);
  91.     assert(bucket != NULL);
  92.  
  93.     bucket->key = key;
  94.     bucket->value = value;
  95.  
  96.     bucket->key_hash = key_hash;
  97.     bucket->previous = previous_bucket;
  98.  
  99.     ht->buckets[bucket_index] = bucket;
  100.     ht->entries += 1;
  101. }
  102.  
  103. void *hashtable_get(struct HashTable *ht, const void *key, Hash key_hash) {
  104.     size_t bucket_index = key_hash % ht->bucket_amount;
  105.     struct BucketNode *bucket = ht->buckets[bucket_index];
  106.  
  107.     while (bucket != NULL) {
  108.         if (ht->cmp_func(key, bucket->key)) {
  109.             return bucket->value;
  110.         }
  111.  
  112.         bucket = bucket->previous;
  113.     }
  114.  
  115.     return NULL;
  116. }
  117.  
  118. void hashtable_free(struct HashTable *ht) {
  119.     for (size_t i = 0; i < ht->bucket_amount; ++i) {
  120.         struct BucketNode *bucket = ht->buckets[i];
  121.         while (bucket) {
  122.             struct BucketNode *previous = bucket->previous;
  123.             free(bucket);
  124.             bucket = previous;
  125.         }
  126.     }
  127.  
  128.     free(ht->buckets);
  129.     free(ht);
  130. }
  131.  
  132. static int int_cmp_func(const void *a, const void *b) {
  133.     return *((int *)a) == *((int *)b);
  134. }
  135.  
  136. int main(void) {
  137.     struct HashTable *ht = hashtable_new(int_cmp_func);
  138.  
  139.     for (int i = 0; i < 100; ++i) {
  140.         int *key = malloc(sizeof *key);
  141.         int *value = malloc(sizeof *value);
  142.  
  143.         *key = 0xDEAD + i;
  144.         *value = 0xBEEF + i;
  145.         Hash key_hash = *key;
  146.  
  147.         hashtable_set(ht, key, key_hash, value);
  148.     }
  149.  
  150.     for (int i = 0; i < 100; ++i) {
  151.         int *key = malloc(sizeof *key);
  152.         *key = 0xDEAD + i;
  153.         Hash key_hash = *key;
  154.         void *retrieved_value = hashtable_get(ht, key, key_hash);
  155.         assert(retrieved_value != NULL);
  156.         assert(*((int *)retrieved_value) == (0xBEEF + i));
  157.     }
  158.  
  159.     hashtable_free(ht);
  160.     puts("Everything is ok.");
  161.  
  162.     // NB: We leak the keys and values.
  163. }
RAW Paste Data
Top