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_NAME(dict_entry) {
   8     char *key;
   9     void *value;
  10     uint64_t key_hash;
  11 };
  12
  13 struct YACJS_NAME(dict) {
  14     struct YACJS_NAME(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_NAME(dict) *dict, int newsize);
  22 static void insert_helper(struct YACJS_NAME(dict) *dict, uint64_t hash,
  23     const char *key, void *value);
  24
  25 struct YACJS_NAME(dict) *YACJS_NAME(dict_make)() {
  26     struct YACJS_NAME(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_NAME(dict_destroy)(struct YACJS_NAME(dict) *dict,
  36     YACJS_NAME(dict_visitor) visitor) {
  37
  38     if(visitor) {
  39         for(int i = 0; i < dict->entries_size; i ++) {
  40             if(dict->entries[i].key) {
  41                 visitor(dict->entries[i].value);
  42                 free(dict->entries[i].key);
  43             }
  44         }
  45     }
  46     free(dict->entries);
  47     free(dict);
  48 }
  49
  50 void YACJS_NAME(dict_set)(struct YACJS_NAME(dict) *dict, const char *key,
  51     void *value) {
  52
  53     if(dict->entries_size == dict->entries_count) {
  54         resize(dict, dict->entries_size*2 + 1);
  55     }
  56
  57     uint64_t hash = string_hash(key);
  58     insert_helper(dict, hash, ystrdup(key), value);
  59 }
  60
  61 void *YACJS_NAME(dict_get)(struct YACJS_NAME(dict) *dict, const char *key) {
  62     uint64_t hash = string_hash(key);
  63     for(int i = 0; i < dict->entries_size; i ++) {
  64         int in = (i+hash) % dict->entries_size;
  65         if(!dict->entries[in].key) return NULL;
  66         if(dict->entries[in].key_hash == hash) return dict->entries[in].value;
  67     }
  68     return NULL;
  69 }
  70
  71 static char *ystrdup(const char *string) {
  72     return strcpy(malloc(strlen(string)+1), string);
  73 }
  74
  75 static uint64_t string_hash(const char *string) {
  76     uint64_t result = 14695981039346656037ULL;
  77
  78     while(*string) {
  79         result ^= *string;
  80         result *= 1099511628211ULL;
  81         string ++;
  82     }
  83
  84     return result;
  85 }
  86
  87 static void resize(struct YACJS_NAME(dict) *dict, int newsize) {
  88     struct YACJS_NAME(dict_entry) *oentries = dict->entries;
  89     int osize = dict->entries_size;
  90     dict->entries_size = newsize;
  91     dict->entries_count = 0;
  92     dict->entries = calloc(newsize, sizeof(oentries[0]));
  93
  94     for(int i = 0; i < osize; i ++) {
  95         if(!oentries[i].key) continue;
  96         insert_helper(dict, oentries[i].key_hash, oentries[i].key,
  97             oentries[i].value);
  98     }
  99 }
 100
 101 static void insert_helper(struct YACJS_NAME(dict) *dict, uint64_t hash,
 102     const char *key, void *value) {
 103     for(int i = 0; i < dict->entries_size; i ++) {
 104         int in = (i+hash) % dict->entries_size;
 105         if(dict->entries[in].key) continue;
 106         dict->entries[in].key = ystrdup(key);
 107         dict->entries[in].key_hash = hash;
 108         dict->entries[in].value = value;
 109         break;
 110     }
 111     dict->entries_count ++;
 112 }