1. 10 Jun, 2014 1 commit
  2. 16 Feb, 2013 1 commit
  3. 02 Feb, 2013 1 commit
  4. 25 Jan, 2013 2 commits
    • Paolo Bonzini's avatar
      hbitmap: add assertion on hbitmap_iter_init · 1b095244
      Paolo Bonzini authored
      hbitmap_iter_init causes an out-of-bounds access when the "first"
      argument is or greater than or equal to the size of the bitmap.
      Forbid this with an assertion, and remove the failing testcase.
      Reported-by: default avatarKevin Wolf <kwolf@redhat.com>
      Signed-off-by: default avatarPaolo Bonzini <pbonzini@redhat.com>
      Reviewed-by: default avatarEric Blake <eblake@redhat.com>
      Reviewed-by: default avatarLaszlo Ersek <lersek@redhat.com>
      Signed-off-by: default avatarKevin Wolf <kwolf@redhat.com>
      1b095244
    • Paolo Bonzini's avatar
      add hierarchical bitmap data type and test cases · e7c033c3
      Paolo Bonzini authored
      HBitmaps provides an array of bits.  The bits are stored as usual in an
      array of unsigned longs, but HBitmap is also optimized to provide fast
      iteration over set bits; going from one bit to the next is O(logB n)
      worst case, with B = sizeof(long) * CHAR_BIT: the result is low enough
      that the number of levels is in fact fixed.
      
      In order to do this, it stacks multiple bitmaps with progressively coarser
      granularity; in all levels except the last, bit N is set iff the N-th
      unsigned long is nonzero in the immediately next level.  When iteration
      completes on the last level it can examine the 2nd-last level to quickly
      skip entire words, and even do so recursively to skip blocks of 64 words or
      powers thereof (32 on 32-bit machines).
      
      Given an index in the bitmap, it can be split in group of bits like
      this (for the 64-bit case):
      
           bits 0-57 => word in the last bitmap     | bits 58-63 => bit in the word
           bits 0-51 => word in the 2nd-last bitmap | bits 52-57 => bit in the word
           bits 0-45 => word in the 3rd-last bitmap | bits 46-51 => bit in the word
      
      So it is easy to move up simply by shifting the index right by
      log2(BITS_PER_LONG) bits.  To move down, you shift the index left
      similarly, and add the word index within the group.  Iteration uses
      ffs (find first set bit) to find the next word to examine; this
      operation can be done in constant time in most current architectures.
      
      Setting or clearing a range of m bits on all levels, the work to perform
      is O(m + m/W + m/W^2 + ...), which is O(m) like on a regular bitmap.
      
      When iterating on a bitmap, each bit (on any level) is only visited
      once.  Hence, The total cost of visiting a bitmap with m bits in it is
      the number of bits that are set in all bitmaps.  Unless the bitmap is
      extremely sparse, this is also O(m + m/W + m/W^2 + ...), so the amortized
      cost of advancing from one bit to the next is usually constant.
      Reviewed-by: default avatarLaszlo Ersek <lersek@redhat.com>
      Reviewed-by: default avatarEric Blake <eblake@redhat.com>
      Signed-off-by: default avatarPaolo Bonzini <pbonzini@redhat.com>
      Signed-off-by: default avatarKevin Wolf <kwolf@redhat.com>
      e7c033c3