1 /* 2 * Copyright (C) 2014 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 __BYTE_BUCKET_ARRAY_H 18 #define __BYTE_BUCKET_ARRAY_H 19 20 #include <algorithm> 21 #include <cstdint> 22 #include <cstring> 23 24 #include "android-base/logging.h" 25 26 namespace android { 27 28 /** 29 * Stores a sparsely populated array. Has a fixed size of 256 30 * (number of entries that a byte can represent). 31 */ 32 template <typename T> 33 class ByteBucketArray { 34 public: ByteBucketArray()35 ByteBucketArray() { 36 memset(buckets_, 0, sizeof(buckets_)); 37 } 38 ~ByteBucketArray()39 ~ByteBucketArray() { 40 deleteBuckets(); 41 } 42 clear()43 void clear() { 44 deleteBuckets(); 45 memset(buckets_, 0, sizeof(buckets_)); 46 } 47 size()48 inline size_t size() const { return kNumBuckets * kBucketSize; } 49 get(size_t index)50 inline const T& get(size_t index) const { return (*this)[index]; } 51 52 const T& operator[](size_t index) const { 53 if (index >= size()) { 54 return default_; 55 } 56 57 uint8_t bucket_index = static_cast<uint8_t>(index) >> 4; 58 T* bucket = buckets_[bucket_index]; 59 if (bucket == nullptr) { 60 return default_; 61 } 62 return bucket[0x0f & static_cast<uint8_t>(index)]; 63 } 64 editItemAt(size_t index)65 T& editItemAt(size_t index) { 66 CHECK(index < size()) << "ByteBucketArray.editItemAt(index=" << index 67 << ") with size=" << size(); 68 69 uint8_t bucket_index = static_cast<uint8_t>(index) >> 4; 70 T*& bucket = buckets_[bucket_index]; 71 if (bucket == nullptr) { 72 bucket = new T[kBucketSize](); 73 } 74 return bucket[0x0f & static_cast<uint8_t>(index)]; 75 } 76 set(size_t index,const T & value)77 bool set(size_t index, const T& value) { 78 if (index >= size()) { 79 return false; 80 } 81 82 editItemAt(index) = value; 83 return true; 84 } 85 86 template <class Func> forEachItem(Func f)87 void forEachItem(Func f) { 88 for (size_t i = 0; i < kNumBuckets; i++) { 89 const auto bucket = buckets_[i]; 90 if (bucket != nullptr) { 91 for (size_t j = 0; j < kBucketSize; j++) { 92 f((i << 4) | j, bucket[j]); 93 } 94 } 95 } 96 } 97 98 template <class Func> trimBuckets(Func isEmptyFunc)99 void trimBuckets(Func isEmptyFunc) { 100 for (size_t i = 0; i < kNumBuckets; i++) { 101 const auto bucket = buckets_[i]; 102 if (bucket != nullptr) { 103 if (std::all_of(bucket, bucket + kBucketSize, isEmptyFunc)) { 104 delete[] bucket; 105 buckets_[i] = nullptr; 106 } 107 } 108 } 109 } 110 111 private: 112 enum { kNumBuckets = 16, kBucketSize = 16 }; 113 deleteBuckets()114 void deleteBuckets() { 115 for (size_t i = 0; i < kNumBuckets; i++) { 116 if (buckets_[i] != nullptr) { 117 delete[] buckets_[i]; 118 } 119 } 120 } 121 122 T* buckets_[kNumBuckets]; 123 static inline const T default_ = {}; 124 }; 125 126 } // namespace android 127 128 #endif // __BYTE_BUCKET_ARRAY_H 129