// 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__