Merged third_party/tcmalloc/vendor/src(google-perftools r87) into...

third_party/tcmalloc/chromium/src/pagemap.h

Index: third_party/tcmalloc/chromium/src/pagemap.h
===================================================================
--- third_party/tcmalloc/chromium/src/pagemap.h	(revision 41942)
+++ third_party/tcmalloc/chromium/src/pagemap.h	(working copy)
@@ -101,10 +101,20 @@
   // REQUIRES "k" is in range "[0,2^BITS-1]".
   // REQUIRES "k" has been ensured before.
   //
-  // Sets the value for KEY.
+  // Sets the value 'v' for key 'k'.
   void set(Number k, void* v) {
     array_[k] = v;
   }
+
+  // Return the first non-NULL pointer found in this map for
+  // a page number >= k.  Returns NULL if no such number is found.
+  void* Next(Number k) const {
+    while (k < (1 << BITS)) {
+      if (array_[k] != NULL) return array_[k];
+      k++;
+    }
+    return NULL;
+  }
 };
 
 #ifdef WIN32
@@ -289,6 +299,15 @@
   void set(Number k, void* v) {
     array_[k] = v;
   }
+  // Return the first non-NULL pointer found in this map for
+  // a page number >= k.  Returns NULL if no such number is found.
+  void* Next(Number k) const {
+    while (k < (1 << BITS)) {
+      if (array_[k] != NULL) return array_[k];
+      k++;
+    }
+    return NULL;
+  }
 };
 #endif  // WIN32
 
@@ -362,6 +381,24 @@
     // Allocate enough to keep track of all possible pages
     Ensure(0, 1 << BITS);
   }
+
+  void* Next(Number k) const {
+    while (k < (1 << BITS)) {
+      const Number i1 = k >> LEAF_BITS;
+      Leaf* leaf = root_[i1];
+      if (leaf != NULL) {
+        // Scan forward in leaf
+        for (Number i2 = k & (LEAF_LENGTH - 1); i2 < LEAF_LENGTH; i2++) {
+          if (leaf->values[i2] != NULL) {
+            return leaf->values[i2];
+          }
+        }
+      }
+      // Skip to next top-level entry
+      k = (i1 + 1) << LEAF_BITS;
+    }
+    return NULL;
+  }
 };
 
 // Three-level radix tree
@@ -456,6 +493,29 @@
 
   void PreallocateMoreMemory() {
   }
+
+  void* Next(Number k) const {
+    while (k < (Number(1) << BITS)) {
+      const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
+      const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1);
+      if (root_->ptrs[i1] == NULL) {
+        // Advance to next top-level entry
+        k = (i1 + 1) << (LEAF_BITS + INTERIOR_BITS);
+      } else {
+        Leaf* leaf = reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2]);
+        if (leaf != NULL) {
+          for (Number i3 = (k & (LEAF_LENGTH-1)); i3 < LEAF_LENGTH; i3++) {
+            if (leaf->values[i3] != NULL) {
+              return leaf->values[i3];
+            }
+          }
+        }
+        // Advance to next interior entry
+        k = ((k >> LEAF_BITS) + 1) << LEAF_BITS;
+      }
+    }
+    return NULL;
+  }
 };
 
 #endif  // TCMALLOC_PAGEMAP_H_