整數集合

整數集合（intset）用于有序、無重復地保存多個整數值，根據元素的值，自動選擇該用什么長度的整數類型來保存元素。

舉個例子，如果在一個 intset 里面，最長的元素可以用 int16_t 類型來保存，那么這個 intset 的所有元素都以 int16_t 類型來保存。

另一方面，如果有一個新元素要加入到這個 intset ，并且這個元素不能用 int16_t 類型來保存 ——比如說，新元素的長度為 int32_t ，那么這個 intset 就會自動進行“升級”：先將集合中現有的所有元素從 int16_t 類型轉換為 int32_t 類型，接著再將新元素加入到集合中。

根據需要，intset 可以自動從 int16_t 升級到 int32_t 或 int64_t ，或者從 int32_t 升級到 int64_t 。

整數集合的應用

Intset 是集合鍵的底層實現之一，如果一個集合：

1. 只保存著整數元素；
2. 元素的數量不多；

那么 Redis 就會使用 intset 來保存集合元素。

具體的信息請參考《集合》。

數據結構和主要操作

以下是 intset.h/intset 類型的定義：

typedef struct intset {

    // 保存元素所使用的類型的長度
    uint32_t encoding;

    // 元素個數
    uint32_t length;

    // 保存元素的數組
    int8_t contents[];

} intset;

encoding 的值可以是以下三個常量之一（定義位于 intset.c ）：

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

contents 數組是實際保存元素的地方，數組中的元素有以下兩個特性：

• 元素不重復；
• 元素在數組中由小到大排列；

contents 數組的 int8_t 類型聲明比較容易讓人誤解，實際上， intset 并不使用 int8_t 類型來保存任何元素，結構中的這個類型聲明只是作為一個占位符使用：在對 contents 中的元素進行讀取或者寫入時，程序并不是直接使用 contents 來對元素進行索引，而是根據 encoding 的值，對 contents 進行類型轉換和指針運算，計算出元素在內存中的正確位置。在添加新元素，進行內存分配時，分配的空間也是由 encoding 的值決定。

下表列出了處理 intset 的一些主要操作，以及這些操作的算法復雜度：

intset 運行實例

讓我們跟蹤一個 intset 的創(chuàng)建和添加過程，借此了解 intset 的運作方式。

創(chuàng)建新 intset

intset.c/intsetNew 函數創(chuàng)建一個新的 intset ，并設置初始化值：

intset *is = intsetNew();

// intset->encoding = INTSET_ENC_INT16;
// intset->length 0;
// intset->contents = [];

注意 encoding 使用 INTSET_ENC_INT16 作為初始值。

添加新元素到 intset

創(chuàng)建 intset 之后，就可以對它添加新元素了。

添加新元素到 intset 的工作由 intset.c/intsetAdd 函數完成，需要處理以下三種情況：

1. 元素已存在于集合，不做動作；
2. 元素不存在于集合，并且添加新元素并不需要升級；
3. 元素不存在于集合，但是要在升級之后，才能添加新元素；

并且， intsetAdd 需要維持 intset->contents 的以下性質：

1. 確保數組中沒有重復元素；
2. 確保數組中的元素按由小到大排序；

整個 intsetAdd 的執(zhí)行流程可以表示為下圖：

check_encoding; upgrade [label="調用\n intsetUpgradeAndAdd\n升級集合\n并將新元素\n添加到升級后的集合中"]; check_encoding -> upgrade [label="不適用"]; value_exists [label="元素已經存在于集合？", shape = diamond, fillcolor = "#95BBE3"]; check_encoding -> value_exists [label="適用"]; insert_fail [label="添加失敗，元素已存在"]; realloc_and_move [label="為新元素分配內存\n并對 contents 數組中現有的元素進行移動，\n確保新元素會被放到有序數組正確的位置上"]; value_exists -> insert_fail [label="是"]; value_exists -> realloc_and_move [label="否"]; done [label="將新元素的值保存到 contents 數組中\(zhòng)n更新 length 計數器"]; realloc_and_move -> done;}" />

以下兩個小節(jié)分別演示添加操作在升級和不升級兩種情況下的執(zhí)行過程。

添加新元素到 intset （不需要升級）

如果 intset 現有的編碼方式適用于新元素，則可直接將新元素添加到 intset ，無須對 intset 進行升級。

以下代碼演示了將三個 int16_t 類型的整數添加到集合的過程，以及在添加過程中，集合的狀態(tài)：

intset *is = intsetNew();

intsetAdd(is, 10, NULL);

// is->encoding = INTSET_ENC_INT16;
// is->length = 1;
// is->contents = [10];

intsetAdd(is, 5, NULL);

// is->encoding = INTSET_ENC_INT16;
// is->length = 2;
// is->contents = [5, 10];

intsetAdd(is, 12, NULL);

// is->encoding = INTSET_ENC_INT16;
// is->length = 3;
// is->contents = [5, 10, 12]

因為添加的三個元素都可以表示為 int16_t ，因此 is->encoding 一直都是 INTSET_ENC_INT16 。

另一方面， is->length 和 is->contents 的值，則隨著新元素的加入而被修改。

添加新元素到 intset （需要升級）

當要添加新元素到 intset ，并且 intset 當前的編碼，不適用于新元素的編碼時，就需要對 intset 進行升級。

以下代碼演示了帶升級的添加操作的執(zhí)行過程：

intset *is = intsetNew();

intsetAdd(is, 1, NULL);

// is->encoding = INTSET_ENC_INT16;
// is->length = 1;
// is->contents = [1];                  // 所有值使用 int16_t 保存

intsetAdd(is, 65535, NULL);

// is->encoding = INTSET_ENC_INT32;     // 升級
// is->length = 2;
// is->contents = [1, 65535];           // 所有值使用 int32_t 保存

intsetAdd(is, 70000, NULL);

// is->encoding = INTSET_ENC_INT32;
// is->length = 3;
// is->contents = [1, 65535, 70000];

intsetAdd(is, 4294967295, NULL);

// is->encoding = INTSET_ENC_INT64;                 // 升級
// is->length = 4;
// is->contents = [1, 65535, 70000, 4294967295];    // 所有值使用 int64_t 保存

在添加 65535 和 4294967295 之后，encoding 屬性的值，以及 contents 數組保存值的方式，都被改變了。

升級

添加新元素時，如果 intsetAdd 發(fā)現新元素，不能用現有的編碼方式來保存，便會將升級集合和添加新元素的任務轉交給 intsetUpgradeAndAdd 來完成：

upgrade_or_not; upgrade_or_not -> intsetAdd [label = "不需要"]; upgrade_or_not -> intsetUpgradeAndAdd [label = "需要"];}" />

intsetUpgradeAndAdd 需要完成以下幾個任務：

1. 對新元素進行檢測，看保存這個新元素需要什么類型的編碼；
2. 將集合 encoding 屬性的值設置為新編碼類型，并根據新編碼類型，對整個 contents 數組進行內存重分配。
3. 調整 contents 數組內原有元素在內存中的排列方式，從舊編碼調整為新編碼。
4. 將新元素添加到集合中。

整個過程中，最復雜的就是第三步，讓我們用一個例子來理解這個步驟。

升級實例

假設有一個 intset ，里面有三個用 int16_t 方式保存的數值，分別是 1 、 2 和 3 ，結構如下：

intset->encoding = INTSET_ENC_INT16;
intset->length = 3;
intset->contents = [1, 2, 3];

其中， intset->contents 在內存中的排列如下：

bit     0    15    31    47
value   |  1  |  2  |  3  |

現在，我們將一個長度為 int32_t 的值 65535 加入到集合中， intset 需要執(zhí)行以下步驟：

1. 將 encoding 屬性設置為 INTSET_ENC_INT32 。

2. 根據 encoding 屬性的值，對 contents 數組進行內存重分配。

重分配完成之后， contents 在內存中的排列如下：

bit     0    15    31    47     63        95       127
value   |  1  |  2  |  3  |  ?  |    ?    |    ?    |

contents 數組現在共有可容納 4 個 int32_t 值的空間。

1. 因為原來的 3 個 int16_t 值還“擠在” contents 前面的 48 個位里， 所以程序需要移動它們并轉換類型， 讓它們適應集合的新編碼方式。

首先是移動 3 ：

bit     0    15    31    47     63        95       127
value   |  1  |  2  |  3  |  ?  |    3    |    ?    |
                       |             ^
                       |             |
                       +-------------+
                     int16_t -> int32_t

接著移動 2 ：

bit     0    15    31   47     63        95       127
value   |  1  |  2  |    2     |    3    |    ?    |
                 |       ^
                 |       |
                 +-------+
            int16_t -> int32_t

最后，移動 1 ：

bit     0   15    31   47     63        95       127
value   |    1     |    2     |    3    |    ?    |
            | ^
            V |
    int16_t -> int32_t

1. 最后，將新值 65535 添加到數組：

bit     0   15    31   47     63        95       127
value   |    1     |    2     |    3    |  65535  |
                                             ^
                                             |
                                            add

將 intset->length 設置為 4 。

至此，集合的升級和添加操作完成，現在的 intset 結構如下：

intset->encoding = INTSET_ENC_INT32;
intset->length = 4;
intset->contents = [1, 2, 3, 65535];

關于升級

關于升級操作，有兩點需要提醒一下：

第一，從較短整數到較長整數的轉換，并不會更改元素里面的值。

在 C 語言中，從長度較短的帶符號整數到長度較長的帶符號整數之間的轉換（比如從 int16_t 轉換為 int32_t ）總是可行的（不會溢出）、無損的。

另一方面，從較長整數到較短整數之間的轉換，可能是有損的（比如從 int32_t 轉換為 int16_t ）。

因為 intset 只進行從較短整數到較長整數的轉換（也即是，只“升級”，不“降級”），因此，“升級”操作并不會修改元素原有的值。

第二，集合編碼元素的方式，由元素中長度最大的那個值來決定。

就像前面演示的例子一樣，當要將一個 int32_t 編碼的新元素添加到集合時，集合原有的所有 int16_t 編碼的元素，都必須轉換為 int32_t 。

盡管這個集合真正需要用 int32_t 長度來保存的元素只有一個，但整個集合的所有元素都必須轉換為這種類型。

關于元素移動

在進行升級的過程中，需要對數組內的元素進行“類型轉換”和“移動”操作。

其中，移動不僅出現在升級（intsetUpgradeAndAdd）操作中，還出現其他對 contents 數組內容進行增刪的操作上，比如 intsetAdd 和 intsetRemove ，因為這種移動操作需要處理 intset 中的所有元素，所以這些函數的復雜度都不低于 (O(N)) 。

其他操作

以下是一些關于 intset 其他操作的討論。

讀取

有兩種方式讀取 intset 的元素，一種是 _intsetGet ，另一種是 intsetSearch ：

• _intsetGet 接受一個給定的索引 pos ，并根據 intset->encoding 的值進行指針運算，計算出給定索引在 intset->contents 數組上的值。
• intsetSearch 則使用二分查找 [http://en.wikipedia.org/wiki/Binary_search_algorithm]算法，判斷一個給定元素在 contents 數組上的索引。

寫入

除了前面介紹過的 intsetAdd 和 intsetUpgradeAndAdd 之外， _intsetSet 也對集合進行寫入操作：它接受一個索引 pos ，以及一個 new_value ，將 contents 數組 pos 位置的值設為 new_value 。

刪除

刪除單個元素的工作由 intsetRemove 操作，它先調用 intsetSearch 找到需要被刪除的元素在 contents 數組中的索引，然后使用內存移位操作，將目標元素從內存中抹去，最后，通過內存重分配，對 contents 數組的長度進行調整。

降級

Intset 不支持降級操作。

Intset 定位為一種受限的中間表示，只能保存整數值，而且元素的個數也不能超過 redis.h/REDIS_SET_MAX_INTSET_ENTRIES （目前版本值為 512 ）這些條件決定了它被保存的時間不會太長，因此沒有必要進行太復雜的操作，

當然，如果內存確實十分緊張的話，給 intset 添加降級功能也是可以實現的，不過這可能會讓 intset 的代碼增長一倍。

小結

• Intset 用于有序、無重復地保存多個整數值，會根據元素的值，自動選擇該用什么長度的整數類型來保存元素。
• 當一個位長度更長的整數值添加到 intset 時，需要對 intset 進行升級，新 intset 中每個元素的位長度，會等于新添加值的位長度，但原有元素的值不變。
• 升級會引起整個 intset 進行內存重分配，并移動集合中的所有元素，這個操作的復雜度為 (O(N)) 。
• Intset 只支持升級，不支持降級。
• Intset 是有序的，程序使用二分查找算法來實現查找操作，復雜度為 (O(\lg N)) 。