1f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski/* 2f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski * Copyright (C) 2014 The Android Open Source Project 3f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski * 4f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski * Licensed under the Apache License, Version 2.0 (the "License"); 5f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski * you may not use this file except in compliance with the License. 6f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski * You may obtain a copy of the License at 7f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski * 8f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski * http://www.apache.org/licenses/LICENSE-2.0 9f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski * 10f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski * Unless required by applicable law or agreed to in writing, software 11f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski * distributed under the License is distributed on an "AS IS" BASIS, 12f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski * See the License for the specific language governing permissions and 14f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski * limitations under the License. 15f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski */ 16f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski 17f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski#ifndef __BYTE_BUCKET_ARRAY_H 18f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski#define __BYTE_BUCKET_ARRAY_H 19f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski 20f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski#include <utils/Log.h> 21f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski#include <stdint.h> 22f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski#include <string.h> 23f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski 24f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinskinamespace android { 25f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski 26f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski/** 27f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski * Stores a sparsely populated array. Has a fixed size of 256 28f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski * (number of entries that a byte can represent). 29f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski */ 30f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinskitemplate<typename T> 31f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinskiclass ByteBucketArray { 32f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinskipublic: 33f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski ByteBucketArray() : mDefault() { 34f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski memset(mBuckets, 0, sizeof(mBuckets)); 35f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski } 36f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski 37f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski ~ByteBucketArray() { 38f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski for (size_t i = 0; i < NUM_BUCKETS; i++) { 39f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski if (mBuckets[i] != NULL) { 40f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski delete [] mBuckets[i]; 41f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski } 42f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski } 43f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski memset(mBuckets, 0, sizeof(mBuckets)); 44f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski } 45f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski 46f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski inline size_t size() const { 47f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski return NUM_BUCKETS * BUCKET_SIZE; 48f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski } 49f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski 50f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski inline const T& get(size_t index) const { 51f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski return (*this)[index]; 52f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski } 53f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski 54f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski const T& operator[](size_t index) const { 55f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski if (index >= size()) { 56f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski return mDefault; 57f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski } 58f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski 59f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski uint8_t bucketIndex = static_cast<uint8_t>(index) >> 4; 60f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski T* bucket = mBuckets[bucketIndex]; 61f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski if (bucket == NULL) { 62f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski return mDefault; 63f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski } 64f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski return bucket[0x0f & static_cast<uint8_t>(index)]; 65f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski } 66f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski 67f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski T& editItemAt(size_t index) { 68f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski ALOG_ASSERT(index < size(), "ByteBucketArray.getOrCreate(index=%u) with size=%u", 69f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski (uint32_t) index, (uint32_t) size()); 70f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski 71f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski uint8_t bucketIndex = static_cast<uint8_t>(index) >> 4; 72f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski T* bucket = mBuckets[bucketIndex]; 73f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski if (bucket == NULL) { 74f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski bucket = mBuckets[bucketIndex] = new T[BUCKET_SIZE](); 75f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski } 76f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski return bucket[0x0f & static_cast<uint8_t>(index)]; 77f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski } 78f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski 79f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski bool set(size_t index, const T& value) { 80f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski if (index >= size()) { 81f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski return false; 82f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski } 83f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski 84f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski editItemAt(index) = value; 85f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski return true; 86f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski } 87f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski 88f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinskiprivate: 89f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski enum { NUM_BUCKETS = 16, BUCKET_SIZE = 16 }; 90f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski 91f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski T* mBuckets[NUM_BUCKETS]; 92f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski T mDefault; 93f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski}; 94f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski 95f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski} // namespace android 96f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski 97f90f2f8dc36e7243b85e0b6a7fd5a590893c827eAdam Lesinski#endif // __BYTE_BUCKET_ARRAY_H 98