diff options
Diffstat (limited to 'include')
| -rw-r--r-- | include/binder/CursorWindow.h | 4 | ||||
| -rw-r--r-- | include/gui/BitTube.h (renamed from include/gui/SensorChannel.h) | 9 | ||||
| -rw-r--r-- | include/gui/DisplayEventReceiver.h | 105 | ||||
| -rw-r--r-- | include/gui/IDisplayEventConnection.h | 55 | ||||
| -rw-r--r-- | include/gui/ISensorEventConnection.h | 4 | ||||
| -rw-r--r-- | include/gui/SensorEventQueue.h | 4 | ||||
| -rw-r--r-- | include/media/AudioRecord.h | 2 | ||||
| -rw-r--r-- | include/media/AudioTrack.h | 4 | ||||
| -rw-r--r-- | include/media/JetPlayer.h | 23 | ||||
| -rw-r--r-- | include/private/gui/ComposerService.h | 53 | ||||
| -rw-r--r-- | include/surfaceflinger/ISurfaceComposer.h | 10 | ||||
| -rw-r--r-- | include/surfaceflinger/SurfaceComposerClient.h | 22 | ||||
| -rw-r--r-- | include/utils/BasicHashtable.h | 393 | ||||
| -rw-r--r-- | include/utils/CallStack.h | 8 | ||||
| -rw-r--r-- | include/utils/GenerationCache.h | 108 | ||||
| -rw-r--r-- | include/utils/TypeHelpers.h | 44 |
16 files changed, 750 insertions, 98 deletions
diff --git a/include/binder/CursorWindow.h b/include/binder/CursorWindow.h index f0284ded0cb2..8a2979a3756d 100644 --- a/include/binder/CursorWindow.h +++ b/include/binder/CursorWindow.h @@ -31,8 +31,8 @@ #else -#define IF_LOG_WINDOW() IF_LOG(LOG_DEBUG, "CursorWindow") -#define LOG_WINDOW(...) LOG(LOG_DEBUG, "CursorWindow", __VA_ARGS__) +#define IF_LOG_WINDOW() IF_ALOG(LOG_DEBUG, "CursorWindow") +#define LOG_WINDOW(...) ALOG(LOG_DEBUG, "CursorWindow", __VA_ARGS__) #endif diff --git a/include/gui/SensorChannel.h b/include/gui/BitTube.h index bb546186a66a..76389a037f5e 100644 --- a/include/gui/SensorChannel.h +++ b/include/gui/BitTube.h @@ -28,14 +28,15 @@ namespace android { // ---------------------------------------------------------------------------- class Parcel; -class SensorChannel : public RefBase +class BitTube : public RefBase { public: - SensorChannel(); - SensorChannel(const Parcel& data); - virtual ~SensorChannel(); + BitTube(); + BitTube(const Parcel& data); + virtual ~BitTube(); + status_t initCheck() const; int getFd() const; ssize_t write(void const* vaddr, size_t size); ssize_t read(void* vaddr, size_t size); diff --git a/include/gui/DisplayEventReceiver.h b/include/gui/DisplayEventReceiver.h new file mode 100644 index 000000000000..8d07c0e492c5 --- /dev/null +++ b/include/gui/DisplayEventReceiver.h @@ -0,0 +1,105 @@ +/* + * Copyright (C) 2011 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef ANDROID_GUI_DISPLAY_EVENT_H +#define ANDROID_GUI_DISPLAY_EVENT_H + +#include <stdint.h> +#include <sys/types.h> + +#include <utils/Errors.h> +#include <utils/RefBase.h> +#include <utils/Timers.h> + +#include <binder/IInterface.h> + +// ---------------------------------------------------------------------------- + +namespace android { + +// ---------------------------------------------------------------------------- + +class BitTube; +class IDisplayEventConnection; + +// ---------------------------------------------------------------------------- + +class DisplayEventReceiver { +public: + enum { + DISPLAY_EVENT_VSYNC = 'vsyn' + }; + + struct Event { + + struct Header { + uint32_t type; + nsecs_t timestamp; + }; + + struct VSync { + uint32_t count; + }; + + Header header; + union { + VSync vsync; + }; + }; + +public: + /* + * DisplayEventReceiver creates and registers an event connection with + * SurfaceFlinger. Events start being delivered immediately. + */ + DisplayEventReceiver(); + + /* + * ~DisplayEventReceiver severs the connection with SurfaceFlinger, new events + * stop being delivered immediately. Note that the queue could have + * some events pending. These will be delivered. + */ + ~DisplayEventReceiver(); + + /* + * initCheck returns the state of DisplayEventReceiver after construction. + */ + status_t initCheck() const; + + /* + * getFd returns the file descriptor to use to receive events. + * OWNERSHIP IS RETAINED by DisplayEventReceiver. DO NOT CLOSE this + * file-descriptor. + */ + int getFd() const; + + /* + * getEvents reads event from the queue and returns how many events were + * read. Returns 0 if there are no more events or a negative error code. + * If NOT_ENOUGH_DATA is returned, the object has become invalid forever, it + * should be destroyed and getEvents() shouldn't be called again. + */ + ssize_t getEvents(Event* events, size_t count); + +private: + sp<IDisplayEventConnection> mEventConnection; + sp<BitTube> mDataChannel; +}; + +// ---------------------------------------------------------------------------- +}; // namespace android + +#endif // ANDROID_GUI_DISPLAY_EVENT_H diff --git a/include/gui/IDisplayEventConnection.h b/include/gui/IDisplayEventConnection.h new file mode 100644 index 000000000000..8728bb5ed73b --- /dev/null +++ b/include/gui/IDisplayEventConnection.h @@ -0,0 +1,55 @@ +/* + * Copyright (C) 2011 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef ANDROID_GUI_IDISPLAY_EVENT_CONNECTION_H +#define ANDROID_GUI_IDISPLAY_EVENT_CONNECTION_H + +#include <stdint.h> +#include <sys/types.h> + +#include <utils/Errors.h> +#include <utils/RefBase.h> + +#include <binder/IInterface.h> + +namespace android { +// ---------------------------------------------------------------------------- + +class BitTube; + +class IDisplayEventConnection : public IInterface +{ +public: + DECLARE_META_INTERFACE(DisplayEventConnection); + + virtual sp<BitTube> getDataChannel() const = 0; +}; + +// ---------------------------------------------------------------------------- + +class BnDisplayEventConnection : public BnInterface<IDisplayEventConnection> +{ +public: + virtual status_t onTransact( uint32_t code, + const Parcel& data, + Parcel* reply, + uint32_t flags = 0); +}; + +// ---------------------------------------------------------------------------- +}; // namespace android + +#endif // ANDROID_GUI_IDISPLAY_EVENT_CONNECTION_H diff --git a/include/gui/ISensorEventConnection.h b/include/gui/ISensorEventConnection.h index ed4e4cc72f1b..749065e84ddc 100644 --- a/include/gui/ISensorEventConnection.h +++ b/include/gui/ISensorEventConnection.h @@ -28,14 +28,14 @@ namespace android { // ---------------------------------------------------------------------------- -class SensorChannel; +class BitTube; class ISensorEventConnection : public IInterface { public: DECLARE_META_INTERFACE(SensorEventConnection); - virtual sp<SensorChannel> getSensorChannel() const = 0; + virtual sp<BitTube> getSensorChannel() const = 0; virtual status_t enableDisable(int handle, bool enabled) = 0; virtual status_t setEventRate(int handle, nsecs_t ns) = 0; }; diff --git a/include/gui/SensorEventQueue.h b/include/gui/SensorEventQueue.h index 97dd3919bdbf..ef7c6e369615 100644 --- a/include/gui/SensorEventQueue.h +++ b/include/gui/SensorEventQueue.h @@ -24,7 +24,7 @@ #include <utils/RefBase.h> #include <utils/Timers.h> -#include <gui/SensorChannel.h> +#include <gui/BitTube.h> // ---------------------------------------------------------------------------- @@ -71,7 +71,7 @@ public: private: sp<Looper> getLooper() const; sp<ISensorEventConnection> mSensorEventConnection; - sp<SensorChannel> mSensorChannel; + sp<BitTube> mSensorChannel; mutable Mutex mLock; mutable sp<Looper> mLooper; }; diff --git a/include/media/AudioRecord.h b/include/media/AudioRecord.h index 605680a1a7ee..2fb69b6edf78 100644 --- a/include/media/AudioRecord.h +++ b/include/media/AudioRecord.h @@ -385,6 +385,8 @@ private: uint32_t mChannelMask; audio_io_handle_t mInput; int mSessionId; + int mPreviousPriority; // before start() + int mPreviousSchedulingGroup; }; }; // namespace android diff --git a/include/media/AudioTrack.h b/include/media/AudioTrack.h index d1a8105612bb..cb3d8338bc84 100644 --- a/include/media/AudioTrack.h +++ b/include/media/AudioTrack.h @@ -38,7 +38,7 @@ class audio_track_cblk_t; // ---------------------------------------------------------------------------- -class AudioTrack +class AudioTrack : virtual public RefBase { public: enum channel_index { @@ -487,6 +487,8 @@ private: int mAuxEffectId; Mutex mLock; status_t mRestoreStatus; + int mPreviousPriority; // before start() + int mPreviousSchedulingGroup; }; diff --git a/include/media/JetPlayer.h b/include/media/JetPlayer.h index 16764a9192bd..6d539897429d 100644 --- a/include/media/JetPlayer.h +++ b/include/media/JetPlayer.h @@ -65,7 +65,6 @@ public: private: - static int renderThread(void*); int render(); void fireUpdateOnStatusChange(); void fireEventsFromJetQueue(); @@ -97,6 +96,28 @@ private: char mJetFilePath[256]; + class JetPlayerThread : public Thread { + public: + JetPlayerThread(JetPlayer *player) : mPlayer(player) { + } + + protected: + virtual ~JetPlayerThread() {} + + private: + JetPlayer *mPlayer; + + bool threadLoop() { + int result; + result = mPlayer->render(); + return false; + } + + JetPlayerThread(const JetPlayerThread &); + JetPlayerThread &operator=(const JetPlayerThread &); + }; + + sp<JetPlayerThread> mThread; }; // end class JetPlayer diff --git a/include/private/gui/ComposerService.h b/include/private/gui/ComposerService.h new file mode 100644 index 000000000000..d04491a86e54 --- /dev/null +++ b/include/private/gui/ComposerService.h @@ -0,0 +1,53 @@ +/* + * Copyright (C) 2011 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef ANDROID_PRIVATE_GUI_COMPOSER_SERVICE_H +#define ANDROID_PRIVATE_GUI_COMPOSER_SERVICE_H + +#include <stdint.h> +#include <sys/types.h> + +#include <utils/Singleton.h> +#include <utils/StrongPointer.h> + + +namespace android { + +// --------------------------------------------------------------------------- + +class IMemoryHeap; +class ISurfaceComposer; +class surface_flinger_cblk_t; + +// --------------------------------------------------------------------------- + +class ComposerService : public Singleton<ComposerService> +{ + // these are constants + sp<ISurfaceComposer> mComposerService; + sp<IMemoryHeap> mServerCblkMemory; + surface_flinger_cblk_t volatile* mServerCblk; + ComposerService(); + friend class Singleton<ComposerService>; +public: + static sp<ISurfaceComposer> getComposerService(); + static surface_flinger_cblk_t const volatile * getControlBlock(); +}; + +// --------------------------------------------------------------------------- +}; // namespace android + +#endif // ANDROID_PRIVATE_GUI_COMPOSER_SERVICE_H diff --git a/include/surfaceflinger/ISurfaceComposer.h b/include/surfaceflinger/ISurfaceComposer.h index 5eb09c79666a..58fd89d3b62c 100644 --- a/include/surfaceflinger/ISurfaceComposer.h +++ b/include/surfaceflinger/ISurfaceComposer.h @@ -33,8 +33,9 @@ namespace android { // ---------------------------------------------------------------------------- -class IMemoryHeap; class ComposerState; +class IDisplayEventConnection; +class IMemoryHeap; class ISurfaceComposer : public IInterface { @@ -124,13 +125,19 @@ public: uint32_t reqWidth, uint32_t reqHeight, uint32_t minLayerZ, uint32_t maxLayerZ) = 0; + /* triggers screen off animation */ virtual status_t turnElectronBeamOff(int32_t mode) = 0; + + /* triggers screen on animation */ virtual status_t turnElectronBeamOn(int32_t mode) = 0; /* verify that an ISurfaceTexture was created by SurfaceFlinger. */ virtual bool authenticateSurfaceTexture( const sp<ISurfaceTexture>& surface) const = 0; + + /* return an IDisplayEventConnection */ + virtual sp<IDisplayEventConnection> createDisplayEventConnection() = 0; }; // ---------------------------------------------------------------------------- @@ -151,6 +158,7 @@ public: TURN_ELECTRON_BEAM_OFF, TURN_ELECTRON_BEAM_ON, AUTHENTICATE_SURFACE, + CREATE_DISPLAY_EVENT_CONNECTION, }; virtual status_t onTransact( uint32_t code, diff --git a/include/surfaceflinger/SurfaceComposerClient.h b/include/surfaceflinger/SurfaceComposerClient.h index 8226abec1c13..99affdae64d0 100644 --- a/include/surfaceflinger/SurfaceComposerClient.h +++ b/include/surfaceflinger/SurfaceComposerClient.h @@ -28,7 +28,6 @@ #include <utils/threads.h> #include <ui/PixelFormat.h> -#include <ui/Region.h> #include <surfaceflinger/Surface.h> @@ -39,30 +38,11 @@ namespace android { class DisplayInfo; class Composer; class IMemoryHeap; -class ISurfaceComposer; +class ISurfaceComposerClient; class Region; -class surface_flinger_cblk_t; -struct layer_state_t; // --------------------------------------------------------------------------- -class ComposerService : public Singleton<ComposerService> -{ - // these are constants - sp<ISurfaceComposer> mComposerService; - sp<IMemoryHeap> mServerCblkMemory; - surface_flinger_cblk_t volatile* mServerCblk; - ComposerService(); - friend class Singleton<ComposerService>; -public: - static sp<ISurfaceComposer> getComposerService(); - static surface_flinger_cblk_t const volatile * getControlBlock(); -}; - -// --------------------------------------------------------------------------- - -class Composer; - class SurfaceComposerClient : public RefBase { friend class Composer; diff --git a/include/utils/BasicHashtable.h b/include/utils/BasicHashtable.h new file mode 100644 index 000000000000..fdf97385f976 --- /dev/null +++ b/include/utils/BasicHashtable.h @@ -0,0 +1,393 @@ +/* + * Copyright (C) 2011 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef ANDROID_BASIC_HASHTABLE_H +#define ANDROID_BASIC_HASHTABLE_H + +#include <stdint.h> +#include <sys/types.h> +#include <utils/SharedBuffer.h> +#include <utils/TypeHelpers.h> + +namespace android { + +/* Implementation type. Nothing to see here. */ +class BasicHashtableImpl { +protected: + struct Bucket { + // The collision flag indicates that the bucket is part of a collision chain + // such that at least two entries both hash to this bucket. When true, we + // may need to seek further along the chain to find the entry. + static const uint32_t COLLISION = 0x80000000UL; + + // The present flag indicates that the bucket contains an initialized entry value. + static const uint32_t PRESENT = 0x40000000UL; + + // Mask for 30 bits worth of the hash code that are stored within the bucket to + // speed up lookups and rehashing by eliminating the need to recalculate the + // hash code of the entry's key. + static const uint32_t HASH_MASK = 0x3fffffffUL; + + // Combined value that stores the collision and present flags as well as + // a 30 bit hash code. + uint32_t cookie; + + // Storage for the entry begins here. + char entry[0]; + }; + + BasicHashtableImpl(size_t entrySize, bool hasTrivialDestructor, + size_t minimumInitialCapacity, float loadFactor); + BasicHashtableImpl(const BasicHashtableImpl& other); + + void dispose(); + + inline void edit() { + if (mBuckets && !SharedBuffer::bufferFromData(mBuckets)->onlyOwner()) { + clone(); + } + } + + void setTo(const BasicHashtableImpl& other); + void clear(); + + ssize_t next(ssize_t index) const; + ssize_t find(ssize_t index, hash_t hash, const void* __restrict__ key) const; + size_t add(hash_t hash, const void* __restrict__ entry); + void removeAt(size_t index); + void rehash(size_t minimumCapacity, float loadFactor); + + const size_t mBucketSize; // number of bytes per bucket including the entry + const bool mHasTrivialDestructor; // true if the entry type does not require destruction + size_t mCapacity; // number of buckets that can be filled before exceeding load factor + float mLoadFactor; // load factor + size_t mSize; // number of elements actually in the table + size_t mFilledBuckets; // number of buckets for which collision or present is true + size_t mBucketCount; // number of slots in the mBuckets array + void* mBuckets; // array of buckets, as a SharedBuffer + + inline const Bucket& bucketAt(const void* __restrict__ buckets, size_t index) const { + return *reinterpret_cast<const Bucket*>( + static_cast<const uint8_t*>(buckets) + index * mBucketSize); + } + + inline Bucket& bucketAt(void* __restrict__ buckets, size_t index) const { + return *reinterpret_cast<Bucket*>(static_cast<uint8_t*>(buckets) + index * mBucketSize); + } + + virtual bool compareBucketKey(const Bucket& bucket, const void* __restrict__ key) const = 0; + virtual void initializeBucketEntry(Bucket& bucket, const void* __restrict__ entry) const = 0; + virtual void destroyBucketEntry(Bucket& bucket) const = 0; + +private: + void clone(); + + // Allocates a bucket array as a SharedBuffer. + void* allocateBuckets(size_t count) const; + + // Releases a bucket array's associated SharedBuffer. + void releaseBuckets(void* __restrict__ buckets, size_t count) const; + + // Destroys the contents of buckets (invokes destroyBucketEntry for each + // populated bucket if needed). + void destroyBuckets(void* __restrict__ buckets, size_t count) const; + + // Copies the content of buckets (copies the cookie and invokes copyBucketEntry + // for each populated bucket if needed). + void copyBuckets(const void* __restrict__ fromBuckets, + void* __restrict__ toBuckets, size_t count) const; + + // Determines the appropriate size of a bucket array to store a certain minimum + // number of entries and returns its effective capacity. + static void determineCapacity(size_t minimumCapacity, float loadFactor, + size_t* __restrict__ outBucketCount, size_t* __restrict__ outCapacity); + + // Trim a hash code to 30 bits to match what we store in the bucket's cookie. + inline static hash_t trimHash(hash_t hash) { + return (hash & Bucket::HASH_MASK) ^ (hash >> 30); + } + + // Returns the index of the first bucket that is in the collision chain + // for the specified hash code, given the total number of buckets. + // (Primary hash) + inline static size_t chainStart(hash_t hash, size_t count) { + return hash % count; + } + + // Returns the increment to add to a bucket index to seek to the next bucket + // in the collision chain for the specified hash code, given the total number of buckets. + // (Secondary hash) + inline static size_t chainIncrement(hash_t hash, size_t count) { + return ((hash >> 7) | (hash << 25)) % (count - 1) + 1; + } + + // Returns the index of the next bucket that is in the collision chain + // that is defined by the specified increment, given the total number of buckets. + inline static size_t chainSeek(size_t index, size_t increment, size_t count) { + return (index + increment) % count; + } +}; + +/* + * A BasicHashtable stores entries that are indexed by hash code in place + * within an array. The basic operations are finding entries by key, + * adding new entries and removing existing entries. + * + * This class provides a very limited set of operations with simple semantics. + * It is intended to be used as a building block to construct more complex + * and interesting data structures such as HashMap. Think very hard before + * adding anything extra to BasicHashtable, it probably belongs at a + * higher level of abstraction. + * + * TKey: The key type. + * TEntry: The entry type which is what is actually stored in the array. + * + * TKey must support the following contract: + * bool operator==(const TKey& other) const; // return true if equal + * bool operator!=(const TKey& other) const; // return true if unequal + * + * TEntry must support the following contract: + * const TKey& getKey() const; // get the key from the entry + * + * This class supports storing entries with duplicate keys. Of course, it can't + * tell them apart during removal so only the first entry will be removed. + * We do this because it means that operations like add() can't fail. + */ +template <typename TKey, typename TEntry> +class BasicHashtable : private BasicHashtableImpl { +public: + /* Creates a hashtable with the specified minimum initial capacity. + * The underlying array will be created when the first entry is added. + * + * minimumInitialCapacity: The minimum initial capacity for the hashtable. + * Default is 0. + * loadFactor: The desired load factor for the hashtable, between 0 and 1. + * Default is 0.75. + */ + BasicHashtable(size_t minimumInitialCapacity = 0, float loadFactor = 0.75f); + + /* Copies a hashtable. + * The underlying storage is shared copy-on-write. + */ + BasicHashtable(const BasicHashtable& other); + + /* Clears and destroys the hashtable. + */ + virtual ~BasicHashtable(); + + /* Making this hashtable a copy of the other hashtable. + * The underlying storage is shared copy-on-write. + * + * other: The hashtable to copy. + */ + inline BasicHashtable<TKey, TEntry>& operator =(const BasicHashtable<TKey, TEntry> & other) { + setTo(other); + return *this; + } + + /* Returns the number of entries in the hashtable. + */ + inline size_t size() const { + return mSize; + } + + /* Returns the capacity of the hashtable, which is the number of elements that can + * added to the hashtable without requiring it to be grown. + */ + inline size_t capacity() const { + return mCapacity; + } + + /* Returns the number of buckets that the hashtable has, which is the size of its + * underlying array. + */ + inline size_t bucketCount() const { + return mBucketCount; + } + + /* Returns the load factor of the hashtable. */ + inline float loadFactor() const { + return mLoadFactor; + }; + + /* Returns a const reference to the entry at the specified index. + * + * index: The index of the entry to retrieve. Must be a valid index within + * the bounds of the hashtable. + */ + inline const TEntry& entryAt(size_t index) const { + return entryFor(bucketAt(mBuckets, index)); + } + + /* Returns a non-const reference to the entry at the specified index. + * + * index: The index of the entry to edit. Must be a valid index within + * the bounds of the hashtable. + */ + inline TEntry& editEntryAt(size_t index) { + edit(); + return entryFor(bucketAt(mBuckets, index)); + } + + /* Clears the hashtable. + * All entries in the hashtable are destroyed immediately. + * If you need to do something special with the entries in the hashtable then iterate + * over them and do what you need before clearing the hashtable. + */ + inline void clear() { + BasicHashtableImpl::clear(); + } + + /* Returns the index of the next entry in the hashtable given the index of a previous entry. + * If the given index is -1, then returns the index of the first entry in the hashtable, + * if there is one, or -1 otherwise. + * If the given index is not -1, then returns the index of the next entry in the hashtable, + * in strictly increasing order, or -1 if there are none left. + * + * index: The index of the previous entry that was iterated, or -1 to begin + * iteration at the beginning of the hashtable. + */ + inline ssize_t next(ssize_t index) const { + return BasicHashtableImpl::next(index); + } + + /* Finds the index of an entry with the specified key. + * If the given index is -1, then returns the index of the first matching entry, + * otherwise returns the index of the next matching entry. + * If the hashtable contains multiple entries with keys that match the requested + * key, then the sequence of entries returned is arbitrary. + * Returns -1 if no entry was found. + * + * index: The index of the previous entry with the specified key, or -1 to + * find the first matching entry. + * hash: The hashcode of the key. + * key: The key. + */ + inline ssize_t find(ssize_t index, hash_t hash, const TKey& key) const { + return BasicHashtableImpl::find(index, hash, &key); + } + + /* Adds the entry to the hashtable. + * Returns the index of the newly added entry. + * If an entry with the same key already exists, then a duplicate entry is added. + * If the entry will not fit, then the hashtable's capacity is increased and + * its contents are rehashed. See rehash(). + * + * hash: The hashcode of the key. + * entry: The entry to add. + */ + inline size_t add(hash_t hash, const TEntry& entry) { + return BasicHashtableImpl::add(hash, &entry); + } + + /* Removes the entry with the specified index from the hashtable. + * The entry is destroyed immediately. + * The index must be valid. + * + * The hashtable is not compacted after an item is removed, so it is legal + * to continue iterating over the hashtable using next() or find(). + * + * index: The index of the entry to remove. Must be a valid index within the + * bounds of the hashtable, and it must refer to an existing entry. + */ + inline void removeAt(size_t index) { + BasicHashtableImpl::removeAt(index); + } + + /* Rehashes the contents of the hashtable. + * Grows the hashtable to at least the specified minimum capacity or the + * current number of elements, whichever is larger. + * + * Rehashing causes all entries to be copied and the entry indices may change. + * Although the hash codes are cached by the hashtable, rehashing can be an + * expensive operation and should be avoided unless the hashtable's size + * needs to be changed. + * + * Rehashing is the only way to change the capacity or load factor of the + * hashtable once it has been created. It can be used to compact the + * hashtable by choosing a minimum capacity that is smaller than the current + * capacity (such as 0). + * + * minimumCapacity: The desired minimum capacity after rehashing. + * loadFactor: The desired load factor after rehashing. + */ + inline void rehash(size_t minimumCapacity, float loadFactor) { + BasicHashtableImpl::rehash(minimumCapacity, loadFactor); + } + +protected: + static inline const TEntry& entryFor(const Bucket& bucket) { + return reinterpret_cast<const TEntry&>(bucket.entry); + } + + static inline TEntry& entryFor(Bucket& bucket) { + return reinterpret_cast<TEntry&>(bucket.entry); + } + + virtual bool compareBucketKey(const Bucket& bucket, const void* __restrict__ key) const; + virtual void initializeBucketEntry(Bucket& bucket, const void* __restrict__ entry) const; + virtual void destroyBucketEntry(Bucket& bucket) const; + +private: + // For dumping the raw contents of a hashtable during testing. + friend class BasicHashtableTest; + inline uint32_t cookieAt(size_t index) const { + return bucketAt(mBuckets, index).cookie; + } +}; + +template <typename TKey, typename TEntry> +BasicHashtable<TKey, TEntry>::BasicHashtable(size_t minimumInitialCapacity, float loadFactor) : + BasicHashtableImpl(sizeof(TEntry), traits<TEntry>::has_trivial_dtor, + minimumInitialCapacity, loadFactor) { +} + +template <typename TKey, typename TEntry> +BasicHashtable<TKey, TEntry>::BasicHashtable(const BasicHashtable<TKey, TEntry>& other) : + BasicHashtableImpl(other) { +} + +template <typename TKey, typename TEntry> +BasicHashtable<TKey, TEntry>::~BasicHashtable() { + dispose(); +} + +template <typename TKey, typename TEntry> +bool BasicHashtable<TKey, TEntry>::compareBucketKey(const Bucket& bucket, + const void* __restrict__ key) const { + return entryFor(bucket).getKey() == *static_cast<const TKey*>(key); +} + +template <typename TKey, typename TEntry> +void BasicHashtable<TKey, TEntry>::initializeBucketEntry(Bucket& bucket, + const void* __restrict__ entry) const { + if (!traits<TEntry>::has_trivial_copy) { + new (&entryFor(bucket)) TEntry(*(static_cast<const TEntry*>(entry))); + } else { + memcpy(&entryFor(bucket), entry, sizeof(TEntry)); + } +} + +template <typename TKey, typename TEntry> +void BasicHashtable<TKey, TEntry>::destroyBucketEntry(Bucket& bucket) const { + if (!traits<TEntry>::has_trivial_dtor) { + entryFor(bucket).~TEntry(); + } +} + +}; // namespace android + +#endif // ANDROID_BASIC_HASHTABLE_H diff --git a/include/utils/CallStack.h b/include/utils/CallStack.h index 8817120effad..079e20c6962f 100644 --- a/include/utils/CallStack.h +++ b/include/utils/CallStack.h @@ -21,6 +21,7 @@ #include <sys/types.h> #include <utils/String8.h> +#include <corkscrew/backtrace.h> // --------------------------------------------------------------------------- @@ -61,11 +62,8 @@ public: size_t size() const { return mCount; } private: - // Internal helper function - String8 toStringSingleLevel(const char* prefix, int32_t level) const; - - size_t mCount; - const void* mStack[MAX_DEPTH]; + size_t mCount; + backtrace_frame_t mStack[MAX_DEPTH]; }; }; // namespace android diff --git a/include/utils/GenerationCache.h b/include/utils/GenerationCache.h index bb9ddd67781f..83cda8689fd1 100644 --- a/include/utils/GenerationCache.h +++ b/include/utils/GenerationCache.h @@ -34,17 +34,17 @@ public: template<typename EntryKey, typename EntryValue> struct Entry: public LightRefBase<Entry<EntryKey, EntryValue> > { - Entry() { } - Entry(const Entry<EntryKey, EntryValue>& e): - key(e.key), value(e.value), parent(e.parent), child(e.child) { } - Entry(sp<Entry<EntryKey, EntryValue> > e): - key(e->key), value(e->value), parent(e->parent), child(e->child) { } + Entry(const Entry<EntryKey, EntryValue>& e) : + key(e.key), value(e.value), + parent(e.parent), child(e.child) { } + Entry(const EntryKey& key, const EntryValue& value) : + key(key), value(value) { } EntryKey key; EntryValue value; - sp<Entry<EntryKey, EntryValue> > parent; - sp<Entry<EntryKey, EntryValue> > child; + sp<Entry<EntryKey, EntryValue> > parent; // next older entry + sp<Entry<EntryKey, EntryValue> > child; // next younger entry }; // struct Entry /** @@ -62,23 +62,20 @@ public: void setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener); - void clear(); + size_t size() const; - bool contains(K key) const; - V get(K key); - K getKeyAt(uint32_t index) const; - bool put(K key, V value); - V remove(K key); - V removeOldest(); - V getValueAt(uint32_t index) const; + void clear(); - uint32_t size() const; + bool contains(const K& key) const; + const K& getKeyAt(size_t index) const; + const V& getValueAt(size_t index) const; - void addToCache(sp<Entry<K, V> > entry, K key, V value); - void attachToCache(sp<Entry<K, V> > entry); - void detachFromCache(sp<Entry<K, V> > entry); + const V& get(const K& key); + bool put(const K& key, const V& value); - V removeAt(ssize_t index); + void removeAt(ssize_t index); + bool remove(const K& key); + bool removeOldest(); private: KeyedVector<K, sp<Entry<K, V> > > mCache; @@ -88,6 +85,9 @@ private: sp<Entry<K, V> > mOldest; sp<Entry<K, V> > mYoungest; + + void attachToCache(const sp<Entry<K, V> >& entry); + void detachFromCache(const sp<Entry<K, V> >& entry); }; // class GenerationCache template<typename K, typename V> @@ -130,45 +130,44 @@ void GenerationCache<K, V>::clear() { } template<typename K, typename V> -bool GenerationCache<K, V>::contains(K key) const { +bool GenerationCache<K, V>::contains(const K& key) const { return mCache.indexOfKey(key) >= 0; } template<typename K, typename V> -K GenerationCache<K, V>::getKeyAt(uint32_t index) const { +const K& GenerationCache<K, V>::getKeyAt(size_t index) const { return mCache.keyAt(index); } template<typename K, typename V> -V GenerationCache<K, V>::getValueAt(uint32_t index) const { +const V& GenerationCache<K, V>::getValueAt(size_t index) const { return mCache.valueAt(index)->value; } template<typename K, typename V> -V GenerationCache<K, V>::get(K key) { +const V& GenerationCache<K, V>::get(const K& key) { ssize_t index = mCache.indexOfKey(key); if (index >= 0) { - sp<Entry<K, V> > entry = mCache.valueAt(index); - if (entry.get()) { - detachFromCache(entry); - attachToCache(entry); - return entry->value; - } + const sp<Entry<K, V> >& entry = mCache.valueAt(index); + detachFromCache(entry); + attachToCache(entry); + return entry->value; } return NULL; } template<typename K, typename V> -bool GenerationCache<K, V>::put(K key, V value) { +bool GenerationCache<K, V>::put(const K& key, const V& value) { if (mMaxCapacity != kUnlimitedCapacity && mCache.size() >= mMaxCapacity) { removeOldest(); } ssize_t index = mCache.indexOfKey(key); if (index < 0) { - sp<Entry<K, V> > entry = new Entry<K, V>; - addToCache(entry, key, value); + sp<Entry<K, V> > entry = new Entry<K, V>(key, value); + mCache.add(key, entry); + attachToCache(entry); return true; } @@ -176,49 +175,44 @@ bool GenerationCache<K, V>::put(K key, V value) { } template<typename K, typename V> -void GenerationCache<K, V>::addToCache(sp<Entry<K, V> > entry, K key, V value) { - entry->key = key; - entry->value = value; - mCache.add(key, entry); - attachToCache(entry); -} - -template<typename K, typename V> -V GenerationCache<K, V>::remove(K key) { +bool GenerationCache<K, V>::remove(const K& key) { ssize_t index = mCache.indexOfKey(key); if (index >= 0) { - return removeAt(index); + removeAt(index); + return true; } - return NULL; + return false; } template<typename K, typename V> -V GenerationCache<K, V>::removeAt(ssize_t index) { +void GenerationCache<K, V>::removeAt(ssize_t index) { sp<Entry<K, V> > entry = mCache.valueAt(index); if (mListener) { (*mListener)(entry->key, entry->value); } mCache.removeItemsAt(index, 1); detachFromCache(entry); - - return entry->value; } template<typename K, typename V> -V GenerationCache<K, V>::removeOldest() { +bool GenerationCache<K, V>::removeOldest() { if (mOldest.get()) { ssize_t index = mCache.indexOfKey(mOldest->key); if (index >= 0) { - return removeAt(index); + removeAt(index); + return true; } + LOGE("GenerationCache: removeOldest failed to find the item in the cache " + "with the given key, but we know it must be in there. " + "Is the key comparator kaput?"); } - return NULL; + return false; } template<typename K, typename V> -void GenerationCache<K, V>::attachToCache(sp<Entry<K, V> > entry) { +void GenerationCache<K, V>::attachToCache(const sp<Entry<K, V> >& entry) { if (!mYoungest.get()) { mYoungest = mOldest = entry; } else { @@ -229,20 +223,16 @@ void GenerationCache<K, V>::attachToCache(sp<Entry<K, V> > entry) { } template<typename K, typename V> -void GenerationCache<K, V>::detachFromCache(sp<Entry<K, V> > entry) { +void GenerationCache<K, V>::detachFromCache(const sp<Entry<K, V> >& entry) { if (entry->parent.get()) { entry->parent->child = entry->child; + } else { + mOldest = entry->child; } if (entry->child.get()) { entry->child->parent = entry->parent; - } - - if (mOldest == entry) { - mOldest = entry->child; - } - - if (mYoungest == entry) { + } else { mYoungest = entry->parent; } diff --git a/include/utils/TypeHelpers.h b/include/utils/TypeHelpers.h index a1663f30e50d..7b4fb70ba641 100644 --- a/include/utils/TypeHelpers.h +++ b/include/utils/TypeHelpers.h @@ -213,6 +213,9 @@ void move_backward_type(TYPE* d, const TYPE* s, size_t n = 1) { template <typename KEY, typename VALUE> struct key_value_pair_t { + typedef KEY key_t; + typedef VALUE value_t; + KEY key; VALUE value; key_value_pair_t() { } @@ -222,6 +225,12 @@ struct key_value_pair_t { inline bool operator < (const key_value_pair_t& o) const { return strictly_order_type(key, o.key); } + inline const KEY& getKey() const { + return key; + } + inline const VALUE& getValue() const { + return value; + } }; template<> @@ -243,6 +252,41 @@ struct trait_trivial_move< key_value_pair_t<K, V> > // --------------------------------------------------------------------------- +/* + * Hash codes. + */ +typedef uint32_t hash_t; + +template <typename TKey> +hash_t hash_type(const TKey& key); + +/* Built-in hash code specializations. + * Assumes pointers are 32bit. */ +#define ANDROID_INT32_HASH(T) \ + template <> inline hash_t hash_type(const T& value) { return hash_t(value); } +#define ANDROID_INT64_HASH(T) \ + template <> inline hash_t hash_type(const T& value) { \ + return hash_t((value >> 32) ^ value); } +#define ANDROID_REINTERPRET_HASH(T, R) \ + template <> inline hash_t hash_type(const T& value) { \ + return hash_type(*reinterpret_cast<const R*>(&value)); } + +ANDROID_INT32_HASH(bool) +ANDROID_INT32_HASH(int8_t) +ANDROID_INT32_HASH(uint8_t) +ANDROID_INT32_HASH(int16_t) +ANDROID_INT32_HASH(uint16_t) +ANDROID_INT32_HASH(int32_t) +ANDROID_INT32_HASH(uint32_t) +ANDROID_INT64_HASH(int64_t) +ANDROID_INT64_HASH(uint64_t) +ANDROID_REINTERPRET_HASH(float, uint32_t) +ANDROID_REINTERPRET_HASH(double, uint64_t) + +template <typename T> inline hash_t hash_type(const T*& value) { + return hash_type(uintptr_t(value)); +} + }; // namespace android // --------------------------------------------------------------------------- |