Move Source/WTF/wtf to Source/wtf

Source/WTF/wtf/TCPageMap.h

-// 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__
-
-#include <stdint.h>
-#include <string.h>
-#include <wtf/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, size_t) {
-    // 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__