size, ht->cap, ht_prime_mod[ht->modid]); Node *hd = ht->head, *cur = hd->next; while (cur != hd) { "> size, ht->cap, ht_prime_mod[ht->modid]); Node *hd = ht->head, *cur = hd->next; while (cur != hd) { "> size, ht->cap, ht_prime_mod[ht->modid]); Node *hd = ht->head, *cur = hd->next; while (cur != hd) { "> 
// ==================== hash table =======================
typedef int HT_KT;
typedef struct {
    int lev;
    int val;
} kt;
// 值类型
typedef kt HT_VT;
const unsigned int ht_prime_mod[] = {13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301, 8388593, 16777213, 33554393, 67108859};
const unsigned int ht_pow_mod[] = {16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864};
typedef struct Node {
    unsigned int h;
    HT_KT key;
    HT_VT val;
    struct Node* next;
    struct Node* prev;
} Node;

typedef struct {
    Node** table;
    int size;
    int cap;
    int modid;
    Node* head;
} hashtable;

// modfy
void ht_print(hashtable* ht) {
    // your code
    printf("hashtable size:%d, cap:%d, mod:%d", ht->size, ht->cap, ht_prime_mod[ht->modid]);
    Node *hd = ht->head, *cur = hd->next;
    while (cur != hd) {
        if (cur->h != cur->prev->h) {
            printf("\\nbucket hash %d:", cur->h);
        }
        printf(" [key=%d, lev=%d, val=%d]", cur->key, cur->val.lev, cur->val.val); // modify
        cur = cur->next;
    }
    printf("\\n");
}

unsigned int ht_hash(hashtable* ht, HT_KT key) {
    unsigned int mod = ht_prime_mod[ht->modid];
    return (mod+(key^key>>16)%mod)%mod;
}

hashtable* ht_new() {
    hashtable* ht = (hashtable*)malloc(sizeof(hashtable));
    assert(ht != NULL);
    
    int cap = 16;
    ht->table = (Node**)malloc(cap * sizeof(Node*));
    assert(ht->table != NULL);
    memset(ht->table, 0, cap*sizeof(Node*));
    
    ht->head = (Node*)malloc(sizeof(Node));
    assert(ht->head != NULL);
    ht->head->prev = ht->head->next = ht->head;
    ht->head->h = -1;

    ht->size = 0;
    ht->cap = cap;
    ht->modid = 0;

    return ht;
}

void ht_del(hashtable* ht) {
    free(ht->table);
    free(ht->head);
    free(ht);
}

bool ht_has(hashtable* ht, HT_KT key) {
    unsigned int hkey = ht_hash(ht, key);
    Node* hnode = ht->table[hkey];
    if(hnode == NULL) return 0;
    while (hnode->h == hkey) {
        if (hnode->key == key) 
            return 1;
        hnode = hnode->next;
    }
    return 0;
}

void ht_add(hashtable* ht, Node* node) {
    Node *hnode = ht->head;   
    if (ht->table[node->h]) {
        hnode = ht->table[node->h];
    }
    node->prev = hnode->prev;
    node->next = hnode;
    node->prev->next = node;
    node->next->prev = node;
    ht->table[node->h] = node;

    ht->size += 1;
}

void ht_set(hashtable* ht, HT_KT key, HT_VT val) {
    // 检测已经存在key
    unsigned int hkey = ht_hash(ht, key);
    Node* hnode = ht->table[hkey];
    while (hnode != NULL && hnode->h == hkey) {
        if (hnode->key == key) {
            hnode->val = val;
            return ;
        }
        hnode = hnode->next;
    }
    // 不存在
    Node *node = (Node*)malloc(sizeof(Node));
    node->h = hkey;
    node->key = key;
    node->val = val;
    ht_add(ht, node);
    // 达到cap扩容二倍
    if (ht->size > ht->cap) {
        ht->size = 0;
        ht->cap *= 2;
        ht->modid += 1;
        free(ht->table);
        ht->table = (Node**)malloc(ht->cap * sizeof(Node*));
        memset(ht->table, 0, ht->cap*sizeof(Node*));
        // head自成环，链表剩余节点重新插入
        Node *hnode = ht->head, *remain = hnode->next, *nxt;
        hnode->prev->next = NULL;
        hnode->prev = hnode;
        hnode->next = hnode;
        
        while (remain != NULL) {
            nxt = remain->next;
            remain->h = ht_hash(ht, remain->key);
            ht_add(ht, remain);
            remain = nxt;
        }
    }
}

HT_VT ht_get(hashtable* ht, HT_KT key) {
    unsigned int hkey = ht_hash(ht, key);
    Node* hnode = ht->table[hkey];
    assert(hnode != NULL);

    while (hnode->h == hkey) {
        if (hnode->key == key) 
            return hnode->val;
        hnode = hnode->next;
    }
    assert(0);
}

void ht_pop(hashtable* ht, HT_KT key) {
    unsigned int hkey = ht_hash(ht, key);
    Node* hnode = ht->table[hkey];
    assert(hnode != NULL);

    while (hnode->h == hkey) {
        if (hnode->key == key) 
            break;
        hnode = hnode->next;
    }
    assert(hnode->key == key);
    hnode->prev->next = hnode->next;
    hnode->next->prev = hnode->prev;
    if (hnode == ht->table[hkey]) {
        ht->table[hkey] = hnode->next;
        if (ht->table[hkey]->h != hkey)
            ht->table[hkey] = NULL;
    }
    free(hnode);
    ht->size -= 1;
}