ByteBucketArray.h revision f90f2f8dc36e7243b85e0b6a7fd5a590893c827e 
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
24namespace 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 */
30template<typename T>
31class ByteBucketArray {
32public:
33    ByteBucketArray() : mDefault() {
34        memset(mBuckets, 0, sizeof(mBuckets));
35    }
36
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
46    inline size_t size() const {
47        return NUM_BUCKETS * BUCKET_SIZE;
48    }
49
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
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
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
88private:
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