intset.c

/*
 * Copyright (c) 2009-2012, Pieter Noordhuis <pcnoordhuis at gmail dot com>
 * Copyright (c) 2009-2012, Salvatore Sanfilippo <antirez at gmail dot com>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 * * Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 * * Neither the name of Redis nor the names of its contributors may be used
 * to endorse or promote products derived from this software without
 * specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"intset.h"
#include"zmalloc.h"
#include"endianconv.h"
#include"redisassert.h"

/* Note that these encodings are ordered, so:
 * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#defineINTSET_ENC_INT16 (sizeof(int16_t))
#defineINTSET_ENC_INT32 (sizeof(int32_t))
#defineINTSET_ENC_INT64 (sizeof(int64_t))

/* Return the required encoding for the provided value. */
staticuint8_t_intsetValueEncoding(int64_tv) {
if (v<INT32_MIN||v>INT32_MAX)
returnINTSET_ENC_INT64;
elseif (v<INT16_MIN||v>INT16_MAX)
returnINTSET_ENC_INT32;
else
returnINTSET_ENC_INT16;
}

/* Return the value at pos, given an encoding. */
staticint64_t_intsetGetEncoded(intset*is, intpos, uint8_tenc) {
int64_tv64;
int32_tv32;
int16_tv16;

if (enc==INTSET_ENC_INT64) {
memcpy(&v64,((int64_t*)is->contents)+pos,sizeof(v64));
memrev64ifbe(&v64);
returnv64;
 } elseif (enc==INTSET_ENC_INT32) {
memcpy(&v32,((int32_t*)is->contents)+pos,sizeof(v32));
memrev32ifbe(&v32);
returnv32;
 } else {
memcpy(&v16,((int16_t*)is->contents)+pos,sizeof(v16));
memrev16ifbe(&v16);
returnv16;
 }
}

/* Return the value at pos, using the configured encoding. */
staticint64_t_intsetGet(intset*is, intpos) {
return_intsetGetEncoded(is,pos,intrev32ifbe(is->encoding));
}

/* Set the value at pos, using the configured encoding. */
staticvoid_intsetSet(intset*is, intpos, int64_tvalue) {
uint32_tencoding=intrev32ifbe(is->encoding);

if (encoding==INTSET_ENC_INT64) {
 ((int64_t*)is->contents)[pos] =value;
memrev64ifbe(((int64_t*)is->contents)+pos);
 } elseif (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) {
intset*is=zmalloc(sizeof(intset));
is->encoding=intrev32ifbe(INTSET_ENC_INT16);
is->length=0;
returnis;
}

/* Resize the intset */
staticintset*intsetResize(intset*is, uint32_tlen) {
uint32_tsize=len*intrev32ifbe(is->encoding);
is=zrealloc(is,sizeof(intset)+size);
returnis;
}

/* 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
 * where "value" can be inserted. */
staticuint8_tintsetSearch(intset*is, int64_tvalue, uint32_t*pos) {
intmin=0, max=intrev32ifbe(is->length)-1, mid=-1;
int64_tcur=-1;

/* The value can never be found when the set is empty */
if (intrev32ifbe(is->length) ==0) {
if (pos) *pos=0;
return0;
 } else {
/* Check for the case where we know we cannot find the value,
 * but do know the insert position. */
if (value>_intsetGet(is,max)) {
if (pos) *pos=intrev32ifbe(is->length);
return0;
 } elseif (value<_intsetGet(is,0)) {
if (pos) *pos=0;
return0;
 }
 }

while(max >= min) {
mid= ((unsigned int)min+ (unsigned int)max) >> 1;
cur=_intsetGet(is,mid);
if (value>cur) {
min=mid+1;
 } elseif (value<cur) {
max=mid-1;
 } else {
break;
 }
 }

if (value==cur) {
if (pos) *pos=mid;
return1;
 } else {
if (pos) *pos=min;
return0;
 }
}

/* Upgrades the intset to a larger encoding and inserts the given integer. */
staticintset*intsetUpgradeAndAdd(intset*is, int64_tvalue) {
uint8_tcurenc=intrev32ifbe(is->encoding);
uint8_tnewenc=_intsetValueEncoding(value);
intlength=intrev32ifbe(is->length);
intprepend=value<0 ? 1 : 0;

/* First set new encoding and resize */
is->encoding=intrev32ifbe(newenc);
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. */
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,intrev32ifbe(is->length),value);
is->length=intrev32ifbe(intrev32ifbe(is->length)+1);
returnis;
}

staticvoidintsetMoveTail(intset*is, uint32_tfrom, uint32_tto) {
void*src, *dst;
uint32_tbytes=intrev32ifbe(is->length)-from;
uint32_tencoding=intrev32ifbe(is->encoding);

if (encoding==INTSET_ENC_INT64) {
src= (int64_t*)is->contents+from;
dst= (int64_t*)is->contents+to;
bytes *= sizeof(int64_t);
 } elseif (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);
 }
memmove(dst,src,bytes);
}

/* Insert an integer in the intset */
intset*intsetAdd(intset*is, int64_tvalue, uint8_t*success) {
uint8_tvalenc=_intsetValueEncoding(value);
uint32_tpos;
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>intrev32ifbe(is->encoding)) {
/* This always succeeds, so we don't need to curry *success. */
returnintsetUpgradeAndAdd(is,value);
 } else {
/* Abort if the value is already present in the set.
 * This call will populate "pos" with the right position to insert
 * the value when it cannot be found. */
if (intsetSearch(is,value,&pos)) {
if (success) *success=0;
returnis;
 }

is=intsetResize(is,intrev32ifbe(is->length)+1);
if (pos<intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
 }

_intsetSet(is,pos,value);
is->length=intrev32ifbe(intrev32ifbe(is->length)+1);
returnis;
}

/* Delete integer from intset */
intset*intsetRemove(intset*is, int64_tvalue, int*success) {
uint8_tvalenc=_intsetValueEncoding(value);
uint32_tpos;
if (success) *success=0;

if (valenc <= intrev32ifbe(is->encoding) &&intsetSearch(is,value,&pos)) {
uint32_tlen=intrev32ifbe(is->length);

/* We know we can delete */
if (success) *success=1;

/* Overwrite value with tail and update length */
if (pos< (len-1)) intsetMoveTail(is,pos+1,pos);
is=intsetResize(is,len-1);
is->length=intrev32ifbe(len-1);
 }
returnis;
}

/* Determine whether a value belongs to this set */
uint8_tintsetFind(intset*is, int64_tvalue) {
uint8_tvalenc=_intsetValueEncoding(value);
returnvalenc <= intrev32ifbe(is->encoding) &&intsetSearch(is,value,NULL);
}

/* Return random member */
int64_tintsetRandom(intset*is) {
uint32_tlen=intrev32ifbe(is->length);
assert(len); /* avoid division by zero on corrupt intset payload. */
return_intsetGet(is,rand()%len);
}

/* Get the value at the given position. When this position is
 * out of range the function returns 0, when in range it returns 1. */
uint8_tintsetGet(intset*is, uint32_tpos, int64_t*value) {
if (pos<intrev32ifbe(is->length)) {
*value=_intsetGet(is,pos);
return1;
 }
return0;
}

/* Return intset length */
uint32_tintsetLen(constintset*is) {
returnintrev32ifbe(is->length);
}

/* Return intset blob size in bytes. */
size_tintsetBlobLen(intset*is) {
returnsizeof(intset)+(size_t)intrev32ifbe(is->length)*intrev32ifbe(is->encoding);
}

/* Validate the integrity of the data structure.
 * when `deep` is 0, only the integrity of the header is validated.
 * when `deep` is 1, we make sure there are no duplicate or out of order records. */
intintsetValidateIntegrity(constunsigned char*p, size_tsize, intdeep) {
intset*is= (intset*)p;
/* check that we can actually read the header. */
if (size<sizeof(*is))
return0;

uint32_tencoding=intrev32ifbe(is->encoding);

size_trecord_size;
if (encoding==INTSET_ENC_INT64) {
record_size=INTSET_ENC_INT64;
 } elseif (encoding==INTSET_ENC_INT32) {
record_size=INTSET_ENC_INT32;
 } elseif (encoding==INTSET_ENC_INT16){
record_size=INTSET_ENC_INT16;
 } else {
return0;
 }

/* check that the size matchies (all records are inside the buffer). */
uint32_tcount=intrev32ifbe(is->length);
if (sizeof(*is) +count*record_size!=size)
return0;

/* check that the set is not empty. */
if (count==0)
return0;

if (!deep)
return1;

/* check that there are no dup or out of order records. */
int64_tprev=_intsetGet(is,0);
for (uint32_ti=1; i<count; i++) {
int64_tcur=_intsetGet(is,i);
if (cur <= prev)
return0;
prev=cur;
 }

return1;
}

#ifdefREDIS_TEST
#include<sys/time.h>
#include<time.h>

#if0
staticvoidintsetRepr(intset*is) {
for (uint32_ti=0; i<intrev32ifbe(is->length); i++) {
printf("%lld\n", (uint64_t)_intsetGet(is,i));
 }
printf("\n");
}

staticvoiderror(char*err) {
printf("%s\n", err);
exit(1);
}
#endif

staticvoidok(void) {
printf("OK\n");
}

staticlong longusec(void) {
structtimevaltv;
gettimeofday(&tv,NULL);
return (((long long)tv.tv_sec)*1000000)+tv.tv_usec;
}

staticintset*createSet(intbits, intsize) {
uint64_tmask= (1<<bits)-1;
uint64_tvalue;
intset*is=intsetNew();

for (inti=0; i<size; i++) {
if (bits>32) {
value= (rand()*rand()) &mask;
 } else {
value=rand() &mask;
 }
is=intsetAdd(is,value,NULL);
 }
returnis;
}

staticvoidcheckConsistency(intset*is) {
for (uint32_ti=0; i< (intrev32ifbe(is->length)-1); i++) {
uint32_tencoding=intrev32ifbe(is->encoding);

if (encoding==INTSET_ENC_INT16) {
int16_t*i16= (int16_t*)is->contents;
assert(i16[i] <i16[i+1]);
 } elseif (encoding==INTSET_ENC_INT32) {
int32_t*i32= (int32_t*)is->contents;
assert(i32[i] <i32[i+1]);
 } else {
int64_t*i64= (int64_t*)is->contents;
assert(i64[i] <i64[i+1]);
 }
 }
}

#defineUNUSED(x) (void)(x)
intintsetTest(intargc, char**argv, intaccurate) {
uint8_tsuccess;
inti;
intset*is;
srand(time(NULL));

UNUSED(argc);
UNUSED(argv);
UNUSED(accurate);

printf("Value encodings: "); {
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();
 }

printf("Basic adding: "); {
is=intsetNew();
is=intsetAdd(is,5,&success); assert(success);
is=intsetAdd(is,6,&success); assert(success);
is=intsetAdd(is,4,&success); assert(success);
is=intsetAdd(is,4,&success); assert(!success);
ok();
zfree(is);
 }

printf("Large number of random adds: "); {
uint32_tinserts=0;
is=intsetNew();
for (i=0; i<1024; i++) {
is=intsetAdd(is,rand()%0x800,&success);
if (success) inserts++;
 }
assert(intrev32ifbe(is->length) ==inserts);
checkConsistency(is);
ok();
zfree(is);
 }

printf("Upgrade from int16 to int32: "); {
is=intsetNew();
is=intsetAdd(is,32,NULL);
assert(intrev32ifbe(is->encoding) ==INTSET_ENC_INT16);
is=intsetAdd(is,65535,NULL);
assert(intrev32ifbe(is->encoding) ==INTSET_ENC_INT32);
assert(intsetFind(is,32));
assert(intsetFind(is,65535));
checkConsistency(is);
zfree(is);

is=intsetNew();
is=intsetAdd(is,32,NULL);
assert(intrev32ifbe(is->encoding) ==INTSET_ENC_INT16);
is=intsetAdd(is,-65535,NULL);
assert(intrev32ifbe(is->encoding) ==INTSET_ENC_INT32);
assert(intsetFind(is,32));
assert(intsetFind(is,-65535));
checkConsistency(is);
ok();
zfree(is);
 }

printf("Upgrade from int16 to int64: "); {
is=intsetNew();
is=intsetAdd(is,32,NULL);
assert(intrev32ifbe(is->encoding) ==INTSET_ENC_INT16);
is=intsetAdd(is,4294967295,NULL);
assert(intrev32ifbe(is->encoding) ==INTSET_ENC_INT64);
assert(intsetFind(is,32));
assert(intsetFind(is,4294967295));
checkConsistency(is);
zfree(is);

is=intsetNew();
is=intsetAdd(is,32,NULL);
assert(intrev32ifbe(is->encoding) ==INTSET_ENC_INT16);
is=intsetAdd(is,-4294967295,NULL);
assert(intrev32ifbe(is->encoding) ==INTSET_ENC_INT64);
assert(intsetFind(is,32));
assert(intsetFind(is,-4294967295));
checkConsistency(is);
ok();
zfree(is);
 }

printf("Upgrade from int32 to int64: "); {
is=intsetNew();
is=intsetAdd(is,65535,NULL);
assert(intrev32ifbe(is->encoding) ==INTSET_ENC_INT32);
is=intsetAdd(is,4294967295,NULL);
assert(intrev32ifbe(is->encoding) ==INTSET_ENC_INT64);
assert(intsetFind(is,65535));
assert(intsetFind(is,4294967295));
checkConsistency(is);
zfree(is);

is=intsetNew();
is=intsetAdd(is,65535,NULL);
assert(intrev32ifbe(is->encoding) ==INTSET_ENC_INT32);
is=intsetAdd(is,-4294967295,NULL);
assert(intrev32ifbe(is->encoding) ==INTSET_ENC_INT64);
assert(intsetFind(is,65535));
assert(intsetFind(is,-4294967295));
checkConsistency(is);
ok();
zfree(is);
 }

printf("Stress lookups: "); {
longnum=100000, size=10000;
inti, bits=20;
long longstart;
is=createSet(bits,size);
checkConsistency(is);

start=usec();
for (i=0; i<num; i++) intsetSearch(is,rand() % ((1<<bits)-1),NULL);
printf("%ld lookups, %ld element set, %lldusec\n",
num,size,usec()-start);
zfree(is);
 }

printf("Stress add+delete: "); {
inti, v1, v2;
is=intsetNew();
for (i=0; i<0xffff; i++) {
v1=rand() % 0xfff;
is=intsetAdd(is,v1,NULL);
assert(intsetFind(is,v1));

v2=rand() % 0xfff;
is=intsetRemove(is,v2,NULL);
assert(!intsetFind(is,v2));
 }
checkConsistency(is);
ok();
zfree(is);
 }

return0;
}
#endif