Redis 升級(jí)

每當(dāng)我們要將一個(gè)新元素添加到整數(shù)集合里面， 并且新元素的類型比整數(shù)集合現(xiàn)有所有元素的類型都要長時(shí)， 整數(shù)集合需要先進(jìn)行升級(jí)（upgrade）， 然后才能將新元素添加到整數(shù)集合里面。

升級(jí)整數(shù)集合并添加新元素共分為三步進(jìn)行：

1. 根據(jù)新元素的類型， 擴(kuò)展整數(shù)集合底層數(shù)組的空間大小， 并為新元素分配空間。
2. 將底層數(shù)組現(xiàn)有的所有元素都轉(zhuǎn)換成與新元素相同的類型， 并將類型轉(zhuǎn)換后的元素放置到正確的位上， 而且在放置元素的過程中， 需要繼續(xù)維持底層數(shù)組的有序性質(zhì)不變。
3. 將新元素添加到底層數(shù)組里面。

舉個(gè)例子， 假設(shè)現(xiàn)在有一個(gè) INTSET_ENC_INT16 編碼的整數(shù)集合， 集合中包含三個(gè) int16_t 類型的元素， 如圖 6-3 所示。

因?yàn)槊總€(gè)元素都占用 16 位空間， 所以整數(shù)集合底層數(shù)組的大小為 3 * 16 = 48 位， 圖 6-4 展示了整數(shù)集合的三個(gè)元素在這 48 位里的位置。

現(xiàn)在， 假設(shè)我們要將類型為 int32_t 的整數(shù)值 65535 添加到整數(shù)集合里面， 因?yàn)?nbsp;65535 的類型 int32_t 比整數(shù)集合當(dāng)前所有元素的類型都要長， 所以在將 65535 添加到整數(shù)集合之前， 程序需要先對(duì)整數(shù)集合進(jìn)行升級(jí)。

升級(jí)首先要做的是， 根據(jù)新類型的長度， 以及集合元素的數(shù)量（包括要添加的新元素在內(nèi)）， 對(duì)底層數(shù)組進(jìn)行空間重分配。

整數(shù)集合目前有三個(gè)元素， 再加上新元素 65535 ， 整數(shù)集合需要分配四個(gè)元素的空間， 因?yàn)槊總€(gè) int32_t 整數(shù)值需要占用 32 位空間， 所以在空間重分配之后， 底層數(shù)組的大小將是 32 * 4 = 128 位， 如圖 6-5 所示。

雖然程序?qū)Φ讓訑?shù)組進(jìn)行了空間重分配， 但數(shù)組原有的三個(gè)元素 1 、 2 、 3 仍然是 int16_t 類型， 這些元素還保存在數(shù)組的前 48 位里面， 所以程序接下來要做的就是將這三個(gè)元素轉(zhuǎn)換成 int32_t 類型， 并將轉(zhuǎn)換后的元素放置到正確的位上面， 而且在放置元素的過程中， 需要維持底層數(shù)組的有序性質(zhì)不變。

首先， 因?yàn)樵?nbsp;3 在 1 、 2 、 3 、 65535 四個(gè)元素中排名第三， 所以它將被移動(dòng)到 contents 數(shù)組的索引 2 位置上， 也即是數(shù)組 64 位至 95 位的空間內(nèi)， 如圖 6-6 所示。

接著， 因?yàn)樵?nbsp;2 在 1 、 2 、 3 、 65535 四個(gè)元素中排名第二， 所以它將被移動(dòng)到 contents 數(shù)組的索引 1 位置上， 也即是數(shù)組的 32位至 63 位的空間內(nèi)， 如圖 6-7 所示。

之后， 因?yàn)樵?nbsp;1 在 1 、 2 、 3 、 65535 四個(gè)元素中排名第一， 所以它將被移動(dòng)到 contents 數(shù)組的索引 0 位置上， 也即是數(shù)組的 0 位至 31 位的空間內(nèi)， 如圖 6-8 所示。

然后， 因?yàn)樵?nbsp;65535 在 1 、 2 、 3 、 65535 四個(gè)元素中排名第四， 所以它將被添加到 contents 數(shù)組的索引 3 位置上， 也即是數(shù)組的96 位至 127 位的空間內(nèi)， 如圖 6-9 所示。

最后， 程序?qū)⒄麛?shù)集合 encoding 屬性的值從 INTSET_ENC_INT16 改為 INTSET_ENC_INT32 ， 并將 length 屬性的值從 3 改為 4 ， 設(shè)置完成之后的整數(shù)集合如圖 6-10 所示。

因?yàn)槊看蜗蛘麛?shù)集合添加新元素都可能會(huì)引起升級(jí)， 而每次升級(jí)都需要對(duì)底層數(shù)組中已有的所有元素進(jìn)行類型轉(zhuǎn)換， 所以向整數(shù)集合添加新元素的時(shí)間復(fù)雜度為  。

其他類型的升級(jí)操作， 比如從 INTSET_ENC_INT16 編碼升級(jí)為 INTSET_ENC_INT64 編碼， 或者從 INTSET_ENC_INT32 編碼升級(jí)為 INTSET_ENC_INT64 編碼， 升級(jí)的過程都和上面展示的升級(jí)過程類似。

升級(jí)之后新元素的擺放位置

因?yàn)橐l(fā)升級(jí)的新元素的長度總是比整數(shù)集合現(xiàn)有所有元素的長度都大， 所以這個(gè)新元素的值要么就大于所有現(xiàn)有元素， 要么就小于所有現(xiàn)有元素：

• 在新元素小于所有現(xiàn)有元素的情況下， 新元素會(huì)被放置在底層數(shù)組的最開頭（索引 0 ）；
• 在新元素大于所有現(xiàn)有元素的情況下， 新元素會(huì)被放置在底層數(shù)組的最末尾（索引 length-1 ）。