15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2007, Google Inc. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// All rights reserved. 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Redistribution and use in source and binary forms, with or without 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// modification, are permitted provided that the following conditions are 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// met: 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Redistributions of source code must retain the above copyright 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// notice, this list of conditions and the following disclaimer. 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Redistributions in binary form must reproduce the above 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// copyright notice, this list of conditions and the following disclaimer 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in the documentation and/or other materials provided with the 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// distribution. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Neither the name of Google Inc. nor the names of its 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// contributors may be used to endorse or promote products derived from 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// this software without specific prior written permission. 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// --- 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Author: Geoff Pike 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file provides a minimal cache that can hold a <key, value> pair 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// with little if any wasted space. The types of the key and value 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// must be unsigned integral types or at least have unsigned semantics 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// for >>, casting, and similar operations. 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Synchronization is not provided. However, the cache is implemented 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// as an array of cache entries whose type is chosen at compile time. 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// If a[i] is atomic on your hardware for the chosen array type then 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// raciness will not necessarily lead to bugginess. The cache entries 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// must be large enough to hold a partial key and a value packed 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// together. The partial keys are bit strings of length 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// kKeybits - kHashbits, and the values are bit strings of length kValuebits. 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// In an effort to use minimal space, every cache entry represents 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// some <key, value> pair; the class provides no way to mark a cache 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// entry as empty or uninitialized. In practice, you may want to have 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// reserved keys or values to get around this limitation. For example, in 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// tcmalloc's PageID-to-sizeclass cache, a value of 0 is used as 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// "unknown sizeclass." 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Usage Considerations 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// -------------------- 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// kHashbits controls the size of the cache. The best value for 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// kHashbits will of course depend on the application. Perhaps try 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// tuning the value of kHashbits by measuring different values on your 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// favorite benchmark. Also remember not to be a pig; other 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// programs that need resources may suffer if you are. 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The main uses for this class will be when performance is 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// critical and there's a convenient type to hold the cache's 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// entries. As described above, the number of bits required 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// for a cache entry is (kKeybits - kHashbits) + kValuebits. Suppose 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// kKeybits + kValuebits is 43. Then it probably makes sense to 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// chose kHashbits >= 11 so that cache entries fit in a uint32. 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// On the other hand, suppose kKeybits = kValuebits = 64. Then 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// using this class may be less worthwhile. You'll probably 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// be using 128 bits for each entry anyway, so maybe just pick 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// a hash function, H, and use an array indexed by H(key): 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// void Put(K key, V value) { a_[H(key)] = pair<K, V>(key, value); } 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// V GetOrDefault(K key, V default) { const pair<K, V> &p = a_[H(key)]; ... } 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// etc. 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Further Details 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// --------------- 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// For caches used only by one thread, the following is true: 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 1. For a cache c, 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (c.Put(key, value), c.GetOrDefault(key, 0)) == value 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// and 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (c.Put(key, value), <...>, c.GetOrDefault(key, 0)) == value 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// if the elided code contains no c.Put calls. 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 2. Has(key) will return false if no <key, value> pair with that key 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// has ever been Put. However, a newly initialized cache will have 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// some <key, value> pairs already present. When you create a new 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// cache, you must specify an "initial value." The initialization 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// procedure is equivalent to Clear(initial_value), which is 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// equivalent to Put(k, initial_value) for all keys k from 0 to 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 2^kHashbits - 1. 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 3. If key and key' differ then the only way Put(key, value) may 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// cause Has(key') to change is that Has(key') may change from true to 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// false. Furthermore, a Put() call that doesn't change Has(key') 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// doesn't change GetOrDefault(key', ...) either. 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Implementation details: 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This is a direct-mapped cache with 2^kHashbits entries; the hash 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// function simply takes the low bits of the key. We store whole keys 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// if a whole key plus a whole value fits in an entry. Otherwise, an 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// entry is the high bits of a key and a value, packed together. 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// E.g., a 20 bit key and a 7 bit value only require a uint16 for each 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// entry if kHashbits >= 11. 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Alternatives to this scheme will be added as needed. 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef TCMALLOC_PACKED_CACHE_INL_H_ 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define TCMALLOC_PACKED_CACHE_INL_H_ 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "config.h" 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stddef.h> // for size_t 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef HAVE_STDINT_H 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdint.h> // for uintptr_t 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/basictypes.h" 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "internal_logging.h" 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A safe way of doing "(1 << n) - 1" -- without worrying about overflow 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Note this will all be resolved to a constant expression at compile-time 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define N_ONES_(IntType, N) \ 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ( (N) == 0 ? 0 : ((static_cast<IntType>(1) << ((N)-1))-1 + \ 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (static_cast<IntType>(1) << ((N)-1))) ) 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The types K and V provide upper bounds on the number of valid keys 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// and values, but we explicitly require the keys to be less than 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 2^kKeybits and the values to be less than 2^kValuebits. The size of 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the table is controlled by kHashbits, and the type of each entry in 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the cache is T. See also the big comment at the top of the file. 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <int kKeybits, typename T> 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class PackedCache { 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef uintptr_t K; 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef size_t V; 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef TCMALLOC_SMALL_BUT_SLOW 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Decrease the size map cache if running in the small memory mode. 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kHashbits = 12; 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kHashbits = 16; 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kValuebits = 7; 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const bool kUseWholeKeys = kKeybits + kValuebits <= 8 * sizeof(T); 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit PackedCache(V initial_value) { 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) COMPILE_ASSERT(kKeybits <= sizeof(K) * 8, key_size); 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) COMPILE_ASSERT(kValuebits <= sizeof(V) * 8, value_size); 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) COMPILE_ASSERT(kHashbits <= kKeybits, hash_function); 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) COMPILE_ASSERT(kKeybits - kHashbits + kValuebits <= kTbits, 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) entry_size_must_be_big_enough); 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Clear(initial_value); 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Put(K key, V value) { 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(key == (key & kKeyMask)); 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(value == (value & kValueMask)); 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) array_[Hash(key)] = KeyToUpper(key) | value; 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool Has(K key) const { 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(key == (key & kKeyMask)); 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return KeyMatch(array_[Hash(key)], key); 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) V GetOrDefault(K key, V default_value) const { 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // As with other code in this class, we touch array_ as few times 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // as we can. Assuming entries are read atomically (e.g., their 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // type is uintptr_t on most hardware) then certain races are 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // harmless. 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(key == (key & kKeyMask)); 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) T entry = array_[Hash(key)]; 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return KeyMatch(entry, key) ? EntryToValue(entry) : default_value; 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Clear(V value) { 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(value == (value & kValueMask)); 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < 1 << kHashbits; i++) { 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(kUseWholeKeys || KeyToUpper(i) == 0); 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) array_[i] = kUseWholeKeys ? (value | KeyToUpper(i)) : value; 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We are going to pack a value and the upper part of a key (or a 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // whole key) into an entry of type T. The UPPER type is for the 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // upper part of a key, after the key has been masked and shifted 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // for inclusion in an entry. 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef T UPPER; 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static V EntryToValue(T t) { return t & kValueMask; } 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If we have space for a whole key, we just shift it left. 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Otherwise kHashbits determines where in a K to find the upper 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // part of the key, and kValuebits determines where in the entry to 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // put it. 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static UPPER KeyToUpper(K k) { 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (kUseWholeKeys) { 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return static_cast<T>(k) << kValuebits; 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int shift = kHashbits - kValuebits; 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Assume kHashbits >= kValuebits. It'd be easy to lift this assumption. 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return static_cast<T>(k >> shift) & kUpperMask; 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static size_t Hash(K key) { 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return static_cast<size_t>(key) & N_ONES_(size_t, kHashbits); 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Does the entry match the relevant part of the given key? 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static bool KeyMatch(T entry, K key) { 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return kUseWholeKeys ? 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (entry >> kValuebits == key) : 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ((KeyToUpper(key) ^ entry) & kUpperMask) == 0; 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kTbits = 8 * sizeof(T); 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kUpperbits = kUseWholeKeys ? kKeybits : kKeybits - kHashbits; 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // For masking a K. 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const K kKeyMask = N_ONES_(K, kKeybits); 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // For masking a T. 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const T kUpperMask = N_ONES_(T, kUpperbits) << kValuebits; 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // For masking a V or a T. 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const V kValueMask = N_ONES_(V, kValuebits); 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // array_ is the cache. Its elements are volatile because any 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // thread can write any array element at any time. 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) volatile T array_[1 << kHashbits]; 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#undef N_ONES_ 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // TCMALLOC_PACKED_CACHE_INL_H_ 239