00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045 #ifndef TCMALLOC_PAGEMAP_H__
00046 #define TCMALLOC_PAGEMAP_H__
00047
00048 #include "config.h"
00049 #if defined HAVE_STDINT_H
00050 #include <stdint.h>
00051 #elif defined HAVE_INTTYPES_H
00052 #include <inttypes.h>
00053 #else
00054 #include <sys/types.h>
00055 #endif
00056 #include "internal_logging.h"
00057
00058
00059 template <int BITS>
00060 class TCMalloc_PageMap1 {
00061 private:
00062 void** array_;
00063
00064 public:
00065 typedef uintptr_t Number;
00066
00067 explicit TCMalloc_PageMap1(void* (*allocator)(size_t)) {
00068 array_ = reinterpret_cast<void**>((*allocator)(sizeof(void*) << BITS));
00069 memset(array_, 0, sizeof(void*) << BITS);
00070 }
00071
00072
00073
00074 bool Ensure(Number x, size_t n) {
00075
00076 return true;
00077 }
00078
00079 void PreallocateMoreMemory() {}
00080
00081
00082
00083
00084
00085
00086 void* get(Number k) const {
00087 return array_[k];
00088 }
00089
00090
00091
00092
00093
00094 void set(Number k, void* v) {
00095 array_[k] = v;
00096 }
00097 };
00098
00099
00100 template <int BITS>
00101 class TCMalloc_PageMap2 {
00102 private:
00103
00104 static const int ROOT_BITS = 5;
00105 static const int ROOT_LENGTH = 1 << ROOT_BITS;
00106
00107 static const int LEAF_BITS = BITS - ROOT_BITS;
00108 static const int LEAF_LENGTH = 1 << LEAF_BITS;
00109
00110
00111 struct Leaf {
00112 void* values[LEAF_LENGTH];
00113 };
00114
00115 Leaf* root_[ROOT_LENGTH];
00116 void* (*allocator_)(size_t);
00117
00118 public:
00119 typedef uintptr_t Number;
00120
00121 explicit TCMalloc_PageMap2(void* (*allocator)(size_t)) {
00122 allocator_ = allocator;
00123 memset(root_, 0, sizeof(root_));
00124 }
00125
00126 void* get(Number k) const {
00127 ASSERT(k >> BITS == 0);
00128 const Number i1 = k >> LEAF_BITS;
00129 const Number i2 = k & (LEAF_LENGTH-1);
00130 return root_[i1]->values[i2];
00131 }
00132
00133 void set(Number k, void* v) {
00134 ASSERT(k >> BITS == 0);
00135 const Number i1 = k >> LEAF_BITS;
00136 const Number i2 = k & (LEAF_LENGTH-1);
00137 root_[i1]->values[i2] = v;
00138 }
00139
00140 bool Ensure(Number start, size_t n) {
00141 for (Number key = start; key <= start + n - 1; ) {
00142 const Number i1 = key >> LEAF_BITS;
00143
00144
00145 if (root_[i1] == NULL) {
00146 Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));
00147 if (leaf == NULL) return false;
00148 memset(leaf, 0, sizeof(*leaf));
00149 root_[i1] = leaf;
00150 }
00151
00152
00153 key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
00154 }
00155 return true;
00156 }
00157
00158 void PreallocateMoreMemory() {
00159
00160 Ensure(0, 1 << BITS);
00161 }
00162 };
00163
00164
00165 template <int BITS>
00166 class TCMalloc_PageMap3 {
00167 private:
00168
00169 static const int INTERIOR_BITS = (BITS + 2) / 3;
00170 static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS;
00171
00172
00173 static const int LEAF_BITS = BITS - 2*INTERIOR_BITS;
00174 static const int LEAF_LENGTH = 1 << LEAF_BITS;
00175
00176
00177 struct Node {
00178 Node* ptrs[INTERIOR_LENGTH];
00179 };
00180
00181
00182 struct Leaf {
00183 void* values[LEAF_LENGTH];
00184 };
00185
00186 Node* root_;
00187 void* (*allocator_)(size_t);
00188
00189 Node* NewNode() {
00190 Node* result = reinterpret_cast<Node*>((*allocator_)(sizeof(Node)));
00191 if (result != NULL) {
00192 memset(result, 0, sizeof(*result));
00193 }
00194 return result;
00195 }
00196
00197 public:
00198 typedef uintptr_t Number;
00199
00200 explicit TCMalloc_PageMap3(void* (*allocator)(size_t)) {
00201 allocator_ = allocator;
00202 root_ = NewNode();
00203 }
00204
00205 void* get(Number k) const {
00206 ASSERT(k >> BITS == 0);
00207 const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
00208 const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1);
00209 const Number i3 = k & (LEAF_LENGTH-1);
00210 return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3];
00211 }
00212
00213 void set(Number k, void* v) {
00214 ASSERT(k >> BITS == 0);
00215 const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
00216 const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1);
00217 const Number i3 = k & (LEAF_LENGTH-1);
00218 reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v;
00219 }
00220
00221 bool Ensure(Number start, size_t n) {
00222 for (Number key = start; key <= start + n - 1; ) {
00223 const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS);
00224 const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH-1);
00225
00226
00227 if (root_->ptrs[i1] == NULL) {
00228 Node* n = NewNode();
00229 if (n == NULL) return false;
00230 root_->ptrs[i1] = n;
00231 }
00232
00233
00234 if (root_->ptrs[i1]->ptrs[i2] == NULL) {
00235 Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));
00236 if (leaf == NULL) return false;
00237 memset(leaf, 0, sizeof(*leaf));
00238 root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf);
00239 }
00240
00241
00242 key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
00243 }
00244 return true;
00245 }
00246
00247 void PreallocateMoreMemory() {
00248 }
00249 };
00250
00251 #endif // TCMALLOC_PAGEMAP_H__