Index: Source/WTF/wtf/TCPackedCache.h |
diff --git a/Source/WTF/wtf/TCPackedCache.h b/Source/WTF/wtf/TCPackedCache.h |
deleted file mode 100644 |
index 0464f8fdc2cf937f9c59ccfc489b34bd8ddccca5..0000000000000000000000000000000000000000 |
--- a/Source/WTF/wtf/TCPackedCache.h |
+++ /dev/null |
@@ -1,234 +0,0 @@ |
-// Copyright (c) 2007, Google Inc. |
-// All rights reserved. |
-// |
-// Redistribution and use in source and binary forms, with or without |
-// modification, are permitted provided that the following conditions are |
-// met: |
-// |
-// * Redistributions of source code must retain the above copyright |
-// notice, this list of conditions and the following disclaimer. |
-// * Redistributions in binary form must reproduce the above |
-// copyright notice, this list of conditions and the following disclaimer |
-// in the documentation and/or other materials provided with the |
-// distribution. |
-// * Neither the name of Google Inc. nor the names of its |
-// contributors may be used to endorse or promote products derived from |
-// this software without specific prior written permission. |
-// |
-// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
-// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
-// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
-// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
-// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
-// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
-// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
-// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
-// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
-// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
-// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
- |
-// --- |
-// Author: Geoff Pike |
-// |
-// This file provides a minimal cache that can hold a <key, value> pair |
-// with little if any wasted space. The types of the key and value |
-// must be unsigned integral types or at least have unsigned semantics |
-// for >>, casting, and similar operations. |
-// |
-// Synchronization is not provided. However, the cache is implemented |
-// as an array of cache entries whose type is chosen at compile time. |
-// If a[i] is atomic on your hardware for the chosen array type then |
-// raciness will not necessarily lead to bugginess. The cache entries |
-// must be large enough to hold a partial key and a value packed |
-// together. The partial keys are bit strings of length |
-// kKeybits - kHashbits, and the values are bit strings of length kValuebits. |
-// |
-// In an effort to use minimal space, every cache entry represents |
-// some <key, value> pair; the class provides no way to mark a cache |
-// entry as empty or uninitialized. In practice, you may want to have |
-// reserved keys or values to get around this limitation. For example, in |
-// tcmalloc's PageID-to-sizeclass cache, a value of 0 is used as |
-// "unknown sizeclass." |
-// |
-// Usage Considerations |
-// -------------------- |
-// |
-// kHashbits controls the size of the cache. The best value for |
-// kHashbits will of course depend on the application. Perhaps try |
-// tuning the value of kHashbits by measuring different values on your |
-// favorite benchmark. Also remember not to be a pig; other |
-// programs that need resources may suffer if you are. |
-// |
-// The main uses for this class will be when performance is |
-// critical and there's a convenient type to hold the cache's |
-// entries. As described above, the number of bits required |
-// for a cache entry is (kKeybits - kHashbits) + kValuebits. Suppose |
-// kKeybits + kValuebits is 43. Then it probably makes sense to |
-// chose kHashbits >= 11 so that cache entries fit in a uint32. |
-// |
-// On the other hand, suppose kKeybits = kValuebits = 64. Then |
-// using this class may be less worthwhile. You'll probably |
-// be using 128 bits for each entry anyway, so maybe just pick |
-// a hash function, H, and use an array indexed by H(key): |
-// void Put(K key, V value) { a_[H(key)] = pair<K, V>(key, value); } |
-// V GetOrDefault(K key, V default) { const pair<K, V> &p = a_[H(key)]; ... } |
-// etc. |
-// |
-// Further Details |
-// --------------- |
-// |
-// For caches used only by one thread, the following is true: |
-// 1. For a cache c, |
-// (c.Put(key, value), c.GetOrDefault(key, 0)) == value |
-// and |
-// (c.Put(key, value), <...>, c.GetOrDefault(key, 0)) == value |
-// if the elided code contains no c.Put calls. |
-// |
-// 2. Has(key) will return false if no <key, value> pair with that key |
-// has ever been Put. However, a newly initialized cache will have |
-// some <key, value> pairs already present. When you create a new |
-// cache, you must specify an "initial value." The initialization |
-// procedure is equivalent to Clear(initial_value), which is |
-// equivalent to Put(k, initial_value) for all keys k from 0 to |
-// 2^kHashbits - 1. |
-// |
-// 3. If key and key' differ then the only way Put(key, value) may |
-// cause Has(key') to change is that Has(key') may change from true to |
-// false. Furthermore, a Put() call that doesn't change Has(key') |
-// doesn't change GetOrDefault(key', ...) either. |
-// |
-// Implementation details: |
-// |
-// This is a direct-mapped cache with 2^kHashbits entries; |
-// the hash function simply takes the low bits of the key. |
-// So, we don't have to store the low bits of the key in the entries. |
-// Instead, an entry is the high bits of a key and a value, packed |
-// together. E.g., a 20 bit key and a 7 bit value only require |
-// a uint16 for each entry if kHashbits >= 11. |
-// |
-// Alternatives to this scheme will be added as needed. |
- |
-#ifndef TCMALLOC_PACKED_CACHE_INL_H__ |
-#define TCMALLOC_PACKED_CACHE_INL_H__ |
- |
-#ifndef WTF_CHANGES |
-#include "base/basictypes.h" // for COMPILE_ASSERT |
-#include "base/logging.h" // for DCHECK |
-#endif |
- |
-#ifndef DCHECK_EQ |
-#define DCHECK_EQ(val1, val2) ASSERT((val1) == (val2)) |
-#endif |
- |
-// A safe way of doing "(1 << n) - 1" -- without worrying about overflow |
-// Note this will all be resolved to a constant expression at compile-time |
-#define N_ONES_(IntType, N) \ |
- ( (N) == 0 ? 0 : ((static_cast<IntType>(1) << ((N)-1))-1 + \ |
- (static_cast<IntType>(1) << ((N)-1))) ) |
- |
-// The types K and V provide upper bounds on the number of valid keys |
-// and values, but we explicitly require the keys to be less than |
-// 2^kKeybits and the values to be less than 2^kValuebits. The size of |
-// the table is controlled by kHashbits, and the type of each entry in |
-// the cache is T. See also the big comment at the top of the file. |
-template <int kKeybits, typename T> |
-class PackedCache { |
- public: |
- typedef uintptr_t K; |
- typedef size_t V; |
- static const size_t kHashbits = 12; |
- static const size_t kValuebits = 8; |
- |
- explicit PackedCache(V initial_value) { |
- COMPILE_ASSERT(kKeybits <= sizeof(K) * 8, key_size); |
- COMPILE_ASSERT(kValuebits <= sizeof(V) * 8, value_size); |
- COMPILE_ASSERT(kHashbits <= kKeybits, hash_function); |
- COMPILE_ASSERT(kKeybits - kHashbits + kValuebits <= kTbits, |
- entry_size_must_be_big_enough); |
- Clear(initial_value); |
- } |
- |
- void Put(K key, V value) { |
- DCHECK_EQ(key, key & kKeyMask); |
- DCHECK_EQ(value, value & kValueMask); |
- array_[Hash(key)] = static_cast<T>(KeyToUpper(key) | value); |
- } |
- |
- bool Has(K key) const { |
- DCHECK_EQ(key, key & kKeyMask); |
- return KeyMatch(array_[Hash(key)], key); |
- } |
- |
- V GetOrDefault(K key, V default_value) const { |
- // As with other code in this class, we touch array_ as few times |
- // as we can. Assuming entries are read atomically (e.g., their |
- // type is uintptr_t on most hardware) then certain races are |
- // harmless. |
- DCHECK_EQ(key, key & kKeyMask); |
- T entry = array_[Hash(key)]; |
- return KeyMatch(entry, key) ? EntryToValue(entry) : default_value; |
- } |
- |
- void Clear(V value) { |
- DCHECK_EQ(value, value & kValueMask); |
- for (int i = 0; i < 1 << kHashbits; i++) { |
- array_[i] = static_cast<T>(value); |
- } |
- } |
- |
- private: |
- // We are going to pack a value and the upper part of a key into |
- // an entry of type T. The UPPER type is for the upper part of a key, |
- // after the key has been masked and shifted for inclusion in an entry. |
- typedef T UPPER; |
- |
- static V EntryToValue(T t) { return t & kValueMask; } |
- |
- static UPPER EntryToUpper(T t) { return t & kUpperMask; } |
- |
- // If v is a V and u is an UPPER then you can create an entry by |
- // doing u | v. kHashbits determines where in a K to find the upper |
- // part of the key, and kValuebits determines where in the entry to put |
- // it. |
- static UPPER KeyToUpper(K k) { |
- const int shift = kHashbits - kValuebits; |
- // Assume kHashbits >= kValuebits. It would be easy to lift this assumption. |
- return static_cast<T>(k >> shift) & kUpperMask; |
- } |
- |
- // This is roughly the inverse of KeyToUpper(). Some of the key has been |
- // thrown away, since KeyToUpper() masks off the low bits of the key. |
- static K UpperToPartialKey(UPPER u) { |
- DCHECK_EQ(u, u & kUpperMask); |
- const int shift = kHashbits - kValuebits; |
- // Assume kHashbits >= kValuebits. It would be easy to lift this assumption. |
- return static_cast<K>(u) << shift; |
- } |
- |
- static size_t Hash(K key) { |
- return static_cast<size_t>(key) & N_ONES_(size_t, kHashbits); |
- } |
- |
- // Does the entry's partial key match the relevant part of the given key? |
- static bool KeyMatch(T entry, K key) { |
- return ((KeyToUpper(key) ^ entry) & kUpperMask) == 0; |
- } |
- |
- static const size_t kTbits = 8 * sizeof(T); |
- static const int kUpperbits = kKeybits - kHashbits; |
- |
- // For masking a K. |
- static const K kKeyMask = N_ONES_(K, kKeybits); |
- |
- // For masking a T. |
- static const T kUpperMask = N_ONES_(T, kUpperbits) << kValuebits; |
- |
- // For masking a V or a T. |
- static const V kValueMask = N_ONES_(V, kValuebits); |
- |
- T array_[1 << kHashbits]; |
-}; |
- |
-#undef N_ONES_ |
- |
-#endif // TCMALLOC_PACKED_CACHE_INL_H__ |