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

third_party/tcmalloc/chromium/src/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
@@ skipping 83 matching lines @@
   void* get(Number k) const {
     if ((k >> BITS) > 0) {
       return NULL;
     }
     return array_[k];
   }
 
   // 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
 // Lazy commit, single-level array.
 // Very similar to PageMap1, except the page map is only committed as needed.
 // Since we don't return memory to the OS, the committed portion of the map will
 // only grow, and we'll only be called to Ensure when we really grow the heap.
 // We maintain a bit map to help us deduce if we've already committed a range
 // in our map.
 template <int BITS>
@@ skipping 164 matching lines @@
     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;
   }
+  // 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
 
 
 // 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;
@@ skipping 53 matching lines @@
       // 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);
   }
+
+  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
 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;
 
@@ skipping 74 matching lines @@
       }
 
       // Advance key past whatever is covered by this leaf node
       key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
     }
     return true;
   }
 
   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_