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