| 124 | */ |
| 125 | template <typename Key> |
| 126 | static Key calculateKey(const Allocator &allocator, const size_t MAPPING_SIZE, |
| 127 | const Mapping *mapping) |
| 128 | { |
| 129 | const Key KEY_ZERO = 0; |
| 130 | const size_t KEY_BITS = size(KEY_ZERO); |
| 131 | const size_t UNIT_SIZE = MAPPING_SIZE / KEY_BITS; |
| 132 | const intptr_t BASE = mapping->base; |
| 133 | const intptr_t END = BASE + (ssize_t)MAPPING_SIZE; |
| 134 | const Key KEY_ONES = ~KEY_ZERO; |
| 135 | |
| 136 | Key key = 0; |
| 137 | auto i = mapping->i, iend = allocator.end(); |
| 138 | const Alloc *a = *i; |
| 139 | if (a->lb < BASE) |
| 140 | { |
| 141 | if (a->ub >= END) |
| 142 | return KEY_ONES; |
| 143 | size_t overlap = MAPPING_SIZE - (END - a->ub); |
| 144 | overlap = (overlap + UNIT_SIZE - 1) / UNIT_SIZE; |
| 145 | if (overlap >= KEY_BITS) |
| 146 | return KEY_ONES; |
| 147 | key = ~(KEY_ONES << overlap); |
| 148 | ++i; |
| 149 | } |
| 150 | |
| 151 | for (; i != iend; ++i) |
| 152 | { |
| 153 | a = *i; |
| 154 | assert(a->lb >= BASE); |
| 155 | if (a->lb >= END) |
| 156 | return key; |
| 157 | if (a->T == nullptr) |
| 158 | continue; |
| 159 | |
| 160 | size_t prologue = a->lb - BASE; |
| 161 | size_t postscript = (a->ub >= END? 0: END - a->ub); |
| 162 | |
| 163 | prologue = prologue / UNIT_SIZE; |
| 164 | postscript = postscript / UNIT_SIZE; |
| 165 | assert(prologue < KEY_BITS); |
| 166 | assert(postscript < KEY_BITS); |
| 167 | |
| 168 | Key tmp = (KEY_ONES << prologue); |
| 169 | tmp &= (KEY_ONES >> postscript); |
| 170 | key |= tmp; |
| 171 | } |
| 172 | |
| 173 | return key; |
| 174 | } |
| 175 | |
| 176 | /* |
| 177 | * Calculate the occupancy bounds of a mapping. |