aocc23

Advent of Code 2023
git clone git://www.tkruger.se/aocc23.git
Log | Files | Refs | README

dict.c (2393B)

      1 #include "dict.h"
      2 
      3 /*
      4 static inline void stack_ptr_init(stack_ptr *d) {
      5   d->nmemb = 0;
      6   d->alloc = DICT_DEFAULT_STACK_SIZE;
      7 
      8   d->data = calloc(d->alloc, sizeof(*(d->data)));
      9 }
     10 */
     11 
     12 static inline void stack_ptr_init_size(stack_ptr *d, const size_t alloc) {
     13   d->nmemb = 0;
     14   d->alloc = alloc;
     15 
     16   d->data = calloc(d->alloc, sizeof(*(d->data)));
     17 }
     18 
     19 static inline void stack_ptr_clear(stack_ptr *d) {
     20   d->nmemb = 0;
     21   free(d->data);
     22   d->data = NULL;
     23 }
     24 
     25 static inline void stack_ptr_push(stack_ptr *d, void *x) {
     26   if (d->alloc <= d->nmemb) {
     27     d->alloc <<= 1;
     28     d->data = realloc(d->data, d->alloc * sizeof(*(d->data)));
     29   }
     30 
     31   d->data[d->nmemb] = x;
     32   d->nmemb++;
     33 }
     34 
     35 /*
     36 static inline void* stack_ptr_get(const stack_ptr *d, const size_t i) {
     37   return d->data[i];
     38 }
     39 
     40 
     41 static inline void* stack_ptr_getlast(const stack_ptr *d) {
     42   return stack_ptr_get(d, d->nmemb - 1);
     43 }
     44 
     45 
     46 static inline void* stack_ptr_pop(stack_ptr *d) {
     47   if (d->nmemb == 0)
     48     return STACK_PTR_EMPTY_POP;
     49   void* r = stack_ptr_getlast(d);
     50   d->nmemb--;
     51   return r;
     52 }
     53 */
     54 
     55 void dict_init_size(dict_t *d, const size_t alloc) {
     56   d->nalloc = alloc;
     57   d->nelts = 0;
     58   d->keys = calloc(d->nalloc, sizeof(*d->keys));
     59   d->values = calloc(d->nalloc, sizeof(*d->values));
     60 
     61   size_t i;
     62   for (i = 0; i < d->nalloc; i++) {
     63     stack_sd_init_size(&d->keys[i], DICT_DEFAULT_STACK_SIZE);
     64     stack_ptr_init_size(&d->values[i], DICT_DEFAULT_STACK_SIZE);
     65   }
     66 }
     67 
     68 void dict_init(dict_t *d) { dict_init_size(d, DICT_DEFAULT_SIZE); }
     69 
     70 void dict_clear(dict_t *d) {
     71   size_t i;
     72   for (i = 0; i < d->nalloc; i++) {
     73     stack_sd_clear(&d->keys[i]);
     74     stack_ptr_clear(&d->values[i]);
     75   }
     76 
     77   d->nalloc = 0;
     78   d->nelts = 0;
     79   free(d->keys);
     80   free(d->values);
     81   d->keys = NULL;
     82   d->values = NULL;
     83 }
     84 
     85 void *dict_lookup(dict_t *d, sd k) {
     86   uint64_t h = sd_hash(&k);
     87   size_t i = h % d->nalloc;
     88   int stack_idx = stack_sd_lookup(&d->keys[i], k);
     89 
     90   if (stack_idx == STACK_SD_LOOKUP_NOT_FOUND) {
     91     return NULL;
     92   }
     93 
     94   return (d->values[i]).data[stack_idx];
     95 }
     96 
     97 #include <stdio.h>
     98 
     99 void dict_insert(dict_t *d, sd k, void *value) {
    100   uint64_t h = sd_hash(&k);
    101   size_t i = h % d->nalloc;
    102   int stack_idx = stack_sd_lookup(&d->keys[i], k);
    103 
    104   if (stack_idx == STACK_SD_LOOKUP_NOT_FOUND) {
    105     stack_sd_push(&(d->keys[i]), k);
    106     stack_ptr_push(&(d->values[i]), value);
    107     d->nelts++;
    108   } else {
    109     (d->values[i]).data[stack_idx] = value;
    110   }
    111 }