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