| 1 |
// Copyright (c) 2018 Kenton Varda and contributors |
| 2 |
// Licensed under the MIT License: |
| 3 |
// |
| 4 |
// Permission is hereby granted, free of charge, to any person obtaining a copy |
| 5 |
// of this software and associated documentation files (the "Software"), to deal |
| 6 |
// in the Software without restriction, including without limitation the rights |
| 7 |
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
| 8 |
// copies of the Software, and to permit persons to whom the Software is |
| 9 |
// furnished to do so, subject to the following conditions: |
| 10 |
// |
| 11 |
// The above copyright notice and this permission notice shall be included in |
| 12 |
// all copies or substantial portions of the Software. |
| 13 |
// |
| 14 |
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 15 |
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| 16 |
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
| 17 |
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| 18 |
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
| 19 |
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN |
| 20 |
// THE SOFTWARE. |
| 21 |
|
| 22 |
#include "table.h" |
| 23 |
#include "debug.h" |
| 24 |
#include <stdlib.h> |
| 25 |
|
| 26 |
#if KJ_DEBUG_TABLE_IMPL |
| 27 |
#undef KJ_DASSERT |
| 28 |
#define KJ_DASSERT KJ_ASSERT |
| 29 |
#endif |
| 30 |
|
| 31 |
namespace kj { |
| 32 |
namespace _ { |
| 33 |
|
| 34 |
static inline uint lg(uint value) { |
| 35 |
// Compute floor(log2(value)). |
| 36 |
// |
| 37 |
// Undefined for value = 0. |
| 38 |
#if _MSC_VER && !defined(__clang__) |
| 39 |
unsigned long i; |
| 40 |
auto found = _BitScanReverse(&i, value); |
| 41 |
KJ_DASSERT(found); // !found means value = 0 |
| 42 |
return i; |
| 43 |
#else |
| 44 |
return sizeof(uint) * 8 - 1 - __builtin_clz(value); |
| 45 |
#endif |
| 46 |
} |
| 47 |
|
| 48 |
void throwDuplicateTableRow() { |
| 49 |
KJ_FAIL_REQUIRE("inserted row already exists in table"); |
| 50 |
} |
| 51 |
|
| 52 |
void logHashTableInconsistency() { |
| 53 |
KJ_LOG(ERROR, |
| 54 |
"HashIndex detected hash table inconsistency. This can happen if you create a kj::Table " |
| 55 |
"with a hash index and you modify the rows in the table post-indexing in a way that would " |
| 56 |
"change their hash. This is a serious bug which will lead to undefined behavior." |
| 57 |
"\nstack: ", kj::getStackTrace()); |
| 58 |
} |
| 59 |
|
| 60 |
// List of primes where each element is roughly double the previous. Obtained |
| 61 |
// from: |
| 62 |
// http://planetmath.org/goodhashtableprimes |
| 63 |
// Primes < 53 were added to ensure that small tables don't allocate excessive memory. |
| 64 |
static const size_t PRIMES[] = { |
| 65 |
1, // 2^ 0 = 1 |
| 66 |
3, // 2^ 1 = 2 |
| 67 |
5, // 2^ 2 = 4 |
| 68 |
11, // 2^ 3 = 8 |
| 69 |
23, // 2^ 4 = 16 |
| 70 |
53, // 2^ 5 = 32 |
| 71 |
97, // 2^ 6 = 64 |
| 72 |
193, // 2^ 7 = 128 |
| 73 |
389, // 2^ 8 = 256 |
| 74 |
769, // 2^ 9 = 512 |
| 75 |
1543, // 2^10 = 1024 |
| 76 |
3079, // 2^11 = 2048 |
| 77 |
6151, // 2^12 = 4096 |
| 78 |
12289, // 2^13 = 8192 |
| 79 |
24593, // 2^14 = 16384 |
| 80 |
49157, // 2^15 = 32768 |
| 81 |
98317, // 2^16 = 65536 |
| 82 |
196613, // 2^17 = 131072 |
| 83 |
393241, // 2^18 = 262144 |
| 84 |
786433, // 2^19 = 524288 |
| 85 |
1572869, // 2^20 = 1048576 |
| 86 |
3145739, // 2^21 = 2097152 |
| 87 |
6291469, // 2^22 = 4194304 |
| 88 |
12582917, // 2^23 = 8388608 |
| 89 |
25165843, // 2^24 = 16777216 |
| 90 |
50331653, // 2^25 = 33554432 |
| 91 |
100663319, // 2^26 = 67108864 |
| 92 |
201326611, // 2^27 = 134217728 |
| 93 |
402653189, // 2^28 = 268435456 |
| 94 |
805306457, // 2^29 = 536870912 |
| 95 |
1610612741, // 2^30 = 1073741824 |
| 96 |
}; |
| 97 |
|
| 98 |
uint chooseBucket(uint hash, uint count) { |
| 99 |
// Integer modulus is really, really slow. It turns out that the compiler can generate much |
| 100 |
// faster code if the denominator is a constant. Since we have a fixed set of possible |
| 101 |
// denominators, a big old switch() statement is a win. |
| 102 |
|
| 103 |
// TODO(perf): Consider using power-of-two bucket sizes. We can safely do so as long as we demand |
| 104 |
// high-quality hash functions -- kj::hashCode() needs good diffusion even for integers, can't |
| 105 |
// just be a cast. Also be sure to implement Robin Hood hashing to avoid extremely bad negative |
| 106 |
// lookup time when elements have sequential hashes (otherwise, it could be necessary to scan |
| 107 |
// the entire list to determine that an element isn't present). |
| 108 |
|
| 109 |
switch (count) { |
| 110 |
#define HANDLE(i) case i##u: return hash % i##u |
| 111 |
HANDLE( 1); |
| 112 |
HANDLE( 3); |
| 113 |
HANDLE( 5); |
| 114 |
HANDLE( 11); |
| 115 |
HANDLE( 23); |
| 116 |
HANDLE( 53); |
| 117 |
HANDLE( 97); |
| 118 |
HANDLE( 193); |
| 119 |
HANDLE( 389); |
| 120 |
HANDLE( 769); |
| 121 |
HANDLE( 1543); |
| 122 |
HANDLE( 3079); |
| 123 |
HANDLE( 6151); |
| 124 |
HANDLE( 12289); |
| 125 |
HANDLE( 24593); |
| 126 |
HANDLE( 49157); |
| 127 |
HANDLE( 98317); |
| 128 |
HANDLE( 196613); |
| 129 |
HANDLE( 393241); |
| 130 |
HANDLE( 786433); |
| 131 |
HANDLE( 1572869); |
| 132 |
HANDLE( 3145739); |
| 133 |
HANDLE( 6291469); |
| 134 |
HANDLE( 12582917); |
| 135 |
HANDLE( 25165843); |
| 136 |
HANDLE( 50331653); |
| 137 |
HANDLE( 100663319); |
| 138 |
HANDLE( 201326611); |
| 139 |
HANDLE( 402653189); |
| 140 |
HANDLE( 805306457); |
| 141 |
HANDLE(1610612741); |
| 142 |
#undef HANDLE |
| 143 |
default: return hash % count; |
| 144 |
} |
| 145 |
} |
| 146 |
|
| 147 |
size_t chooseHashTableSize(uint size) { |
| 148 |
if (size == 0) return 0; |
| 149 |
|
| 150 |
// Add 1 to compensate for the floor() above, then look up the best prime bucket size for that |
| 151 |
// target size. |
| 152 |
return PRIMES[lg(size) + 1]; |
| 153 |
} |
| 154 |
|
| 155 |
kj::Array<HashBucket> rehash(kj::ArrayPtr<const HashBucket> oldBuckets, size_t targetSize) { |
| 156 |
// Rehash the whole table. |
| 157 |
|
| 158 |
KJ_REQUIRE(targetSize < (1 << 30), "hash table has reached maximum size"); |
| 159 |
|
| 160 |
size_t size = chooseHashTableSize(targetSize); |
| 161 |
|
| 162 |
if (size < oldBuckets.size()) { |
| 163 |
size = oldBuckets.size(); |
| 164 |
} |
| 165 |
|
| 166 |
auto newBuckets = kj::heapArray<HashBucket>(size); |
| 167 |
memset(newBuckets.begin(), 0, sizeof(HashBucket) * size); |
| 168 |
|
| 169 |
uint entryCount = 0; |
| 170 |
uint collisionCount = 0; |
| 171 |
|
| 172 |
for (auto& oldBucket: oldBuckets) { |
| 173 |
if (oldBucket.isOccupied()) { |
| 174 |
++entryCount; |
| 175 |
for (uint i = oldBucket.hash % newBuckets.size();; i = probeHash(newBuckets, i)) { |
| 176 |
auto& newBucket = newBuckets[i]; |
| 177 |
if (newBucket.isEmpty()) { |
| 178 |
newBucket = oldBucket; |
| 179 |
break; |
| 180 |
} |
| 181 |
++collisionCount; |
| 182 |
} |
| 183 |
} |
| 184 |
} |
| 185 |
|
| 186 |
if (collisionCount > 16 + entryCount * 4) { |
| 187 |
static bool warned = false; |
| 188 |
if (!warned) { |
| 189 |
KJ_LOG(WARNING, "detected excessive collisions in hash table; is your hash function OK?", |
| 190 |
entryCount, collisionCount, kj::getStackTrace()); |
| 191 |
warned = true; |
| 192 |
} |
| 193 |
} |
| 194 |
|
| 195 |
return newBuckets; |
| 196 |
} |
| 197 |
|
| 198 |
// ======================================================================================= |
| 199 |
// BTree |
| 200 |
|
| 201 |
#if _WIN32 |
| 202 |
#define aligned_free _aligned_free |
| 203 |
#else |
| 204 |
#define aligned_free ::free |
| 205 |
#endif |
| 206 |
|
| 207 |
BTreeImpl::BTreeImpl() |
| 208 |
: tree(const_cast<NodeUnion*>(&EMPTY_NODE)), |
| 209 |
treeCapacity(1), |
| 210 |
height(0), |
| 211 |
freelistHead(1), |
| 212 |
freelistSize(0), |
| 213 |
beginLeaf(0), |
| 214 |
endLeaf(0) {} |
| 215 |
|
| 216 |
BTreeImpl::~BTreeImpl() noexcept(false) { |
| 217 |
if (tree != &EMPTY_NODE) { |
| 218 |
aligned_free(tree); |
| 219 |
} |
| 220 |
} |
| 221 |
|
| 222 |
BTreeImpl::BTreeImpl(BTreeImpl&& other) |
| 223 |
: BTreeImpl() { |
| 224 |
*this = kj::mv(other); |
| 225 |
} |
| 226 |
|
| 227 |
BTreeImpl& BTreeImpl::operator=(BTreeImpl&& other) { |
| 228 |
KJ_DASSERT(&other != this); |
| 229 |
|
| 230 |
if (tree != &EMPTY_NODE) { |
| 231 |
aligned_free(tree); |
| 232 |
} |
| 233 |
tree = other.tree; |
| 234 |
treeCapacity = other.treeCapacity; |
| 235 |
height = other.height; |
| 236 |
freelistHead = other.freelistHead; |
| 237 |
freelistSize = other.freelistSize; |
| 238 |
beginLeaf = other.beginLeaf; |
| 239 |
endLeaf = other.endLeaf; |
| 240 |
|
| 241 |
other.tree = const_cast<NodeUnion*>(&EMPTY_NODE); |
| 242 |
other.treeCapacity = 1; |
| 243 |
other.height = 0; |
| 244 |
other.freelistHead = 1; |
| 245 |
other.freelistSize = 0; |
| 246 |
other.beginLeaf = 0; |
| 247 |
other.endLeaf = 0; |
| 248 |
|
| 249 |
return *this; |
| 250 |
} |
| 251 |
|
| 252 |
const BTreeImpl::NodeUnion BTreeImpl::EMPTY_NODE = {{{0, {0}}}}; |
| 253 |
|
| 254 |
void BTreeImpl::verify(size_t size, FunctionParam<bool(uint, uint)> f) { |
| 255 |
KJ_ASSERT(verifyNode(size, f, 0, height, nullptr) == size); |
| 256 |
} |
| 257 |
size_t BTreeImpl::verifyNode(size_t size, FunctionParam<bool(uint, uint)>& f, |
| 258 |
uint pos, uint height, MaybeUint maxRow) { |
| 259 |
if (height > 0) { |
| 260 |
auto& parent = tree[pos].parent; |
| 261 |
|
| 262 |
auto n = parent.keyCount(); |
| 263 |
size_t total = 0; |
| 264 |
for (auto i: kj::zeroTo(n)) { |
| 265 |
KJ_ASSERT(*parent.keys[i] < size, n, i); |
| 266 |
total += verifyNode(size, f, parent.children[i], height - 1, parent.keys[i]); |
| 267 |
if (i > 0) { |
| 268 |
KJ_ASSERT(f(*parent.keys[i - 1], *parent.keys[i]), |
| 269 |
n, i, parent.keys[i - 1], parent.keys[i]); |
| 270 |
} |
| 271 |
} |
| 272 |
total += verifyNode(size, f, parent.children[n], height - 1, maxRow); |
| 273 |
if (maxRow != nullptr) { |
| 274 |
KJ_ASSERT(f(*parent.keys[n-1], *maxRow), n, parent.keys[n-1], maxRow); |
| 275 |
} |
| 276 |
return total; |
| 277 |
} else { |
| 278 |
auto& leaf = tree[pos].leaf; |
| 279 |
auto n = leaf.size(); |
| 280 |
for (auto i: kj::zeroTo(n)) { |
| 281 |
KJ_ASSERT(*leaf.rows[i] < size, n, i); |
| 282 |
if (i > 0) { |
| 283 |
KJ_ASSERT(f(*leaf.rows[i - 1], *leaf.rows[i]), |
| 284 |
n, i, leaf.rows[i - 1], leaf.rows[i]); |
| 285 |
} |
| 286 |
} |
| 287 |
if (maxRow != nullptr) { |
| 288 |
KJ_ASSERT(leaf.rows[n-1] == maxRow, n); |
| 289 |
} |
| 290 |
return n; |
| 291 |
} |
| 292 |
} |
| 293 |
|
| 294 |
kj::String BTreeImpl::MaybeUint::toString() const { |
| 295 |
return i == 0 ? kj::str("(null)") : kj::str(i - 1); |
| 296 |
} |
| 297 |
|
| 298 |
void BTreeImpl::logInconsistency() const { |
| 299 |
KJ_LOG(ERROR, |
| 300 |
"BTreeIndex detected tree state inconsistency. This can happen if you create a kj::Table " |
| 301 |
"with a b-tree index and you modify the rows in the table post-indexing in a way that would " |
| 302 |
"change their ordering. This is a serious bug which will lead to undefined behavior." |
| 303 |
"\nstack: ", kj::getStackTrace()); |
| 304 |
} |
| 305 |
|
| 306 |
void BTreeImpl::reserve(size_t size) { |
| 307 |
KJ_REQUIRE(size < (1u << 31), "b-tree has reached maximum size"); |
| 308 |
|
| 309 |
// Calculate the worst-case number of leaves to cover the size, given that a leaf is always at |
| 310 |
// least half-full. (Note that it's correct for this calculation to round down, not up: The |
| 311 |
// remainder will necessarily be distributed among the non-full leaves, rather than creating a |
| 312 |
// new leaf, because if it went into a new leaf, that leaf would be less than half-full.) |
| 313 |
uint leaves = size / (Leaf::NROWS / 2); |
| 314 |
|
| 315 |
// Calculate the worst-case number of parents to cover the leaves, given that a parent is always |
| 316 |
// at least half-full. Since the parents form a tree with branching factor B, the size of the |
| 317 |
// tree is N/B + N/B^2 + N/B^3 + N/B^4 + ... = N / (B - 1). Math. |
| 318 |
constexpr uint branchingFactor = Parent::NCHILDREN / 2; |
| 319 |
uint parents = leaves / (branchingFactor - 1); |
| 320 |
|
| 321 |
// Height is log-base-branching-factor of leaves, plus 1 for the root node. |
| 322 |
uint height = lg(leaves | 1) / lg(branchingFactor) + 1; |
| 323 |
|
| 324 |
size_t newSize = leaves + |
| 325 |
parents + 1 + // + 1 for the root |
| 326 |
height + 2; // minimum freelist size needed by insert() |
| 327 |
|
| 328 |
if (treeCapacity < newSize) { |
| 329 |
growTree(newSize); |
| 330 |
} |
| 331 |
} |
| 332 |
|
| 333 |
void BTreeImpl::clear() { |
| 334 |
if (tree != &EMPTY_NODE) { |
| 335 |
azero(tree, treeCapacity); |
| 336 |
height = 0; |
| 337 |
freelistHead = 1; |
| 338 |
freelistSize = treeCapacity - 1; // subtract one to account for the root node |
| 339 |
beginLeaf = 0; |
| 340 |
endLeaf = 0; |
| 341 |
} |
| 342 |
} |
| 343 |
|
| 344 |
void BTreeImpl::growTree(uint minCapacity) { |
| 345 |
uint newCapacity = kj::max(kj::max(minCapacity, treeCapacity * 2), 4); |
| 346 |
freelistSize += newCapacity - treeCapacity; |
| 347 |
|
| 348 |
// Allocate some aligned memory! In theory this should be as simple as calling the C11 standard |
| 349 |
// aligned_alloc() function. Unfortunately, many platforms don't implement it. Luckily, there |
| 350 |
// are usually alternatives. |
| 351 |
|
| 352 |
#if _WIN32 |
| 353 |
// Windows lacks aligned_alloc() but has its own _aligned_malloc() (which requires freeing using |
| 354 |
// _aligned_free()). |
| 355 |
// WATCH OUT: The argument order for _aligned_malloc() is opposite of aligned_alloc()! |
| 356 |
NodeUnion* newTree = reinterpret_cast<NodeUnion*>( |
| 357 |
_aligned_malloc(newCapacity * sizeof(BTreeImpl::NodeUnion), sizeof(BTreeImpl::NodeUnion))); |
| 358 |
KJ_ASSERT(newTree != nullptr, "memory allocation failed", newCapacity); |
| 359 |
#else |
| 360 |
// macOS, OpenBSD, and Android lack aligned_alloc(), but have posix_memalign(). Fine. |
| 361 |
void* allocPtr; |
| 362 |
int error = posix_memalign(&allocPtr, |
| 363 |
sizeof(BTreeImpl::NodeUnion), newCapacity * sizeof(BTreeImpl::NodeUnion)); |
| 364 |
if (error != 0) { |
| 365 |
KJ_FAIL_SYSCALL("posix_memalign", error); |
| 366 |
} |
| 367 |
NodeUnion* newTree = reinterpret_cast<NodeUnion*>(allocPtr); |
| 368 |
#endif |
| 369 |
|
| 370 |
// Note: C11 introduces aligned_alloc() as a standard, but it's still missing on many platforms, |
| 371 |
// so we don't use it. But if you wanted to use it, you'd do this: |
| 372 |
// NodeUnion* newTree = reinterpret_cast<NodeUnion*>( |
| 373 |
// aligned_alloc(sizeof(BTreeImpl::NodeUnion), newCapacity * sizeof(BTreeImpl::NodeUnion))); |
| 374 |
// KJ_ASSERT(newTree != nullptr, "memory allocation failed", newCapacity); |
| 375 |
|
| 376 |
acopy(newTree, tree, treeCapacity); |
| 377 |
azero(newTree + treeCapacity, newCapacity - treeCapacity); |
| 378 |
if (tree != &EMPTY_NODE) aligned_free(tree); |
| 379 |
tree = newTree; |
| 380 |
treeCapacity = newCapacity; |
| 381 |
} |
| 382 |
|
| 383 |
BTreeImpl::Iterator BTreeImpl::search(const SearchKey& searchKey) const { |
| 384 |
// Find the "first" row number (in sorted order) for which searchKey.isAfter(rowNumber) returns |
| 385 |
// false. |
| 386 |
|
| 387 |
uint pos = 0; |
| 388 |
|
| 389 |
for (auto i KJ_UNUSED: zeroTo(height)) { |
| 390 |
auto& parent = tree[pos].parent; |
| 391 |
pos = parent.children[searchKey.search(parent)]; |
| 392 |
} |
| 393 |
|
| 394 |
auto& leaf = tree[pos].leaf; |
| 395 |
return { tree, &leaf, searchKey.search(leaf) }; |
| 396 |
} |
| 397 |
|
| 398 |
template <typename T> |
| 399 |
struct BTreeImpl::AllocResult { |
| 400 |
uint index; |
| 401 |
T& node; |
| 402 |
}; |
| 403 |
|
| 404 |
template <typename T> |
| 405 |
inline BTreeImpl::AllocResult<T> BTreeImpl::alloc() { |
| 406 |
// Allocate a new item from the freelist. Guaranteed to be zero'd except for the first member. |
| 407 |
uint i = freelistHead; |
| 408 |
NodeUnion* ptr = &tree[i]; |
| 409 |
freelistHead = i + 1 + ptr->freelist.nextOffset; |
| 410 |
--freelistSize; |
| 411 |
return { i, *ptr }; |
| 412 |
} |
| 413 |
|
| 414 |
inline void BTreeImpl::free(uint pos) { |
| 415 |
// Add the given node to the freelist. |
| 416 |
|
| 417 |
// HACK: This is typically called on a node immediately after copying its contents away, but the |
| 418 |
// pointer used to copy it away may be a different pointer pointing to a different union member |
| 419 |
// which the compiler may not recgonize as aliasing with this object. Just to be extra-safe, |
| 420 |
// insert a compiler barrier. |
| 421 |
compilerBarrier(); |
| 422 |
|
| 423 |
auto& node = tree[pos]; |
| 424 |
node.freelist.nextOffset = freelistHead - pos - 1; |
| 425 |
azero(node.freelist.zero, kj::size(node.freelist.zero)); |
| 426 |
freelistHead = pos; |
| 427 |
++freelistSize; |
| 428 |
} |
| 429 |
|
| 430 |
BTreeImpl::Iterator BTreeImpl::insert(const SearchKey& searchKey) { |
| 431 |
// Like search() but ensures that there is room in the leaf node to insert a new row. |
| 432 |
|
| 433 |
// If we split the root node it will generate two new nodes. If we split any other node in the |
| 434 |
// path it will generate one new node. `height` doesn't count leaf nodes, but we can equivalently |
| 435 |
// think of it as not counting the root node, so in the worst case we may allocate height + 2 |
| 436 |
// new nodes. |
| 437 |
// |
| 438 |
// (Also note that if the tree is currently empty, then `tree` points to a dummy root node in |
| 439 |
// read-only memory. We definitely need to allocate a real tree node array in this case, and |
| 440 |
// we'll start out allocating space for four nodes, which will be all we need up to 28 rows.) |
| 441 |
if (freelistSize < height + 2) { |
| 442 |
if (height > 0 && !tree[0].parent.isFull() && freelistSize >= height) { |
| 443 |
// Slight optimization: The root node is not full, so we're definitely not going to split it. |
| 444 |
// That means that the maximum allocations we might do is equal to `height`, not |
| 445 |
// `height + 2`, and we have that much space, so no need to grow yet. |
| 446 |
// |
| 447 |
// This optimization is particularly important for small trees, e.g. when treeCapacity is 4 |
| 448 |
// and the tree so far consists of a root and two children, we definitely don't need to grow |
| 449 |
// the tree yet. |
| 450 |
} else { |
| 451 |
growTree(); |
| 452 |
|
| 453 |
if (freelistHead == 0) { |
| 454 |
// We have no root yet. Allocate one. |
| 455 |
KJ_ASSERT(alloc<Parent>().index == 0); |
| 456 |
} |
| 457 |
} |
| 458 |
} |
| 459 |
|
| 460 |
uint pos = 0; |
| 461 |
|
| 462 |
// Track grandparent node and child index within grandparent. |
| 463 |
Parent* parent = nullptr; |
| 464 |
uint indexInParent = 0; |
| 465 |
|
| 466 |
for (auto i KJ_UNUSED: zeroTo(height)) { |
| 467 |
Parent& node = insertHelper(searchKey, tree[pos].parent, parent, indexInParent, pos); |
| 468 |
|
| 469 |
parent = &node; |
| 470 |
indexInParent = searchKey.search(node); |
| 471 |
pos = node.children[indexInParent]; |
| 472 |
} |
| 473 |
|
| 474 |
Leaf& leaf = insertHelper(searchKey, tree[pos].leaf, parent, indexInParent, pos); |
| 475 |
|
| 476 |
// Fun fact: Unlike erase(), there's no need to climb back up the tree modifying keys, because |
| 477 |
// either the newly-inserted node will not be the last in the leaf (and thus parent keys aren't |
| 478 |
// modified), or the leaf is the last leaf in the tree (and thus there's no parent key to |
| 479 |
// modify). |
| 480 |
|
| 481 |
return { tree, &leaf, searchKey.search(leaf) }; |
| 482 |
} |
| 483 |
|
| 484 |
template <typename Node> |
| 485 |
Node& BTreeImpl::insertHelper(const SearchKey& searchKey, |
| 486 |
Node& node, Parent* parent, uint indexInParent, uint pos) { |
| 487 |
if (node.isFull()) { |
| 488 |
// This node is full. Need to split. |
| 489 |
if (parent == nullptr) { |
| 490 |
// This is the root node. We need to split into two nodes and create a new root. |
| 491 |
auto n1 = alloc<Node>(); |
| 492 |
auto n2 = alloc<Node>(); |
| 493 |
|
| 494 |
uint pivot = split(n2.node, n2.index, node, pos); |
| 495 |
move(n1.node, n1.index, node); |
| 496 |
|
| 497 |
// Rewrite root to have the two children. |
| 498 |
tree[0].parent.initRoot(pivot, n1.index, n2.index); |
| 499 |
|
| 500 |
// Increased height. |
| 501 |
++height; |
| 502 |
|
| 503 |
// Decide which new branch has our search key. |
| 504 |
if (searchKey.isAfter(pivot)) { |
| 505 |
// the right one |
| 506 |
return n2.node; |
| 507 |
} else { |
| 508 |
// the left one |
| 509 |
return n1.node; |
| 510 |
} |
| 511 |
} else { |
| 512 |
// This is a non-root parent node. We need to split it into two and insert the new node |
| 513 |
// into the grandparent. |
| 514 |
auto n = alloc<Node>(); |
| 515 |
uint pivot = split(n.node, n.index, node, pos); |
| 516 |
|
| 517 |
// Insert new child into grandparent. |
| 518 |
parent->insertAfter(indexInParent, pivot, n.index); |
| 519 |
|
| 520 |
// Decide which new branch has our search key. |
| 521 |
if (searchKey.isAfter(pivot)) { |
| 522 |
// the new one, which is right of the original |
| 523 |
return n.node; |
| 524 |
} else { |
| 525 |
// the original one, which is left of the new one |
| 526 |
return node; |
| 527 |
} |
| 528 |
} |
| 529 |
} else { |
| 530 |
// No split needed. |
| 531 |
return node; |
| 532 |
} |
| 533 |
} |
| 534 |
|
| 535 |
void BTreeImpl::erase(uint row, const SearchKey& searchKey) { |
| 536 |
// Erase the given row number from the tree. predicate() returns true for the given row and all |
| 537 |
// rows after it. |
| 538 |
|
| 539 |
uint pos = 0; |
| 540 |
|
| 541 |
// Track grandparent node and child index within grandparent. |
| 542 |
Parent* parent = nullptr; |
| 543 |
uint indexInParent = 0; |
| 544 |
|
| 545 |
MaybeUint* fixup = nullptr; |
| 546 |
|
| 547 |
for (auto i KJ_UNUSED: zeroTo(height)) { |
| 548 |
Parent& node = eraseHelper(tree[pos].parent, parent, indexInParent, pos, fixup); |
| 549 |
|
| 550 |
parent = &node; |
| 551 |
indexInParent = searchKey.search(node); |
| 552 |
pos = node.children[indexInParent]; |
| 553 |
|
| 554 |
if (indexInParent < kj::size(node.keys) && node.keys[indexInParent] == row) { |
| 555 |
// Oh look, the row is a key in this node! We'll need to come back and fix this up later. |
| 556 |
// Note that any particular row can only appear as *one* key value anywhere in the tree, so |
| 557 |
// we only need one fixup pointer, which is nice. |
| 558 |
MaybeUint* newFixup = &node.keys[indexInParent]; |
| 559 |
if (fixup == newFixup) { |
| 560 |
// The fixup pointer was already set while processing a parent node, and then a merge or |
| 561 |
// rotate caused it to be moved, but the fixup pointer was updated... so it's already set |
| 562 |
// to point at the slot we wanted it to point to, so nothing to see here. |
| 563 |
} else { |
| 564 |
KJ_DASSERT(fixup == nullptr); |
| 565 |
fixup = newFixup; |
| 566 |
} |
| 567 |
} |
| 568 |
} |
| 569 |
|
| 570 |
Leaf& leaf = eraseHelper(tree[pos].leaf, parent, indexInParent, pos, fixup); |
| 571 |
|
| 572 |
uint r = searchKey.search(leaf); |
| 573 |
if (leaf.rows[r] == row) { |
| 574 |
leaf.erase(r); |
| 575 |
|
| 576 |
if (fixup != nullptr) { |
| 577 |
// There's a key in a parent node that needs fixup. This is only possible if the removed |
| 578 |
// node is the last in its leaf. |
| 579 |
KJ_DASSERT(leaf.rows[r] == nullptr); |
| 580 |
KJ_DASSERT(r > 0); // non-root nodes must be at least half full so this can't be item 0 |
| 581 |
KJ_DASSERT(*fixup == row); |
| 582 |
*fixup = leaf.rows[r - 1]; |
| 583 |
} |
| 584 |
} else { |
| 585 |
logInconsistency(); |
| 586 |
} |
| 587 |
} |
| 588 |
|
| 589 |
template <typename Node> |
| 590 |
Node& BTreeImpl::eraseHelper( |
| 591 |
Node& node, Parent* parent, uint indexInParent, uint pos, MaybeUint*& fixup) { |
| 592 |
if (parent != nullptr && !node.isMostlyFull()) { |
| 593 |
// This is not the root, but it's only half-full. Rebalance. |
| 594 |
KJ_DASSERT(node.isHalfFull()); |
| 595 |
|
| 596 |
if (indexInParent > 0) { |
| 597 |
// There's a sibling to the left. |
| 598 |
uint sibPos = parent->children[indexInParent - 1]; |
| 599 |
Node& sib = tree[sibPos]; |
| 600 |
if (sib.isMostlyFull()) { |
| 601 |
// Left sibling is more than half full. Steal one member. |
| 602 |
rotateRight(sib, node, *parent, indexInParent - 1); |
| 603 |
return node; |
| 604 |
} else { |
| 605 |
// Left sibling is half full, too. Merge. |
| 606 |
KJ_ASSERT(sib.isHalfFull()); |
| 607 |
merge(sib, sibPos, *parent->keys[indexInParent - 1], node); |
| 608 |
parent->eraseAfter(indexInParent - 1); |
| 609 |
free(pos); |
| 610 |
if (fixup == &parent->keys[indexInParent]) --fixup; |
| 611 |
|
| 612 |
if (parent->keys[0] == nullptr) { |
| 613 |
// Oh hah, the parent has no keys left. It must be the root. We can eliminate it. |
| 614 |
KJ_DASSERT(parent == &tree->parent); |
| 615 |
compilerBarrier(); // don't reorder any writes to parent below here |
| 616 |
move(tree[0], 0, sib); |
| 617 |
free(sibPos); |
| 618 |
--height; |
| 619 |
return tree[0]; |
| 620 |
} else { |
| 621 |
return sib; |
| 622 |
} |
| 623 |
} |
| 624 |
} else if (indexInParent < Parent::NKEYS && parent->keys[indexInParent] != nullptr) { |
| 625 |
// There's a sibling to the right. |
| 626 |
uint sibPos = parent->children[indexInParent + 1]; |
| 627 |
Node& sib = tree[sibPos]; |
| 628 |
if (sib.isMostlyFull()) { |
| 629 |
// Right sibling is more than half full. Steal one member. |
| 630 |
rotateLeft(node, sib, *parent, indexInParent, fixup); |
| 631 |
return node; |
| 632 |
} else { |
| 633 |
// Right sibling is half full, too. Merge. |
| 634 |
KJ_ASSERT(sib.isHalfFull()); |
| 635 |
merge(node, pos, *parent->keys[indexInParent], sib); |
| 636 |
parent->eraseAfter(indexInParent); |
| 637 |
free(sibPos); |
| 638 |
if (fixup == &parent->keys[indexInParent]) fixup = nullptr; |
| 639 |
|
| 640 |
if (parent->keys[0] == nullptr) { |
| 641 |
// Oh hah, the parent has no keys left. It must be the root. We can eliminate it. |
| 642 |
KJ_DASSERT(parent == &tree->parent); |
| 643 |
compilerBarrier(); // don't reorder any writes to parent below here |
| 644 |
move(tree[0], 0, node); |
| 645 |
free(pos); |
| 646 |
--height; |
| 647 |
return tree[0]; |
| 648 |
} else { |
| 649 |
return node; |
| 650 |
} |
| 651 |
} |
| 652 |
} else { |
| 653 |
KJ_FAIL_ASSERT("inconsistent b-tree"); |
| 654 |
} |
| 655 |
} |
| 656 |
|
| 657 |
return node; |
| 658 |
} |
| 659 |
|
| 660 |
void BTreeImpl::renumber(uint oldRow, uint newRow, const SearchKey& searchKey) { |
| 661 |
// Renumber the given row from oldRow to newRow. predicate() returns true for oldRow and all |
| 662 |
// rows after it. (It will not be called on newRow.) |
| 663 |
|
| 664 |
uint pos = 0; |
| 665 |
|
| 666 |
for (auto i KJ_UNUSED: zeroTo(height)) { |
| 667 |
auto& node = tree[pos].parent; |
| 668 |
uint indexInParent = searchKey.search(node); |
| 669 |
pos = node.children[indexInParent]; |
| 670 |
if (indexInParent < kj::size(node.keys) && node.keys[indexInParent] == oldRow) { |
| 671 |
node.keys[indexInParent] = newRow; |
| 672 |
} |
| 673 |
KJ_DASSERT(pos != 0); |
| 674 |
} |
| 675 |
|
| 676 |
auto& leaf = tree[pos].leaf; |
| 677 |
uint r = searchKey.search(leaf); |
| 678 |
if (leaf.rows[r] == oldRow) { |
| 679 |
leaf.rows[r] = newRow; |
| 680 |
} else { |
| 681 |
logInconsistency(); |
| 682 |
} |
| 683 |
} |
| 684 |
|
| 685 |
uint BTreeImpl::split(Parent& dst, uint dstPos, Parent& src, uint srcPos) { |
| 686 |
constexpr size_t mid = Parent::NKEYS / 2; |
| 687 |
uint pivot = *src.keys[mid]; |
| 688 |
acopy(dst.keys, src.keys + mid + 1, Parent::NKEYS - mid - 1); |
| 689 |
azero(src.keys + mid, Parent::NKEYS - mid); |
| 690 |
acopy(dst.children, src.children + mid + 1, Parent::NCHILDREN - mid - 1); |
| 691 |
azero(src.children + mid + 1, Parent::NCHILDREN - mid - 1); |
| 692 |
return pivot; |
| 693 |
} |
| 694 |
|
| 695 |
uint BTreeImpl::split(Leaf& dst, uint dstPos, Leaf& src, uint srcPos) { |
| 696 |
constexpr size_t mid = Leaf::NROWS / 2; |
| 697 |
uint pivot = *src.rows[mid - 1]; |
| 698 |
acopy(dst.rows, src.rows + mid, Leaf::NROWS - mid); |
| 699 |
azero(src.rows + mid, Leaf::NROWS - mid); |
| 700 |
|
| 701 |
if (src.next == 0) { |
| 702 |
endLeaf = dstPos; |
| 703 |
} else { |
| 704 |
tree[src.next].leaf.prev = dstPos; |
| 705 |
} |
| 706 |
dst.next = src.next; |
| 707 |
dst.prev = srcPos; |
| 708 |
src.next = dstPos; |
| 709 |
|
| 710 |
return pivot; |
| 711 |
} |
| 712 |
|
| 713 |
void BTreeImpl::merge(Parent& dst, uint dstPos, uint pivot, Parent& src) { |
| 714 |
// merge() is only legal if both nodes are half-empty. Meanwhile, B-tree invariants |
| 715 |
// guarantee that the node can't be more than half-empty, or we would have merged it sooner. |
| 716 |
// (The root can be more than half-empty, but it is never merged with anything.) |
| 717 |
KJ_DASSERT(src.isHalfFull()); |
| 718 |
KJ_DASSERT(dst.isHalfFull()); |
| 719 |
|
| 720 |
constexpr size_t mid = Parent::NKEYS/2; |
| 721 |
dst.keys[mid] = pivot; |
| 722 |
acopy(dst.keys + mid + 1, src.keys, mid); |
| 723 |
acopy(dst.children + mid + 1, src.children, mid + 1); |
| 724 |
} |
| 725 |
|
| 726 |
void BTreeImpl::merge(Leaf& dst, uint dstPos, uint pivot, Leaf& src) { |
| 727 |
// merge() is only legal if both nodes are half-empty. Meanwhile, B-tree invariants |
| 728 |
// guarantee that the node can't be more than half-empty, or we would have merged it sooner. |
| 729 |
// (The root can be more than half-empty, but it is never merged with anything.) |
| 730 |
KJ_DASSERT(src.isHalfFull()); |
| 731 |
KJ_DASSERT(dst.isHalfFull()); |
| 732 |
|
| 733 |
constexpr size_t mid = Leaf::NROWS/2; |
| 734 |
KJ_DASSERT(dst.rows[mid-1] == pivot); |
| 735 |
acopy(dst.rows + mid, src.rows, mid); |
| 736 |
|
| 737 |
dst.next = src.next; |
| 738 |
if (dst.next == 0) { |
| 739 |
endLeaf = dstPos; |
| 740 |
} else { |
| 741 |
tree[dst.next].leaf.prev = dstPos; |
| 742 |
} |
| 743 |
} |
| 744 |
|
| 745 |
void BTreeImpl::move(Parent& dst, uint dstPos, Parent& src) { |
| 746 |
dst = src; |
| 747 |
} |
| 748 |
|
| 749 |
void BTreeImpl::move(Leaf& dst, uint dstPos, Leaf& src) { |
| 750 |
dst = src; |
| 751 |
if (src.next == 0) { |
| 752 |
endLeaf = dstPos; |
| 753 |
} else { |
| 754 |
tree[src.next].leaf.prev = dstPos; |
| 755 |
} |
| 756 |
if (src.prev == 0) { |
| 757 |
beginLeaf = dstPos; |
| 758 |
} else { |
| 759 |
tree[src.prev].leaf.next = dstPos; |
| 760 |
} |
| 761 |
} |
| 762 |
|
| 763 |
void BTreeImpl::rotateLeft( |
| 764 |
Parent& left, Parent& right, Parent& parent, uint indexInParent, MaybeUint*& fixup) { |
| 765 |
// Steal one item from the right node and move it to the left node. |
| 766 |
|
| 767 |
// Like merge(), this is only called on an exactly-half-empty node. |
| 768 |
KJ_DASSERT(left.isHalfFull()); |
| 769 |
KJ_DASSERT(right.isMostlyFull()); |
| 770 |
|
| 771 |
constexpr size_t mid = Parent::NKEYS/2; |
| 772 |
left.keys[mid] = parent.keys[indexInParent]; |
| 773 |
if (fixup == &parent.keys[indexInParent]) fixup = &left.keys[mid]; |
| 774 |
parent.keys[indexInParent] = right.keys[0]; |
| 775 |
left.children[mid + 1] = right.children[0]; |
| 776 |
amove(right.keys, right.keys + 1, Parent::NKEYS - 1); |
| 777 |
right.keys[Parent::NKEYS - 1] = nullptr; |
| 778 |
amove(right.children, right.children + 1, Parent::NCHILDREN - 1); |
| 779 |
right.children[Parent::NCHILDREN - 1] = 0; |
| 780 |
} |
| 781 |
|
| 782 |
void BTreeImpl::rotateLeft( |
| 783 |
Leaf& left, Leaf& right, Parent& parent, uint indexInParent, MaybeUint*& fixup) { |
| 784 |
// Steal one item from the right node and move it to the left node. |
| 785 |
|
| 786 |
// Like merge(), this is only called on an exactly-half-empty node. |
| 787 |
KJ_DASSERT(left.isHalfFull()); |
| 788 |
KJ_DASSERT(right.isMostlyFull()); |
| 789 |
|
| 790 |
constexpr size_t mid = Leaf::NROWS/2; |
| 791 |
parent.keys[indexInParent] = left.rows[mid] = right.rows[0]; |
| 792 |
if (fixup == &parent.keys[indexInParent]) fixup = nullptr; |
| 793 |
amove(right.rows, right.rows + 1, Leaf::NROWS - 1); |
| 794 |
right.rows[Leaf::NROWS - 1] = nullptr; |
| 795 |
} |
| 796 |
|
| 797 |
void BTreeImpl::rotateRight(Parent& left, Parent& right, Parent& parent, uint indexInParent) { |
| 798 |
// Steal one item from the left node and move it to the right node. |
| 799 |
|
| 800 |
// Like merge(), this is only called on an exactly-half-empty node. |
| 801 |
KJ_DASSERT(right.isHalfFull()); |
| 802 |
KJ_DASSERT(left.isMostlyFull()); |
| 803 |
|
| 804 |
constexpr size_t mid = Parent::NKEYS/2; |
| 805 |
amove(right.keys + 1, right.keys, mid); |
| 806 |
amove(right.children + 1, right.children, mid + 1); |
| 807 |
|
| 808 |
uint back = left.keyCount() - 1; |
| 809 |
|
| 810 |
right.keys[0] = parent.keys[indexInParent]; |
| 811 |
parent.keys[indexInParent] = left.keys[back]; |
| 812 |
right.children[0] = left.children[back + 1]; |
| 813 |
left.keys[back] = nullptr; |
| 814 |
left.children[back + 1] = 0; |
| 815 |
} |
| 816 |
|
| 817 |
void BTreeImpl::rotateRight(Leaf& left, Leaf& right, Parent& parent, uint indexInParent) { |
| 818 |
// Steal one item from the left node and move it to the right node. |
| 819 |
|
| 820 |
// Like mergeFrom(), this is only called on an exactly-half-empty node. |
| 821 |
KJ_DASSERT(right.isHalfFull()); |
| 822 |
KJ_DASSERT(left.isMostlyFull()); |
| 823 |
|
| 824 |
constexpr size_t mid = Leaf::NROWS/2; |
| 825 |
amove(right.rows + 1, right.rows, mid); |
| 826 |
|
| 827 |
uint back = left.size() - 1; |
| 828 |
|
| 829 |
right.rows[0] = left.rows[back]; |
| 830 |
parent.keys[indexInParent] = left.rows[back - 1]; |
| 831 |
left.rows[back] = nullptr; |
| 832 |
} |
| 833 |
|
| 834 |
void BTreeImpl::Parent::initRoot(uint key, uint leftChild, uint rightChild) { |
| 835 |
// HACK: This is typically called on the root node immediately after copying its contents away, |
| 836 |
// but the pointer used to copy it away may be a different pointer pointing to a different |
| 837 |
// union member which the compiler may not recgonize as aliasing with this object. Just to |
| 838 |
// be extra-safe, insert a compiler barrier. |
| 839 |
compilerBarrier(); |
| 840 |
|
| 841 |
keys[0] = key; |
| 842 |
children[0] = leftChild; |
| 843 |
children[1] = rightChild; |
| 844 |
azero(keys + 1, Parent::NKEYS - 1); |
| 845 |
azero(children + 2, Parent::NCHILDREN - 2); |
| 846 |
} |
| 847 |
|
| 848 |
void BTreeImpl::Parent::insertAfter(uint i, uint splitKey, uint child) { |
| 849 |
KJ_IREQUIRE(children[Parent::NCHILDREN - 1] == 0); // check not full |
| 850 |
|
| 851 |
amove(keys + i + 1, keys + i, Parent::NKEYS - (i + 1)); |
| 852 |
keys[i] = splitKey; |
| 853 |
|
| 854 |
amove(children + i + 2, children + i + 1, Parent::NCHILDREN - (i + 2)); |
| 855 |
children[i + 1] = child; |
| 856 |
} |
| 857 |
|
| 858 |
void BTreeImpl::Parent::eraseAfter(uint i) { |
| 859 |
amove(keys + i, keys + i + 1, Parent::NKEYS - (i + 1)); |
| 860 |
keys[Parent::NKEYS - 1] = nullptr; |
| 861 |
amove(children + i + 1, children + i + 2, Parent::NCHILDREN - (i + 2)); |
| 862 |
children[Parent::NCHILDREN - 1] = 0; |
| 863 |
} |
| 864 |
|
| 865 |
} // namespace _ |
| 866 |
|
| 867 |
// ======================================================================================= |
| 868 |
// Insertion order |
| 869 |
|
| 870 |
const InsertionOrderIndex::Link InsertionOrderIndex::EMPTY_LINK = { 0, 0 }; |
| 871 |
|
| 872 |
InsertionOrderIndex::InsertionOrderIndex(): capacity(0), links(const_cast<Link*>(&EMPTY_LINK)) {} |
| 873 |
InsertionOrderIndex::InsertionOrderIndex(InsertionOrderIndex&& other) |
| 874 |
: capacity(other.capacity), links(other.links) { |
| 875 |
other.capacity = 0; |
| 876 |
other.links = const_cast<Link*>(&EMPTY_LINK); |
| 877 |
} |
| 878 |
InsertionOrderIndex& InsertionOrderIndex::operator=(InsertionOrderIndex&& other) { |
| 879 |
KJ_DASSERT(&other != this); |
| 880 |
capacity = other.capacity; |
| 881 |
links = other.links; |
| 882 |
other.capacity = 0; |
| 883 |
other.links = const_cast<Link*>(&EMPTY_LINK); |
| 884 |
return *this; |
| 885 |
} |
| 886 |
InsertionOrderIndex::~InsertionOrderIndex() noexcept(false) { |
| 887 |
if (links != &EMPTY_LINK) delete[] links; |
| 888 |
} |
| 889 |
|
| 890 |
void InsertionOrderIndex::reserve(size_t size) { |
| 891 |
KJ_ASSERT(size < (1u << 31), "Table too big for InsertionOrderIndex"); |
| 892 |
|
| 893 |
if (size > capacity) { |
| 894 |
// Need to grow. |
| 895 |
// Note that `size` and `capacity` do not include the special link[0]. |
| 896 |
|
| 897 |
// Round up to the next power of 2. |
| 898 |
size_t allocation = 1u << (_::lg(size) + 1); |
| 899 |
KJ_DASSERT(allocation > size); |
| 900 |
KJ_DASSERT(allocation <= size * 2); |
| 901 |
|
| 902 |
// Round first allocation up to 8. |
| 903 |
allocation = kj::max(allocation, 8); |
| 904 |
|
| 905 |
Link* newLinks = new Link[allocation]; |
| 906 |
#ifdef KJ_DEBUG |
| 907 |
// To catch bugs, fill unused links with 0xff. |
| 908 |
memset(newLinks, 0xff, allocation * sizeof(Link)); |
| 909 |
#endif |
| 910 |
_::acopy(newLinks, links, capacity + 1); |
| 911 |
if (links != &EMPTY_LINK) delete[] links; |
| 912 |
links = newLinks; |
| 913 |
capacity = allocation - 1; |
| 914 |
} |
| 915 |
} |
| 916 |
|
| 917 |
void InsertionOrderIndex::clear() { |
| 918 |
links[0] = Link { 0, 0 }; |
| 919 |
|
| 920 |
#ifdef KJ_DEBUG |
| 921 |
// To catch bugs, fill unused links with 0xff. |
| 922 |
memset(links + 1, 0xff, capacity * sizeof(Link)); |
| 923 |
#endif |
| 924 |
} |
| 925 |
|
| 926 |
kj::Maybe<size_t> InsertionOrderIndex::insertImpl(size_t pos) { |
| 927 |
if (pos >= capacity) { |
| 928 |
reserve(pos + 1); |
| 929 |
} |
| 930 |
|
| 931 |
links[pos + 1].prev = links[0].prev; |
| 932 |
links[pos + 1].next = 0; |
| 933 |
links[links[0].prev].next = pos + 1; |
| 934 |
links[0].prev = pos + 1; |
| 935 |
|
| 936 |
return nullptr; |
| 937 |
} |
| 938 |
|
| 939 |
void InsertionOrderIndex::eraseImpl(size_t pos) { |
| 940 |
Link& link = links[pos + 1]; |
| 941 |
links[link.next].prev = link.prev; |
| 942 |
links[link.prev].next = link.next; |
| 943 |
|
| 944 |
#ifdef KJ_DEBUG |
| 945 |
memset(&link, 0xff, sizeof(Link)); |
| 946 |
#endif |
| 947 |
} |
| 948 |
|
| 949 |
void InsertionOrderIndex::moveImpl(size_t oldPos, size_t newPos) { |
| 950 |
Link& link = links[oldPos + 1]; |
| 951 |
Link& newLink = links[newPos + 1]; |
| 952 |
|
| 953 |
newLink = link; |
| 954 |
|
| 955 |
KJ_DASSERT(links[link.next].prev == oldPos + 1); |
| 956 |
KJ_DASSERT(links[link.prev].next == oldPos + 1); |
| 957 |
links[link.next].prev = newPos + 1; |
| 958 |
links[link.prev].next = newPos + 1; |
| 959 |
|
| 960 |
#ifdef KJ_DEBUG |
| 961 |
memset(&link, 0xff, sizeof(Link)); |
| 962 |
#endif |
| 963 |
} |
| 964 |
|
| 965 |
} // namespace kj |