Home | History | Annotate | Download | only in wtf 
      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 "wtf/LeakAnnotations.h"
     30 #include "wtf/PartitionAlloc.h"
     31 #include "wtf/PrintStream.h"
     32 #include "wtf/WTF.h"
     33 #include <algorithm>
     34 #include <string.h>
     35 
     36 namespace WTF {
     37 
     38 void BitVector::setSlow(const BitVector& other)
     39 {
     40     uintptr_t newBitsOrPointer;
     41     if (other.isInline())
     42         newBitsOrPointer = other.m_bitsOrPointer;
     43     else {
     44         OutOfLineBits* newOutOfLineBits = OutOfLineBits::create(other.size());
     45         memcpy(newOutOfLineBits->bits(), other.bits(), byteCount(other.size()));
     46         newBitsOrPointer = bitwise_cast<uintptr_t>(newOutOfLineBits) >> 1;
     47     }
     48     if (!isInline())
     49         OutOfLineBits::destroy(outOfLineBits());
     50     m_bitsOrPointer = newBitsOrPointer;
     51 }
     52 
     53 void BitVector::resize(size_t numBits)
     54 {
     55     if (numBits <= maxInlineBits()) {
     56         if (isInline())
     57             return;
     58 
     59         OutOfLineBits* myOutOfLineBits = outOfLineBits();
     60         m_bitsOrPointer = makeInlineBits(*myOutOfLineBits->bits());
     61         OutOfLineBits::destroy(myOutOfLineBits);
     62         return;
     63     }
     64 
     65     resizeOutOfLine(numBits);
     66 }
     67 
     68 void BitVector::clearAll()
     69 {
     70     if (isInline())
     71         m_bitsOrPointer = makeInlineBits(0);
     72     else
     73         memset(outOfLineBits()->bits(), 0, byteCount(size()));
     74 }
     75 
     76 BitVector::OutOfLineBits* BitVector::OutOfLineBits::create(size_t numBits)
     77 {
     78     // Because of the way BitVector stores the pointer, memory tools
     79     // will erroneously report a leak here.
     80     WTF_ANNOTATE_SCOPED_MEMORY_LEAK;
     81     numBits = (numBits + bitsInPointer() - 1) & ~(bitsInPointer() - 1);
     82     size_t size = sizeof(OutOfLineBits) + sizeof(uintptr_t) * (numBits / bitsInPointer());
     83     void* allocation = partitionAllocGeneric(Partitions::getBufferPartition(), size);
     84     OutOfLineBits* result = new (NotNull, allocation) OutOfLineBits(numBits);
     85     return result;
     86 }
     87 
     88 void BitVector::OutOfLineBits::destroy(OutOfLineBits* outOfLineBits)
     89 {
     90     partitionFreeGeneric(Partitions::getBufferPartition(), outOfLineBits);
     91 }
     92 
     93 void BitVector::resizeOutOfLine(size_t numBits)
     94 {
     95     ASSERT(numBits > maxInlineBits());
     96     OutOfLineBits* newOutOfLineBits = OutOfLineBits::create(numBits);
     97     size_t newNumWords = newOutOfLineBits->numWords();
     98     if (isInline()) {
     99         // Make sure that all of the bits are zero in case we do a no-op resize.
    100         *newOutOfLineBits->bits() = m_bitsOrPointer & ~(static_cast<uintptr_t>(1) << maxInlineBits());
    101         memset(newOutOfLineBits->bits() + 1, 0, (newNumWords - 1) * sizeof(void*));
    102     } else {
    103         if (numBits > size()) {
    104             size_t oldNumWords = outOfLineBits()->numWords();
    105             memcpy(newOutOfLineBits->bits(), outOfLineBits()->bits(), oldNumWords * sizeof(void*));
    106             memset(newOutOfLineBits->bits() + oldNumWords, 0, (newNumWords - oldNumWords) * sizeof(void*));
    107         } else
    108             memcpy(newOutOfLineBits->bits(), outOfLineBits()->bits(), newOutOfLineBits->numWords() * sizeof(void*));
    109         OutOfLineBits::destroy(outOfLineBits());
    110     }
    111     m_bitsOrPointer = bitwise_cast<uintptr_t>(newOutOfLineBits) >> 1;
    112 }
    113 
    114 void BitVector::dump(PrintStream& out)
    115 {
    116     for (size_t i = 0; i < size(); ++i) {
    117         if (get(i))
    118             out.printf("1");
    119         else
    120             out.printf("-");
    121     }
    122 }
    123 
    124 } // namespace WTF
    125