map.c

map.c

#include "array.c"
#include <stddef.h>
#include <stdint.h>

// Must be a prime number.
#define MAP_SIZE 1009
// Another prime number, but less than MAP_SIZE.
#define MAP_PRIME 31

typedef struct map_item {
  char *key;
  void *value;
} map_item;

typedef struct map {
  map_item **items;
  size_t cap;
  // used indexes as an array of uint32_t.
  array *idx;
} map;

map *new_map() {
  // use a prime number above 1,000 as default cap.
  map *m = malloc(sizeof(map));
  m->items = calloc(MAP_SIZE, sizeof(map_item *));
  m->cap = MAP_SIZE;
  m->idx = new_array();
  return m;
};

static uint32_t primary_hash(char *key) {
  int hash = 0;
  for (int i = 0; key[i] != '\0'; i++) {
    hash = (hash * MAP_PRIME + key[i]) % MAP_SIZE;
  }
  return hash;
}

static uint32_t secondary_hash(uint32_t primary_hash) {
  return MAP_PRIME - (primary_hash % MAP_PRIME);
}

char *copy_key(char *key) {
  size_t len = strlen(key);
  char *copy = malloc(sizeof(char) * (len + 1));
  strcpy(copy, key);
  return copy;
}

void store_index(map *m, uint32_t index) {
  uint32_t *idx = malloc(sizeof(uint32_t));
  *idx = index;
  array_push(m->idx, idx);
}

static void grow_map(map *m) {
  size_t old_cap = m->cap;
  size_t new_cap = old_cap * 2;

  map_item **tmp = realloc(m->items, sizeof(map_item *) * new_cap);
  if (tmp == NULL) {
    err(EXIT_FAILURE, "realloc failure on grow_map()");
  }

  m->items = tmp;
  m->cap = new_cap;

  map_item **begins_at = tmp + old_cap;
  size_t bytes = sizeof(map_item *) * (new_cap - old_cap);
  memset(begins_at, 0, bytes);
}

void map_push(map *m, char *key, void *data) {
  // TODO: Check load factor before inserting.
  uint32_t idx = primary_hash(key);
  uint32_t step = secondary_hash(idx);

  for (size_t i = 0; m->items[idx] != NULL; i++) {
    idx = idx + (i * step);
    if (idx >= m->cap) {
      grow_map(m);
    }
  }

  store_index(m, idx);

  map_item *item = malloc(sizeof(map_item));
  item->key = copy_key(key);
  item->value = data;

  m->items[idx] = item;
}

map_item *map_get(map *m, char *key) {
  uint32_t idx = primary_hash(key);
  uint32_t step = secondary_hash(idx);

  for (size_t i = 0; m->items[idx] != NULL; i++) {
    idx = idx + (i * step);
    map_item *item = m->items[idx];
    if (item != NULL && strcmp(key, item->key) == 0) {
      return item;
    }
  }

  return NULL;
}

void free_map(map *m, bool free_values) {
  uint32_t **items = (uint32_t **)m->idx->items;
  for (size_t i = 0; i < m->idx->len; i++) {
    uint32_t idx = *items[i];
    map_item *item = m->items[idx];
    free(item->key);
    if (free_values) {
      free(item->value);
    }
    free(item);
  }
  free_array(m->idx, true);
  free(m->items);
  free(m);
}

void free_map_custom(map *m, bool free_values, void(values_freer)(void*)) {
  uint32_t **items = (uint32_t **)m->idx->items;
  for (size_t i = 0; i < m->idx->len; i++) {
    uint32_t idx = *items[i];
    map_item *item = m->items[idx];
    free(item->key);
    if (free_values) {
      if (values_freer) {
        values_freer(item->value);
      };
      free(item->value);
    }
    free(item);
  }
  free_array(m->idx, true);
  free(m->items);
  free(m);
}

#ifdef DEBUG_MAP

#include <stdio.h>

void insert_items_for_testing(map *m) {
  int sample_size = 100;
  for (int i = 0; i < sample_size; i++) {
    int len = snprintf(NULL, 0, "%d", i);
    char *buff = malloc(sizeof(char) * (len + 1));
    snprintf(buff, len + 1, "%d", i);
    int *data = malloc(sizeof(int));
    *data = i;
    map_push(m, buff, data);
    free(buff);
  }
}

void print_items_for_testing(map *m) {
  for (int i = 0; i < m->idx->len + 1; i++) {
    int len = snprintf(NULL, 0, "%d", i);
    char *key = malloc(sizeof(char) * (len + 1));
    snprintf(key, len + 1, "%d", i);

    map_item *item = map_get(m, key);
    if (item == NULL) {
      printf("Key not found.\n");
    } else {
      printf("{'%s': %d}\n", item->key, *(int *)item->value);
    }
    free(key);
  }
}

int main() {
  for (size_t i = 0; i < 1; i++) {
    map *m = new_map();
    insert_items_for_testing(m);
    print_items_for_testing(m);
    free_map(m, true);
  }
}

#endif