Home | History | Annotate | Download | only in dex 
      1 /*
      2  * Copyright (C) 2013 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #ifndef ART_COMPILER_DEX_ARENA_BIT_VECTOR_H_
     18 #define ART_COMPILER_DEX_ARENA_BIT_VECTOR_H_
     19 
     20 #include <stdint.h>
     21 #include <stddef.h>
     22 #include "compiler_enums.h"
     23 #include "arena_allocator.h"
     24 
     25 namespace art {
     26 
     27 /*
     28  * Expanding bitmap, used for tracking resources.  Bits are numbered starting
     29  * from zero.  All operations on a BitVector are unsynchronized.
     30  */
     31 class ArenaBitVector {
     32   public:
     33     class Iterator {
     34       public:
     35         explicit Iterator(ArenaBitVector* bit_vector)
     36           : p_bits_(bit_vector),
     37             bit_storage_(bit_vector->GetRawStorage()),
     38             bit_index_(0),
     39             bit_size_(p_bits_->storage_size_ * sizeof(uint32_t) * 8) {}
     40 
     41         // Return the position of the next set bit.  -1 means end-of-element reached.
     42         int Next() {
     43           // Did anything obviously change since we started?
     44           DCHECK_EQ(bit_size_, p_bits_->GetStorageSize() * sizeof(uint32_t) * 8);
     45           DCHECK_EQ(bit_storage_, p_bits_->GetRawStorage());
     46 
     47           if (bit_index_ >= bit_size_) return -1;
     48 
     49           uint32_t word_index = bit_index_ / 32;
     50           uint32_t word = bit_storage_[word_index];
     51           // Mask out any bits in the first word we've already considered.
     52           word >>= bit_index_ & 0x1f;
     53           if (word == 0) {
     54             bit_index_ &= ~0x1f;
     55             do {
     56               word_index++;
     57               if ((word_index * 32) >= bit_size_) {
     58                 bit_index_ = bit_size_;
     59                 return -1;
     60               }
     61               word = bit_storage_[word_index];
     62               bit_index_ += 32;
     63             } while (word == 0);
     64           }
     65           bit_index_ += CTZ(word) + 1;
     66           return bit_index_ - 1;
     67         }
     68 
     69         static void* operator new(size_t size, ArenaAllocator* arena) {
     70           return arena->Alloc(sizeof(ArenaBitVector::Iterator),
     71                               ArenaAllocator::kAllocGrowableBitMap);
     72         };
     73         static void operator delete(void* p) {}  // Nop.
     74 
     75       private:
     76         ArenaBitVector* const p_bits_;
     77         uint32_t* const bit_storage_;
     78         uint32_t bit_index_;              // Current index (size in bits).
     79         const uint32_t bit_size_;       // Size of vector in bits.
     80     };
     81 
     82     ArenaBitVector(ArenaAllocator* arena, unsigned int start_bits, bool expandable,
     83                    OatBitMapKind kind = kBitMapMisc);
     84     ~ArenaBitVector() {}
     85 
     86     static void* operator new(size_t size, ArenaAllocator* arena) {
     87       return arena->Alloc(sizeof(ArenaBitVector), ArenaAllocator::kAllocGrowableBitMap);
     88     }
     89     static void operator delete(void* p) {}  // Nop.
     90 
     91     void SetBit(unsigned int num);
     92     void ClearBit(unsigned int num);
     93     void MarkAllBits(bool set);
     94     void DebugBitVector(char* msg, int length);
     95     bool IsBitSet(unsigned int num);
     96     void ClearAllBits();
     97     void SetInitialBits(unsigned int num_bits);
     98     void Copy(ArenaBitVector* src);
     99     void Intersect(const ArenaBitVector* src2);
    100     void Union(const ArenaBitVector* src);
    101     // Are we equal to another bit vector?  Note: expandability attributes must also match.
    102     bool Equal(const ArenaBitVector* src) {
    103       return (storage_size_ == src->GetStorageSize()) &&
    104         (expandable_ == src->IsExpandable()) &&
    105         (memcmp(storage_, src->GetRawStorage(), storage_size_ * 4) == 0);
    106     }
    107     int NumSetBits();
    108 
    109     uint32_t GetStorageSize() const { return storage_size_; }
    110     bool IsExpandable() const { return expandable_; }
    111     uint32_t GetRawStorageWord(size_t idx) const { return storage_[idx]; }
    112     uint32_t* GetRawStorage() { return storage_; }
    113     const uint32_t* GetRawStorage() const { return storage_; }
    114 
    115   private:
    116     ArenaAllocator* const arena_;
    117     const bool expandable_;         // expand bitmap if we run out?
    118     const OatBitMapKind kind_;      // for memory use tuning.
    119     uint32_t   storage_size_;       // current size, in 32-bit words.
    120     uint32_t*  storage_;
    121 };
    122 
    123 
    124 }  // namespace art
    125 
    126 #endif  // ART_COMPILER_DEX_ARENA_BIT_VECTOR_H_
    127