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

typedef struct ztl_hashmap_kv ztl_hashmap_kv_t;
typedef ztl_hashmap_kv_t* ztl_hashmap_kv_p;
struct ztl_hashmap_kv{
    char* key;
    size_t value;
    ztl_hashmap_kv_p next;
};

typedef struct ztl_hashmap ztl_hashmap_t;
typedef ztl_hashmap_t* ztl_hashmap_p;
struct ztl_hashmap{
    int size;
    int capacity;
    ztl_hashmap_kv_p* array;
};

ztl_hashmap_p ztl_hashmap_init(int capacity);
void ztl_hashmap_put(ztl_hashmap_p map, char* key, size_t value);
size_t ztl_hashmap_get(ztl_hashmap_p map,char* key);
size_t ztl_hashmap_remove(ztl_hashmap_p map, char* key);
static void ztl_hashmap_resize(ztl_hashmap_p map, int type);
void ztl_hashmap_destory(ztl_hashmap_p map);
size_t ztl_hashmap_fnv1a(char* buf);

ztl_hashmap_p ztl_hashmap_init(int capacity)
{
    ztl_hashmap_p map = calloc(1, sizeof(ztl_hashmap_t));
    map->size = 0;
    map->capacity = capacity;
    map->array = calloc(capacity, sizeof(ztl_hashmap_kv_p));
    return map;
}

void ztl_hashmap_put(ztl_hashmap_p map, char* key, size_t value)
{
    int hash = ztl_hashmap_fnv1a(key) % map->capacity;
    ztl_hashmap_kv_p* kvp = map->array + hash;
    ztl_hashmap_kv_p kv = *kvp;
    if(kv){
        while(kv){
            if(0 == strcmp(key, kv->key)){
                kv->value = value;
                return;
            }
            if(kv->next){
                kv = kv->next;
            }else{
                ztl_hashmap_kv_p nkv = calloc(1, sizeof(ztl_hashmap_kv_t));
                nkv->key = key;
                nkv->value = value;
                kv->next = nkv;
                map->size++;
                break;
            }
        }
    }else{
        ztl_hashmap_kv_p nkv = calloc(1, sizeof(ztl_hashmap_kv_t));
        nkv->key = key;
        nkv->value = value;
        *kvp = nkv;
        map->size++;
    }
    ztl_hashmap_resize(map, 1);
}

int hashmap_getnum=0;
size_t ztl_hashmap_get(ztl_hashmap_p map,char* key)
{
    int hash = ztl_hashmap_fnv1a(key) % map->capacity;
    ztl_hashmap_kv_p* kvp = map->array+hash;
    ztl_hashmap_kv_p kv = *kvp;
    hashmap_getnum = 0;

    while(kv){ hashmap_getnum++;
        if(0 == strcmp(key, kv->key)){
            printf("hashmap get num: %d\n", hashmap_getnum);
            return kv->value;
        }
        if(kv->next){
            kv = kv->next;
        }else{
            break;
        }
        
    }
    
    printf("hashmap get num: %d\n", hashmap_getnum);
    return -1;
}

size_t ztl_hashmap_remove(ztl_hashmap_p map, char* key)
{
    int hash = ztl_hashmap_fnv1a(key) % map->capacity;
    ztl_hashmap_kv_p* kvp = map->array+hash;
    ztl_hashmap_kv_p kv = *kvp;

    ztl_hashmap_kv_p prev=0;
    while(kv){
        if(0 == strcmp(key, kv->key)){
            if(prev){
                if(kv->next)prev->next = kv->next;
                else prev->next = 0;
            }else{
                if(kv->next)*kvp = kv->next;
                else *kvp = 0;
            }
            size_t rv = kv->value;
            free(kv);
            map->size--;
            ztl_hashmap_resize(map, 0);
            return rv;
        }
        if(kv->next){
            prev = kv;
            kv = kv->next;
        }else{
            break;
        }
        
    }
    
    return -1;
}
//扩容与减容
static void ztl_hashmap_resize(ztl_hashmap_p map, int type)
{
    int osiz = map->size;
    int ocap = map->capacity;
    ztl_hashmap_kv_p* oarray = map->array;
    
    float s = osiz * 1.0;
    float c = ocap * 1.0;
    int ncap;
    if(type){
        if(s/c<0.8)return;
        ncap = ocap*1.51;
    }else{
        if(s/c>0.3)return;
        ncap = ocap*0.57;
    }
    map->size = 0;
    map->capacity = ncap;
    map->array = calloc(ncap, sizeof(ztl_hashmap_kv_p));
    //printf("ztl_hashmap_resize------->ocap: %d, osiz:%d, s/c: %f\n", ocap, osiz, s/c);
    
    for(int i=0; i<ocap; i++){
        ztl_hashmap_kv_p okv = *(oarray + i);
        while(okv){
            int hash = ztl_hashmap_fnv1a(okv->key) % map->capacity;
            ztl_hashmap_kv_p* kvp = map->array + hash;
            ztl_hashmap_kv_p kv = *kvp;
            if(kv){
                while(kv->next){
                    kv = kv->next;
                }
                kv->next = okv;
                map->size++;
            }else{
                *kvp = okv;
                map->size++;
            }
            ztl_hashmap_kv_p tkv = okv->next;
            okv->next = 0;
            okv = tkv;
        }
    }
    free(oarray);
}

void ztl_hashmap_destory(ztl_hashmap_p map)
{
    for(int i=0; i<map->capacity; i++){
        ztl_hashmap_kv_p kv = *(map->array + i);
        while(kv){
            ztl_hashmap_kv_p tkv = kv->next;
            free(kv);
            kv = tkv;
        }
    }
    
    free(map->array);
    free(map);
}

size_t ztl_hashmap_fnv1a(char* buf)
{
    size_t oft = 2166136261U;
    size_t prm = 16777619U;
    char* bp = buf;
     for(; *bp; ++bp) {
        oft ^= (size_t) *bp;
        oft *= prm;
    }
    return oft; 
}

int main(int argc, char** argv)
{
    ztl_hashmap_p map = ztl_hashmap_init(23);
    ztl_hashmap_put(map, "长烟一空",  111111);
    ztl_hashmap_put(map, "上下天光",  222222222);
    ztl_hashmap_put(map, "一碧万顷",  333333333);
    
    ztl_hashmap_put(map, "长烟一空", 7777777);

    ztl_hashmap_put(map, "abc", 1234);
    ztl_hashmap_put(map, "aac", 2345);
    ztl_hashmap_put(map, "acc", 3456);
    ztl_hashmap_put(map, "acca", 4567);
    
    printf("000----hashmap cap: %d, size: %d\n", map->capacity, map->size);
    int csn = 93;
    char cs[csn][16];
    
    for(int i=0; i<csn; i++){
        sprintf( cs[i], "mapkey%d", i);
        ztl_hashmap_put(map, cs[i], i+1);
    }
    
    printf("111----hashmap cap: %d, size: %d\n", map->capacity, map->size);
    
    printf("pl: %d, pr: %d, pb: %d\n\n",  
        (int)ztl_hashmap_get(map, "长烟一空"),  
        (int)ztl_hashmap_get(map, "上下天光"), 
        (int)ztl_hashmap_get(map, "一碧万顷")
    );
    
    printf(" %d, %d, %d, %d, %d\n\n",  
        (int)ztl_hashmap_get(map, "abc"),  
        (int)ztl_hashmap_get(map, "aac"), 
        (int)ztl_hashmap_get(map, "acc"),
        (int)ztl_hashmap_get(map, "acca"),
        (int)ztl_hashmap_get(map, "mapkey11")
    );
    
    for(int i=0; i<77; i++){
        ztl_hashmap_remove(map, cs[i]);
    }
    
    ztl_hashmap_remove(map, "acca");
    
    printf(" %d, %d, %d, %d, %d\n\n",  
        (int)ztl_hashmap_get(map, "abc"),  
        (int)ztl_hashmap_get(map, "aac"), 
        (int)ztl_hashmap_get(map, "acc"),
        (int)ztl_hashmap_get(map, "acca"),
        (int)ztl_hashmap_get(map, "mapkey11")
    );

    
    printf("-------------------\n");
    for(int i=0; i<map->capacity; i++){
        ztl_hashmap_kv_p kv = *(map->array + i);
        while(kv){
            printf("%s = %d\n", kv->key, (int)kv->value);
            kv = kv->next;
        }
        
    }
    
    printf("222----hashmap cap: %d, size: %d\n", map->capacity, map->size);
    
    ztl_hashmap_destory(map);
    
    return 0;
}