Source/WTF/wtf/BitVector.cpp

   1 /*
   2  * Copyright (C) 2011 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "BitVector.h"
  28
  29 #include <algorithm>
  30 #include <string.h>
  31 #include <wtf/Assertions.h>
  32 #include <wtf/FastMalloc.h>
  33 #include <wtf/StdLibExtras.h>
  34
  35 namespace WTF {
  36
  37 void BitVector::setSlow(const BitVector& other)
  38 {
  39     uintptr_t newBitsOrPointer;
  40     if (other.isInline())
  41         newBitsOrPointer = other.m_bitsOrPointer;
  42     else {
  43         OutOfLineBits* newOutOfLineBits = OutOfLineBits::create(other.size());
  44         memcpy(newOutOfLineBits->bits(), other.bits(), byteCount(other.size()));
  45         newBitsOrPointer = bitwise_cast<uintptr_t>(newOutOfLineBits) >> 1;
  46     }
  47     if (!isInline())
  48         OutOfLineBits::destroy(outOfLineBits());
  49     m_bitsOrPointer = newBitsOrPointer;
  50 }
  51
  52 void BitVector::resize(size_t numBits)
  53 {
  54     if (numBits <= maxInlineBits()) {
  55         if (isInline())
  56             return;
  57
  58         OutOfLineBits* myOutOfLineBits = outOfLineBits();
  59         m_bitsOrPointer = makeInlineBits(*myOutOfLineBits->bits());
  60         OutOfLineBits::destroy(myOutOfLineBits);
  61         return;
  62     }
  63
  64     resizeOutOfLine(numBits);
  65 }
  66
  67 void BitVector::clearAll()
  68 {
  69     if (isInline())
  70         m_bitsOrPointer = makeInlineBits(0);
  71     else
  72         memset(outOfLineBits()->bits(), 0, byteCount(size()));
  73 }
  74
  75 BitVector::OutOfLineBits* BitVector::OutOfLineBits::create(size_t numBits)
  76 {
  77     numBits = (numBits + bitsInPointer() - 1) & ~(bitsInPointer() - 1);
  78     size_t size = sizeof(OutOfLineBits) + sizeof(uintptr_t) * (numBits / bitsInPointer());
  79     OutOfLineBits* result = new (NotNull, fastMalloc(size)) OutOfLineBits(numBits);
  80     return result;
  81 }
  82
  83 void BitVector::OutOfLineBits::destroy(OutOfLineBits* outOfLineBits)
  84 {
  85     fastFree(outOfLineBits);
  86 }
  87
  88 void BitVector::resizeOutOfLine(size_t numBits)
  89 {
  90     ASSERT(numBits > maxInlineBits());
  91     OutOfLineBits* newOutOfLineBits = OutOfLineBits::create(numBits);
  92     size_t newNumWords = newOutOfLineBits->numWords();
  93     if (isInline()) {
  94         // Make sure that all of the bits are zero in case we do a no-op resize.
  95         *newOutOfLineBits->bits() = m_bitsOrPointer & ~(static_cast<uintptr_t>(1) << maxInlineBits());
  96         memset(newOutOfLineBits->bits() + 1, 0, (newNumWords - 1) * sizeof(void*));
  97     } else {
  98         if (numBits > size()) {
  99             size_t oldNumWords = outOfLineBits()->numWords();
 100             memcpy(newOutOfLineBits->bits(), outOfLineBits()->bits(), oldNumWords * sizeof(void*));
 101             memset(newOutOfLineBits->bits() + oldNumWords, 0, (newNumWords - oldNumWords) * sizeof(void*));
 102         } else
 103             memcpy(newOutOfLineBits->bits(), outOfLineBits()->bits(), newOutOfLineBits->numWords() * sizeof(void*));
 104         OutOfLineBits::destroy(outOfLineBits());
 105     }
 106     m_bitsOrPointer = bitwise_cast<uintptr_t>(newOutOfLineBits) >> 1;
 107 }
 108
 109 void BitVector::dump(FILE* out)
 110 {
 111     for (size_t i = 0; i < size(); ++i) {
 112         if (get(i))
 113             fprintf(out, "1");
 114         else
 115             fprintf(out, "-");
 116     }
 117 }
 118
 119 } // namespace WTF