X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/aaada3f962a9f87fb239e55e3d26c1e794d411d5..a3fcd6bc21ec16f227bd98f7155372b2fd80de11:/src/intset.c diff --git a/src/intset.c b/src/intset.c index 2532582e..4dd0141d 100644 --- a/src/intset.c +++ b/src/intset.c @@ -3,6 +3,7 @@ #include #include "intset.h" #include "zmalloc.h" +#include "endian.h" /* Note that these encodings are ordered, so: * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */ @@ -10,21 +11,55 @@ #define INTSET_ENC_INT32 (sizeof(int32_t)) #define INTSET_ENC_INT64 (sizeof(int64_t)) -/* Accessors for each type of encoding */ -#define INTSET_VALUE_ENCODING(__val) (((__val) < INT32_MIN || (__val) > INT32_MAX) ? \ - INTSET_ENC_INT64 : (((__val) < INT16_MIN || (__val) > INT16_MAX) ? \ - INTSET_ENC_INT32 : INTSET_ENC_INT16)) -#define INTSET_GET_ENCODED(__is,__pos,__enc) ((__enc == INTSET_ENC_INT64) ? \ - ((int64_t*)(__is)->contents)[__pos] : ((__enc == INTSET_ENC_INT32) ? \ - ((int32_t*)(__is)->contents)[__pos] : ((int16_t*)(__is)->contents)[__pos])) -#define INTSET_GET(__is,__pos) (INTSET_GET_ENCODED(__is,__pos,(__is)->encoding)) -#define INTSET_SET(__is,__pos,__val) { \ - if ((__is)->encoding == INTSET_ENC_INT64) \ - ((int64_t*)(__is)->contents)[__pos] = (__val); \ - else if ((__is)->encoding == INTSET_ENC_INT32) \ - ((int32_t*)(__is)->contents)[__pos] = (__val); \ - else \ - ((int16_t*)(__is)->contents)[__pos] = (__val); } +/* Return the required encoding for the provided value. */ +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. */ +static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc) { + int64_t v64; + int32_t v32; + int16_t v16; + + 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. */ +static int64_t _intsetGet(intset *is, int pos) { + return _intsetGetEncoded(is,pos,is->encoding); +} + +/* Set the value at pos, using the configured encoding. */ +static void _intsetSet(intset *is, int pos, int64_t value) { + if (is->encoding == INTSET_ENC_INT64) { + ((int64_t*)is->contents)[pos] = value; + memrev64ifbe(((int64_t*)is->contents)+pos); + } else if (is->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. */ intset *intsetNew(void) { @@ -41,20 +76,6 @@ static intset *intsetResize(intset *is, uint32_t len) { return is; } -static intset *intsetUpgrade(intset *is, uint8_t newenc, uint8_t extra, uint8_t offset) { - uint8_t curenc = is->encoding; - int length = is->length; - - /* First set new encoding and resize */ - is->encoding = newenc; - is = intsetResize(is,is->length+extra); - - /* Upgrade back-to-front so we don't overwrite values */ - while(length--) - INTSET_SET(is,length+offset,INTSET_GET_ENCODED(is,length,curenc)); - return is; -} - /* Search for the position of "value". Return 1 when the value was found and * sets "pos" to the position of the value within the intset. Return 0 when * the value is not present in the intset and sets "pos" to the position @@ -70,10 +91,10 @@ static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) { } else { /* Check for the case where we know we cannot find the value, * but do know the insert position. */ - if (value > INTSET_GET(is,is->length-1)) { + if (value > _intsetGet(is,is->length-1)) { if (pos) *pos = is->length; return 0; - } else if (value < INTSET_GET(is,0)) { + } else if (value < _intsetGet(is,0)) { if (pos) *pos = 0; return 0; } @@ -81,7 +102,7 @@ static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) { while(max >= min) { mid = (min+max)/2; - cur = INTSET_GET(is,mid); + cur = _intsetGet(is,mid); if (value > cur) { min = mid+1; } else if (value < cur) { @@ -100,6 +121,32 @@ static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) { } } +/* Upgrades the intset to a larger encoding and inserts the given integer. */ +static intset *intsetUpgradeAndAdd(intset *is, int64_t value) { + uint8_t curenc = is->encoding; + uint8_t newenc = _intsetValueEncoding(value); + int length = is->length; + int prepend = value < 0 ? 1 : 0; + + /* First set new encoding and resize */ + is->encoding = newenc; + is = intsetResize(is,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. */ + while(length--) + _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc)); + + /* Set the value at the beginning or the end. */ + if (prepend) + _intsetSet(is,0,value); + else + _intsetSet(is,is->length,value); + is->length++; + return is; +} + static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) { void *src, *dst; uint32_t bytes = is->length-from; @@ -121,17 +168,16 @@ static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) { /* Insert an integer in the intset */ intset *intsetAdd(intset *is, int64_t value, uint8_t *success) { - uint8_t valenc = INTSET_VALUE_ENCODING(value); - uint32_t pos, offset; + uint8_t valenc = _intsetValueEncoding(value); + uint32_t pos; if (success) *success = 1; /* Upgrade encoding if necessary. If we need to upgrade, we know that * this value should be either appended (if > 0) or prepended (if < 0), * because it lies outside the range of existing values. */ if (valenc > is->encoding) { - offset = value < 0 ? 1 : 0; - is = intsetUpgrade(is,valenc,1,offset); - pos = (value < 0) ? 0 : is->length; + /* This always succeeds, so we don't need to curry *success. */ + return intsetUpgradeAndAdd(is,value); } else { /* Abort if the value is already present in the set. * This call will populate "pos" with the right position to insert @@ -145,14 +191,14 @@ intset *intsetAdd(intset *is, int64_t value, uint8_t *success) { if (pos < is->length) intsetMoveTail(is,pos,pos+1); } - INTSET_SET(is,pos,value); + _intsetSet(is,pos,value); is->length++; return is; } /* Delete integer from intset */ -intset *intsetRemove(intset *is, int64_t value, uint8_t *success) { - uint8_t valenc = INTSET_VALUE_ENCODING(value); +intset *intsetRemove(intset *is, int64_t value, int *success) { + uint8_t valenc = _intsetValueEncoding(value); uint32_t pos; if (success) *success = 0; @@ -170,20 +216,20 @@ intset *intsetRemove(intset *is, int64_t value, uint8_t *success) { /* Determine whether a value belongs to this set */ uint8_t intsetFind(intset *is, int64_t value) { - uint8_t valenc = INTSET_VALUE_ENCODING(value); + uint8_t valenc = _intsetValueEncoding(value); return valenc <= is->encoding && intsetSearch(is,value,NULL); } /* Return random member */ int64_t intsetRandom(intset *is) { - return INTSET_GET(is,rand()%is->length); + return _intsetGet(is,rand()%is->length); } /* Sets the value to the value at the given position. When this position is * out of range the function returns 0, when in range it returns 1. */ uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value) { if (pos < is->length) { - *value = INTSET_GET(is,pos); + *value = _intsetGet(is,pos); return 1; } return 0; @@ -194,13 +240,18 @@ uint32_t intsetLen(intset *is) { return is->length; } +/* Return intset blob size in bytes. */ +size_t intsetBlobLen(intset *is) { + return sizeof(intset)+is->length*is->encoding; +} + #ifdef INTSET_TEST_MAIN #include void intsetRepr(intset *is) { int i; for (i = 0; i < is->length; i++) { - printf("%lld\n", (uint64_t)INTSET_GET(is,i)); + printf("%lld\n", (uint64_t)_intsetGet(is,i)); } printf("\n"); } @@ -266,16 +317,16 @@ int main(int argc, char **argv) { sranddev(); printf("Value encodings: "); { - assert(INTSET_VALUE_ENCODING(-32768) == INTSET_ENC_INT16); - assert(INTSET_VALUE_ENCODING(+32767) == INTSET_ENC_INT16); - assert(INTSET_VALUE_ENCODING(-32769) == INTSET_ENC_INT32); - assert(INTSET_VALUE_ENCODING(+32768) == INTSET_ENC_INT32); - assert(INTSET_VALUE_ENCODING(-2147483648) == INTSET_ENC_INT32); - assert(INTSET_VALUE_ENCODING(+2147483647) == INTSET_ENC_INT32); - assert(INTSET_VALUE_ENCODING(-2147483649) == INTSET_ENC_INT64); - assert(INTSET_VALUE_ENCODING(+2147483648) == INTSET_ENC_INT64); - assert(INTSET_VALUE_ENCODING(-9223372036854775808ull) == INTSET_ENC_INT64); - assert(INTSET_VALUE_ENCODING(+9223372036854775807ull) == INTSET_ENC_INT64); + assert(_intsetValueEncoding(-32768) == INTSET_ENC_INT16); + assert(_intsetValueEncoding(+32767) == INTSET_ENC_INT16); + assert(_intsetValueEncoding(-32769) == INTSET_ENC_INT32); + assert(_intsetValueEncoding(+32768) == INTSET_ENC_INT32); + assert(_intsetValueEncoding(-2147483648) == INTSET_ENC_INT32); + assert(_intsetValueEncoding(+2147483647) == INTSET_ENC_INT32); + assert(_intsetValueEncoding(-2147483649) == INTSET_ENC_INT64); + assert(_intsetValueEncoding(+2147483648) == INTSET_ENC_INT64); + assert(_intsetValueEncoding(-9223372036854775808ull) == INTSET_ENC_INT64); + assert(_intsetValueEncoding(+9223372036854775807ull) == INTSET_ENC_INT64); ok(); }