third_party/WebKit/Source/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 "wtf/LeakAnnotations.h"
  30 #include "wtf/PartitionAlloc.h"
  31 #include "wtf/Partitions.h"
  32 #include "wtf/PrintStream.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 = Partitions::bufferMalloc(size);
  84     OutOfLineBits* result = new (NotNull, allocation) OutOfLineBits(numBits);
  85     return result;
  86 }
  87
  88 void BitVector::OutOfLineBits::destroy(OutOfLineBits* outOfLineBits)
  89 {
  90     Partitions::bufferFree(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