E:/p4/sw/physx/PxShared/1.0/trunk/src/foundation/include/PsHashMap.h
Go to the documentation of this file.00001 // This code contains NVIDIA Confidential Information and is disclosed to you 00002 // under a form of NVIDIA software license agreement provided separately to you. 00003 // 00004 // Notice 00005 // NVIDIA Corporation and its licensors retain all intellectual property and 00006 // proprietary rights in and to this software and related documentation and 00007 // any modifications thereto. Any use, reproduction, disclosure, or 00008 // distribution of this software and related documentation without an express 00009 // license agreement from NVIDIA Corporation is strictly prohibited. 00010 // 00011 // ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES 00012 // NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO 00013 // THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT, 00014 // MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE. 00015 // 00016 // Information and code furnished is believed to be accurate and reliable. 00017 // However, NVIDIA Corporation assumes no responsibility for the consequences of use of such 00018 // information or for any infringement of patents or other rights of third parties that may 00019 // result from its use. No license is granted by implication or otherwise under any patent 00020 // or patent rights of NVIDIA Corporation. Details are subject to change without notice. 00021 // This code supersedes and replaces all information previously supplied. 00022 // NVIDIA Corporation products are not authorized for use as critical 00023 // components in life support devices or systems without express written approval of 00024 // NVIDIA Corporation. 00025 // 00026 // Copyright (c) 2008-2014 NVIDIA Corporation. All rights reserved. 00027 // Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved. 00028 // Copyright (c) 2001-2004 NovodeX AG. All rights reserved. 00029 00030 #ifndef PSFOUNDATION_PSHASHMAP_H 00031 #define PSFOUNDATION_PSHASHMAP_H 00032 00033 #include "PsHashInternals.h" 00034 00035 // TODO: make this doxy-format 00036 // 00037 // This header defines two hash maps. Hash maps 00038 // * support custom initial table sizes (rounded up internally to power-of-2) 00039 // * support custom static allocator objects 00040 // * auto-resize, based on a load factor (i.e. a 64-entry .75 load factor hash will resize 00041 // when the 49th element is inserted) 00042 // * are based on open hashing 00043 // * have O(1) contains, erase 00044 // 00045 // Maps have STL-like copying semantics, and properly initialize and destruct copies of objects 00046 // 00047 // There are two forms of map: coalesced and uncoalesced. Coalesced maps keep the entries in the 00048 // initial segment of an array, so are fast to iterate over; however deletion is approximately 00049 // twice as expensive. 00050 // 00051 // HashMap<T>: 00052 // bool insert(const Key& k, const Value& v) O(1) amortized (exponential resize policy) 00053 // Value & operator[](const Key& k) O(1) for existing objects, else O(1) amortized 00054 // const Entry * find(const Key& k); O(1) 00055 // bool erase(const T& k); O(1) 00056 // uint32_t size(); constant 00057 // void reserve(uint32_t size); O(MAX(currentOccupancy,size)) 00058 // void clear(); O(currentOccupancy) (with zero constant for objects 00059 // without 00060 // destructors) 00061 // Iterator getIterator(); 00062 // 00063 // operator[] creates an entry if one does not exist, initializing with the default constructor. 00064 // CoalescedHashMap<T> does not support getIterator, but instead supports 00065 // const Key *getEntries(); 00066 // 00067 // Use of iterators: 00068 // 00069 // for(HashMap::Iterator iter = test.getIterator(); !iter.done(); ++iter) 00070 // myFunction(iter->first, iter->second); 00071 00072 namespace physx 00073 { 00074 namespace shdfnd 00075 { 00076 template <class Key, class Value, class HashFn = Hash<Key>, class Allocator = NonTrackingAllocator> 00077 class HashMap : public internal::HashMapBase<Key, Value, HashFn, Allocator> 00078 { 00079 public: 00080 typedef internal::HashMapBase<Key, Value, HashFn, Allocator> HashMapBase; 00081 typedef typename HashMapBase::Iterator Iterator; 00082 00083 HashMap(uint32_t initialTableSize = 64, float loadFactor = 0.75f) : HashMapBase(initialTableSize, loadFactor) 00084 { 00085 } 00086 HashMap(uint32_t initialTableSize, float loadFactor, const Allocator& alloc) 00087 : HashMapBase(initialTableSize, loadFactor, alloc) 00088 { 00089 } 00090 HashMap(const Allocator& alloc) : HashMapBase(64, 0.75f, alloc) 00091 { 00092 } 00093 Iterator getIterator() 00094 { 00095 return Iterator(HashMapBase::mBase); 00096 } 00097 }; 00098 00099 template <class Key, class Value, class HashFn = Hash<Key>, class Allocator = NonTrackingAllocator> 00100 class CoalescedHashMap : public internal::HashMapBase<Key, Value, HashFn, Allocator> 00101 { 00102 public: 00103 typedef internal::HashMapBase<Key, Value, HashFn, Allocator> HashMapBase; 00104 00105 CoalescedHashMap(uint32_t initialTableSize = 64, float loadFactor = 0.75f) 00106 : HashMapBase(initialTableSize, loadFactor) 00107 { 00108 } 00109 const Pair<const Key, Value>* getEntries() const 00110 { 00111 return HashMapBase::mBase.getEntries(); 00112 } 00113 }; 00114 00115 } // namespace shdfnd 00116 } // namespace physx 00117 00118 #endif // #ifndef PSFOUNDATION_PSHASHMAP_H
Generated on Tue Jul 28 14:21:55 2015 for NVIDIA(R) PsFoundation Reference by
1.5.8