ordered_map.c

/**
 * ordered_map.c
 *
 * A custum ordered map implementation bulit on unordered map by storing an array
 * of pointers to the chaining node in the lists.
 *
 * Author: Haoling Zhou
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ordered_map.h"
//#include "dynamic_array.h"    already included in the ordered_map.h

//#define DEBUG
#define PRIME 101
#define A 53
#define B 79

int hash(char *key, int key_len, int table_size) {
  int key_val = 0;

  for (int i = 0; i < key_len; i++) {
    key_val += key[i];
  } 

  return ((A * key_val + B) % PRIME) % table_size;
}

void insert(chain_node *node, ordered_map *map) { 
  int idx = hash(node->key, strlen(node->key), map->size);

#ifdef DEBUG
  printf("node key: %s\n", node->key); 
  printf("hash value: %d\n", idx); 
#endif 

  if (idx < 0 || idx >= map->size) {
    printf("Error: idx out of bound\n");
    exit(EXIT_FAILURE);
  }

  if (map->lists[idx]->head == NULL) {
    map->lists[idx]->head = node;
  } else {
    chain_node *tmp = map->lists[idx]->head;
    map->lists[idx]->head = node;
    node->next = tmp;
    tmp->prev = node;
  }

  /* Track order */
  push_back(map->node_list, node);

#ifdef DEBUG
  printf("New head node key: %s\n", map->lists[idx]->head->key); 
  if (map->lists[idx]->head->next != NULL)
    printf("Old head node key: %s\n", map->lists[idx]->head->next->key); 
#endif 
}

void *search(char *key, ordered_map *map) {
  int idx = hash(key, strlen(key), map->size); 

  chain_node *cur = map->lists[idx]->head;
  while (strcmp(key, cur->key) != 0 && cur != NULL)
    cur = cur->next;

  if (cur == NULL)
    return NULL;
  
  return cur->val;
}