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