utils/open-isns/bitvector.c

   1 /*
   2  * Handle bit vector as a run length encoded array of
   3  * 32bit words.
   4  *
   5  * Copyright (C) 2007 Olaf Kirch <olaf.kirch@oracle.com>
   6  */
   7
   8 #include <stdlib.h>
   9 #include <string.h>
  10 #include "isns.h"
  11 #include "util.h"
  12
  13 struct isns_bitvector {
  14         unsigned int    ib_count;
  15         uint32_t *      ib_words;
  16 };
  17
  18 void
  19 isns_bitvector_init(isns_bitvector_t *bv)
  20 {
  21         memset(bv, 0, sizeof(*bv));
  22 }
  23
  24 void
  25 isns_bitvector_destroy(isns_bitvector_t *bv)
  26 {
  27         isns_free(bv->ib_words);
  28         memset(bv, 0, sizeof(*bv));
  29 }
  30
  31 isns_bitvector_t *
  32 isns_bitvector_alloc(void)
  33 {
  34         return isns_calloc(1, sizeof(isns_bitvector_t));
  35 }
  36
  37 void
  38 isns_bitvector_free(isns_bitvector_t *bv)
  39 {
  40         if (bv) {
  41                 isns_free(bv->ib_words);
  42                 memset(bv, 0xa5, sizeof(*bv));
  43                 isns_free(bv);
  44         }
  45 }
  46
  47 /*
  48  * Helper function to locate bit
  49  */
  50 uint32_t *
  51 __isns_bitvector_find_word(const isns_bitvector_t *bv, unsigned int bit)
  52 {
  53         uint32_t        *wp, *end;
  54
  55         if (bv->ib_words == NULL)
  56                 return NULL;
  57
  58         wp = bv->ib_words;
  59         end = wp + bv->ib_count;
  60         while (wp < end) {
  61                 unsigned int    base, rlen;
  62
  63                 base = wp[0];
  64                 rlen = wp[1];
  65
  66                 isns_assert(!(base % 32));
  67                 if (base <= bit && bit < base + rlen * 32)
  68                         return wp + 2 + ((bit - base) / 32);
  69
  70                 wp += 2 + rlen;
  71                 isns_assert(wp <= end);
  72         }
  73
  74         return NULL;
  75 }
  76
  77 /*
  78  * Insert words in the middle of the array
  79  */
  80 static inline void
  81 __isns_bitvector_insert_words(isns_bitvector_t *bv,
  82                 unsigned int offset, unsigned int count)
  83 {
  84         bv->ib_words = isns_realloc(bv->ib_words,
  85                         (bv->ib_count + count) * sizeof(uint32_t));
  86
  87         /* If we insert in the middle, shift out the tail
  88          * to make room for the new range. */
  89         isns_assert(offset <= bv->ib_count);
  90         if (offset < bv->ib_count) {
  91                 memmove(bv->ib_words + offset + count,
  92                         bv->ib_words + offset,
  93                         (bv->ib_count - offset) * sizeof(uint32_t));
  94         }
  95
  96         memset(bv->ib_words + offset, 0, count * sizeof(uint32_t));
  97         bv->ib_count += count;
  98 }
  99
 100 /*
 101  * Insert a new range
 102  */
 103 static inline uint32_t *
 104 __isns_bitvector_insert_range(isns_bitvector_t *bv,
 105                 unsigned int offset, unsigned int base)
 106 {
 107         uint32_t        *pos;
 108
 109         __isns_bitvector_insert_words(bv, offset, 3);
 110
 111         pos = bv->ib_words + offset;
 112
 113         *pos++ = base & ~31;
 114         *pos++ = 1;
 115
 116         return pos;
 117 }
 118
 119 /*
 120  * Extend an existing range
 121  * @offset marks the beginning of the existing range.
 122  */
 123 static inline uint32_t *
 124 __isns_bitvector_extend_range(isns_bitvector_t *bv,
 125                 unsigned int offset, unsigned int count)
 126 {
 127         uint32_t        *pos, rlen;
 128
 129         /* Find the end of the range */
 130         pos = bv->ib_words + offset;
 131         rlen = pos[1];
 132
 133         __isns_bitvector_insert_words(bv, offset + 2 + rlen, count);
 134
 135         pos = bv->ib_words + offset;
 136         pos[1] += count;
 137
 138         /* Return pointer to the last word of the new range. */
 139         return pos + 2 + rlen + count - 1;
 140 }
 141
 142 /*
 143  * Find a suitable range for insertion
 144  */
 145 static uint32_t *
 146 __isns_bitvector_find_insert_word(isns_bitvector_t *bv, unsigned int bit)
 147 {
 148         uint32_t        *wp, *end;
 149
 150         if (bv->ib_words == NULL)
 151                 return __isns_bitvector_insert_range(bv, 0, bit);
 152
 153         wp = bv->ib_words;
 154         end = wp + bv->ib_count;
 155         while (wp < end) {
 156                 unsigned int    base, rlen, distance;
 157
 158                 base = wp[0];
 159                 rlen = wp[1];
 160
 161                 isns_assert(!(base % 32));
 162
 163                 if (bit < base) {
 164                         return __isns_bitvector_insert_range(bv,
 165                                         wp - bv->ib_words, bit);
 166                 }
 167
 168                 distance = (bit - base) / 32;
 169                 if (distance < rlen) {
 170                         /* This bit is within range */
 171                         return wp + 2 + distance;
 172                 }
 173
 174                 /* Is it efficient to extend this range?
 175                  * The break even point is if we have to add
 176                  * 3 words to extend the range, because a new
 177                  * range would be at least that much.
 178                  */
 179                 if (distance + 1 <= rlen + 3) {
 180                         return __isns_bitvector_extend_range(bv,
 181                                         wp - bv->ib_words,
 182                                         distance + 1 - rlen);
 183                 }
 184
 185                 wp += 2 + rlen;
 186                 isns_assert(wp <= end);
 187         }
 188
 189         /* No suitable range found. Append one at the end */
 190         return __isns_bitvector_insert_range(bv,
 191                         bv->ib_count, bit);
 192 }
 193
 194 /*
 195  * After clearing a bit, check if the bitvector can be
 196  * compacted.
 197  */
 198 static void
 199 __isns_bitvector_compact(isns_bitvector_t *bv)
 200 {
 201         uint32_t        *src, *dst, *end;
 202         unsigned int    dst_base = 0, dst_len = 0;
 203
 204         if (bv->ib_words == NULL)
 205                 return;
 206
 207         src = dst = bv->ib_words;
 208         end = src + bv->ib_count;
 209         while (src < end) {
 210                 unsigned int    base, rlen;
 211
 212                 base = *src++;
 213                 rlen = *src++;
 214
 215                 /* Consume leading NUL words */
 216                 while (rlen && *src == 0) {
 217                         base += 32;
 218                         src++;
 219                         rlen--;
 220                 }
 221
 222                 /* Consume trailing NUL words */
 223                 while (rlen && src[rlen-1] == 0)
 224                         rlen--;
 225
 226                 if (rlen != 0) {
 227                         if (dst_len && dst_base + 32 * dst_len == base) {
 228                                 /* We can extend the previous run */
 229                         } else {
 230                                 /* New run. Close off the previous one,
 231                                  * if we had one. */
 232                                 if (dst_len != 0) {
 233                                         dst[0] = dst_base;
 234                                         dst[1] = dst_len;
 235                                         dst += 2 + dst_len;
 236                                 }
 237
 238                                 dst_base = base;
 239                                 dst_len = 0;
 240                         }
 241
 242                         while (rlen--)
 243                                 dst[2 + dst_len++] = *src++;
 244                 }
 245
 246                 isns_assert(src <= end);
 247         }
 248
 249
 250         if (dst_len != 0) {
 251                 dst[0] = dst_base;
 252                 dst[1] = dst_len;
 253                 dst += 2 + dst_len;
 254         }
 255
 256         bv->ib_count = dst - bv->ib_words;
 257         if (bv->ib_count == 0)
 258                 isns_bitvector_destroy(bv);
 259 }
 260
 261 /*
 262  * Test the value of a single bit
 263  */
 264 int
 265 isns_bitvector_test_bit(const isns_bitvector_t *bv, unsigned int bit)
 266 {
 267         const uint32_t  *pos;
 268         uint32_t        mask;
 269
 270         pos = __isns_bitvector_find_word(bv, bit);
 271         if (pos == NULL)
 272                 return 0;
 273
 274         mask = 1 << (bit % 32);
 275         return !!(*pos & mask);
 276 }
 277
 278 int
 279 isns_bitvector_clear_bit(isns_bitvector_t *bv, unsigned int bit)
 280 {
 281         uint32_t        *pos, oldval, mask;
 282
 283         pos = __isns_bitvector_find_word(bv, bit);
 284         if (pos == NULL)
 285                 return 0;
 286
 287         mask = 1 << (bit % 32);
 288         oldval = *pos;
 289         *pos &= ~mask;
 290
 291         __isns_bitvector_compact(bv);
 292         return !!(oldval & mask);
 293 }
 294
 295 int
 296 isns_bitvector_set_bit(isns_bitvector_t *bv, unsigned int bit)
 297 {
 298         uint32_t        *pos, oldval = 0, mask;
 299
 300         mask = 1 << (bit % 32);
 301
 302         pos = __isns_bitvector_find_insert_word(bv, bit);
 303         if (pos != NULL) {
 304                 oldval = *pos;
 305                 *pos |= mask;
 306
 307                 return !!(oldval & mask);
 308         }
 309
 310         return 0;
 311 }
 312
 313 int
 314 isns_bitvector_is_empty(const isns_bitvector_t *bv)
 315 {
 316         uint32_t        *wp, *end;
 317
 318         if (bv == NULL || bv->ib_count == 0)
 319                 return 1;
 320
 321         /* In theory, we should never have a non-compacted
 322          * empty bitvector, as the only way to get one
 323          * is through clear_bit.
 324          * Better safe than sorry...
 325          */
 326
 327         wp = bv->ib_words;
 328         end = wp + bv->ib_count;
 329         while (wp < end) {
 330                 unsigned int    base, rlen;
 331
 332                 base = *wp++;
 333                 rlen = *wp++;
 334
 335                 while (rlen--) {
 336                         if (*wp++)
 337                                 return 0;
 338                 }
 339                 isns_assert(wp <= end);
 340         }
 341
 342         return 1;
 343 }
 344
 345 int
 346 isns_bitvector_intersect(const isns_bitvector_t *a,
 347                         const isns_bitvector_t *b,
 348                         isns_bitvector_t *result)
 349 {
 350         const uint32_t  *runa, *runb, *enda, *endb;
 351         const uint32_t  *wpa = NULL, *wpb = NULL;
 352         uint32_t        bita = 0, lena = 0, bitb = 0, lenb = 0;
 353         int             found = -1;
 354
 355         if (a == NULL || b == NULL)
 356                 return -1;
 357
 358         /* Returning the intersect is not implemented yet. */
 359         isns_assert(result == NULL);
 360
 361         runa = a->ib_words;
 362         enda = runa + a->ib_count;
 363         runb = b->ib_words;
 364         endb = runb + b->ib_count;
 365
 366         while (1) {
 367                 unsigned int    skip;
 368
 369                 if (lena == 0) {
 370 next_a:
 371                         if (runa >= enda)
 372                                 break;
 373                         bita = *runa++;
 374                         lena = *runa++;
 375                         wpa  = runa;
 376                         runa += lena;
 377                         lena *= 32;
 378                 }
 379
 380                 if (lenb == 0) {
 381 next_b:
 382                         if (runb >= endb)
 383                                 break;
 384                         bitb = *runb++;
 385                         lenb = *runb++;
 386                         wpb  = runb;
 387                         runb += lenb;
 388                         lenb *= 32;
 389                 }
 390
 391                 if (bita < bitb) {
 392                         skip = bitb - bita;
 393
 394                         /* range A ends before range B starts.
 395                          * Proceed to next run in vector A. */
 396                         if (skip >= lena)
 397                                 goto next_a;
 398
 399                         bita += skip;
 400                         lena -= skip;
 401                         wpa  += skip / 32;
 402                 } else
 403                 if (bitb < bita) {
 404                         skip = bita - bitb;
 405
 406                         /* range B ends before range A starts.
 407                          * Proceed to next run in vector B. */
 408                         if (skip >= lenb)
 409                                 goto next_b;
 410
 411                         bitb += skip;
 412                         lenb -= skip;
 413                         wpb  += skip / 32;
 414                 }
 415
 416                 isns_assert(bita == bitb);
 417
 418                 while (lena && lenb) {
 419                         uint32_t intersect;
 420
 421                         intersect = *wpa & *wpb;
 422
 423                         if (!intersect)
 424                                 goto next_word;
 425
 426                         /* Find the bit */
 427                         if (found < 0) {
 428                                 uint32_t mask = intersect;
 429
 430                                 found = bita;
 431                                 while (!(mask & 1)) {
 432                                         found++;
 433                                         mask >>= 1;
 434                                 }
 435                         }
 436
 437                         if (result == NULL)
 438                                 return found;
 439
 440                         /* Append to result vector */
 441                         /* FIXME: TBD */
 442
 443 next_word:
 444                         bita += 32; lena -= 32; wpa++;
 445                         bitb += 32; lenb -= 32; wpb++;
 446                 }
 447         }
 448
 449         return found;
 450 }
 451
 452 /*
 453  * Iterate over the bit vector
 454  */
 455 void
 456 isns_bitvector_foreach(const isns_bitvector_t *bv,
 457                 int (*cb)(uint32_t, void *),
 458                 void *user_data)
 459 {
 460         uint32_t        *wp, *end;
 461
 462         wp = bv->ib_words;
 463         end = wp + bv->ib_count;
 464         while (wp < end) {
 465                 unsigned int    base, rlen, bits;
 466
 467                 base = wp[0];
 468                 rlen = wp[1];
 469                 bits = rlen * 32;
 470                 wp += 2;
 471
 472                 while (rlen--) {
 473                         uint32_t        mask, word;
 474
 475                         word = *wp++;
 476                         for (mask = 1; mask; mask <<= 1, ++base) {
 477                                 if (word & mask)
 478                                         cb(base, user_data);
 479                         }
 480                 }
 481                 isns_assert(wp <= end);
 482         }
 483 }
 484
 485 void
 486 isns_bitvector_dump(const isns_bitvector_t *bv, isns_print_fn_t *fn)
 487 {
 488         uint32_t        *wp, *end;
 489
 490         fn("Bit Vector %p (%u words):", bv, bv->ib_count);
 491
 492         wp = bv->ib_words;
 493         end = wp + bv->ib_count;
 494         while (wp < end) {
 495                 unsigned int    base, rlen, bits;
 496
 497                 base = wp[0];
 498                 rlen = wp[1];
 499                 bits = rlen * 32;
 500                 wp += 2;
 501
 502                 fn(" <%u:", base);
 503                 while (rlen--)
 504                         fn(" 0x%x", *wp++);
 505                 fn(">");
 506
 507                 isns_assert(wp <= end);
 508         }
 509
 510         if (bv->ib_count == 0)
 511                 fn("<empty>");
 512         fn("\n");
 513 }
 514
 515 static inline void
 516 __isns_bitvector_print_next(uint32_t first, uint32_t last,
 517                 isns_print_fn_t *fn)
 518 {
 519         switch (last - first) {
 520         case 0:
 521                 return;
 522         case 1:
 523                 fn(", %u", last);
 524                 break;
 525         default:
 526                 fn("-%u", last);
 527                 break;
 528         }
 529 }
 530
 531 void
 532 isns_bitvector_print(const isns_bitvector_t *bv,
 533                 isns_print_fn_t *fn)
 534 {
 535         uint32_t        *wp, *end, first = 0, next = 0;
 536         const char      *sepa = "";
 537
 538         wp = bv->ib_words;
 539         end = wp + bv->ib_count;
 540         while (wp < end) {
 541                 unsigned int    base, rlen, bits;
 542
 543                 base = wp[0];
 544                 rlen = wp[1];
 545                 bits = rlen * 32;
 546                 wp += 2;
 547
 548                 while (rlen--) {
 549                         uint32_t        mask, word;
 550
 551                         word = *wp++;
 552                         for (mask = 1; mask; mask <<= 1, ++base) {
 553                                 if (word & mask) {
 554                                         if (next++)
 555                                                 continue;
 556                                         fn("%s%u", sepa, base);
 557                                         sepa = ", ";
 558                                         first = base;
 559                                         next = base + 1;
 560                                 } else {
 561                                         if (next)
 562                                                 __isns_bitvector_print_next(first, next - 1, fn);
 563                                         first = next = 0;
 564                                 }
 565                         }
 566                 }
 567                 isns_assert(wp <= end);
 568         }
 569
 570         if (next)
 571                 __isns_bitvector_print_next(first, next - 1, fn);
 572
 573         if (*sepa == '\0')
 574                 fn("<empty>");
 575         fn("\n");
 576 }
 577
 578 #ifdef TEST
 579 int
 580 main(void)
 581 {
 582         isns_bitvector_t        a, b;
 583         int     i;
 584
 585         isns_bitvector_init(&a);
 586         isns_bitvector_set_bit(&a, 0);
 587         isns_bitvector_dump(&a, isns_print_stdout);
 588         isns_bitvector_set_bit(&a, 1);
 589         isns_bitvector_set_bit(&a, 16);
 590         isns_bitvector_set_bit(&a, 32);
 591         isns_bitvector_set_bit(&a, 64);
 592         isns_bitvector_dump(&a, isns_print_stdout);
 593         isns_bitvector_set_bit(&a, 8192);
 594         isns_bitvector_set_bit(&a, 8196);
 595         isns_bitvector_set_bit(&a, 8194);
 596         isns_bitvector_dump(&a, isns_print_stdout);
 597         isns_bitvector_set_bit(&a, 2052);
 598         isns_bitvector_set_bit(&a, 2049);
 599         isns_bitvector_set_bit(&a, 2051);
 600         isns_bitvector_set_bit(&a, 2050);
 601         isns_bitvector_dump(&a, isns_print_stdout);
 602         isns_bitvector_print(&a, isns_print_stdout);
 603         isns_bitvector_destroy(&a);
 604
 605         isns_bitvector_init(&a);
 606         for (i = 127; i >= 0; --i)
 607                 isns_bitvector_set_bit(&a, i);
 608         isns_bitvector_dump(&a, isns_print_stdout);
 609         printf("[Compacting]\n");
 610         __isns_bitvector_compact(&a);
 611         isns_bitvector_dump(&a, isns_print_stdout);
 612         isns_bitvector_print(&a, isns_print_stdout);
 613         isns_bitvector_destroy(&a);
 614
 615         isns_bitvector_init(&a);
 616         for (i = 0; i < 128; ++i)
 617                 isns_bitvector_set_bit(&a, i);
 618         isns_bitvector_dump(&a, isns_print_stdout);
 619         isns_bitvector_print(&a, isns_print_stdout);
 620         isns_bitvector_destroy(&a);
 621
 622         isns_bitvector_init(&a);
 623         isns_bitvector_init(&b);
 624         isns_bitvector_set_bit(&a, 0);
 625         isns_bitvector_set_bit(&a, 77);
 626         isns_bitvector_set_bit(&a, 249);
 627         isns_bitvector_set_bit(&a, 102);
 628
 629         isns_bitvector_set_bit(&b, 1);
 630         isns_bitvector_set_bit(&b, 76);
 631         isns_bitvector_set_bit(&b, 250);
 632         isns_bitvector_set_bit(&b, 102);
 633         i = isns_bitvector_intersect(&a, &b, NULL);
 634         if (i != 102)
 635                 fprintf(stderr, "*** BAD: Intersect should return 102 (got %d)! ***\n", i);
 636         else
 637                 printf("Intersect okay: %d\n", i);
 638         isns_bitvector_destroy(&a);
 639         isns_bitvector_destroy(&b);
 640
 641         isns_bitvector_init(&a);
 642         isns_bitvector_set_bit(&a, 0);
 643         isns_bitvector_set_bit(&a, 1);
 644         isns_bitvector_clear_bit(&a, 1);
 645         isns_bitvector_clear_bit(&a, 0);
 646         isns_bitvector_dump(&a, isns_print_stdout);
 647         isns_bitvector_print(&a, isns_print_stdout);
 648         isns_bitvector_destroy(&a);
 649         return 0;
 650 }
 651 #endif