1.整數(shù)集合：整數(shù)的集合，升序排序，無(wú)重復(fù)元素

2.整數(shù)集合intset是集合鍵的底層實(shí)現(xiàn)之一，當(dāng)一個(gè)集合只包含整數(shù)值的元素，并且這個(gè)集合的元素?cái)?shù)量不多時(shí)，redis會(huì)使用整數(shù)集合作為集合鍵的底層實(shí)現(xiàn)

3.intset可通過(guò)屬性自定義編碼方式(int16_t/int32_t/int64_t)

4.當(dāng)往inset插入新元素時(shí)，如果新元素的類(lèi)型比inset的原編碼類(lèi)型長(zhǎng)，那么要先對(duì)inset進(jìn)行“升級(jí)”操作

5.升級(jí)操作：（不可逆操作）

1）根據(jù)新元素的類(lèi)型，擴(kuò)展intset底層數(shù)組的空間大小，并且為新元素分配空間

2）將原有的元素轉(zhuǎn)化成與新元素相同的類(lèi)型，并且將他們放在正確的位置上，仍然保持有序無(wú)重復(fù)

3）將新元素添加到底層數(shù)組中

6.因?yàn)榭赡艽嬖谏?jí)操作，所以往intset中添加元素的時(shí)間復(fù)雜度為O(N),N為元素個(gè)數(shù)

7.進(jìn)行升級(jí)操作的好處：1）提升靈活性，避免類(lèi)型錯(cuò)誤，2）節(jié)約內(nèi)存，在需要升級(jí)的時(shí)候才升級(jí)，節(jié)約了內(nèi)存，只有我們需要更大類(lèi)型的時(shí)候，才會(huì)升級(jí)成大類(lèi)型，其余時(shí)間都是小類(lèi)型，這樣節(jié)省內(nèi)存空間

源碼分析如下：

intset.h文件：

#ifndef __INTSET_H #define __INTSET_H #include <stdint.h>//====== 數(shù)據(jù)結(jié)構(gòu) ========// typedef struct intset {// 編碼方式 uint32_t encoding;// 集合包含的元素?cái)?shù)量 uint32_t length;// 保存元素的數(shù)組 int8_t contents[];} intset;//======= API ===========////創(chuàng)建一個(gè)新的整數(shù)集合 intset *intsetNew(void);//將給定的元素加到整數(shù)集合中 intset *intsetAdd(intset *is, int64_t value, uint8_t *success);//從整數(shù)集合中移除給定元素 intset *intsetRemove(intset *is, int64_t value, int *success);//檢查給定值是否存在集合 uint8_t intsetFind(intset *is, int64_t value);//從整數(shù)集合中隨機(jī)返回一個(gè)元素 int64_t intsetRandom(intset *is);//取出給定索引上的元素 uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value);//返回整數(shù)集合包含元素的個(gè)數(shù) uint32_t intsetLen(intset *is);//返回整數(shù)集合占用的內(nèi)存字節(jié)數(shù) 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;elsereturn INTSET_ENC_INT16; }/* Return the value at pos, given an encoding.** 根據(jù)給定的編碼方式 enc ，返回集合的底層數(shù)組在 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) 首先將數(shù)組轉(zhuǎn)換回被編碼的類(lèi)型// 然后 ((ENCODING*)is->contents)+pos 計(jì)算出元素在數(shù)組中的正確位置// 之后 member(&vEnc, ..., sizeof(vEnc)) 再?gòu)臄?shù)組中拷貝出正確數(shù)量的字節(jié)// 如果有需要的話， memrevEncifbe(&vEnc) 會(huì)對(duì)拷貝出的字節(jié)進(jìn)行大小端轉(zhuǎn)換// 最后將值返回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.** 根據(jù)集合的編碼方式，返回底層數(shù)組在 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.** 根據(jù)集合的編碼方式，將底層數(shù)組在 pos 位置上的值設(shè)為 value 。** T = O(1)*/ static void _intsetSet(intset *is, int pos, int64_t value) {// 取出集合的編碼方式uint32_t encoding = intrev32ifbe(is->encoding);// 根據(jù)編碼 ((Enc_t*)is->contents) 將數(shù)組轉(zhuǎn)換回正確的類(lèi)型// 然后 ((Enc_t*)is->contents)[pos] 定位到數(shù)組索引上// 接著 ((Enc_t*)is->contents)[pos] = value 將值賦給數(shù)組// 最后， ((Enc_t*)is->contents)+pos 定位到剛剛設(shè)置的新值上// 如果有需要的話， memrevEncifbe 將對(duì)值進(jìn)行大小端轉(zhuǎn)換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.** 創(chuàng)建并返回一個(gè)新的空整數(shù)集合** T = O(1)*/ intset *intsetNew(void) {// 為整數(shù)集合結(jié)構(gòu)分配空間intset *is = zmalloc(sizeof(intset));// 設(shè)置初始編碼is->encoding = intrev32ifbe(INTSET_ENC_INT16);// 初始化元素?cái)?shù)量is->length = 0;return is; }/* Resize the intset** 調(diào)整整數(shù)集合的內(nèi)存空間大小** 如果調(diào)整后的大小要比集合原來(lái)的大小要大，* 那么集合中原有元素的值不會(huì)被改變。** 返回值：調(diào)整大小后的整數(shù)集合** T = O(N)*/ static intset *intsetResize(intset *is, uint32_t len) {// 計(jì)算數(shù)組的空間大小uint32_t size = len*intrev32ifbe(is->encoding);// 根據(jù)空間大小，重新分配空間// 注意這里使用的是 zrealloc ，// 所以如果新空間大小比原來(lái)的空間大小要大，// 那么數(shù)組原有的數(shù)據(jù)會(huì)被保留is = zrealloc(is,sizeof(intset)+size);return is; }/** 在集合 is 的底層數(shù)組中查找值 value 所在的索引。** 成功找到 value 時(shí)，函數(shù)返回 1 ，并將 *pos 的值設(shè)為 value 所在的索引。** 當(dāng)在數(shù)組中沒(méi)找到 value 時(shí)，返回 0 。* 并將 *pos 的值設(shè)為 value 可以插入到數(shù)組中的位置。** 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 為空時(shí)的情況if (intrev32ifbe(is->length) == 0){if (pos) *pos = 0;return 0;}else{// 因?yàn)榈讓訑?shù)組是有序的，如果 value 比數(shù)組中最后一個(gè)值都要大// 那么 value 肯定不存在于集合中，// 并且應(yīng)該將 value 添加到底層數(shù)組的最末端if (value > _intsetGet(is,intrev32ifbe(is->length)-1)){if (pos) *pos = intrev32ifbe(is->length);return 0;// 因?yàn)榈讓訑?shù)組是有序的，如果 value 比數(shù)組中最前一個(gè)值都要小// 那么 value 肯定不存在于集合中，// 并且應(yīng)該將它添加到底層數(shù)組的最前端 }else if (value < _intsetGet(is,0)){if (pos) *pos = 0;return 0;}}// 在有序數(shù)組中進(jìn)行二分查找// 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;}}// 檢查是否已經(jīng)找到了 valueif (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.** 根據(jù)值 value 所使用的編碼方式，對(duì)整數(shù)集合的編碼進(jìn)行升級(jí)，* 并將值 value 添加到升級(jí)后的整數(shù)集合中。** 返回值：添加新元素之后的整數(shù)集合** T = O(N)*/ static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {// 當(dāng)前的編碼方式uint8_t curenc = intrev32ifbe(is->encoding);// 新值所需的編碼方式uint8_t newenc = _intsetValueEncoding(value);// 當(dāng)前集合的元素?cái)?shù)量int length = intrev32ifbe(is->length);// 根據(jù) value 的值，決定是將它添加到底層數(shù)組的最前端還是最后端// 注意，因?yàn)?value 的編碼比集合原有的其他元素的編碼都要大// 所以 value 要么大于集合中的所有元素，要么小于集合中的所有元素// 因此，value 只能添加到底層數(shù)組的最前端或最后端int prepend = value < 0 ? 1 : 0;/* First set new encoding and resize */// 更新集合的編碼方式is->encoding = intrev32ifbe(newenc);// 根據(jù)新編碼對(duì)集合（的底層數(shù)組）進(jìn)行空間調(diào)整// 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. */// 根據(jù)集合原來(lái)的編碼方式，從底層數(shù)組中取出集合元素// 然后再將元素以新編碼的方式添加到集合中// 當(dāng)完成了這個(gè)步驟之后，集合中所有原有的元素就完成了從舊編碼到新編碼的轉(zhuǎn)換// 因?yàn)樾路峙涞目臻g都放在數(shù)組的后端，所以程序先從后端向前端移動(dòng)元素// 舉個(gè)例子，假設(shè)原來(lái)有 curenc 編碼的三個(gè)元素，它們?cè)跀?shù)組中排列如下：// | x | y | z |// 當(dāng)程序?qū)?shù)組進(jìn)行重分配之后，數(shù)組就被擴(kuò)容了（符號(hào) ？ 表示未使用的內(nèi)存）：// | x | y | z | ? | ? | ? |// 這時(shí)程序從數(shù)組后端開(kāi)始，重新插入元素：// | x | y | z | ? | z | ? |// | x | y | y | z | ? |// | x | y | z | ? |// 最后，程序可以將新元素添加到最后 ？ 號(hào)標(biāo)示的位置中：// | x | y | z | new |// 上面演示的是新元素比原來(lái)的所有元素都大的情況，也即是 prepend == 0// 當(dāng)新元素比原來(lái)的所有元素都小時(shí)（prepend == 1），調(diào)整的過(guò)程如下：// | x | y | z | ? | ? | ? |// | x | y | z | ? | ? | z |// | x | y | z | ? | y | z |// | x | y | x | y | z |// 當(dāng)添加新值時(shí)，原本的 | x | y | 的數(shù)據(jù)將被新值代替// | 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. */// 設(shè)置新值，根據(jù) prepend 的值來(lái)決定是添加到數(shù)組頭還是數(shù)組尾if (prepend)_intsetSet(is,0,value);else_intsetSet(is,intrev32ifbe(is->length),value);// 更新整數(shù)集合的元素?cái)?shù)量is->length = intrev32ifbe(intrev32ifbe(is->length)+1);return is; }/** 向前或先后移動(dòng)指定索引范圍內(nèi)的數(shù)組元素** 函數(shù)名中的 MoveTail 其實(shí)是一個(gè)有誤導(dǎo)性的名字，* 這個(gè)函數(shù)可以向前或向后移動(dòng)元素，* 而不僅僅是向后** 在添加新元素到數(shù)組時(shí)，就需要進(jìn)行向后移動(dòng)，* 如果數(shù)組表示如下（？表示一個(gè)未設(shè)置新值的空間）：* | x | y | z | ? |* |<----->|* 而新元素 n 的 pos 為 1 ，那么數(shù)組將移動(dòng) y 和 z 兩個(gè)元素* | x | y | y | z |* |<----->|* 接著就可以將新元素 n 設(shè)置到 pos 上了：* | x | n | y | z |** 當(dāng)從數(shù)組中刪除元素時(shí)，就需要進(jìn)行向前移動(dòng)，* 如果數(shù)組表示如下，并且 b 為要?jiǎng)h除的目標(biāo)：* | a | b | c | d |* |<----->|* 那么程序就會(huì)移動(dòng) b 后的所有元素向前一個(gè)元素的位置，* 從而覆蓋 b 的數(shù)據(jù)：* | a | c | d | d |* |<----->|* 最后，程序再?gòu)臄?shù)組末尾刪除一個(gè)元素的空間：* | a | c | d |* 這樣就完成了刪除操作。** T = O(N)*/ static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) {void *src, *dst;// 要移動(dòng)的元素個(gè)數(shù)uint32_t bytes = intrev32ifbe(is->length)-from;// 集合的編碼方式uint32_t encoding = intrev32ifbe(is->encoding);// 根據(jù)不同的編碼// src = (Enc_t*)is->contents+from 記錄移動(dòng)開(kāi)始的位置// dst = (Enc_t*)is_.contents+to 記錄移動(dòng)結(jié)束的位置// bytes *= sizeof(Enc_t) 計(jì)算一共要移動(dòng)多少字節(jié)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);}// 進(jìn)行移動(dòng)// T = O(N) memmove(dst,src,bytes); }/* Insert an integer in the intset** 嘗試將元素 value 添加到整數(shù)集合中。** *success 的值指示添加是否成功：* - 如果添加成功，那么將 *success 的值設(shè)為 1 。* - 因?yàn)樵匾汛嬖诙斐商砑邮r(shí)，將 *success 的值設(shè)為 0 。** T = O(N)*/ intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {// 計(jì)算編碼 value 所需的長(zhǎng)度uint8_t valenc = _intsetValueEncoding(value);uint32_t pos;// 默認(rèn)設(shè)置插入為成功if (success) *success = 1;// 如果 value 的編碼比整數(shù)集合現(xiàn)在的編碼要大// 那么表示 value 必然可以添加到整數(shù)集合中// 并且整數(shù)集合需要對(duì)自身進(jìn)行升級(jí)，才能滿足 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{// 運(yùn)行到這里，表示整數(shù)集合現(xiàn)有的編碼方式適用于 value// 在整數(shù)集合中查找 value ，看他是否存在：// - 如果存在，那么將 *success 設(shè)置為 0 ，并返回未經(jīng)改動(dòng)的整數(shù)集合// - 如果不存在，那么可以插入 value 的位置將被保存到 pos 指針中// 等待后續(xù)程序使用if (intsetSearch(is,value,&pos)){if (success) *success = 0;return is;}// 運(yùn)行到這里，表示 value 不存在于集合中// 程序需要將 value 添加到整數(shù)集合中// 為 value 在集合中分配空間is = intsetResize(is,intrev32ifbe(is->length)+1);// 如果新元素不是被添加到底層數(shù)組的末尾// 那么需要對(duì)現(xiàn)有元素的數(shù)據(jù)進(jìn)行移動(dòng)，空出 pos 上的位置，用于設(shè)置新值// 舉個(gè)例子// 如果數(shù)組為：// | x | y | z | ? |// |<----->|// 而新元素 n 的 pos 為 1 ，那么數(shù)組將移動(dòng) y 和 z 兩個(gè)元素// | x | y | y | z |// |<----->|// 這樣就可以將新元素設(shè)置到 pos 上了：// | x | n | y | z |// T = O(N)if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);}// 將新值設(shè)置到底層數(shù)組的指定位置中_intsetSet(is,pos,value);// 增一集合元素?cái)?shù)量的計(jì)數(shù)器is->length = intrev32ifbe(intrev32ifbe(is->length)+1);// 返回添加新元素后的整數(shù)集合return is; }/* Delete integer from intset** 從整數(shù)集合中刪除值 value 。** *success 的值指示刪除是否成功：* - 因值不存在而造成刪除失敗時(shí)該值為 0 。* - 刪除成功時(shí)該值為 1 。** T = O(N)*/ intset *intsetRemove(intset *is, int64_t value, int *success) {// 計(jì)算 value 的編碼方式uint8_t valenc = _intsetValueEncoding(value);uint32_t pos;// 默認(rèn)設(shè)置標(biāo)識(shí)值為刪除失敗if (success) *success = 0;// 當(dāng) value 的編碼大小小于或等于集合的當(dāng)前編碼方式（說(shuō)明 value 有可能存在于集合）// 并且 intsetSearch 的結(jié)果為真，那么執(zhí)行刪除// T = O(log N)if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)){// 取出集合當(dāng)前的元素?cái)?shù)量uint32_t len = intrev32ifbe(is->length);/* We know we can delete */// 設(shè)置標(biāo)識(shí)值為刪除成功if (success) *success = 1;/* Overwrite value with tail and update length */// 如果 value 不是位于數(shù)組的末尾// 那么需要對(duì)原本位于 value 之后的元素進(jìn)行移動(dòng)//// 舉個(gè)例子，如果數(shù)組表示如下，而 b 為刪除的目標(biāo)// | a | b | c | d |// 那么 intsetMoveTail 將 b 之后的所有數(shù)據(jù)向前移動(dòng)一個(gè)元素的空間，// 覆蓋 b 原來(lái)的數(shù)據(jù)// | a | c | d | d |// 之后 intsetResize 縮小內(nèi)存大小時(shí)，// 數(shù)組末尾多出來(lái)的一個(gè)元素的空間將被移除// | a | c | d |if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);// 縮小數(shù)組的大小，移除被刪除元素占用的空間// T = O(N)is = intsetResize(is,len-1);// 更新集合的元素?cái)?shù)量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) {// 計(jì)算 value 的編碼uint8_t valenc = _intsetValueEncoding(value);// 如果 value 的編碼大于集合的當(dāng)前編碼，那么 value 一定不存在于集合// 當(dāng) value 的編碼小于等于集合的當(dāng)前編碼時(shí)，// 才再使用 intsetSearch 進(jìn)行查找return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL); }/* Return random member** 從整數(shù)集合中隨機(jī)返回一個(gè)元素** 只能在集合非空時(shí)使用** T = O(1)*/ int64_t intsetRandom(intset *is) {// intrev32ifbe(is->length) 取出集合的元素?cái)?shù)量// 而 rand() % intrev32ifbe(is->length) 根據(jù)元素?cái)?shù)量計(jì)算一個(gè)隨機(jī)索引// 然后 _intsetGet 負(fù)責(zé)根據(jù)隨機(jī)索引來(lái)查找值return _intsetGet(is,rand()%intrev32ifbe(is->length)); }/** 取出集合底層數(shù)組指定位置中的值，并將它保存到 value 指針中。** 如果 pos 沒(méi)超出數(shù)組的索引范圍，那么返回 1 ，如果超出索引，那么返回 0 。** T = O(1)*/ uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value) {// pos < intrev32ifbe(is->length)// 檢查 pos 是否符合數(shù)組的范圍if (pos < intrev32ifbe(is->length)){// 保存值到指針*value = _intsetGet(is,pos);// 返回成功指示值return 1;}// 超出索引范圍return 0; }/* Return intset length** 返回整數(shù)集合現(xiàn)有的元素個(gè)數(shù)** T = O(1)*/ uint32_t intsetLen(intset *is) {return intrev32ifbe(is->length); }/* Return intset blob size in bytes.** 返回整數(shù)集合現(xiàn)在占用的字節(jié)總數(shù)量* 這個(gè)數(shù)量包括整數(shù)集合的結(jié)構(gòu)大小，以及整數(shù)集合所有元素的總大小** T = O(1)*/ size_t intsetBlobLen(intset *is) {return sizeof(intset)+intrev32ifbe(is->length)*intrev32ifbe(is->encoding); }int main() {}

說(shuō)明：依賴于redis的endianconv.h和zmalloc.h文件

endianconv.h，zmalloc.c：大端和小端的相互轉(zhuǎn)換

zmalloc.h，zmalloc.c:對(duì)free和malloc函數(shù)的封裝，內(nèi)存分配

轉(zhuǎn)載于:https://www.cnblogs.com/yinbiao/p/11249161.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的Redis学习之intset整数集合源码分析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。