--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/webengine/osswebengine/JavaScriptCore/wtf/TCPageMap.h Mon Mar 30 12:54:55 2009 +0300
@@ -0,0 +1,281 @@
+// 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 "config.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;
+ }
+
+ // 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;
+ }
+
+#ifdef WTF_CHANGES
+ template<class Visitor, class MemoryReader>
+ void visit(const 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]))
+ ;
+ }
+ }
+#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;
+ }
+
+#ifdef WTF_CHANGES
+ template<class Visitor, class MemoryReader>
+ void visit(const 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]))
+ ;
+ }
+ }
+ }
+#endif
+};
+
+#endif // TCMALLOC_PAGEMAP_H__