Redis 整數(shù)集合的實現(xiàn)

2018-08-02 14:45 更新

整數(shù)集合(intset)是 Redis 用于保存整數(shù)值的集合抽象數(shù)據(jù)結(jié)構(gòu), 它可以保存類型為 int16_t 、 int32_t 或者 int64_t 的整數(shù)值, 并且保證集合中不會出現(xiàn)重復(fù)元素。

每個 intset.h/intset 結(jié)構(gòu)表示一個整數(shù)集合:

typedef struct intset {

    // 編碼方式
    uint32_t encoding;

    // 集合包含的元素數(shù)量
    uint32_t length;

    // 保存元素的數(shù)組
    int8_t contents[];

} intset;

contents 數(shù)組是整數(shù)集合的底層實現(xiàn): 整數(shù)集合的每個元素都是 contents 數(shù)組的一個數(shù)組項(item), 各個項在數(shù)組中按值的大小從小到大有序地排列, 并且數(shù)組中不包含任何重復(fù)項。

length 屬性記錄了整數(shù)集合包含的元素數(shù)量, 也即是 contents 數(shù)組的長度。

雖然 intset 結(jié)構(gòu)將 contents 屬性聲明為 int8_t 類型的數(shù)組, 但實際上 contents 數(shù)組并不保存任何 int8_t 類型的值 —— contents 數(shù)組的真正類型取決于 encoding 屬性的值:

  • 如果 encoding 屬性的值為 INTSET_ENC_INT16 , 那么 contents 就是一個 int16_t 類型的數(shù)組, 數(shù)組里的每個項都是一個 int16_t 類型的整數(shù)值 (最小值為 -32,768 ,最大值為 32,767 )。
  • 如果 encoding 屬性的值為 INTSET_ENC_INT32 , 那么 contents 就是一個 int32_t 類型的數(shù)組, 數(shù)組里的每個項都是一個 int32_t 類型的整數(shù)值 (最小值為 -2,147,483,648 ,最大值為 2,147,483,647 )。
  • 如果 encoding 屬性的值為 INTSET_ENC_INT64 , 那么 contents 就是一個 int64_t 類型的數(shù)組, 數(shù)組里的每個項都是一個 int64_t 類型的整數(shù)值 (最小值為 -9,223,372,036,854,775,808 ,最大值為 9,223,372,036,854,775,807 )。

圖 6-1 展示了一個整數(shù)集合示例:

  • encoding 屬性的值為 INTSET_ENC_INT16 , 表示整數(shù)集合的底層實現(xiàn)為 int16_t 類型的數(shù)組, 而集合保存的都是 int16_t 類型的整數(shù)值。
  • length 屬性的值為 5 , 表示整數(shù)集合包含五個元素。
  • contents 數(shù)組按從小到大的順序保存著集合中的五個元素。
  • 因為每個集合元素都是 int16_t 類型的整數(shù)值, 所以 contents 數(shù)組的大小等于 sizeof(int16_t) * 5 = 16 * 5 = 80 位。

圖 6-2 展示了另一個整數(shù)集合示例:

  • encoding 屬性的值為 INTSET_ENC_INT64 , 表示整數(shù)集合的底層實現(xiàn)為 int64_t 類型的數(shù)組, 而數(shù)組中保存的都是 int64_t 類型的整數(shù)值。
  • length 屬性的值為 4 , 表示整數(shù)集合包含四個元素。
  • contents 數(shù)組按從小到大的順序保存著集合中的四個元素。
  • 因為每個集合元素都是 int64_t 類型的整數(shù)值, 所以 contents 數(shù)組的大小為 sizeof(int64_t) * 4 = 64 * 4 = 256 位。

雖然 contents 數(shù)組保存的四個整數(shù)值中, 只有 -2675256175807981027 是真正需要用 int64_t 類型來保存的, 而其他的 1 、 3 、 5 三個值都可以用 int16_t 類型來保存, 不過根據(jù)整數(shù)集合的升級規(guī)則, 當(dāng)向一個底層為 int16_t 數(shù)組的整數(shù)集合添加一個 int64_t 類型的整數(shù)值時, 整數(shù)集合已有的所有元素都會被轉(zhuǎn)換成 int64_t 類型, 所以 contents 數(shù)組保存的四個整數(shù)值都是 int64_t 類型的, 不僅僅是-2675256175807981027 。

接下來的一節(jié)將對整數(shù)集合的升級操作進行詳細的介紹。

以上內(nèi)容是否對您有幫助:
在線筆記
App下載
App下載

掃描二維碼

下載編程獅App

公眾號
微信公眾號

編程獅公眾號