Jadual Kandungan
intset 结构体
intset 搜索
intset 插入
Rumah pangkalan data tutorial mysql 深入剖析 redis 数据结构 intset

深入剖析 redis 数据结构 intset

Jun 07, 2016 pm 04:37 PM
redis Menganalisis struktur data pergi dalam

intset 和 dict 都是 sadd 命令的底层数据结构,当添加的所有数据都是整数时,会使用前者;否则使用后者。 特别的 ,当遇到添加数据为字符串,即不能表示为整数时,redis 会把数据结构转换为 dict,即把 intset 中的数据全部搬迁到 dict。 本片展开的是 ints

intset 和 dict 都是 sadd 命令的底层数据结构,当添加的所有数据都是整数时,会使用前者;否则使用后者。特别的,当遇到添加数据为字符串,即不能表示为整数时,redis 会把数据结构转换为 dict,即把 intset 中的数据全部搬迁到 dict。

本片展开的是 intset,dict 的文章可以参看之前写的《深入剖析 redis 数据结构 dict》。

intset 结构体

intset 底层本质是一个有序的、不重复的、整型的数组,支持不同类型整数。

typedef struct intset {
    // 每个整数的类型
    uint32_t encoding;
    // intset 长度
    uint32_t length;
    // 整数数组
    int8_t contents[];
} intset;
Salin selepas log masuk

encoding 能下面的三个值:分别是 16,32 和 64位整数:

/* Note that these encodings are ordered, so:
* INTSET_ENC_INT16 
<h3 id="intset-搜索">intset 搜索</h3>
<p>intset 是有序的整数数组,可以用二分搜索查找。</p>
<pre class="brush:php;toolbar:false">static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    int min = 0, max = intrev32ifbe(is-&gt;length)-1, mid = -1;
    int64_t cur = -1;
    /* The value can never be found when the set is empty */
    // 集合为空
    if (intrev32ifbe(is-&gt;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. */
        // value 比最大元素还大
        if (value &gt; _intsetGet(is,intrev32ifbe(is-&gt;length)-1)) {
            if (pos) *pos = intrev32ifbe(is-&gt;length);
            return 0;
        // value 比最小元素还小
        } else if (value = min) {
        mid = (min+max)/2;
        cur = _intsetGet(is,mid);
        if (value &gt; cur) {
            min = mid+1;
        } else if (value 
<h3 id="intset-插入">intset 插入</h3>
<p>intset 实现中比较远有意思的是插入算法部分。</p>
<pre class="brush:php;toolbar:false">/* Insert an integer in the intset */
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    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 &gt; 0) or prepended (if  intrev32ifbe(is-&gt;encoding)) {
        /* This always succeeds, so we don't need to curry *success. */
        return intsetUpgradeAndAdd(is,value);
    // 正常,分配内存,插入
    } else {
        // intset 内部不允许重复
        /* 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,&amp;pos)) {
            if (success) *success = 0;
            return is;
        }
        // realloc
        is = intsetResize(is,intrev32ifbe(is-&gt;length)+1);
        // 迁移内存,腾出空间给新的数据。intsetMoveTail() 完成内存迁移工作
        if (pos length)) intsetMoveTail(is,pos,pos+1);
    }
    // 在腾出的空间中设置新的数据
    _intsetSet(is,pos,value);
    // 更新 intset size
    is-&gt;length = intrev32ifbe(intrev32ifbe(is-&gt;length)+1);
    return is;
}
// 升级整数类型,譬如从 short-&gt;int。当插入数据的内存占用比原有数据大
// 的时候,会被调用
/* Upgrades the intset to a larger encoding and inserts the given integer. */
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32ifbe(is-&gt;encoding);
    uint8_t newenc = _intsetValueEncoding(value);
    int length = intrev32ifbe(is-&gt;length);
    // value0 尾插
    int prepend = value encoding = intrev32ifbe(newenc);
    is = intsetResize(is,intrev32ifbe(is-&gt;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--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
    // valuelength),value);
    // 更新 set size
    is-&gt;length = intrev32ifbe(intrev32ifbe(is-&gt;length)+1);
    return is;
}
Salin selepas log masuk

捣乱 2014-7-3

http://daoluan.net

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
2 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Repo: Cara menghidupkan semula rakan sepasukan
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Cara mendapatkan biji gergasi
3 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
2 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Repo: Cara menghidupkan semula rakan sepasukan
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Cara mendapatkan biji gergasi
3 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Tag artikel panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Penyelesaian kepada ralat 0x80242008 semasa memasang Windows 11 10.0.22000.100 Penyelesaian kepada ralat 0x80242008 semasa memasang Windows 11 10.0.22000.100 May 08, 2024 pm 03:50 PM

Penyelesaian kepada ralat 0x80242008 semasa memasang Windows 11 10.0.22000.100

Menganalisis kesesakan fungsi PHP dan meningkatkan kecekapan pelaksanaan Menganalisis kesesakan fungsi PHP dan meningkatkan kecekapan pelaksanaan Apr 23, 2024 pm 03:42 PM

Menganalisis kesesakan fungsi PHP dan meningkatkan kecekapan pelaksanaan

Strategi dan pengoptimuman caching API Golang Strategi dan pengoptimuman caching API Golang May 07, 2024 pm 02:12 PM

Strategi dan pengoptimuman caching API Golang

Mekanisme caching dan amalan aplikasi dalam pembangunan PHP Mekanisme caching dan amalan aplikasi dalam pembangunan PHP May 09, 2024 pm 01:30 PM

Mekanisme caching dan amalan aplikasi dalam pembangunan PHP

Bagaimana untuk menggunakan cache Redis dalam penomboran tatasusunan PHP? Bagaimana untuk menggunakan cache Redis dalam penomboran tatasusunan PHP? May 01, 2024 am 10:48 AM

Bagaimana untuk menggunakan cache Redis dalam penomboran tatasusunan PHP?

Bagaimana untuk menaik taraf Win11 English 21996 kepada Simplified Chinese 22000_Cara untuk menaik taraf Win11 English 21996 kepada Simplified Chinese 22000 Bagaimana untuk menaik taraf Win11 English 21996 kepada Simplified Chinese 22000_Cara untuk menaik taraf Win11 English 21996 kepada Simplified Chinese 22000 May 08, 2024 pm 05:10 PM

Bagaimana untuk menaik taraf Win11 English 21996 kepada Simplified Chinese 22000_Cara untuk menaik taraf Win11 English 21996 kepada Simplified Chinese 22000

Struktur dan algoritma data Java: penjelasan mendalam Struktur dan algoritma data Java: penjelasan mendalam May 08, 2024 pm 10:12 PM

Struktur dan algoritma data Java: penjelasan mendalam

Bolehkah navicat menyambung ke redis? Bolehkah navicat menyambung ke redis? Apr 23, 2024 pm 05:12 PM

Bolehkah navicat menyambung ke redis?

See all articles