// Copyright (c) 2005, 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: Sanjay Ghemawat <opensource@google.com>

//

// A data structure used by the caching malloc.  It maps from page# to

// a pointer that contains info about that page.  We use two

// representations: one for 32-bit addresses, and another for 64 bit

// addresses.  Both representations provide the same interface.  The

// first representation is implemented as a flat array, the seconds as

// a three-level radix tree that strips away approximately 1/3rd of

// the bits every time.

//

// The BITS parameter should be the number of bits required to hold

// a page number.  E.g., with 32 bit pointers and 4K pages (i.e.,

// page offset fits in lower 12 bits), BITS == 20.

#ifndef TCMALLOC_PAGEMAP_H__

#define TCMALLOC_PAGEMAP_H__

#if HAVE(STDINT_H)

#include <stdint.h>

#elif HAVE(INTTYPES_H)

#include <inttypes.h>

#else

#include <sys/types.h>

#endif

#include <string.h>

#include "Assertions.h"

// Single-level array

template <int BITS>

class TCMalloc_PageMap1 {

 private:

  void** array_;

 public:

  typedef uintptr_t Number;

  void init(void* (*allocator)(size_t)) {

    array_ = reinterpret_cast<void**>((*allocator)(sizeof(void*) << BITS));

    memset(array_, 0, sizeof(void*) << BITS);

  }

  // Ensure that the map contains initialized entries "x .. x+n-1".

  // Returns true if successful, false if we could not allocate memory.

  bool Ensure(Number x, size_t n) {

    // Nothing to do since flat array was allocate at start

    return true;

  }

  void PreallocateMoreMemory() {}

  // REQUIRES "k" is in range "[0,2^BITS-1]".

  // REQUIRES "k" has been ensured before.

  //

  // Return the current value for KEY.  Returns "Value()" if not

  // yet set.

  void* get(Number k) const {

    return array_[k];

  }

  // REQUIRES "k" is in range "[0,2^BITS-1]".

  // REQUIRES "k" has been ensured before.

  //

  // Sets the value for KEY.

  void set(Number k, void* v) {

    array_[k] = v;

  }

};

// Two-level radix tree

template <int BITS>

class TCMalloc_PageMap2 {

 private:

  // Put 32 entries in the root and (2^BITS)/32 entries in each leaf.

  static const int ROOT_BITS = 5;

  static const int ROOT_LENGTH = 1 << ROOT_BITS;

  static const int LEAF_BITS = BITS - ROOT_BITS;

  static const int LEAF_LENGTH = 1 << LEAF_BITS;

  // Leaf node

  struct Leaf {

    void* values[LEAF_LENGTH];

  };

  Leaf* root_[ROOT_LENGTH];             // Pointers to 32 child nodes

  void* (*allocator_)(size_t);          // Memory allocator

 public:

  typedef uintptr_t Number;

  void init(void* (*allocator)(size_t)) {

    allocator_ = allocator;

    memset(root_, 0, sizeof(root_));

  }

  void* get(Number k) const {

    ASSERT(k >> BITS == 0);

    const Number i1 = k >> LEAF_BITS;

    const Number i2 = k & (LEAF_LENGTH-1);

    return root_[i1]->values[i2];

  }

  void set(Number k, void* v) {

    ASSERT(k >> BITS == 0);

    const Number i1 = k >> LEAF_BITS;

    const Number i2 = k & (LEAF_LENGTH-1);

    root_[i1]->values[i2] = v;

  }

  bool Ensure(Number start, size_t n) {

    for (Number key = start; key <= start + n - 1; ) {

      const Number i1 = key >> LEAF_BITS;

      // Make 2nd level node if necessary

      if (root_[i1] == NULL) {

        Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));

        if (leaf == NULL) return false;

        memset(leaf, 0, sizeof(*leaf));

        root_[i1] = leaf;

      }

      // Advance key past whatever is covered by this leaf node

      key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;

    }

    return true;

  }

  void PreallocateMoreMemory() {

    // Allocate enough to keep track of all possible pages

    Ensure(0, 1 << BITS);

  }

#ifdef WTF_CHANGES

  template<class Visitor, class MemoryReader>

  void visitValues(Visitor& visitor, const MemoryReader& reader)

  {

    for (int i = 0; i < ROOT_LENGTH; i++) {

      if (!root_[i])

        continue;

      Leaf* l = reader(reinterpret_cast<Leaf*>(root_[i]));

      for (int j = 0; j < LEAF_LENGTH; j += visitor.visit(l->values[j]))

        ;

    }

  }

  template<class Visitor, class MemoryReader>

  void visitAllocations(Visitor& visitor, const MemoryReader&) {

    for (int i = 0; i < ROOT_LENGTH; i++) {

      if (root_[i])

        visitor.visit(root_[i], sizeof(Leaf));

    }

  }

#endif

};

// Three-level radix tree

template <int BITS>

class TCMalloc_PageMap3 {

 private:

  // How many bits should we consume at each interior level

  static const int INTERIOR_BITS = (BITS + 2) / 3; // Round-up

  static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS;

  // How many bits should we consume at leaf level

  static const int LEAF_BITS = BITS - 2*INTERIOR_BITS;

  static const int LEAF_LENGTH = 1 << LEAF_BITS;

  // Interior node

  struct Node {

    Node* ptrs[INTERIOR_LENGTH];

  };

  // Leaf node

  struct Leaf {

    void* values[LEAF_LENGTH];

  };

  Node* root_;                          // Root of radix tree

  void* (*allocator_)(size_t);          // Memory allocator

  Node* NewNode() {

    Node* result = reinterpret_cast<Node*>((*allocator_)(sizeof(Node)));

    if (result != NULL) {

      memset(result, 0, sizeof(*result));

    }

    return result;

  }

 public:

  typedef uintptr_t Number;

  void init(void* (*allocator)(size_t)) {

    allocator_ = allocator;

    root_ = NewNode();

  }

  void* get(Number k) const {

    ASSERT(k >> BITS == 0);

    const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);

    const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1);

    const Number i3 = k & (LEAF_LENGTH-1);

    return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3];

  }

  void set(Number k, void* v) {

    ASSERT(k >> BITS == 0);

    const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);

    const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1);

    const Number i3 = k & (LEAF_LENGTH-1);

    reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v;

  }

  bool Ensure(Number start, size_t n) {

    for (Number key = start; key <= start + n - 1; ) {

      const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS);

      const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH-1);

      // Make 2nd level node if necessary

      if (root_->ptrs[i1] == NULL) {

        Node* n = NewNode();

        if (n == NULL) return false;

        root_->ptrs[i1] = n;

      }

      // Make leaf node if necessary

      if (root_->ptrs[i1]->ptrs[i2] == NULL) {

        Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));

        if (leaf == NULL) return false;

        memset(leaf, 0, sizeof(*leaf));

        root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf);

      }

      // Advance key past whatever is covered by this leaf node

      key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;

    }

    return true;

  }

  void PreallocateMoreMemory() {

  }

#ifdef WTF_CHANGES

  template<class Visitor, class MemoryReader>

  void visitValues(Visitor& visitor, const MemoryReader& reader) {

    Node* root = reader(root_);

    for (int i = 0; i < INTERIOR_LENGTH; i++) {

      if (!root->ptrs[i])

        continue;

      Node* n = reader(root->ptrs[i]);

      for (int j = 0; j < INTERIOR_LENGTH; j++) {

        if (!n->ptrs[j])

          continue;

        Leaf* l = reader(reinterpret_cast<Leaf*>(n->ptrs[j]));

        for (int k = 0; k < LEAF_LENGTH; k += visitor.visit(l->values[k]))

          ;

      }

    }

  }

  template<class Visitor, class MemoryReader>

  void visitAllocations(Visitor& visitor, const MemoryReader& reader) {

    visitor.visit(root_, sizeof(Node));

    Node* root = reader(root_);

    for (int i = 0; i < INTERIOR_LENGTH; i++) {

      if (!root->ptrs[i])

        continue;

      visitor.visit(root->ptrs[i], sizeof(Node));

      Node* n = reader(root->ptrs[i]);

      for (int j = 0; j < INTERIOR_LENGTH; j++) {

        if (!n->ptrs[j])

          continue;

        visitor.visit(n->ptrs[j], sizeof(Leaf));

      }

    }

  }

#endif

};

#endif  // TCMALLOC_PAGEMAP_H__