void do_item_unlink(item *it) {
    if ((it->it_flags & ITEM_LINKED) != 0) {
        it->it_flags &= ~ITEM_LINKED;
        STATS_LOCK();
        stats.curr_bytes -= ITEM_ntotal(it);
        stats.curr_items -= 1;
        STATS_UNLOCK();
        assoc_delete(ITEM_key(it), it->nkey);
        item_unlink_q(it);
        if (it->refcount == 0) item_free(it);
    }
}

/* Copy/paste to avoid adding two extra branches for all common calls, since
 * _nolock is only used in an uncommon case. */
void do_item_update_nolock(item *it) {
    MEMCACHED_ITEM_UPDATE(ITEM_key(it), it->nkey, it->nbytes);
    if (it->time < current_time - ITEM_UPDATE_INTERVAL) {
        assert((it->it_flags & ITEM_SLABBED) == 0);

        if ((it->it_flags & ITEM_LINKED) != 0) {
            item_unlink_q(it);
            it->time = current_time;
            item_link_q(it);
        }
    }
}

/*
 * Stores an item in the cache (high level, obeys set/add/replace semantics)
 * 在缓存中存储一个数据项
 */
enum store_item_type store_item(item *item, int comm, conn* c) {
    enum store_item_type ret;
    uint32_t hv;

    // 先做一次哈希计算
    hv = hash(ITEM_key(item), item->nkey, 0);

    item_lock(hv);
    // 正真存储数据的方法 do_store_item()
    ret = do_store_item(item, comm, c, hv);
    item_unlock(hv);
    return ret;
}

/* Bump the last accessed time, or relink if we're in compat mode */
void do_item_update(item *it) {
    MEMCACHED_ITEM_UPDATE(ITEM_key(it), it->nkey, it->nbytes);
    if (it->time < current_time - ITEM_UPDATE_INTERVAL) {
        assert((it->it_flags & ITEM_SLABBED) == 0);

        if ((it->it_flags & ITEM_LINKED) != 0) {
            it->time = current_time;
            if (!settings.lru_maintainer_thread) {
                item_unlink_q(it);
                item_link_q(it);
            }
        }
    }
}

/* This is walking the line of violating lock order, but I think it's safe.
 * If the LRU lock is held, an item in the LRU cannot be wiped and freed.
 * The data could possibly be overwritten, but this is only accessing the
 * headers.
 * It may not be the best idea to leave it like this, but for now it's safe.
 * FIXME: only dumps the hot LRU with the new LRU's.
 */
char *item_cachedump(const unsigned int slabs_clsid, const unsigned int limit, unsigned int *bytes) {
    unsigned int memlimit = 2 * 1024 * 1024;   /* 2MB max response size */
    char *buffer;
    unsigned int bufcurr;
    item *it;
    unsigned int len;
    unsigned int shown = 0;
    char key_temp[KEY_MAX_LENGTH + 1];
    char temp[512];
    unsigned int id = slabs_clsid;
    if (!settings.lru_maintainer_thread)
        id |= COLD_LRU;

    pthread_mutex_lock(&lru_locks[id]);
    it = heads[id];

    buffer = malloc((size_t)memlimit);
    if (buffer == 0) {
        return NULL;
    }
    bufcurr = 0;

    while (it != NULL && (limit == 0 || shown < limit)) {
        assert(it->nkey <= KEY_MAX_LENGTH);
        if (it->nbytes == 0 && it->nkey == 0) {
            it = it->next;
            continue;
        }
        /* Copy the key since it may not be null-terminated in the struct */
        strncpy(key_temp, ITEM_key(it), it->nkey);
        key_temp[it->nkey] = 0x00; /* terminate */
        len = snprintf(temp, sizeof(temp), "ITEM %s [%d b; %llu s]\r\n",
                       key_temp, it->nbytes - 2,
                       it->exptime == 0 ? 0 :
                       (unsigned long long)it->exptime + process_started);
        if (bufcurr + len + 6 > memlimit)  /* 6 is END\r\n\0 */
            break;
        memcpy(buffer + bufcurr, temp, len);
        bufcurr += len;
        shown++;
        it = it->next;
    }

    memcpy(buffer + bufcurr, "END\r\n", 6);
    bufcurr += 5;

    *bytes = bufcurr;
    pthread_mutex_unlock(&lru_locks[id]);
    return buffer;
}

shadow_item* create_shadow_item(item *it)
{
    shadow_item* shadow_it = (shadow_item*)malloc(sizeof(shadow_item));
    assert(shadow_it && it);
    shadow_it->key = (char*)malloc(it->nkey*sizeof(char));
    memcpy(shadow_it->key, ITEM_key(it), it->nkey);
    shadow_it->nkey = it->nkey;
    shadow_it->next = NULL;
    shadow_it->prev = NULL;
    shadow_it->h_next = NULL;
    shadow_it->slabs_clsid = it->slabs_clsid;

    return shadow_it;
}

static void *assoc_maintenance_thread(void *arg) {

    while (do_run_maintenance_thread) {
        int ii = 0;

        /* Lock the cache, and bulk move multiple buckets to the new
         * hash table. */
        mutex_lock(&cache_lock);

        for (ii = 0; ii < hash_bulk_move && expanding; ++ii) {
            item *it, *next;
            int bucket;

            for (it = old_hashtable[expand_bucket]; NULL != it; it = next) {
                next = it->h_next;

                bucket = hash(ITEM_key(it), it->nkey, 0) & hashmask(hashpower);
                it->h_next = primary_hashtable[bucket];
                primary_hashtable[bucket] = it;
            }

            old_hashtable[expand_bucket] = NULL;

            expand_bucket++;
            if (expand_bucket == hashsize(hashpower - 1)) {
                expanding = false;
                free(old_hashtable);
                STATS_LOCK();
                stats.hash_bytes -= hashsize(hashpower - 1) * sizeof(void *);
                stats.hash_is_expanding = 0;
                STATS_UNLOCK();
                if (settings.verbose > 1)
                    fprintf(stderr, "Hash table expansion done\n");
            }
        }

        if (!expanding) {
            // added by Bin:
            fprintf(stderr, "\nHash table expansion done\n");
            //assoc_pre_bench();
            //assoc_post_bench();

            /* We are done expanding.. just wait for next invocation */
            pthread_cond_wait(&maintenance_cond, &cache_lock);
        }

        pthread_mutex_unlock(&cache_lock);
    }
    return NULL;
}

void do_item_update(item *it) {
		syslog(LOG_INFO, "[%s:%s:%d]", __FILE__, __func__, __LINE__);
    MEMCACHED_ITEM_UPDATE(ITEM_key(it), it->nkey, it->nbytes);
    if (it->time < current_time - ITEM_UPDATE_INTERVAL) {
        assert((it->it_flags & ITEM_SLABBED) == 0);

        mutex_lock(&cache_lock);
        if ((it->it_flags & ITEM_LINKED) != 0) {
            item_unlink_q(it);
            it->time = current_time;
            item_link_q(it);
        }
        mutex_unlock(&cache_lock);
    }
}

void do_item_remove(item *it) {
#ifdef MOXI_ITEM_MALLOC
    item_free(it);
#else
    MEMCACHED_ITEM_REMOVE(ITEM_key(it), it->nkey, it->nbytes);
    assert((it->it_flags & ITEM_SLABBED) == 0);
    if (it->refcount != 0) {
        it->refcount--;
        DEBUG_REFCNT(it, '-');
    }
    if (it->refcount == 0 && (it->it_flags & ITEM_LINKED) == 0) {
        item_free(it);
    }
#endif
}

int item_link(item *it) {
    assert((it->it_flags & (ITEM_LINKED|ITEM_SLABBED)) == 0);
    assert(it->nbytes < 1048576);
    it->it_flags |= ITEM_LINKED;
    it->time = current_time;
    assoc_insert(ITEM_key(it), it);

    stats.curr_bytes += ITEM_ntotal(it);
    stats.curr_items += 1;
    stats.total_items += 1;

    item_link_q(it);

    return 1;
}

/* Copy/paste to avoid adding two extra branches for all common calls, since
 * _nolock is only used in an uncommon case. */
void do_item_update_nolock(item *it) {
#ifdef CLOCK_REPLACEMENT    
    if (it->recency == 0) it->recency = 1;
#else
    MEMCACHED_ITEM_UPDATE(ITEM_key(it), it->nkey, it->nbytes);
    if (it->time < current_time - ITEM_UPDATE_INTERVAL) {
        assert((it->it_flags & ITEM_SLABBED) == 0);

        if ((it->it_flags & ITEM_LINKED) != 0) {
            item_unlink_q(it);
            it->time = current_time;
            item_link_q(it);
        }
    }
#endif
}

int item_test() {
    int maxi = 0; 
    
    //test set.
    for(int i = 0; i < 10; i++) {
        char key[1024];
        memset(key, 0, 1024);
        sprintf(key, "charlie_%d", i);
        const size_t nkey = strlen(key) + 1;
        const int flags = 0;
        const time_t exptime = 0;
        const int nbytes = 1024; 
        uint32_t cur_hv = jenkins_hash((void *)key, nkey);
        item *it = do_item_alloc((const char *)key, nkey, flags, exptime, nbytes, cur_hv);
        if(it == NULL) {
            fprintf(stderr, "\033[31malloc fail\033[0m");
            maxi = i;
            break; 
        }
        char val[1024];
        sprintf(val, "%d", i);
        memcpy(ITEM_data(it), (void *)&val, strlen(val)+1);
    }
    
    //test get.
    for(int i = 0; i < 10; ++i) {
        char key[1024];
        memset(key, 0, 1024);
        sprintf(key, "charlie_%d", i); 
        const size_t nkey = strlen(key) + 1;
        uint32_t cur_hv = jenkins_hash((void *)key, nkey);
        item *it = assoc_find(key, nkey, cur_hv);
        if(it == NULL) {
            fprintf(stderr, "\033[31mget fail\033[0m");
            return -1;
        }
        int val = 0;
        memcpy((void *)&val, ITEM_data(it), sizeof(val));
        if(i&0x1) {
            fprintf(stdout, "del key:%s value:%d\n", ITEM_key(it), val);
            do_item_unlink(it, cur_hv); 
            lru_traverse(NULL);
        }
        
    }
    return 0;
}

item *assoc_find(const char *key, const size_t nkey, const uint32_t hv) {
    item *it;
    unsigned int oldbucket;

    /* 如果hashtable正在扩容阶段，所找item在老hashtable中，则在老hashtable中查询，否则从新表中查询
     * 判断在哪个表中的思路：
     * 1. 定位key所在hashtable中桶的位置
     * 2. 如果此位置大于等于从旧hashtable中移到新hashtable的数量，则所查找元素在旧hashtable中，否则在新hash表中
     *
     * eg.
     * primary hashtable
     * [0]
     * [1] -> a -> b -> null
     * [2]
     * [3] -> x
     *
     * old hashtable
     * [0]
     * [1]
     * [2]
     * [3]
     * [4] -> y ->null
     * [5] -> p -> null          <--- hash(key)
     * ...
     */
    if (expanding &&
            (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
    {
        it = old_hashtable[oldbucket];
    } else {
        it = primary_hashtable[hv & hashmask(hashpower)];
    }

    item *ret = NULL;
    int depth = 0;
    while (it) {
        if ((nkey == it->nkey) && (memcmp(key, ITEM_key(it), nkey) == 0)) {
            ret = it;
            break;
        }
        it = it->h_next;
        ++depth;
    }
    MEMCACHED_ASSOC_FIND(key, nkey, depth);
    return ret;
}

char *assoc_key_snap(int *n)
{
    char *p = NULL;
    char *b = NULL;
    item *i = NULL;
    int  co = 0;
    int  sz = 1;
    int  hs = 0;
    int  hm = hashsize(hashpower);

    hs = hm;
    while(hs--){
        if(expanding && hs < hashsize(hashpower - 1) && hs >= expand_bucket){
            i = old_hashtable[hs];
        }else{
            i = primary_hashtable[hs];
        }
        while(i){
            sz += i->nkey + 1;
            co++;
            i = i->h_next;
        }
    }

    if(co){
        if(p = b = malloc(sz)){
            hs = hm;
            while(hs--){
                if(expanding && hs < hashsize(hashpower - 1) && hs >= expand_bucket){
                    i = old_hashtable[hs];
                }else{
                    i = primary_hashtable[hs];
                }
                while(i){
                    memcpy(p, ITEM_key(i), i->nkey);
                    p += i->nkey;
                    *(p++) = 0;
                    i = i->h_next;
                }
            }
            *(p++) = 0;
        }
    }
    if(n) *n = co;
    return(b);
}

/* Note: this isn't an assoc_update.  The key must not already exist to call this */
int assoc_insert(item *it, const uint32_t hv) {
    unsigned int oldbucket;

//    assert(assoc_find(ITEM_key(it), it->nkey) == 0);  /* shouldn't have duplicately named things defined */
    // commented by Bin
    /* if (assoc_find(ITEM_key(it), it->nkey, hv) != 0) { */
    /*     printf("see duplicate keys"); */
    /* } */


    if (expanding &&
        (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
    {
        it->h_next = old_hashtable[oldbucket];
        old_hashtable[oldbucket] = it;
    } else {
        it->h_next = primary_hashtable[hv & hashmask(hashpower)];
        primary_hashtable[hv & hashmask(hashpower)] = it;
#ifdef COUNT_LARGEST_BUCKET
        bucket_size[hv & hashmask(hashpower)] ++;
        if (bucket_size[hv & hashmask(hashpower)] > largest_bucket) {
            largest_bucket = bucket_size[hv & hashmask(hashpower)];
        }
#endif
    }

    hash_items++;
    // added by Bin:
    /* if ((hash_items) && (hash_items % 1000000 == 0)) { */
    /*     printf("%u Million items inserted!\n", hash_items / 1000000); */
    /* }  */

    if (! expanding && hash_items > (hashsize(hashpower) * 3) / 2) {
        // commented by Bin
        //assoc_expand();
        // added by Bin
        /* perror("can not insert!\n"); */
        /* exit(1); */
        printf("hash table is full (hashpower = %d, hash_items = %u,), need to increase hashpower\n",
               hashpower, hash_items);
        return 0;
    }

    MEMCACHED_ASSOC_INSERT(ITEM_key(it), it->nkey, hash_items);
    return 1;
}

//按访问时间，更新在LRU队列的位置
void do_item_update(item *it) {
    MEMCACHED_ITEM_UPDATE(ITEM_key(it), it->nkey, it->nbytes);
    if (it->time < current_time - ITEM_UPDATE_INTERVAL) {
        assert((it->it_flags & ITEM_SLABBED) == 0);

        mutex_lock(&cache_lock);
        //达到更新时间间隔
        if ((it->it_flags & ITEM_LINKED) != 0) {
            //从LUR中删除
            item_unlink_q(it);
            //更新访问时间
            it->time = current_time;
            //插入到LRU队列头部
            item_link_q(it);
        }
        mutex_unlock(&cache_lock);
    }
}

/** wrapper around assoc_find which does the lazy expiration logic */
item *do_item_get(const char *key, const size_t nkey) {
    item *it = assoc_find(key, nkey);
    int was_found = 0;

    if (settings.verbose > 2) {
        if (it == NULL) {
            fprintf(stderr, "> NOT FOUND %s", key);
        } else {
            fprintf(stderr, "> FOUND KEY %s", ITEM_key(it));
            was_found++;
        }
    }

    if (it != NULL && settings.oldest_live != 0 && settings.oldest_live <= current_time &&
        it->time <= settings.oldest_live) {
        do_item_unlink(it);           /* MTSAFE - cache_lock held */
        it = NULL;
    }

    if (it == NULL && was_found) {
        fprintf(stderr, " -nuked by flush");
        was_found--;
    }

    if (it != NULL && it->exptime != 0 && it->exptime <= current_time) {
        do_item_unlink(it);           /* MTSAFE - cache_lock held */
        it = NULL;
    }

    if (it == NULL && was_found) {
        fprintf(stderr, " -nuked by expire");
        was_found--;
    }

    if (it != NULL) {
        it->refcount++;
        DEBUG_REFCNT(it, '+');
    }

    if (settings.verbose > 2)
        fprintf(stderr, "\n");

    return it;
}

//更新item，这个只更新时间
void do_item_update(item *it)
{
    MEMCACHED_ITEM_UPDATE(ITEM_key(it), it->nkey, it->nbytes);
    if (it->time < current_time - ITEM_UPDATE_INTERVAL)
    {//更新有时间限制
        assert((it->it_flags & ITEM_SLABBED) == 0);

        mutex_lock(&cache_lock);//保持同步

        //更新LRU队列的Item ,先删除，然后在添加，相当于刚刚使用
        if ((it->it_flags & ITEM_LINKED) != 0)
        {
            item_unlink_q(it);//断开连接
            it->time = current_time;//更新item的时间
            item_link_q(it);//重新添加
        }
        mutex_unlock(&cache_lock);
    }
}

int do_item_link(item *it) {
    MEMCACHED_ITEM_LINK(ITEM_key(it), it->nkey, it->nbytes);
    assert((it->it_flags & (ITEM_LINKED|ITEM_SLABBED)) == 0);
    it->it_flags |= ITEM_LINKED;
    it->time = current_time;
    assoc_insert(it);

    STATS_LOCK();
    stats.curr_bytes += ITEM_ntotal(it);
    stats.curr_items += 1;
    stats.total_items += 1;
    STATS_UNLOCK();

    /* Allocate a new CAS ID on link. */
    ITEM_set_cas(it, (settings.use_cas) ? get_cas_id() : 0);

    item_link_q(it);

    return 1;
}

static void assoc_maintenance_thread(void *arg) {
    (void)arg;

    while (do_run_maintenance_thread) {
        int ii = 0;

        /* Lock the cache, and bulk move multiple buckets to the new
         * hash table. */
        cb_mutex_enter(&cache_lock);

        for (ii = 0; ii < hash_bulk_move && expanding; ++ii) {
            item *it, *next;
            int bucket;

            for (it = old_hashtable[expand_bucket]; NULL != it; it = next) {
                next = it->h_next;

                bucket = hash(ITEM_key(it), it->nkey, 0) & hashmask(hashpower);
                it->h_next = primary_hashtable[bucket];
                primary_hashtable[bucket] = it;
            }

            old_hashtable[expand_bucket] = NULL;

            expand_bucket++;
            if (expand_bucket == hashsize(hashpower - 1)) {
                expanding = false;
                free(old_hashtable);
                if (settings.verbose > 1)
                    moxi_log_write("Hash table expansion done\n");
            }
        }

        if (!expanding) {
            /* We are done expanding.. just wait for next invocation */
            cb_cond_wait(&maintenance_cond, &cache_lock);
        }

        cb_mutex_exit(&cache_lock);
    }
}