src/yacjs_dict.c

   1 #include <stdlib.h>
   2 #include <stdint.h>
   3 #include <string.h>
   4
   5 #include "yacjs_dict.h"
   6
   7 struct yacjs_dict_entry {
   8     char *key;
   9     void *value;
  10     uint64_t key_hash;
  11 };
  12
  13 struct yacjs_dict {
  14     struct yacjs_dict_entry *entries;
  15     int entries_size;
  16     int entries_count;
  17 };
  18
  19 static char *ystrdup(const char *string);
  20 static uint64_t string_hash(const char *string);
  21 static void resize(struct yacjs_dict *dict, int newsize);
  22 static void insert_helper(struct yacjs_dict *dict, uint64_t hash,
  23     const char *key, void *value);
  24
  25 struct yacjs_dict *yacjs_dict_make() {
  26     struct yacjs_dict *result = malloc(sizeof(*result));
  27
  28     result->entries = NULL;
  29     result->entries_size = 0;
  30     result->entries_count = 0;
  31
  32     return result;
  33 }
  34
  35 void yacjs_dict_destroy(struct yacjs_dict *dict, yacjs_dict_visitor visitor) {
  36     if(visitor) {
  37         for(int i = 0; i < dict->entries_size; i ++) {
  38             if(dict->entries[i].key) {
  39                 visitor(dict->entries[i].value);
  40                 free(dict->entries[i].key);
  41             }
  42         }
  43     }
  44     free(dict->entries);
  45     free(dict);
  46 }
  47
  48 void yacjs_dict_set(struct yacjs_dict *dict, const char *key,
  49     void *value) {
  50
  51     if(dict->entries_size == dict->entries_count) {
  52         resize(dict, dict->entries_size*2 + 1);
  53     }
  54
  55     uint64_t hash = string_hash(key);
  56     insert_helper(dict, hash, ystrdup(key), value);
  57 }
  58
  59 void *yacjs_dict_get(struct yacjs_dict *dict, const char *key) {
  60     uint64_t hash = string_hash(key);
  61     for(int i = 0; i < dict->entries_size; i ++) {
  62         int in = (i+hash) % dict->entries_size;
  63         if(!dict->entries[in].key) return NULL;
  64         if(dict->entries[in].key_hash == hash) return dict->entries[in].value;
  65     }
  66     return NULL;
  67 }
  68
  69 static char *ystrdup(const char *string) {
  70     return strcpy(malloc(strlen(string)+1), string);
  71 }
  72
  73 static uint64_t string_hash(const char *string) {
  74     uint64_t result = 14695981039346656037ULL;
  75
  76     while(*string) {
  77         result ^= *string;
  78         result *= 1099511628211ULL;
  79         string ++;
  80     }
  81
  82     return result;
  83 }
  84
  85 static void resize(struct yacjs_dict *dict, int newsize) {
  86     struct yacjs_dict_entry *oentries = dict->entries;
  87     int osize = dict->entries_size;
  88     dict->entries_size = newsize;
  89     dict->entries_count = 0;
  90     dict->entries = calloc(newsize, sizeof(oentries[0]));
  91
  92     for(int i = 0; i < osize; i ++) {
  93         if(!oentries[i].key) continue;
  94         insert_helper(dict, oentries[i].key_hash, oentries[i].key,
  95             oentries[i].value);
  96     }
  97 }
  98
  99 static void insert_helper(struct yacjs_dict *dict, uint64_t hash,
 100     const char *key, void *value) {
 101     for(int i = 0; i < dict->entries_size; i ++) {
 102         int in = (i+hash) % dict->entries_size;
 103         if(dict->entries[in].key) continue;
 104         dict->entries[in].key = ystrdup(key);
 105         dict->entries[in].key_hash = hash;
 106         dict->entries[in].value = value;
 107         break;
 108     }
 109     dict->entries_count ++;
 110 }