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 <cstdint> 21 #include <cstring> 22 23 #include "android-base/logging.h" 24 25 namespace android { 26 27 /** 28 * Stores a sparsely populated array. Has a fixed size of 256 29 * (number of entries that a byte can represent). 30 */ 31 template <typename T> 32 class ByteBucketArray { 33 public: ByteBucketArray()34 ByteBucketArray() : default_() { memset(buckets_, 0, sizeof(buckets_)); } 35 ~ByteBucketArray()36 ~ByteBucketArray() { 37 for (size_t i = 0; i < kNumBuckets; i++) { 38 if (buckets_[i] != NULL) { 39 delete[] buckets_[i]; 40 } 41 } 42 memset(buckets_, 0, sizeof(buckets_)); 43 } 44 size()45 inline size_t size() const { return kNumBuckets * kBucketSize; } 46 get(size_t index)47 inline const T& get(size_t index) const { return (*this)[index]; } 48 49 const T& operator[](size_t index) const { 50 if (index >= size()) { 51 return default_; 52 } 53 54 uint8_t bucket_index = static_cast<uint8_t>(index) >> 4; 55 T* bucket = buckets_[bucket_index]; 56 if (bucket == NULL) { 57 return default_; 58 } 59 return bucket[0x0f & static_cast<uint8_t>(index)]; 60 } 61 editItemAt(size_t index)62 T& editItemAt(size_t index) { 63 CHECK(index < size()) << "ByteBucketArray.getOrCreate(index=" << index 64 << ") with size=" << size(); 65 66 uint8_t bucket_index = static_cast<uint8_t>(index) >> 4; 67 T* bucket = buckets_[bucket_index]; 68 if (bucket == NULL) { 69 bucket = buckets_[bucket_index] = new T[kBucketSize](); 70 } 71 return bucket[0x0f & static_cast<uint8_t>(index)]; 72 } 73 set(size_t index,const T & value)74 bool set(size_t index, const T& value) { 75 if (index >= size()) { 76 return false; 77 } 78 79 editItemAt(index) = value; 80 return true; 81 } 82 83 private: 84 enum { kNumBuckets = 16, kBucketSize = 16 }; 85 86 T* buckets_[kNumBuckets]; 87 T default_; 88 }; 89 90 } // namespace android 91 92 #endif // __BYTE_BUCKET_ARRAY_H 93