Intset

A sorted, packed array of unique integers. The encoding for sets that contain only integer members and are small.

Source layout

File	Role
src/intset.c	Implementation.
src/intset.h	Public API.

Layout

typedef struct intset {
    uint32_t encoding;   /* INTSET_ENC_INT16 / INT32 / INT64 */
    uint32_t length;     /* count of elements */
    int8_t   contents[]; /* packed array, sorted ascending */
} intset;

The encoding adapts to the largest element:

• All elements ≤ 32767 → INT16 (2 bytes per element).
• Elements ≤ 2^31-1 → INT32.
• Otherwise → INT64.

When a larger element is added the whole array is upgraded in place to the next bigger encoding.

Why a packed array

For small integer-only sets the memory overhead of a hash table is huge (dict header + bucket array + per-entry struct). An intset stores elements with no overhead beyond two uint32_t and the array itself. Membership is O(log N) (binary search), insertion/deletion are O(N) (memmove). For sets of a few hundred elements the constant factors win against a hash table.

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(const intset *is);
size_t intsetBlobLen(intset *is);
intset *intsetUpgradeAndAdd(intset *is, int64_t value);

Conversion thresholds

The intset is used for sets up to set-max-intset-entries (default 512). Beyond that, the set is converted to a listpack (if set-max-listpack-entries allows) or a hash table.

The conversion happens in setTypeAdd / setTypeMaybeConvert in src/t_set.c.

Embedded tests

Run via ./redis-server test intset. The tests cover encoding upgrades, sorted-order invariant, find/insert/delete, and randomised stress.

Related pages

• robj, Data types.
• Listpack & quicklist — the next encoding step up for sets.