intset.c

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