src/third_party/WebKit/Source/WTF/wtf/TCPageMap.h - cobalt - Git at Google

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