README.md

C Hash Map

• 负载计算自动扩容

• 加速哈希比较查找

• 更小的实现代码

• 支持多个平台构建

compile

root@localhost:~/Map$ cc -o main main.c -Lbuild -Wl,-rpath,build -lmap -g -O0 && ./main

demo

#include <stdio.h>

#include "map.h"

int main(int argc, char const *argv[])
{

  Map *m = map_new();

  map_set(m, "a", "123");

  map_set(m, "b", "456");

  map_set(m, "c", "789");


  printf("%s\n", (char*) map_get(m, "a"));

  printf("%s\n", (char*) map_get(m, "b"));

  printf("%s\n", (char*) map_get(m, "c"));


  printf("unset %d\n", map_set(m, "a", NULL));

  printf("unset %d\n", map_set(m, "b", NULL));

  printf("unset %d\n", map_set(m, "c", NULL));

  printf("unset %d\n", map_set(m, "a", NULL));

  printf("unset %d\n", map_set(m, "b", NULL));

  printf("unset %d\n", map_set(m, "c", NULL));

  printf("%p\n", map_get(m, "a"));

  printf("%p\n", map_get(m, "b"));

  printf("%p\n", map_get(m, "c"));


  map_free(m);

  while (1)
  {
    for (size_t i = 0; i < 1000000; i++)
    {
      Map *m = map_new();

      map_set(m, "a", "123");

      map_set(m, "b", "456");

      map_set(m, "c", "789");

      map_set(m, "a", NULL);

      map_set(m, "b", NULL);

      map_set(m, "c", NULL);
      
      map_free(m);
    }

    // sleep(1);
  }
  
  return 0;
}

CMakeLists.txt

message("======================================")
message("Project Name   : HashMap")
message("Author  Name   : CandyMi")
message("Author  Email  : [email protected]")
message("Author  Github : github.com/CandyMi")
message("======================================")

# 最低版本号
cmake_minimum_required(VERSION 2.8...3.13)

# 项目名称
project("HashMap" C)

if(${CMAKE_SYSTEM_NAME} MATCHES "Darwin")
  set(CMAKE_MACOSX_RPATH 1)
else()
  set(CMAKE_BUILD_WITH_INSTALL_RPATH TRUE)
endif()

# 使用指定的编译标准
set(CMAKE_C_STANDARD_REQUIRED ON)
set(CMAKE_C_EXTENSIONS OFF)
set(CMAKE_C_STANDARD 99)

add_library(map-static STATIC map.c)
add_library(map SHARED map.c)

set_target_properties(
  map-static PROPERTIES 
    PREFIX "lib"
    OUTPUT_NAME   "map"
    map PROPERTIES
    PREFIX "lib"
    OUTPUT_NAME   "map"
)

map.c

/*
**  LICENSE: BSD
**  Author: CandyMi[https://github.com/candymi]
*/

#include "map.h"

#ifndef and
  #define and &&
#endif

#ifndef or
  #define or ||
#endif

#define map_ivalue (0x811c9dc5)

#define map_eq(p, hash, key, kl) ((p)->hash == (hash) and !memcmp((p)->key, (key), (kl)))

#define map_need_resize(len, cap, factor) ((cap) >= ((uint32_t)((len) * ((factor) * 0.01))))

typedef struct slot {
  uint64_t hash;
  char* key;
  void* data;
  struct slot* next;
} Slot;

struct map {
  uint32_t len;
  uint32_t cap;
  uint32_t factor;
  struct slot** list;
};

static inline void map_hash(const char* text, uint32_t tsize, uint64_t *hash) {
  while (tsize--)
    *hash ^= ((*hash << 5) + (*hash >> 2) + (text[tsize]));
}

static inline void map_rehash(Slot** nlist, uint32_t nlen, Slot** olist, uint32_t olen) {
  Slot* tmp = NULL; uint32_t idx, i;
  for (i = 0; i < olen; i++)
  {
    Slot* slot = olist[i];
    while (slot)
    {
      tmp = slot->next;
      idx = (slot->hash) % nlen;
      Slot* nslot = nlist[idx];
      if (!nslot)
      {
        nlist[idx] = slot;
        slot->next = NULL;
      }
      else
      {
        slot->next = nslot;
        nlist[idx] = slot;
      }
      slot = tmp;
    }
  }
}

static inline void map_resize(Map* m) {
  uint32_t len = m->len;
  if (!len)
    len = DEFAULT_MAP_LEN;
  else
    len <<= DEFAULT_MAP_OFFSET;
  
  Slot** list = map_xmalloc(sizeof(Slot *) * len);
  /* resize failed must safety and harmless. */
  if (!list)
    return;
  memset(list, 0x0, len);

  /* maybe need rehash. */
  if (m->list) {
    map_rehash(list, len, m->list, m->len);
    map_xfree(m->list);
  }
  m->list = list;
  m->len = len;
}

Map* map_new() {
  Map* m = map_xmalloc(sizeof(Map));
  if (!m)
    return NULL;
  m->list = NULL;
  m->len = m->cap = 0;
  m->factor = DEFAULT_MAP_FACTOR;
  return m;
} 

Slot* slot_new(uint64_t hash, const char* key, uint32_t ksize, void* data) {
  Slot* o = map_xmalloc(sizeof(Slot));
  o->key = map_xmalloc(ksize + 1); memcpy(o->key, key, ksize); o->key[ksize] = '\x00';
  o->next = NULL; o->data = data; o->hash = hash;
  return o;
}

void map_free(Map* m) {
  if (m->list) {
    uint32_t i; Slot* tmp = NULL;
    for (i = 0; i < m->len; i++)
    {
      Slot* slot = m->list[i];
      while (slot)
      {
        tmp = slot->next;
        map_xfree(slot->key);
        map_xfree(slot);
        slot = tmp;
      }
      m->list[i] = NULL;
    }
    map_xfree(m->list); // map_xfree
  }
  map_xfree(m); // map_xfree
}

void* map_get(Map* m, const char *key) {
  if (!m or !key or m->cap == 0)
    return NULL;
  
  /* Calculate hash value */
  uint32_t ksize = (uint32_t)strlen(key);
  uint64_t hash = map_ivalue;
  map_hash(key, ksize, &hash);
  
  Slot* slot = m->list[(hash) % m->len];
  if (!slot)
    return NULL;

  while (slot)
  {
    if (map_eq(slot, hash, key, ksize))
      return slot->data;
    slot = slot->next;
  }
  return NULL;
}

int map_set(Map* m, const char *key, void *value) {
  if (!m or !key)
    return -1;

  /* Calculate hash value */
  uint32_t ksize = (uint32_t)strlen(key);
  uint64_t hash = map_ivalue;
  map_hash(key, ksize, &hash);

  /* init map list */
  if (!m->list)
    map_resize(m);

  uint32_t idx = (hash) % m->len;
  Slot* slot = m->list[idx];

  /* Remove ? */
  if (!value) {  /* Return 0 if not found. */
    if (!slot)
      return 0;
    Slot* prev = NULL;
    while (slot)
    {
      if (map_eq(slot, hash, key, ksize))
      {
        if (!prev)
          m->list[idx] = slot->next;
        else
          prev->next = slot->next;
        map_xfree(slot->key); map_xfree(slot); m->cap--;
        return 1;
      }
      prev = slot; slot = slot->next;
    }
    return 0;
  }

  /* Checking resize and rehash. */
  if (map_need_resize(m->len, m->cap, m->factor))
    map_resize(m);

  /* Insert */
  Slot* o = slot_new(hash, key, ksize, value);
  o->next = slot;
  m->list[idx] = o;

  /* Store capacity */
  m->cap++;
  return 1;
}

map.h

/*
**  LICENSE: BSD
**  Author: CandyMi[https://github.com/candymi]
*/

#ifndef __MAP_H__
#define __MAP_H__

#include <stdint.h>
#include <string.h>
#include <stdlib.h>

#ifndef map_xmalloc
  #define map_xmalloc malloc
#endif

#ifndef map_xfree
  #define map_xfree free
#endif

#ifndef DEFAULT_MAP_OFFSET
  #define DEFAULT_MAP_OFFSET (2)
#endif

#ifndef DEFAULT_MAP_LEN
  #define DEFAULT_MAP_LEN (128)
#endif

#ifndef DEFAULT_MAP_FACTOR
  #define DEFAULT_MAP_FACTOR (75)
#endif

#ifdef _WIN32
  #ifndef export
    #define export __declspec(dllexport)
  #endif
#else
  #ifndef export
    #define export extern
  #endif
#endif

#ifdef __cplusplus
  extern "C" {
#endif

struct map;
typedef struct map Map;

/* Create hash map */
export Map* map_new();

/* Destory hash map */
export void map_free(Map* m);

/* Get Value from key */
export void* map_get(Map* m, const char *key);

/* Set or Unset (if key is null) */
export int map_set(Map* m, const char *key, void *value);

#ifdef __cplusplus
  }
#endif

#endif