OLD | NEW |
1 // Copyright (c) 2007, Google Inc. | 1 // Copyright (c) 2007, Google Inc. |
2 // All rights reserved. | 2 // All rights reserved. |
3 // | 3 // |
4 // Redistribution and use in source and binary forms, with or without | 4 // Redistribution and use in source and binary forms, with or without |
5 // modification, are permitted provided that the following conditions are | 5 // modification, are permitted provided that the following conditions are |
6 // met: | 6 // met: |
7 // | 7 // |
8 // * Redistributions of source code must retain the above copyright | 8 // * Redistributions of source code must retain the above copyright |
9 // notice, this list of conditions and the following disclaimer. | 9 // notice, this list of conditions and the following disclaimer. |
10 // * Redistributions in binary form must reproduce the above | 10 // * Redistributions in binary form must reproduce the above |
(...skipping 94 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
105 // entry is the high bits of a key and a value, packed together. | 105 // entry is the high bits of a key and a value, packed together. |
106 // E.g., a 20 bit key and a 7 bit value only require a uint16 for each | 106 // E.g., a 20 bit key and a 7 bit value only require a uint16 for each |
107 // entry if kHashbits >= 11. | 107 // entry if kHashbits >= 11. |
108 // | 108 // |
109 // Alternatives to this scheme will be added as needed. | 109 // Alternatives to this scheme will be added as needed. |
110 | 110 |
111 #ifndef TCMALLOC_PACKED_CACHE_INL_H_ | 111 #ifndef TCMALLOC_PACKED_CACHE_INL_H_ |
112 #define TCMALLOC_PACKED_CACHE_INL_H_ | 112 #define TCMALLOC_PACKED_CACHE_INL_H_ |
113 | 113 |
114 #include "config.h" | 114 #include "config.h" |
| 115 #include <stddef.h> // for size_t |
115 #ifdef HAVE_STDINT_H | 116 #ifdef HAVE_STDINT_H |
116 #include <stdint.h> | 117 #include <stdint.h> // for uintptr_t |
117 #endif | 118 #endif |
118 #include "base/basictypes.h" // for COMPILE_ASSERT | 119 #include "base/basictypes.h" |
119 #include "internal_logging.h" | 120 #include "internal_logging.h" |
120 | 121 |
121 // A safe way of doing "(1 << n) - 1" -- without worrying about overflow | 122 // A safe way of doing "(1 << n) - 1" -- without worrying about overflow |
122 // Note this will all be resolved to a constant expression at compile-time | 123 // Note this will all be resolved to a constant expression at compile-time |
123 #define N_ONES_(IntType, N) \ | 124 #define N_ONES_(IntType, N) \ |
124 ( (N) == 0 ? 0 : ((static_cast<IntType>(1) << ((N)-1))-1 + \ | 125 ( (N) == 0 ? 0 : ((static_cast<IntType>(1) << ((N)-1))-1 + \ |
125 (static_cast<IntType>(1) << ((N)-1))) ) | 126 (static_cast<IntType>(1) << ((N)-1))) ) |
126 | 127 |
127 // The types K and V provide upper bounds on the number of valid keys | 128 // The types K and V provide upper bounds on the number of valid keys |
128 // and values, but we explicitly require the keys to be less than | 129 // and values, but we explicitly require the keys to be less than |
129 // 2^kKeybits and the values to be less than 2^kValuebits. The size of | 130 // 2^kKeybits and the values to be less than 2^kValuebits. The size of |
130 // the table is controlled by kHashbits, and the type of each entry in | 131 // the table is controlled by kHashbits, and the type of each entry in |
131 // the cache is T. See also the big comment at the top of the file. | 132 // the cache is T. See also the big comment at the top of the file. |
132 template <int kKeybits, typename T> | 133 template <int kKeybits, typename T> |
133 class PackedCache { | 134 class PackedCache { |
134 public: | 135 public: |
135 typedef uintptr_t K; | 136 typedef uintptr_t K; |
136 typedef size_t V; | 137 typedef size_t V; |
| 138 #ifdef TCMALLOC_SMALL_BUT_SLOW |
| 139 // Decrease the size map cache if running in the small memory mode. |
137 static const int kHashbits = 12; | 140 static const int kHashbits = 12; |
| 141 #else |
| 142 static const int kHashbits = 16; |
| 143 #endif |
138 static const int kValuebits = 7; | 144 static const int kValuebits = 7; |
139 static const bool kUseWholeKeys = kKeybits + kValuebits <= 8 * sizeof(T); | 145 static const bool kUseWholeKeys = kKeybits + kValuebits <= 8 * sizeof(T); |
140 | 146 |
141 explicit PackedCache(V initial_value) { | 147 explicit PackedCache(V initial_value) { |
142 COMPILE_ASSERT(kKeybits <= sizeof(K) * 8, key_size); | 148 COMPILE_ASSERT(kKeybits <= sizeof(K) * 8, key_size); |
143 COMPILE_ASSERT(kValuebits <= sizeof(V) * 8, value_size); | 149 COMPILE_ASSERT(kValuebits <= sizeof(V) * 8, value_size); |
144 COMPILE_ASSERT(kHashbits <= kKeybits, hash_function); | 150 COMPILE_ASSERT(kHashbits <= kKeybits, hash_function); |
145 COMPILE_ASSERT(kKeybits - kHashbits + kValuebits <= kTbits, | 151 COMPILE_ASSERT(kKeybits - kHashbits + kValuebits <= kTbits, |
146 entry_size_must_be_big_enough); | 152 entry_size_must_be_big_enough); |
147 Clear(initial_value); | 153 Clear(initial_value); |
(...skipping 75 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
223 static const V kValueMask = N_ONES_(V, kValuebits); | 229 static const V kValueMask = N_ONES_(V, kValuebits); |
224 | 230 |
225 // array_ is the cache. Its elements are volatile because any | 231 // array_ is the cache. Its elements are volatile because any |
226 // thread can write any array element at any time. | 232 // thread can write any array element at any time. |
227 volatile T array_[1 << kHashbits]; | 233 volatile T array_[1 << kHashbits]; |
228 }; | 234 }; |
229 | 235 |
230 #undef N_ONES_ | 236 #undef N_ONES_ |
231 | 237 |
232 #endif // TCMALLOC_PACKED_CACHE_INL_H_ | 238 #endif // TCMALLOC_PACKED_CACHE_INL_H_ |
OLD | NEW |