libds/src/ht.c

#include "ht.h"
#include <stdlib.h>
#include <string.h>

unsigned long ht_default_hash_func(const void* data) {
  const unsigned long fnv_prime = 16777619;
  const unsigned long fnv_offset_basis = 2166136261;
  unsigned long hash;
  const char* string;
  hash = fnv_offset_basis;
  string = data;
  while (*string) {
    hash = hash * fnv_prime;
    hash = hash ^ (*(string++));
  }
  return hash;
}
int ht_default_cmp_func(const void* a, const void* b) { return strcmp(a, b) == 0; }
void* ht_default_copy_func(const void* from) {
  void* copy = malloc(sizeof(char) * (strlen(from) + 1));
  if (copy) {
    strcpy(copy, from);
  }
  return copy;
}
void ht_default_free_func(void* data) { free(data); }

void ht_init(ht* ht) {
  ht->cmp_func = ht_default_cmp_func;
  ht->copy_func = ht_default_copy_func;
  ht->free_func = ht_default_free_func;
  ht->hash_func = ht_default_hash_func;
  memset(ht->data, 0, sizeof(ht->data));
}
void ht_free(ht* ht) {
  int index = 0;
  for (; index < LIBDS_HT_SIZE; index++) {
    while (ht->data[index]) {
      ht_node* to_delete = ht->data[index];
      ht->data[index] = to_delete->next;
      ht->free_func(to_delete->key);
      free(to_delete);
    }
  }
  ht->cmp_func = NULL;
  ht->copy_func = NULL;
  ht->free_func = NULL;
  ht->hash_func = NULL;
}

libds_result ht_put(ht* ht, const void* key, void* data) {
  libds_result result = LIBDS_SUCCESS;
  ht_node* new_node = NULL;
  void* new_key = NULL;
  unsigned long key_int = ht->hash_func(key) % LIBDS_HT_SIZE;

  new_node = malloc(sizeof(*new_node));
  new_key = ht->copy_func(key);
  if (new_node && new_key) {
    new_node->data = data;
    new_node->key = new_key;
    new_node->next = ht->data[key_int];
    ht->data[key_int] = new_node;
  } else {
    free(new_node);
    free(new_key);
    result = LIBDS_MALLOC;
  }

  return result;
}
void* ht_get(const ht* ht, const void* key) {
  void* data = NULL;
  ht_node* search_node;
  unsigned long key_int = ht->hash_func(key) % LIBDS_HT_SIZE;

  search_node = ht->data[key_int];
  while (search_node && data == NULL) {
    if (ht->cmp_func(search_node->key, key)) {
      data = search_node->data;
    }
    search_node = search_node->next;
  }

  return data;
}
void* ht_find(const ht* ht, const void* key, void* data, compare_func compare) {
  void* found = NULL;
  ht_node* search_node;
  unsigned long key_int = ht->hash_func(key) % LIBDS_HT_SIZE;

  search_node = ht->data[key_int];
  while (search_node && found == NULL) {
    if (ht->cmp_func(search_node->key, key) &&
        compare(data, search_node->data)) {
      found = search_node->data;
    }
    search_node = search_node->next;
  }
  return found;
}
void ht_remove(ht* ht, const void* key) {
  ht_node** search_ptr;
  unsigned long key_int = ht->hash_func(key) % LIBDS_HT_SIZE;

  search_ptr = &ht->data[key_int];
  while (*search_ptr) {
    if (ht->cmp_func((*search_ptr)->key, key)) {
      ht_node* to_delete = *search_ptr;
      *search_ptr = (*search_ptr)->next;
      ht->free_func(to_delete->key);
      free(to_delete);
    } else {
      search_ptr = &(*search_ptr)->next;
    }
  }
}

int ht_foreach(const ht* ht, void* data, compare_func compare, foreach_func foreach,
               ...) {
  int index = 0;
  int return_code = 0;
  va_list args;
  for (; index < LIBDS_HT_SIZE && return_code == 0; index++) {
    ht_node* search_node = ht->data[index];
    while (search_node && return_code == 0) {
      if (compare(data, search_node->data)) {
        va_start(args, foreach);
        return_code = foreach (search_node->data, args);
        va_end(args);
      }
      search_node = search_node->next;
    }
  }
  return return_code;
}