1.整數集合：整數的集合，升序排序，無重複元素
2.整數集合intset是集合鍵的底層實作之一，當一個集合隻包含整數值的元素，并且這個集合的元素數量不多時，redis會使用整數集合作為集合鍵的底層實作
3.intset可通過屬性自定義編碼方式(int16_t/int32_t/int64_t)
4.當往inset插入新元素時，如果新元素的類型比inset的原編碼類型長，那麼要先對inset進行“更新”操作
5.更新操作：（不可逆操作）
1）根據新元素的類型，擴充intset底層數組的空間大小，并且為新元素配置設定空間
2）将原有的元素轉化成與新元素相同的類型，并且将他們放在正确的位置上，仍然保持有序無重複
3）将新元素添加到底層數組中
6.因為可能存在更新操作，是以往intset中添加元素的時間複雜度為O(N),N為元素個數
7.進行更新操作的好處：1）提升靈活性，避免類型錯誤，2）節約記憶體，在需要更新的時候才更新，節約了記憶體，隻有我們需要更大類型的時候，才會更新成大類型，其餘時間都是小類型，這樣節省記憶體空間
源碼分析如下：
intset.h檔案：
#ifndef __INTSET_H
#define __INTSET_H
#include <stdint.h>
//====== 資料結構 ========//
typedef struct intset
{
// 編碼方式
uint32_t encoding;
// 集合包含的元素數量
uint32_t length;
// 儲存元素的數組
int8_t contents[];
} intset;
//======= API ===========//
//建立一個新的整數集合
intset *intsetNew(void);
//将給定的元素加到整數集合中
intset *intsetAdd(intset *is, int64_t value, uint8_t *success);
//從整數集合中移除給定元素
intset *intsetRemove(intset *is, int64_t value, int *success);
//檢查給定值是否存在集合
uint8_t intsetFind(intset *is, int64_t value);
//從整數集合中随機傳回一個元素
int64_t intsetRandom(intset *is);
//取出給定索引上的元素
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value);
//傳回整數集合包含元素的個數
uint32_t intsetLen(intset *is);
//傳回整數集合占用的記憶體位元組數
size_t intsetBlobLen(intset *is);
#endif // __INTSET_H intset.c檔案：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "intset.h"
#include "endianconv.h"
#include "zmalloc.h"
/* intset的三種編碼方式 */
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))
/* Return the required encoding for the provided value.
*
* 傳回适用于傳入值 v 的編碼方式
*
* T = O(1)
*/
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;
}
/* Return the value at pos, given an encoding.
*
* 根據給定的編碼方式 enc ，傳回集合的底層數組在 pos 索引上的元素。
*
* T = O(1)
*/
static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc)
{
int64_t v64;
int32_t v32;
int16_t v16;
// ((ENCODING*)is->contents) 首先将數組轉換回被編碼的類型
// 然後 ((ENCODING*)is->contents)+pos 計算出元素在數組中的正确位置
// 之後 member(&vEnc, ..., sizeof(vEnc)) 再從數組中拷貝出正确數量的位元組
// 如果有需要的話， memrevEncifbe(&vEnc) 會對拷貝出的位元組進行大小端轉換
// 最後将值傳回
if (enc == INTSET_ENC_INT64)
{
memcpy(&v64,((int64_t*)is->contents)+pos,sizeof(v64));
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;
}
}
/* Return the value at pos, using the configured encoding.
*
* 根據集合的編碼方式，傳回底層數組在 pos 索引上的值
*
* T = O(1)
*/
static int64_t _intsetGet(intset *is, int pos)
{
return _intsetGetEncoded(is,pos,intrev32ifbe(is->encoding));
}
/* Set the value at pos, using the configured encoding.
*
* 根據集合的編碼方式，将底層數組在 pos 位置上的值設為 value 。
*
* T = O(1)
*/
static void _intsetSet(intset *is, int pos, int64_t value)
{
// 取出集合的編碼方式
uint32_t encoding = intrev32ifbe(is->encoding);
// 根據編碼 ((Enc_t*)is->contents) 将數組轉換回正确的類型
// 然後 ((Enc_t*)is->contents)[pos] 定位到數組索引上
// 接着 ((Enc_t*)is->contents)[pos] = value 将值賦給數組
// 最後， ((Enc_t*)is->contents)+pos 定位到剛剛設定的新值上
// 如果有需要的話， memrevEncifbe 将對值進行大小端轉換
if (encoding == INTSET_ENC_INT64)
{
((int64_t*)is->contents)[pos] = value;
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);
}
}
/* Create an empty intset.
*
* 建立并傳回一個新的空整數集合
*
* T = O(1)
*/
intset *intsetNew(void)
{
// 為整數集合結構配置設定空間
intset *is = zmalloc(sizeof(intset));
// 設定初始編碼
is->encoding = intrev32ifbe(INTSET_ENC_INT16);
// 初始化元素數量
is->length = 0;
return is;
}
/* Resize the intset
*
* 調整整數集合的記憶體空間大小
*
* 如果調整後的大小要比集合原來的大小要大，
* 那麼集合中原有元素的值不會被改變。
*
* 傳回值：調整大小後的整數集合
*
* T = O(N)
*/
static intset *intsetResize(intset *is, uint32_t len)
{
// 計算數組的空間大小
uint32_t size = len*intrev32ifbe(is->encoding);
// 根據空間大小，重新配置設定空間
// 注意這裡使用的是 zrealloc ，
// 是以如果新空間大小比原來的空間大小要大，
// 那麼數組原有的資料會被保留
is = zrealloc(is,sizeof(intset)+size);
return is;
}
/*
* 在集合 is 的底層數組中查找值 value 所在的索引。
*
* 成功找到 value 時，函數傳回 1 ，并将 *pos 的值設為 value 所在的索引。
*
* 當在數組中沒找到 value 時，傳回 0 。
* 并将 *pos 的值設為 value 可以插入到數組中的位置。
*
* T = O(log N)
*/
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;
// 處理 is 為空時的情況
if (intrev32ifbe(is->length) == 0)
{
if (pos) *pos = 0;
return 0;
}
else
{
// 因為底層數組是有序的，如果 value 比數組中最後一個值都要大
// 那麼 value 肯定不存在于集合中，
// 并且應該将 value 添加到底層數組的最末端
if (value > _intsetGet(is,intrev32ifbe(is->length)-1))
{
if (pos) *pos = intrev32ifbe(is->length);
return 0;
// 因為底層數組是有序的，如果 value 比數組中最前一個值都要小
// 那麼 value 肯定不存在于集合中，
// 并且應該将它添加到底層數組的最前端
}
else if (value < _intsetGet(is,0))
{
if (pos) *pos = 0;
return 0;
}
}
// 在有序數組中進行二分查找
// T = O(log N)
while(max >= min)
{
mid = (min+max)/2;
cur = _intsetGet(is,mid);
if (value > cur)
{
min = mid+1;
}
else if (value < cur)
{
max = mid-1;
}
else
{
break;
}
}
// 檢查是否已經找到了 value
if (value == cur)
{
if (pos) *pos = mid;
return 1;
}
else
{
if (pos) *pos = min;
return 0;
}
}
/* Upgrades the intset to a larger encoding and inserts the given integer.
*
* 根據值 value 所使用的編碼方式，對整數集合的編碼進行更新，
* 并将值 value 添加到更新後的整數集合中。
*
* 傳回值：添加新元素之後的整數集合
*
* T = O(N)
*/
static intset *intsetUpgradeAndAdd(intset *is, int64_t value)
{
// 目前的編碼方式
uint8_t curenc = intrev32ifbe(is->encoding);
// 新值所需的編碼方式
uint8_t newenc = _intsetValueEncoding(value);
// 目前集合的元素數量
int length = intrev32ifbe(is->length);
// 根據 value 的值，決定是将它添加到底層數組的最前端還是最後端
// 注意，因為 value 的編碼比集合原有的其他元素的編碼都要大
// 是以 value 要麼大于集合中的所有元素，要麼小于集合中的所有元素
// 是以，value 隻能添加到底層數組的最前端或最後端
int prepend = value < 0 ? 1 : 0;
/* First set new encoding and resize */
// 更新集合的編碼方式
is->encoding = intrev32ifbe(newenc);
// 根據新編碼對集合（的底層數組）進行空間調整
// T = O(N)
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. */
// 根據集合原來的編碼方式，從底層數組中取出集合元素
// 然後再将元素以新編碼的方式添加到集合中
// 當完成了這個步驟之後，集合中所有原有的元素就完成了從舊編碼到新編碼的轉換
// 因為新配置設定的空間都放在數組的後端，是以程式先從後端向前端移動元素
// 舉個例子，假設原來有 curenc 編碼的三個元素，它們在數組中排列如下：
// | x | y | z |
// 當程式對數組進行重配置設定之後，數組就被擴容了（符号 ？ 表示未使用的記憶體）：
// | x | y | z | ? | ? | ? |
// 這時程式從數組後端開始，重新插入元素：
// | x | y | z | ? | z | ? |
// | x | y | y | z | ? |
// | x | y | z | ? |
// 最後，程式可以将新元素添加到最後 ？ 号标示的位置中：
// | x | y | z | new |
// 上面示範的是新元素比原來的所有元素都大的情況，也即是 prepend == 0
// 當新元素比原來的所有元素都小時（prepend == 1），調整的過程如下：
// | x | y | z | ? | ? | ? |
// | x | y | z | ? | ? | z |
// | x | y | z | ? | y | z |
// | x | y | x | y | z |
// 當添加新值時，原本的 | x | y | 的資料将被新值代替
// | new | x | y | z |
// T = O(N)
while(length--)
_intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
/* Set the value at the beginning or the end. */
// 設定新值，根據 prepend 的值來決定是添加到數組頭還是數組尾
if (prepend)
_intsetSet(is,0,value);
else
_intsetSet(is,intrev32ifbe(is->length),value);
// 更新整數集合的元素數量
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}
/*
* 向前或先後移動指定索引範圍内的數組元素
*
* 函數名中的 MoveTail 其實是一個有誤導性的名字，
* 這個函數可以向前或向後移動元素，
* 而不僅僅是向後
*
* 在添加新元素到數組時，就需要進行向後移動，
* 如果數組表示如下（？表示一個未設定新值的空間）：
* | x | y | z | ? |
* |<----->|
* 而新元素 n 的 pos 為 1 ，那麼數組将移動 y 和 z 兩個元素
* | x | y | y | z |
* |<----->|
* 接着就可以将新元素 n 設定到 pos 上了：
* | x | n | y | z |
*
* 當從數組中删除元素時，就需要進行向前移動，
* 如果數組表示如下，并且 b 為要删除的目标：
* | a | b | c | d |
* |<----->|
* 那麼程式就會移動 b 後的所有元素向前一個元素的位置，
* 進而覆寫 b 的資料：
* | a | c | d | d |
* |<----->|
* 最後，程式再從數組末尾删除一個元素的空間：
* | a | c | d |
* 這樣就完成了删除操作。
*
* T = O(N)
*/
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);
// 根據不同的編碼
// src = (Enc_t*)is->contents+from 記錄移動開始的位置
// dst = (Enc_t*)is_.contents+to 記錄移動結束的位置
// bytes *= sizeof(Enc_t) 計算一共要移動多少位元組
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);
}
// 進行移動
// T = O(N)
memmove(dst,src,bytes);
}
/* Insert an integer in the intset
*
* 嘗試将元素 value 添加到整數集合中。
*
* *success 的值訓示添加是否成功：
* - 如果添加成功，那麼将 *success 的值設為 1 。
* - 因為元素已存在而造成添加失敗時，将 *success 的值設為 0 。
*
* T = O(N)
*/
intset *intsetAdd(intset *is, int64_t value, uint8_t *success)
{
// 計算編碼 value 所需的長度
uint8_t valenc = _intsetValueEncoding(value);
uint32_t pos;
// 預設設定插入為成功
if (success) *success = 1;
// 如果 value 的編碼比整數集合現在的編碼要大
// 那麼表示 value 必然可以添加到整數集合中
// 并且整數集合需要對自身進行更新，才能滿足 value 所需的編碼
if (valenc > intrev32ifbe(is->encoding))
{
/* This always succeeds, so we don't need to curry *success. */
// T = O(N)
return intsetUpgradeAndAdd(is,value);
}
else
{
// 運作到這裡，表示整數集合現有的編碼方式适用于 value
// 在整數集合中查找 value ，看他是否存在：
// - 如果存在，那麼将 *success 設定為 0 ，并傳回未經改動的整數集合
// - 如果不存在，那麼可以插入 value 的位置将被儲存到 pos 指針中
// 等待後續程式使用
if (intsetSearch(is,value,&pos))
{
if (success) *success = 0;
return is;
}
// 運作到這裡，表示 value 不存在于集合中
// 程式需要将 value 添加到整數集合中
// 為 value 在集合中配置設定空間
is = intsetResize(is,intrev32ifbe(is->length)+1);
// 如果新元素不是被添加到底層數組的末尾
// 那麼需要對現有元素的資料進行移動，空出 pos 上的位置，用于設定新值
// 舉個例子
// 如果數組為：
// | x | y | z | ? |
// |<----->|
// 而新元素 n 的 pos 為 1 ，那麼數組将移動 y 和 z 兩個元素
// | x | y | y | z |
// |<----->|
// 這樣就可以将新元素設定到 pos 上了：
// | x | n | y | z |
// T = O(N)
if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
}
// 将新值設定到底層數組的指定位置中
_intsetSet(is,pos,value);
// 增一集合元素數量的計數器
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
// 傳回添加新元素後的整數集合
return is;
}
/* Delete integer from intset
*
* 從整數集合中删除值 value 。
*
* *success 的值訓示删除是否成功：
* - 因值不存在而造成删除失敗時該值為 0 。
* - 删除成功時該值為 1 。
*
* T = O(N)
*/
intset *intsetRemove(intset *is, int64_t value, int *success)
{
// 計算 value 的編碼方式
uint8_t valenc = _intsetValueEncoding(value);
uint32_t pos;
// 預設設定辨別值為删除失敗
if (success) *success = 0;
// 當 value 的編碼大小小于或等于集合的目前編碼方式（說明 value 有可能存在于集合）
// 并且 intsetSearch 的結果為真，那麼執行删除
// T = O(log N)
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 */
// 如果 value 不是位于數組的末尾
// 那麼需要對原本位于 value 之後的元素進行移動
//
// 舉個例子，如果數組表示如下，而 b 為删除的目标
// | a | b | c | d |
// 那麼 intsetMoveTail 将 b 之後的所有資料向前移動一個元素的空間，
// 覆寫 b 原來的資料
// | a | c | d | d |
// 之後 intsetResize 縮小記憶體大小時，
// 數組末尾多出來的一個元素的空間将被移除
// | a | c | d |
if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
// 縮小數組的大小，移除被删除元素占用的空間
// T = O(N)
is = intsetResize(is,len-1);
// 更新集合的元素數量
is->length = intrev32ifbe(len-1);
}
return is;
}
/* Determine whether a value belongs to this set
*
* 檢查給定值 value 是否集合中的元素。
*
* 是傳回 1 ，不是傳回 0 。
*
* T = O(log N)
*/
uint8_t intsetFind(intset *is, int64_t value)
{
// 計算 value 的編碼
uint8_t valenc = _intsetValueEncoding(value);
// 如果 value 的編碼大于集合的目前編碼，那麼 value 一定不存在于集合
// 當 value 的編碼小于等于集合的目前編碼時，
// 才再使用 intsetSearch 進行查找
return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL);
}
/* Return random member
*
* 從整數集合中随機傳回一個元素
*
* 隻能在集合非空時使用
*
* T = O(1)
*/
int64_t intsetRandom(intset *is)
{
// intrev32ifbe(is->length) 取出集合的元素數量
// 而 rand() % intrev32ifbe(is->length) 根據元素數量計算一個随機索引
// 然後 _intsetGet 負責根據随機索引來查找值
return _intsetGet(is,rand()%intrev32ifbe(is->length));
}
/*
* 取出集合底層數組指定位置中的值，并将它儲存到 value 指針中。
*
* 如果 pos 沒超出數組的索引範圍，那麼傳回 1 ，如果超出索引，那麼傳回 0 。
*
* T = O(1)
*/
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value)
{
// pos < intrev32ifbe(is->length)
// 檢查 pos 是否符合數組的範圍
if (pos < intrev32ifbe(is->length))
{
// 儲存值到指針
*value = _intsetGet(is,pos);
// 傳回成功訓示值
return 1;
}
// 超出索引範圍
return 0;
}
/* Return intset length
*
* 傳回整數集合現有的元素個數
*
* T = O(1)
*/
uint32_t intsetLen(intset *is)
{
return intrev32ifbe(is->length);
}
/* Return intset blob size in bytes.
*
* 傳回整數集合現在占用的位元組總數量
* 這個數量包括整數集合的結構大小，以及整數集合所有元素的總大小
*
* T = O(1)
*/
size_t intsetBlobLen(intset *is)
{
return sizeof(intset)+intrev32ifbe(is->length)*intrev32ifbe(is->encoding);
}
int main()
{
} 說明：依賴于redis的endianconv.h和zmalloc.h檔案
endianconv.h，zmalloc.c：大端和小端的互相轉換
zmalloc.h，zmalloc.c:對free和malloc函數的封裝，記憶體配置設定