成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

Redis3.2源碼分析-整數(shù)集合intset

JohnLui / 3046人閱讀

摘要:是集合的底層實(shí)現(xiàn)之一,當(dāng)存儲(chǔ)整數(shù)集合并且數(shù)據(jù)量較小的情況下會(huì)使用作為的底層實(shí)現(xiàn)。當(dāng)數(shù)據(jù)量較大或者集合元素為字符串時(shí)則會(huì)使用實(shí)現(xiàn)。快速復(fù)習(xí)字節(jié)序不論大端小端,內(nèi)存中數(shù)據(jù)按照位字節(jié)分割。舉個(gè)例子整數(shù)對(duì)應(yīng)的進(jìn)制表示是。

intset是Redis集合的底層實(shí)現(xiàn)之一,當(dāng)存儲(chǔ)整數(shù)集合并且數(shù)據(jù)量較小的情況下Redis會(huì)使用intset作為set的底層實(shí)現(xiàn)。當(dāng)數(shù)據(jù)量較大或者集合元素為字符串時(shí)則會(huì)使用dict實(shí)現(xiàn)set。
intset將整數(shù)元素按順序存儲(chǔ)在數(shù)組里,并通過二分法降低查找元素的時(shí)間復(fù)雜度。數(shù)據(jù)量大時(shí),依賴于“查找”的命令(如SISMEMBER)就會(huì)由于O(logn)的時(shí)間復(fù)雜度而遇到一定的瓶頸,所以數(shù)據(jù)量大時(shí)會(huì)用dict來代替intset。但是intset的優(yōu)勢(shì)就在于比dict更省內(nèi)存,而且數(shù)據(jù)量小的時(shí)候O(logn)未必會(huì)慢于O(1)的hash function。這也是intset存在的原因。

intset結(jié)構(gòu)體聲明

intset的結(jié)構(gòu)體非常簡單

typedef struct intset {
    uint32_t encoding; //intset的類型編碼
    uint32_t length; //成員元素的個(gè)數(shù)
    int8_t contents[];//用來存儲(chǔ)成員的柔性數(shù)組
}

需要注意contents數(shù)組成員被聲明為int8_t類型并不表示contents里存的是int8_t類型的成員,這個(gè)類型聲明對(duì)于contents來說可以認(rèn)為是毫無意義的,因?yàn)閕ntset成員是什么類型完全取決于encoding變量的值。encoding提供下面三種值:

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

如果intset的encoding為INTSET_ENC_INT16,則contents的每個(gè)成員的“邏輯類型”都為int16_t。
雖然每個(gè)成員的“實(shí)際類型”是int8_t,無法直接通過contents[x]取出索引為x的成員元素,但是intset.c里提供了些函數(shù),可以按照不同的encoding方式設(shè)置/取出contents的成員。(用指針設(shè)置,memcpy取出)
由于這種方法在內(nèi)存上暴力地賦值與取值,所以希望元素在不同機(jī)器上存儲(chǔ)的字節(jié)序一致,但是不同處理器 在內(nèi)存中存放數(shù)據(jù)的方式不一定相同,主要分為大端字節(jié)序和小端字節(jié)序。快速復(fù)習(xí)字節(jié)序:不論大端小端,內(nèi)存中數(shù)據(jù)按照8位(1字節(jié))分割。大端字節(jié)序就是高位的字節(jié)存放在低地址處;小端字節(jié)序就是高位的字節(jié)存放在高地址處。舉個(gè)例子:

int d = 1415926;

整數(shù)d對(duì)應(yīng)的16進(jìn)制表示是0x159AF6。8個(gè)二進(jìn)制位可以被2個(gè)十六進(jìn)制位表示,所以15、9A、F6各是一個(gè)字節(jié),15是高位字節(jié),F(xiàn)6是低位字節(jié)。
大端的處理器在內(nèi)存中這樣存放d:

而小端的處理器在內(nèi)存中這樣存放d:

如果老老實(shí)實(shí)通過contents[x]的方式賦值取值,我們就不需要考慮這個(gè)字節(jié)序的問題,但是intset根據(jù)encoding的值指定元素的地址偏移,暴力地對(duì)內(nèi)存進(jìn)行操作。若數(shù)據(jù)被截?cái)嗔?,則大端機(jī)器和小端機(jī)器會(huì)表現(xiàn)出不統(tǒng)一的狀況。為了避免這種情況發(fā)生,intset不管在什么機(jī)器上都按照同一種字節(jié)序(小端)在內(nèi)存中存intset的成員變量。

/* variants of the function doing the actual convertion only if the target
 * host is big endian */
#if (BYTE_ORDER == LITTLE_ENDIAN)
#define memrev16ifbe(p)
#define memrev32ifbe(p)
#define memrev64ifbe(p)
#define intrev16ifbe(v) (v)
#define intrev32ifbe(v) (v)
#define intrev64ifbe(v) (v)
#else
#define memrev16ifbe(p) memrev16(p)
#define memrev32ifbe(p) memrev32(p)
#define memrev64ifbe(p) memrev64(p)
#define intrev16ifbe(v) intrev16(v)
#define intrev32ifbe(v) intrev32(v)
#define intrev64ifbe(v) intrev64(v)
#endif

//翻轉(zhuǎn)
void memrev64(void *p) {
    unsigned char *x = p, t;

    t = x[0];
    x[0] = x[7];
    x[7] = t;
    t = x[1];
    x[1] = x[6];
    x[6] = t;
    t = x[2];
    x[2] = x[5];
    x[5] = t;
    t = x[3];
    x[3] = x[4];
    x[4] = t;
}
uint64_t intrev64(uint64_t v) {
    memrev64(&v);
    return v;
}
intset基本操作 底層賦值/取值操作

通過_intsetSet和_intsetGet這兩個(gè)工具函數(shù),可以根據(jù)intset的encoding 讀/寫contents里索引為pos的值。這是后續(xù)intset操作的基礎(chǔ)。

/* Set the value at pos, using the configured encoding. */
//按照intset的encoding設(shè)置指定位置pos的值
static void _intsetSet(intset *is, int pos, int64_t value) {
    uint32_t encoding = intrev32ifbe(is->encoding);

    if (encoding == INTSET_ENC_INT64) {
        ((int64_t*)is->contents)[pos] = value;
        //大端機(jī)器在設(shè)置contents時(shí)將數(shù)據(jù)按字節(jié)翻轉(zhuǎn),按照小端序存儲(chǔ)
        memrev64ifbe(((int64_t*)is->contents)+pos);
    } else if (encoding == INTSET_ENC_INT32) {
        ((int32_t*)is->contents)[pos] = value;
        memrev32ifbe(((int32_t*)is->contents)+pos);
    } else {
        ((int16_t*)is->contents)[pos] = value;
        memrev16ifbe(((int16_t*)is->contents)+pos);
    }
}
/* Return the value at pos, using the configured encoding. */
//按照intset的encoding取出指定位置pos的值
//不對(duì)pos進(jìn)行越界判斷,可能會(huì)導(dǎo)致undefined behavior
static int64_t _intsetGet(intset *is, int pos) {
    return _intsetGetEncoded(is,pos,intrev32ifbe(is->encoding));
}
/* Return the value at pos, given an encoding. */
//以enc為編碼取出整數(shù)集合is在pos索引上的值
//不對(duì)pos進(jìn)行越界判斷,可能會(huì)導(dǎo)致undefined behavior
static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc) {
    int64_t v64;
    int32_t v32;
    int16_t v16;

    if (enc == INTSET_ENC_INT64) {
        //將contents在pos位置的值賦給v64
        //不能直接寫contents[pos]的原因是contents時(shí)int8_t類型的,contents[pos]表示是以sizeof(int8_t)為單位移動(dòng)的指針,而實(shí)際的編碼是INTSET_ENC_INT64,先將contents指針的類型變?yōu)閕nt64_t*
        memcpy(&v64,((int64_t*)is->contents)+pos,sizeof(v64));
        //大端機(jī)器在取出contents時(shí)將原本按照小端序存儲(chǔ)的數(shù)據(jù)按字節(jié)翻轉(zhuǎn),讀出正確的值
        memrev64ifbe(&v64);
        return v64;
    } else if (enc == INTSET_ENC_INT32) {
        memcpy(&v32,((int32_t*)is->contents)+pos,sizeof(v32));
        memrev32ifbe(&v32);
        return v32;
    } else {
        memcpy(&v16,((int16_t*)is->contents)+pos,sizeof(v16));
        memrev16ifbe(&v16);
        return v16;
    }
}
創(chuàng)建一個(gè)空intset

空intset的默認(rèn)encoding是INTSET_ENC_INT16,contents每個(gè)成員的邏輯類型是int16_t(雖然還沒有成員)

/* Create an empty intset. */
intset *intsetNew(void) {
    intset *is = zmalloc(sizeof(intset));
    is->encoding = intrev32ifbe(INTSET_ENC_INT16);
    is->length = 0;
    return is;
}
查詢一個(gè)成員

前面說了intset是將元素按大小順序存儲(chǔ)在contents數(shù)組里,所以在插入新元素之前,必須通過二分法找到合理的插入位置,這由intsetSearch(intset is, int64_t value, uint32_t pos)函數(shù)實(shí)現(xiàn)。
它的作用是在整數(shù)集合里用二分法找到value的位置,并把位置寫給pos參數(shù),函數(shù)返回1;若沒找到,則寫給pos的是能被插入的value的位置(intset按順序存儲(chǔ)),函數(shù)返回0。

static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
    int64_t cur = -1;

    /* The value can never be found when the set is empty */
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {
        /* Check for the case where we know we cannot find the value,
         * but do know the insert position. */
        //判斷是否大于小于邊界值
        if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
            if (pos) *pos = intrev32ifbe(is->length);//value可以被插入的位置
            return 0;
        } else if (value < _intsetGet(is,0)) {
            if (pos) *pos = 0;
            return 0;
        }
    }

    //二分
    while(max >= min) {
        mid = ((unsigned int)min + (unsigned int)max) >> 1;
        cur = _intsetGet(is,mid);
        if (value > cur) {
            min = mid+1;
        } else if (value < cur) {
            max = mid-1;
        } else {
            break;
        }
    }

    if (value == cur) {
        if (pos) *pos = mid;//找到了
        return 1;
    } else {
        if (pos) *pos = min;
        return 0;
    }
}
插入一個(gè)成員

插入一個(gè)值為value的成員時(shí),會(huì)做以下判斷邏輯:

計(jì)算value的encoding

若value的encoding大于要插入的intset的encoding,則調(diào)用intsetUpgradeAndAdd直接升級(jí)intset的encoding并插入到首部或者尾部。

若value的encoding小于要插入的intset的encoding,則不需要升級(jí)intset的encoding,調(diào)用intsetSearch找到合適的插入位置,再將該位置到contents尾部的數(shù)據(jù)全部右移一格,最后將value插入到pos。

代碼如下

/* Insert an integer in the intset */
//success傳null進(jìn)來則說明外層調(diào)用者不需要知道是否插入成功(value是否已存在),否則success用于此目的
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value);//根據(jù)value的大小計(jì)算value的encoding
    uint32_t pos;
    if (success) *success = 1;

    /* Upgrade encoding if necessary. If we need to upgrade, we know that
     * this value should be either appended (if > 0) or prepended (if < 0),
     * because it lies outside the range of existing values. */
    if (valenc > intrev32ifbe(is->encoding)) {
        //這種插入需要改變encoding(不需要search,因?yàn)閑ncoding改變說明value一定插入在contents首部或者尾部)
        /* This always succeeds, so we don"t need to curry *success. */
        return intsetUpgradeAndAdd(is,value);
    } else {
        /* Abort if the value is already present in the set.
         * This call will populate "pos" with the right position to insert
         * the value when it cannot be found. */
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;//intset里已存在該值,返回失敗
            return is;
        }

        is = intsetResize(is,intrev32ifbe(is->length)+1);
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);//右移一格
    }

    _intsetSet(is,pos,value);//插入值
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

/* Return the required encoding for the provided value. */
//根據(jù)v值的大小決定需要的編碼類型
static uint8_t _intsetValueEncoding(int64_t v) {
    if (v < INT32_MIN || v > INT32_MAX)
        return INTSET_ENC_INT64;
    else if (v < INT16_MIN || v > INT16_MAX)
        return INTSET_ENC_INT32;
    else
        return INTSET_ENC_INT16;
}

/* Upgrades the intset to a larger encoding and inserts the given integer. */
//這個(gè)函數(shù)執(zhí)行的前提是value參數(shù)的大小超過了當(dāng)前編碼
//為is->content重新分配內(nèi)存并修改編碼添加value進(jìn)這個(gè)intset
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32ifbe(is->encoding);//當(dāng)前編碼類型
    uint8_t newenc = _intsetValueEncoding(value);//新的編碼類型
    int length = intrev32ifbe(is->length);
    int prepend = value < 0 ? 1 : 0;//因?yàn)関alue一定超過了編碼的限制,所以看value是大于0還是小于0以此決定value放置在content[0]還是content[length]

    /* First set new encoding and resize */
    is->encoding = intrev32ifbe(newenc);
    is = intsetResize(is,intrev32ifbe(is->length)+1);

    /* Upgrade back-to-front so we don"t overwrite values.
     * Note that the "prepend" variable is used to make sure we have an empty
     * space at either the beginning or the end of the intset. */
    while(length--)
        //以curenc為編碼倒序取出所有值并賦值給新的位置
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    /* Set the value at the beginning or the end. */
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

/* Resize the intset */
//解除is的內(nèi)存分配并重新分配長度為len的intset的內(nèi)存
static intset *intsetResize(intset *is, uint32_t len) {
    uint32_t size = len*intrev32ifbe(is->encoding);
    is = zrealloc(is,sizeof(intset)+size);
    return is;
}

//把from索引到intset尾部的整塊數(shù)據(jù)復(fù)制to索引(復(fù)制之后from值不變,但是可以被覆蓋)
static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) {
    void *src, *dst;
    uint32_t bytes = intrev32ifbe(is->length)-from;
    uint32_t encoding = intrev32ifbe(is->encoding);

    if (encoding == INTSET_ENC_INT64) {
        src = (int64_t*)is->contents+from;
        dst = (int64_t*)is->contents+to;
        bytes *= sizeof(int64_t);
    } else if (encoding == INTSET_ENC_INT32) {
        src = (int32_t*)is->contents+from;
        dst = (int32_t*)is->contents+to;
        bytes *= sizeof(int32_t);
    } else {
        src = (int16_t*)is->contents+from;
        dst = (int16_t*)is->contents+to;
        bytes *= sizeof(int16_t);
    }
    memmove(dst,src,bytes);
}
移除一個(gè)成員

不同于插入一個(gè)成員,移除一個(gè)成員時(shí)不會(huì)改變intset的encoding,盡管移除這個(gè)成員之后所有成員的encoding都小于所在intset的encoding。

/* Delete integer from intset */
intset *intsetRemove(intset *is, int64_t value, int *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 0;

    //valenc不可能大于當(dāng)前編碼,否則value一定不在該intset中
    if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) {
        uint32_t len = intrev32ifbe(is->length);

        /* We know we can delete */
        if (success) *success = 1;

        /* Overwrite value with tail and update length */
        if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
        is = intsetResize(is,len-1);//減小內(nèi)存分配
        is->length = intrev32ifbe(len-1);//size-1
    }
    return is;
}
總結(jié)

通過intset底層實(shí)現(xiàn)我們可以發(fā)現(xiàn):基于順序存儲(chǔ)的整數(shù)集合 執(zhí)行一些需要用到查詢的命令時(shí) 其時(shí)間復(fù)雜度不會(huì)是文檔里注明O(1),例如:SADD、SREM 操作一個(gè)成員時(shí),時(shí)間復(fù)雜度會(huì)是O(logn)。所以當(dāng)整數(shù)集合數(shù)據(jù)量變大的時(shí)候,redis會(huì)用dict作為集合的底層實(shí)現(xiàn),將SADD、SREM、SISMEMBER這些命令的時(shí)間復(fù)雜度降至O(1),當(dāng)然,這會(huì)比intset消耗更多內(nèi)存。

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://systransis.cn/yun/28432.html

相關(guān)文章

  • Redis專題(2):Redis數(shù)據(jù)結(jié)構(gòu)底層探秘

    摘要:用指令來看一個(gè)值的數(shù)據(jù)結(jié)構(gòu)。對(duì)象只有同時(shí)滿足下面兩個(gè)條件時(shí),才會(huì)使用壓縮列表哈希中元素?cái)?shù)量小于個(gè)哈希中所有鍵值對(duì)的鍵和值字符串長度都小于字節(jié)。采用了鏈地址法的方法解決了哈希沖突的問題。數(shù)據(jù)類型的底層可以是整數(shù)集或者是散列表也叫哈希表。 前言 上篇文章 Redis閑談(1):構(gòu)建知識(shí)圖譜介紹了redis的基本概念、優(yōu)缺點(diǎn)以及它的內(nèi)存淘汰機(jī)制,相信大家對(duì)redis有了初步的認(rèn)識(shí)?;ヂ?lián)網(wǎng)的很...

    evin2016 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<