src/intset.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include "intset.h"
   5 #include "zmalloc.h"
   6
   7 /* Note that these encodings are ordered, so:
   8  * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
   9 #define INTSET_ENC_INT16 (sizeof(int16_t))
  10 #define INTSET_ENC_INT32 (sizeof(int32_t))
  11 #define INTSET_ENC_INT64 (sizeof(int64_t))
  12
  13 /* Accessors for each type of encoding */
  14 #define INTSET_VALUE_ENCODING(__val) (((__val) < INT32_MIN || (__val) > INT32_MAX) ? \
  15     INTSET_ENC_INT64 : (((__val) < INT16_MIN || (__val) > INT16_MAX) ? \
  16     INTSET_ENC_INT32 : INTSET_ENC_INT16))
  17 #define INTSET_GET_ENCODED(__is,__pos,__enc) ((__enc == INTSET_ENC_INT64) ? \
  18     ((int64_t*)(__is)->contents)[__pos] : ((__enc == INTSET_ENC_INT32) ? \
  19     ((int32_t*)(__is)->contents)[__pos] : ((int16_t*)(__is)->contents)[__pos]))
  20 #define INTSET_GET(__is,__pos) (INTSET_GET_ENCODED(__is,__pos,(__is)->encoding))
  21 #define INTSET_SET(__is,__pos,__val) { \
  22     if ((__is)->encoding == INTSET_ENC_INT64) \
  23         ((int64_t*)(__is)->contents)[__pos] = (__val); \
  24     else if ((__is)->encoding == INTSET_ENC_INT32) \
  25         ((int32_t*)(__is)->contents)[__pos] = (__val); \
  26     else \
  27         ((int16_t*)(__is)->contents)[__pos] = (__val); }
  28
  29 /* Create an empty intset. */
  30 intset *intsetNew(void) {
  31     intset *is = zmalloc(sizeof(intset));
  32     is->encoding = INTSET_ENC_INT16;
  33     is->length = 0;
  34     return is;
  35 }
  36
  37 /* Resize the intset */
  38 static intset *intsetResize(intset *is, uint32_t len) {
  39     uint32_t size = len*is->encoding;
  40     is = zrealloc(is,sizeof(intset)+size);
  41     return is;
  42 }
  43
  44 static intset *intsetUpgrade(intset *is, uint8_t newenc, uint8_t extra, uint8_t offset) {
  45     uint8_t curenc = is->encoding;
  46     int length = is->length;
  47
  48     /* First set new encoding and resize */
  49     is->encoding = newenc;
  50     is = intsetResize(is,is->length+extra);
  51
  52     /* Upgrade back-to-front so we don't overwrite values */
  53     while(length--)
  54         INTSET_SET(is,length+offset,INTSET_GET_ENCODED(is,length,curenc));
  55     return is;
  56 }
  57
  58 /* Search for the position of "value". Return 1 when the value was found and
  59  * sets "pos" to the position of the value within the intset. Return 0 when
  60  * the value is not present in the intset and sets "pos" to the position
  61  * where "value" can be inserted. */
  62 static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
  63     int min = 0, max = is->length-1, mid = -1;
  64     int64_t cur = -1;
  65
  66     /* The value can never be found when the set is empty */
  67     if (is->length == 0) {
  68         if (pos) *pos = 0;
  69         return 0;
  70     } else {
  71         /* Check for the case where we know we cannot find the value,
  72          * but do know the insert position. */
  73         if (value > INTSET_GET(is,is->length-1)) {
  74             if (pos) *pos = is->length;
  75             return 0;
  76         } else if (value < INTSET_GET(is,0)) {
  77             if (pos) *pos = 0;
  78             return 0;
  79         }
  80     }
  81
  82     while(max >= min) {
  83         mid = (min+max)/2;
  84         cur = INTSET_GET(is,mid);
  85         if (value > cur) {
  86             min = mid+1;
  87         } else if (value < cur) {
  88             max = mid-1;
  89         } else {
  90             break;
  91         }
  92     }
  93
  94     if (value == cur) {
  95         if (pos) *pos = mid;
  96         return 1;
  97     } else {
  98         if (pos) *pos = min;
  99         return 0;
 100     }
 101 }
 102
 103 static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) {
 104     void *src, *dst;
 105     uint32_t bytes = is->length-from;
 106     if (is->encoding == INTSET_ENC_INT64) {
 107         src = (int64_t*)is->contents+from;
 108         dst = (int64_t*)is->contents+to;
 109         bytes *= sizeof(int64_t);
 110     } else if (is->encoding == INTSET_ENC_INT32) {
 111         src = (int32_t*)is->contents+from;
 112         dst = (int32_t*)is->contents+to;
 113         bytes *= sizeof(int32_t);
 114     } else {
 115         src = (int16_t*)is->contents+from;
 116         dst = (int16_t*)is->contents+to;
 117         bytes *= sizeof(int16_t);
 118     }
 119     memmove(dst,src,bytes);
 120 }
 121
 122 /* Insert an integer in the intset */
 123 intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
 124     uint8_t valenc = INTSET_VALUE_ENCODING(value);
 125     uint32_t pos, offset;
 126     if (success) *success = 1;
 127
 128     /* Upgrade encoding if necessary. If we need to upgrade, we know that
 129      * this value should be either appended (if > 0) or prepended (if < 0),
 130      * because it lies outside the range of existing values. */
 131     if (valenc > is->encoding) {
 132         offset = value < 0 ? 1 : 0;
 133         is = intsetUpgrade(is,valenc,1,offset);
 134         pos = (value < 0) ? 0 : is->length;
 135     } else {
 136         /* Abort if the value is already present in the set.
 137          * This call will populate "pos" with the right position to insert
 138          * the value when it cannot be found. */
 139         if (intsetSearch(is,value,&pos)) {
 140             if (success) *success = 0;
 141             return is;
 142         }
 143
 144         is = intsetResize(is,is->length+1);
 145         if (pos < is->length) intsetMoveTail(is,pos,pos+1);
 146     }
 147
 148     INTSET_SET(is,pos,value);
 149     is->length++;
 150     return is;
 151 }
 152
 153 /* Delete integer from intset */
 154 intset *intsetRemove(intset *is, int64_t value, uint8_t *success) {
 155     uint8_t valenc = INTSET_VALUE_ENCODING(value);
 156     uint32_t pos;
 157     if (success) *success = 0;
 158
 159     if (valenc <= is->encoding && intsetSearch(is,value,&pos)) {
 160         /* We know we can delete */
 161         if (success) *success = 1;
 162
 163         /* Overwrite value with tail and update length */
 164         if (pos < (is->length-1)) intsetMoveTail(is,pos+1,pos);
 165         is = intsetResize(is,is->length-1);
 166         is->length--;
 167     }
 168     return is;
 169 }
 170
 171 /* Determine whether a value belongs to this set */
 172 uint8_t intsetFind(intset *is, int64_t value) {
 173     uint8_t valenc = INTSET_VALUE_ENCODING(value);
 174     return valenc <= is->encoding && intsetSearch(is,value,NULL);
 175 }
 176
 177 /* Return random member */
 178 int64_t intsetRandom(intset *is) {
 179     return INTSET_GET(is,rand()%is->length);
 180 }
 181
 182 /* Sets the value to the value at the given position. When this position is
 183  * out of range the function returns 0, when in range it returns 1. */
 184 uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value) {
 185     if (pos < is->length) {
 186         *value = INTSET_GET(is,pos);
 187         return 1;
 188     }
 189     return 0;
 190 }
 191
 192 /* Return intset length */
 193 uint32_t intsetLen(intset *is) {
 194     return is->length;
 195 }
 196
 197 #ifdef INTSET_TEST_MAIN
 198 #include <sys/time.h>
 199
 200 void intsetRepr(intset *is) {
 201     int i;
 202     for (i = 0; i < is->length; i++) {
 203         printf("%lld\n", (uint64_t)INTSET_GET(is,i));
 204     }
 205     printf("\n");
 206 }
 207
 208 void error(char *err) {
 209     printf("%s\n", err);
 210     exit(1);
 211 }
 212
 213 void ok(void) {
 214     printf("OK\n");
 215 }
 216
 217 long long usec(void) {
 218     struct timeval tv;
 219     gettimeofday(&tv,NULL);
 220     return (((long long)tv.tv_sec)*1000000)+tv.tv_usec;
 221 }
 222
 223 #define assert(_e) ((_e)?(void)0:(_assert(#_e,__FILE__,__LINE__),exit(1)))
 224 void _assert(char *estr, char *file, int line) {
 225     printf("\n\n=== ASSERTION FAILED ===\n");
 226     printf("==> %s:%d '%s' is not true\n",file,line,estr);
 227 }
 228
 229 intset *createSet(int bits, int size) {
 230     uint64_t mask = (1<<bits)-1;
 231     uint64_t i, value;
 232     intset *is = intsetNew();
 233
 234     for (i = 0; i < size; i++) {
 235         if (bits > 32) {
 236             value = (rand()*rand()) & mask;
 237         } else {
 238             value = rand() & mask;
 239         }
 240         is = intsetAdd(is,value,NULL);
 241     }
 242     return is;
 243 }
 244
 245 void checkConsistency(intset *is) {
 246     int i;
 247
 248     for (i = 0; i < (is->length-1); i++) {
 249         if (is->encoding == INTSET_ENC_INT16) {
 250             int16_t *i16 = (int16_t*)is->contents;
 251             assert(i16[i] < i16[i+1]);
 252         } else if (is->encoding == INTSET_ENC_INT32) {
 253             int32_t *i32 = (int32_t*)is->contents;
 254             assert(i32[i] < i32[i+1]);
 255         } else {
 256             int64_t *i64 = (int64_t*)is->contents;
 257             assert(i64[i] < i64[i+1]);
 258         }
 259     }
 260 }
 261
 262 int main(int argc, char **argv) {
 263     uint8_t success;
 264     int i;
 265     intset *is;
 266     sranddev();
 267
 268     printf("Value encodings: "); {
 269         assert(INTSET_VALUE_ENCODING(-32768) == INTSET_ENC_INT16);
 270         assert(INTSET_VALUE_ENCODING(+32767) == INTSET_ENC_INT16);
 271         assert(INTSET_VALUE_ENCODING(-32769) == INTSET_ENC_INT32);
 272         assert(INTSET_VALUE_ENCODING(+32768) == INTSET_ENC_INT32);
 273         assert(INTSET_VALUE_ENCODING(-2147483648) == INTSET_ENC_INT32);
 274         assert(INTSET_VALUE_ENCODING(+2147483647) == INTSET_ENC_INT32);
 275         assert(INTSET_VALUE_ENCODING(-2147483649) == INTSET_ENC_INT64);
 276         assert(INTSET_VALUE_ENCODING(+2147483648) == INTSET_ENC_INT64);
 277         assert(INTSET_VALUE_ENCODING(-9223372036854775808ull) == INTSET_ENC_INT64);
 278         assert(INTSET_VALUE_ENCODING(+9223372036854775807ull) == INTSET_ENC_INT64);
 279         ok();
 280     }
 281
 282     printf("Basic adding: "); {
 283         is = intsetNew();
 284         is = intsetAdd(is,5,&success); assert(success);
 285         is = intsetAdd(is,6,&success); assert(success);
 286         is = intsetAdd(is,4,&success); assert(success);
 287         is = intsetAdd(is,4,&success); assert(!success);
 288         ok();
 289     }
 290
 291     printf("Large number of random adds: "); {
 292         int inserts = 0;
 293         is = intsetNew();
 294         for (i = 0; i < 1024; i++) {
 295             is = intsetAdd(is,rand()%0x800,&success);
 296             if (success) inserts++;
 297         }
 298         assert(is->length == inserts);
 299         checkConsistency(is);
 300         ok();
 301     }
 302
 303     printf("Upgrade from int16 to int32: "); {
 304         is = intsetNew();
 305         is = intsetAdd(is,32,NULL);
 306         assert(is->encoding == INTSET_ENC_INT16);
 307         is = intsetAdd(is,65535,NULL);
 308         assert(is->encoding == INTSET_ENC_INT32);
 309         assert(intsetFind(is,32));
 310         assert(intsetFind(is,65535));
 311         checkConsistency(is);
 312
 313         is = intsetNew();
 314         is = intsetAdd(is,32,NULL);
 315         assert(is->encoding == INTSET_ENC_INT16);
 316         is = intsetAdd(is,-65535,NULL);
 317         assert(is->encoding == INTSET_ENC_INT32);
 318         assert(intsetFind(is,32));
 319         assert(intsetFind(is,-65535));
 320         checkConsistency(is);
 321         ok();
 322     }
 323
 324     printf("Upgrade from int16 to int64: "); {
 325         is = intsetNew();
 326         is = intsetAdd(is,32,NULL);
 327         assert(is->encoding == INTSET_ENC_INT16);
 328         is = intsetAdd(is,4294967295,NULL);
 329         assert(is->encoding == INTSET_ENC_INT64);
 330         assert(intsetFind(is,32));
 331         assert(intsetFind(is,4294967295));
 332         checkConsistency(is);
 333
 334         is = intsetNew();
 335         is = intsetAdd(is,32,NULL);
 336         assert(is->encoding == INTSET_ENC_INT16);
 337         is = intsetAdd(is,-4294967295,NULL);
 338         assert(is->encoding == INTSET_ENC_INT64);
 339         assert(intsetFind(is,32));
 340         assert(intsetFind(is,-4294967295));
 341         checkConsistency(is);
 342         ok();
 343     }
 344
 345     printf("Upgrade from int32 to int64: "); {
 346         is = intsetNew();
 347         is = intsetAdd(is,65535,NULL);
 348         assert(is->encoding == INTSET_ENC_INT32);
 349         is = intsetAdd(is,4294967295,NULL);
 350         assert(is->encoding == INTSET_ENC_INT64);
 351         assert(intsetFind(is,65535));
 352         assert(intsetFind(is,4294967295));
 353         checkConsistency(is);
 354
 355         is = intsetNew();
 356         is = intsetAdd(is,65535,NULL);
 357         assert(is->encoding == INTSET_ENC_INT32);
 358         is = intsetAdd(is,-4294967295,NULL);
 359         assert(is->encoding == INTSET_ENC_INT64);
 360         assert(intsetFind(is,65535));
 361         assert(intsetFind(is,-4294967295));
 362         checkConsistency(is);
 363         ok();
 364     }
 365
 366     printf("Stress lookups: "); {
 367         long num = 100000, size = 10000;
 368         int i, bits = 20;
 369         long long start;
 370         is = createSet(bits,size);
 371         checkConsistency(is);
 372
 373         start = usec();
 374         for (i = 0; i < num; i++) intsetSearch(is,rand() % ((1<<bits)-1),NULL);
 375         printf("%ld lookups, %ld element set, %lldusec\n",num,size,usec()-start);
 376     }
 377
 378     printf("Stress add+delete: "); {
 379         int i, v1, v2;
 380         is = intsetNew();
 381         for (i = 0; i < 0xffff; i++) {
 382             v1 = rand() % 0xfff;
 383             is = intsetAdd(is,v1,NULL);
 384             assert(intsetFind(is,v1));
 385
 386             v2 = rand() % 0xfff;
 387             is = intsetRemove(is,v2,NULL);
 388             assert(!intsetFind(is,v2));
 389         }
 390         checkConsistency(is);
 391         ok();
 392     }
 393 }
 394 #endif