suwako / LittleBeast

master
ブランチ master
LittleBeast / src / Std / Lib / Db / Sqlite / Btree.php
28.5 KB、853行 生 Blame 履歴
1<?php
2/*************************************************************
3# 076 License
4
5Copyright (c) テクニカル諏訪子
6
7Permission is hereby granted to any person obtaining a copy of the software
8Little Beast (the "Software") to use, modify, merge, copy, publish, distribute,
9sublicense, and/or sell copies of the Software, subject to the following conditions:
10
11 1. **Origin Attribution**:
12 - You must not misrepresent the origin of the Software; you must not claim
13 you created the original Software.
14 - If the Software is used in a product, you must either:
15 a. Provide clear attribution in the product's documentation, user interface,
16 or other visible areas, **OR**
17 b. Pay the original developers a fee they specify in writing.
18 2. **Usage Restriction**:
19 - The Software, or any derivative works, dependencies, or libraries
20 incorporating it, must not be used for censorship or to suppress freedom of
21 speech, expression, or creativity. Prohibited uses include, but are not
22 limited to:
23 - Censorship of so-called "hate speech", visuals, non-mainstream opinions,
24 ideas, or objective reality.
25 - Tools or systems designed to restrict access to information or
26 artistic works.
27 3. **Notice Preservation**:
28 - This license and the above copyright notice must remain intact in all copies
29 of the source code.
30
31THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
32INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
33PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
34HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
35CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
36OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 */
38namespace Std\Lib\Db\Sqlite;
39
40use Std\Lib\Db\DbException;
41
42/**
43 * SQLiteのBツリー（テーブル：rowidがキー、インデックス：レコードがキー）
44 *
45 * ページはPageのオブジェクトとして持ち、flush()でPagerに書く。セルは毎回ページの最後に詰めて書き直すので、
46 * フリーブロックは使わない。ページが溢れたり少なくなったりしたら、SQLiteと同じく最大3つの兄弟のページで分け直す。
47 */
48final class Btree {
49 public const TABLE_LEAF = 13;
50 public const TABLE_INTERIOR = 5;
51 public const INDEX_LEAF = 10;
52 public const INDEX_INTERIOR = 2;
53
54 /** @var array<int, Page> */
55 private array $pages = [];
56 private array $dirty = [];
57 private int $generation = -1;
58 /** スナップショット（文・セーブポイント）：ページ番号 => [変更前のページ, 変更されていたか]、又はnull（無かった） */
59 private array $snaps = [];
60
61 public function __construct(private Pager $pager) {}
62
63 ///////////////
64 // ページ
65
66 /** ページを読む（オブジェクトのキャッシュ） */
67 public function page(int $pgno): Page {
68 $this->sync();
69 if ($this->snaps) $this->remember($pgno);
70 if (isset($this->pages[$pgno])) return $this->pages[$pgno];
71 if (count($this->pages) > 3000 && empty($this->dirty)) $this->pages = [];
72 return $this->pages[$pgno] = $this->parse($pgno);
73 }
74
75 /** Pagerのキャッシュが捨てられたら、こちらも捨てる */
76 private function sync(): void {
77 if ($this->generation !== $this->pager->generation) {
78 $this->pages = [];
79 $this->dirty = [];
80 $this->snaps = [];
81 $this->generation = $this->pager->generation;
82 }
83 }
84
85 /** キャッシュを捨てる（ロールバックの後） */
86 public function reset(): void {
87 $this->pages = [];
88 $this->dirty = [];
89 $this->snaps = [];
90 }
91
92 /** ページの変更前の状態を覚える（今のスナップショットで初めての場合） */
93 private function remember(int $pgno): void {
94 $k = array_key_last($this->snaps);
95 if (array_key_exists($pgno, $this->snaps[$k])) return;
96 $this->snaps[$k][$pgno] = isset($this->pages[$pgno]) ? [clone $this->pages[$pgno], isset($this->dirty[$pgno])] : null;
97 }
98
99 /**
100 * スナップショット（Pagerと一緒に使う。変更されたページをPagerに書かなくても、文だけを元に戻せる）
101 *
102 * @return int
103 */
104 public function snapPush(): int {
105 $this->sync();
106 $this->snaps[] = [];
107 return count($this->snaps) - 1;
108 }
109
110 /** スナップショットを捨てる（変更は残す） */
111 public function snapPop(?int $n): void {
112 if ($n === null) return;
113 while (count($this->snaps) > $n) {
114 $top = array_pop($this->snaps);
115 if ($this->snaps) {
116 $k = array_key_last($this->snaps);
117 $this->snaps[$k] += $top;
118 }
119 }
120 }
121
122 /** スナップショットの時に戻す（スナップショットは残す） */
123 public function snapRestore(?int $n): void {
124 if ($n === null || !isset($this->snaps[$n])) return;
125 $all = [];
126 for ($k = $n; $k < count($this->snaps); $k++) $all += $this->snaps[$k];
127 foreach ($all as $pgno => $e) {
128 if ($e === null) {
129 unset($this->pages[$pgno], $this->dirty[$pgno]);
130 } else {
131 $this->pages[$pgno] = $e[0];
132 if ($e[1]) $this->dirty[$pgno] = true;
133 else unset($this->dirty[$pgno]);
134 }
135 }
136 $this->snaps = array_slice($this->snaps, 0, $n);
137 $this->snaps[] = [];
138 }
139
140 private function parse(int $pgno): Page {
141 if ($pgno === 1 && $this->pager->nPages === 0) {
142 // 空のファイル：sqlite_schemaは空
143 $p = new Page(1);
144 $p->type = self::TABLE_LEAF;
145 return $p;
146 }
147 $raw = $this->pager->read($pgno);
148 $h = $pgno === 1 ? 100 : 0;
149 $p = new Page($pgno);
150 $p->type = ord($raw[$h]);
151 if (!in_array($p->type, [2, 5, 10, 13], true)) throw new DbException("データベースが壊れています（ページ{$pgno}の種類：{$p->type}）", 11, 'HY000');
152 $n = unpack('n', $raw, $h + 3)[1];
153 $leaf = $p->isLeaf();
154 $table = $p->isTable();
155 if (!$leaf) $p->right = unpack('N', $raw, $h + 8)[1];
156 $base = $h + ($leaf ? 8 : 12);
157 $ptrs = $n > 0 ? array_values(unpack("n{$n}", $raw, $base)) : [];
158 $size = 0;
159 foreach ($ptrs as $off) {
160 $pos = $off;
161 if (!$leaf) {
162 $p->left[] = unpack('N', $raw, $off)[1];
163 $pos += 4;
164 }
165 $start = $pos;
166 if ($table && !$leaf) {
167 $p->keys[] = Record::getVarint($raw, $pos);
168 } else {
169 $len = Record::getVarint($raw, $pos);
170 if ($table) $p->keys[] = Record::getVarint($raw, $pos);
171 $local = $this->localSize($len, $table);
172 $pos += $local + ($len > $local ? 4 : 0);
173 }
174 $p->cells[] = substr($raw, $start, $pos - $start);
175 $size += $pos - $off + 2;
176 }
177 $p->size = $size;
178 if (!$table) $p->dec = $n > 0 ? array_fill(0, $n, null) : [];
179 return $p;
180 }
181
182 private function serialize(Page $p): string {
183 $h = $p->pgno === 1 ? 100 : 0;
184 $leaf = $p->isLeaf();
185 $off = $this->pager->usable;
186 $ptrs = '';
187 $parts = [];
188 foreach ($p->cells as $i => $c) {
189 $cell = $leaf ? $c : pack('N', $p->left[$i]).$c;
190 $off -= strlen($cell);
191 $ptrs .= pack('n', $off);
192 $parts[] = $cell;
193 }
194 $n = count($p->cells);
195 $head = chr($p->type)."\0\0".pack('n', $n).pack('n', $off === 65536 ? 0 : $off)."\0".($leaf ? '' : pack('N', $p->right));
196 $gap = $off - ($h + strlen($head) + strlen($ptrs));
197 if ($gap < 0) throw new \LogicException("SQLite：ページ{$p->pgno}が溢れました");
198 $prefix = $h ? $this->pager->header() : '';
199 return $prefix.$head.$ptrs.str_repeat("\0", $gap).implode('', array_reverse($parts))
200 .str_repeat("\0", $this->pager->pageSize - $this->pager->usable);
201 }
202
203 /** 変更されたページ */
204 private function touch(Page $p): void {
205 $this->dirty[$p->pgno] = true;
206 }
207
208 /** 変更されたページが多ければPagerに書く（操作の間だけ。途中のページは溢れているかもしれない） */
209 private function spill(): void {
210 if (count($this->dirty) > 500) $this->flush();
211 }
212
213 /** 変更されたページをPagerに書く */
214 public function flush(): void {
215 foreach (array_keys($this->dirty) as $pgno) {
216 if (isset($this->pages[$pgno])) $this->pager->write($pgno, $this->serialize($this->pages[$pgno]));
217 }
218 $this->dirty = [];
219 }
220
221 private function newPage(int $type): Page {
222 $this->sync();
223 $pgno = $this->pager->allocate();
224 if ($this->snaps) $this->remember($pgno);
225 $p = new Page($pgno);
226 $p->type = $type;
227 $this->pages[$pgno] = $p;
228 $this->touch($p);
229 return $p;
230 }
231
232 private function freePage(int $pgno): void {
233 if ($this->snaps) $this->remember($pgno);
234 unset($this->pages[$pgno], $this->dirty[$pgno]);
235 $this->pager->free($pgno);
236 }
237
238 /** ページに入るセルの大きさ */
239 private function capacity(Page $p): int {
240 return $this->pager->usable - ($p->pgno === 1 ? 100 : 0) - ($p->isLeaf() ? 8 : 12);
241 }
242
243 private function cellSize(Page $p, string $cell): int {
244 return strlen($cell) + ($p->isLeaf() ? 2 : 6);
245 }
246
247 ///////////////
248 // ペイロードとオーバーフロー
249
250 /** ページに置くペイロードのバイト数（残りはオーバーフローのページ） */
251 public function localSize(int $len, bool $table): int {
252 $u = $this->pager->usable;
253 $x = $table ? $u - 35 : intdiv(($u - 12) * 64, 255) - 23;
254 if ($len <= $x) return $len;
255 $m = intdiv(($u - 12) * 32, 255) - 23;
256 $k = $m + (($len - $m) % ($u - 4));
257 return $k <= $x ? $k : $m;
258 }
259
260 /** セルのペイロードの全部 */
261 public function payload(Page $p, int $i): string {
262 $c = $p->cells[$i];
263 $pos = 0;
264 $len = Record::getVarint($c, $pos);
265 $table = $p->isTable();
266 if ($table) Record::getVarint($c, $pos);
267 $local = $this->localSize($len, $table);
268 $data = substr($c, $pos, $local);
269 if ($len > $local) {
270 $next = unpack('N', $c, $pos + $local)[1];
271 $rest = $len - $local;
272 $chunk = $this->pager->usable - 4;
273 while ($rest > 0) {
274 if ($next < 1) throw new DbException('データベースが壊れています（オーバーフロー）', 11, 'HY000');
275 $o = $this->pager->read($next);
276 $take = min($rest, $chunk);
277 $data .= substr($o, 4, $take);
278 $rest -= $take;
279 $next = unpack('N', $o)[1];
280 }
281 }
282 return $data;
283 }
284
285 /** インデックスのセルのキー（デコードした物） */
286 public function key(Page $p, int $i): array {
287 return $p->dec[$i] ??= Record::decode($this->payload($p, $i));
288 }
289
290 private function makeCell(string $payload, ?int $rowid): string {
291 $len = strlen($payload);
292 $table = $rowid !== null;
293 $head = Record::putVarint($len).($table ? Record::putVarint($rowid) : '');
294 $local = $this->localSize($len, $table);
295 if ($local >= $len) return $head.$payload;
296 $chunk = $this->pager->usable - 4;
297 $pieces = str_split(substr($payload, $local), $chunk);
298 $pgnos = [];
299 foreach ($pieces as $_) $pgnos[] = $this->pager->allocate();
300 foreach ($pieces as $k => $piece) {
301 $next = $pgnos[$k + 1] ?? 0;
302 $this->pager->write($pgnos[$k], str_pad(pack('N', $next).$piece, $this->pager->pageSize, "\0"));
303 }
304 return $head.substr($payload, 0, $local).pack('N', $pgnos[0]);
305 }
306
307 /** セルのオーバーフローのページを解放する */
308 private function freeOverflow(Page $p, string $c): void {
309 if (!$p->isLeaf() && $p->isTable()) return;
310 $pos = 0;
311 $len = Record::getVarint($c, $pos);
312 if ($p->isTable()) Record::getVarint($c, $pos);
313 $local = $this->localSize($len, $p->isTable());
314 if ($len <= $local) return;
315 $next = unpack('N', $c, $pos + $local)[1];
316 $n = intdiv($len - $local + $this->pager->usable - 5, $this->pager->usable - 4);
317 for ($k = 0; $k < $n && $next > 0; $k++) {
318 $o = $this->pager->read($next);
319 $this->freePage($next);
320 $next = unpack('N', $o)[1];
321 }
322 }
323
324 ///////////////
325 // テーブル
326
327 /** 新しいテーブル（又はインデックス）のツリー */
328 public function create(bool $table): int {
329 return $this->newPage($table ? self::TABLE_LEAF : self::INDEX_LEAF)->pgno;
330 }
331
332 private static function lowerBound(array $keys, int $k): int {
333 $lo = 0;
334 $hi = count($keys);
335 while ($lo < $hi) {
336 $mid = ($lo + $hi) >> 1;
337 if ($keys[$mid] < $k) $lo = $mid + 1;
338 else $hi = $mid;
339 }
340 return $lo;
341 }
342
343 private function child(Page $p, int $i): int {
344 return $i < count($p->cells) ? $p->left[$i] : $p->right;
345 }
346
347 /** @return array [path, 葉, 位置, 有るか] */
348 private function seek(int $root, int $rowid): array {
349 $path = [];
350 $p = $this->page($root);
351 while (!$p->isLeaf()) {
352 $i = self::lowerBound($p->keys, $rowid);
353 $path[] = [$p, $i];
354 $p = $this->page($this->child($p, $i));
355 }
356 $i = self::lowerBound($p->keys, $rowid);
357 return [$path, $p, $i, $i < count($p->keys) && $p->keys[$i] === $rowid];
358 }
359
360 /**
361 * 行を読む
362 *
363 * @return string|null レコード（無ければnull）
364 */
365 public function get(int $root, int $rowid): ?string {
366 [, $p, $i, $found] = $this->seek($root, $rowid);
367 return $found ? $this->payload($p, $i) : null;
368 }
369
370 /** 行を入れる（同じrowidが有れば置き換える） */
371 public function insert(int $root, int $rowid, string $record): void {
372 $this->spill();
373 [$path, $p, $i, $found] = $this->seek($root, $rowid);
374 $cell = $this->makeCell($record, $rowid);
375 if ($found) {
376 $this->freeOverflow($p, $p->cells[$i]);
377 $p->size += strlen($cell) - strlen($p->cells[$i]);
378 $p->cells[$i] = $cell;
379 } else {
380 array_splice($p->cells, $i, 0, [$cell]);
381 array_splice($p->keys, $i, 0, [$rowid]);
382 $p->size += strlen($cell) + 2;
383 }
384 $this->touch($p);
385 $this->fix($path, $p);
386 }
387
388 /** 行を消す */
389 public function delete(int $root, int $rowid): bool {
390 $this->spill();
391 [$path, $p, $i, $found] = $this->seek($root, $rowid);
392 if (!$found) return false;
393 $this->freeOverflow($p, $p->cells[$i]);
394 $p->size -= strlen($p->cells[$i]) + 2;
395 array_splice($p->cells, $i, 1);
396 array_splice($p->keys, $i, 1);
397 $this->touch($p);
398 $this->fix($path, $p);
399 return true;
400 }
401
402 /** 一番大きいrowid（空なら0） */
403 public function maxRowid(int $root): int {
404 $p = $this->page($root);
405 while (!$p->isLeaf()) $p = $this->page($p->right);
406 return empty($p->keys) ? 0 : end($p->keys);
407 }
408
409 /**
410 * テーブルの行を順番に
411 *
412 * @param int $root
413 * @param int|null $from 最小のrowid
414 * @param int|null $to 最大のrowid
415 * @return \Generator rowid => レコード
416 */
417 public function scan(int $root, ?int $from = null, ?int $to = null): \Generator {
418 $stop = false;
419 yield from $this->walkTable($root, $from, $to, $stop);
420 }
421
422 private function walkTable(int $pgno, ?int $from, ?int $to, bool &$stop): \Generator {
423 $p = $this->page($pgno);
424 $n = count($p->cells);
425 $i = $from === null ? 0 : self::lowerBound($p->keys, $from);
426 if ($p->isLeaf()) {
427 for (; $i < $n; $i++) {
428 if ($to !== null && $p->keys[$i] > $to) {
429 $stop = true;
430 return;
431 }
432 yield $p->keys[$i] => $this->payload($p, $i);
433 }
434 return;
435 }
436 for (; $i <= $n; $i++) {
437 yield from $this->walkTable($this->child($p, $i), $from, $to, $stop);
438 if ($stop || ($to !== null && $i < $n && $p->keys[$i] >= $to)) {
439 $stop = true;
440 return;
441 }
442 }
443 }
444
445 /** 行の数 */
446 public function count(int $root): int {
447 $p = $this->page($root);
448 if ($p->isLeaf()) return count($p->cells);
449 $n = 0;
450 for ($i = 0; $i <= count($p->cells); $i++) $n += $this->count($this->child($p, $i));
451 return $n;
452 }
453
454 /**
455 * ツリーを空にする（$dropならルートも解放する）
456 */
457 public function clear(int $root, bool $drop = false): void {
458 $p = $this->page($root);
459 $this->freeSubtree($p, false);
460 if ($drop) {
461 $this->freePage($root);
462 return;
463 }
464 $p->type = $p->isTable() ? self::TABLE_LEAF : self::INDEX_LEAF;
465 $p->cells = $p->left = $p->keys = $p->dec = [];
466 $p->right = 0;
467 $p->size = 0;
468 $this->touch($p);
469 }
470
471 private function freeSubtree(Page $p, bool $self): void {
472 foreach ($p->cells as $c) $this->freeOverflow($p, $c);
473 if (!$p->isLeaf()) {
474 for ($i = 0; $i <= count($p->cells); $i++) $this->freeSubtree($this->page($this->child($p, $i)), true);
475 }
476 if ($self) $this->freePage($p->pgno);
477 }
478
479 ///////////////
480 // インデックス
481
482 /**
483 * 最初の位置（キーの前方一致で比べる）
484 *
485 * @param bool $strict trueなら「＞」、falseなら「≧」
486 */
487 private function bound(Page $p, array $key, array $idx, bool $strict): int {
488 $lo = 0;
489 $hi = count($p->cells);
490 while ($lo < $hi) {
491 $mid = ($lo + $hi) >> 1;
492 $c = Record::compareKeys($this->key($p, $mid), $key, $idx['colls'], $idx['desc']);
493 if ($c < 0 || ($strict && $c === 0)) $lo = $mid + 1;
494 else $hi = $mid;
495 }
496 return $lo;
497 }
498
499 /**
500 * インデックスにキーを入れる
501 *
502 * @param array $idx root、colls、desc（rowidの列も含む）
503 * @param array $key 列の値…、rowid
504 */
505 public function indexInsert(array $idx, array $key): void {
506 $this->spill();
507 $path = [];
508 $p = $this->page($idx['root']);
509 while (true) {
510 $i = $this->bound($p, $key, $idx, false);
511 if ($i < count($p->cells) && count($this->key($p, $i)) === count($key)
512 && Record::compareKeys($this->key($p, $i), $key, $idx['colls'], $idx['desc']) === 0) return;
513 if ($p->isLeaf()) break;
514 $path[] = [$p, $i];
515 $p = $this->page($this->child($p, $i));
516 }
517 $cell = $this->makeCell(Record::encode($key), null);
518 array_splice($p->cells, $i, 0, [$cell]);
519 array_splice($p->dec, $i, 0, [$key]);
520 $p->size += strlen($cell) + 2;
521 $this->touch($p);
522 $this->fix($path, $p);
523 }
524
525 /**
526 * キーの前方一致の項目を探す（一意の制約の確認用）
527 *
528 * @param int|null $self 除くrowid
529 * @return int|null 見つけた項目のrowid
530 */
531 public function indexFind(array $idx, array $prefix, ?int $self = null): ?int {
532 $p = $this->page($idx['root']);
533 while (true) {
534 $i = $this->bound($p, $prefix, $idx, false);
535 if ($i < count($p->cells)) {
536 $k = $this->key($p, $i);
537 if (Record::compareKeys($k, $prefix, $idx['colls'], $idx['desc']) === 0) {
538 $id = end($k);
539 if ($id !== $self) return $id;
540 // 自分自身：他にも有るかもしれないので全部を見る
541 foreach ($this->indexScan($idx, $prefix, true, $prefix, true) as $k2) {
542 if (end($k2) !== $self) return end($k2);
543 }
544 return null;
545 }
546 }
547 if ($p->isLeaf()) return null;
548 $p = $this->page($this->child($p, $i));
549 }
550 }
551
552 /** インデックスからキーを消す */
553 public function indexDelete(array $idx, array $key): bool {
554 $this->spill();
555 $path = [];
556 $p = $this->page($idx['root']);
557 while (true) {
558 $i = $this->bound($p, $key, $idx, false);
559 if ($i < count($p->cells) && Record::compareKeys($this->key($p, $i), $key, $idx['colls'], $idx['desc']) === 0) break;
560 if ($p->isLeaf()) return false;
561 $path[] = [$p, $i];
562 $p = $this->page($this->child($p, $i));
563 }
564 $this->decAll($p);
565 if ($p->isLeaf()) {
566 $this->freeOverflow($p, $p->cells[$i]);
567 $p->size -= strlen($p->cells[$i]) + 2;
568 array_splice($p->cells, $i, 1);
569 array_splice($p->dec, $i, 1);
570 $this->touch($p);
571 $this->fix($path, $p);
572 return true;
573 }
574
575 // 内部のページ：左のツリーの一番大きいキーと置き換える
576 $pathL = array_merge($path, [[$p, $i]]);
577 $q = $this->page($p->left[$i]);
578 while (!$q->isLeaf()) {
579 $pathL[] = [$q, count($q->cells)];
580 $q = $this->page($q->right);
581 }
582 $this->decAll($q);
583 $last = count($q->cells) - 1;
584 $cell = $q->cells[$last];
585 $dec = $this->key($q, $last);
586 $q->size -= strlen($cell) + 2;
587 array_splice($q->cells, $last, 1);
588 array_splice($q->dec, $last, 1);
589 $this->freeOverflow($p, $p->cells[$i]);
590 $p->size += strlen($cell) - strlen($p->cells[$i]);
591 $p->cells[$i] = $cell;
592 $p->dec[$i] = $dec;
593 $this->touch($p);
594 $this->touch($q);
595 if ($this->fix($pathL, $q) > count($path)) $this->fix($path, $p);
596 return true;
597 }
598
599 /** decの配列をセルと同じ長さにする（array_spliceの前に） */
600 private function decAll(Page $p): void {
601 for ($i = 0, $n = count($p->cells); $i < $n; $i++) $p->dec[$i] ??= null;
602 ksort($p->dec);
603 }
604
605 /**
606 * インデックスの範囲
607 *
608 * @param array $idx
609 * @param array|null $lo 最小のキー（前方一致）
610 * @param bool $loInc 最小を含む
611 * @param array|null $hi 最大のキー（前方一致）
612 * @param bool $hiInc 最大を含む
613 * @return \Generator キー（列の値…、rowid）
614 */
615 public function indexScan(array $idx, ?array $lo = null, bool $loInc = true, ?array $hi = null, bool $hiInc = true): \Generator {
616 $stop = false;
617 yield from $this->walkIndex($idx['root'], $idx, $lo, $loInc, $hi, $hiInc, $stop);
618 }
619
620 private function walkIndex(int $pgno, array $idx, ?array $lo, bool $loInc, ?array $hi, bool $hiInc, bool &$stop): \Generator {
621 $p = $this->page($pgno);
622 $n = count($p->cells);
623 $i = $lo === null ? 0 : $this->bound($p, $lo, $idx, !$loInc);
624 $leaf = $p->isLeaf();
625 for (; $i <= $n; $i++) {
626 if (!$leaf) {
627 yield from $this->walkIndex($this->child($p, $i), $idx, $lo, $loInc, $hi, $hiInc, $stop);
628 if ($stop) return;
629 }
630 if ($i === $n) return;
631 $k = $this->key($p, $i);
632 if ($hi !== null) {
633 $c = Record::compareKeys($k, $hi, $idx['colls'], $idx['desc']);
634 if ($c > 0 || (!$hiInc && $c === 0)) {
635 $stop = true;
636 return;
637 }
638 }
639 yield $k;
640 }
641 }
642
643 ///////////////
644 // 釣り合い
645
646 /**
647 * 変更したページを直す（溢れた・少なくなったら兄弟と分け直す）
648 *
649 * @param array $path 親のページと位置の配列（ルートから）
650 * @param Page $p 変更したページ
651 * @return int 確認を終えた深さ（パスの長さ）
652 */
653 private function fix(array $path, Page $p): int {
654 while (true) {
655 $cap = $this->capacity($p);
656 $over = $p->size > $cap;
657 if (empty($path)) {
658 if ($over) {
659 $c = $this->deeper($p);
660 $path = [[$p, 0]];
661 $p = $c;
662 continue;
663 }
664 if (!$p->isLeaf() && empty($p->cells)) $this->shallower($p);
665 return 0;
666 }
667 $under = $p->size < intdiv($cap, 3);
668 if (!$over && !$under) return count($path);
669 [$parent, $idx] = array_pop($path);
670 if (!$over && empty($parent->cells)) {
671 // 兄弟が無い
672 $p = $parent;
673 continue;
674 }
675 $this->balance($parent, $idx);
676 $p = $parent;
677 }
678 }
679
680 /** ルートが溢れた：中身を新しいページに移して、ルートを1段上にする */
681 private function deeper(Page $root): Page {
682 $c = $this->newPage($root->type);
683 $c->cells = $root->cells;
684 $c->left = $root->left;
685 $c->keys = $root->keys;
686 $c->dec = $root->dec;
687 $c->right = $root->right;
688 $c->size = $root->size;
689 $root->type = $root->isTable() ? self::TABLE_INTERIOR : self::INDEX_INTERIOR;
690 $root->cells = $root->left = $root->keys = $root->dec = [];
691 $root->size = 0;
692 $root->right = $c->pgno;
693 $this->touch($root);
694 return $c;
695 }
696
697 /** ルートの子が1つだけ：子の中身をルートに入れる（入れば） */
698 private function shallower(Page $root): void {
699 $c = $this->page($root->right);
700 $cap = $this->pager->usable - ($root->pgno === 1 ? 100 : 0) - ($c->isLeaf() ? 8 : 12);
701 if ($c->size > $cap) return;
702 $this->decAll($c);
703 $root->type = $c->type;
704 $root->cells = $c->cells;
705 $root->left = $c->left;
706 $root->keys = $c->keys;
707 $root->dec = $c->dec;
708 $root->right = $c->right;
709 $root->size = $c->size;
710 $this->freePage($c->pgno);
711 $this->touch($root);
712 }
713
714 /** 親の$idx番目の子とその兄弟（最大3つ）のセルを分け直す */
715 private function balance(Page $parent, int $idx): void {
716 $n = count($parent->cells);
717 $first = max(0, $idx - 1);
718 $last = min($n, $first + 2);
719 $first = max(0, $last - 2);
720 $sibs = [];
721 for ($j = $first; $j <= $last; $j++) $sibs[] = $this->page($this->child($parent, $j));
722 $leaf = $sibs[0]->isLeaf();
723 $table = $sibs[0]->isTable();
724 $type = $sibs[0]->type;
725 if (!$table) $this->decAll($parent);
726
727 // 全部のセル（間の区切りも）
728 $items = [];
729 $lastRight = 0;
730 $ns = count($sibs);
731 foreach ($sibs as $j => $s) {
732 if ($s->isLeaf() !== $leaf) throw new DbException('データベースが壊れています（ツリーの深さ）', 11, 'HY000');
733 foreach ($s->cells as $i => $c) {
734 $items[] = [$c, $leaf ? 0 : $s->left[$i], $table ? $s->keys[$i] : 0, $table ? null : ($s->dec[$i] ?? null)];
735 }
736 if (!$leaf) $lastRight = $s->right;
737 if ($j < $ns - 1) {
738 $pi = $first + $j;
739 if ($table && $leaf) continue;
740 if ($table) {
741 $items[] = [Record::putVarint($parent->keys[$pi]), $s->right, $parent->keys[$pi], null];
742 } else {
743 $items[] = [$parent->cells[$pi], $leaf ? 0 : $s->right, 0, $parent->dec[$pi] ?? null];
744 }
745 }
746 }
747
748 $cap = $this->pager->usable - ($leaf ? 8 : 12);
749 $extra = $leaf ? 2 : 6;
750 [$groups, $divs] = $this->distribute($items, $cap, !($table && $leaf), $extra);
751 $k = count($groups);
752
753 $pgs = [];
754 for ($j = 0; $j < $k; $j++) $pgs[] = $j < $ns ? $sibs[$j] : $this->newPage($type);
755 for ($j = $k; $j < $ns; $j++) $this->freePage($sibs[$j]->pgno);
756
757 foreach ($groups as $j => $g) {
758 $pg = $pgs[$j];
759 $pg->type = $type;
760 $pg->cells = $pg->left = $pg->keys = $pg->dec = [];
761 $pg->size = 0;
762 foreach ($g as $it) {
763 $pg->cells[] = $it[0];
764 if (!$leaf) $pg->left[] = $it[1];
765 if ($table) $pg->keys[] = $it[2];
766 else $pg->dec[] = $it[3];
767 $pg->size += strlen($it[0]) + $extra;
768 }
769 if (!$leaf) $pg->right = $j < $k - 1 ? $divs[$j][1] : $lastRight;
770 $this->touch($pg);
771 }
772
773 // 親の区切り
774 $cells = $left = $keys = $dec = [];
775 for ($j = 0; $j < $k - 1; $j++) {
776 if ($table) {
777 $key = $leaf ? end($groups[$j])[2] : $divs[$j][2];
778 $cells[] = Record::putVarint($key);
779 $keys[] = $key;
780 } else {
781 $cells[] = $divs[$j][0];
782 $dec[] = $divs[$j][3];
783 }
784 $left[] = $pgs[$j]->pgno;
785 }
786 array_splice($parent->cells, $first, $ns - 1, $cells);
787 array_splice($parent->left, $first, $ns - 1, $left);
788 if ($table) array_splice($parent->keys, $first, $ns - 1, $keys);
789 else array_splice($parent->dec, $first, $ns - 1, $dec);
790 $slot = $first + $k - 1;
791 if ($slot < count($parent->cells)) $parent->left[$slot] = $pgs[$k - 1]->pgno;
792 else $parent->right = $pgs[$k - 1]->pgno;
793 $parent->size = 0;
794 foreach ($parent->cells as $c) $parent->size += strlen($c) + 6;
795 $this->touch($parent);
796 }
797
798 /**
799 * セルをページに分ける
800 *
801 * @param bool $promote グループの間のセルを親の区切りにする（テーブルの葉以外）
802 * @return array [グループの配列, 区切りの配列]
803 */
804 private function distribute(array $items, int $cap, bool $promote, int $extra): array {
805 $sizes = [];
806 $total = 0;
807 $max = 0;
808 foreach ($items as $it) {
809 $s = strlen($it[0]) + $extra;
810 $sizes[] = $s;
811 $total += $s;
812 $max = max($max, $s);
813 }
814 $pack = function(int $limit) use ($items, $sizes, $promote): array {
815 $groups = $divs = $cur = [];
816 $cs = 0;
817 foreach ($items as $i => $it) {
818 if ($cur && $cs + $sizes[$i] > $limit) {
819 $groups[] = $cur;
820 $cur = [];
821 $cs = 0;
822 if ($promote) {
823 $divs[] = $it;
824 continue;
825 }
826 }
827 $cur[] = $it;
828 $cs += $sizes[$i];
829 }
830 if ($cur || empty($groups)) {
831 $groups[] = $cur;
832 } else if ($promote) {
833 $groups[] = [array_pop($divs)];
834 }
835 return [$groups, $divs];
836 };
837 $res = $pack($cap);
838 $k = count($res[0]);
839 if ($k > 1) {
840 // なるべく同じ大きさに
841 $target = max($max, intdiv($total, $k));
842 $step = max(1, intdiv($cap - $target, 8));
843 for ($limit = $target; $limit < $cap; $limit += $step) {
844 $try = $pack($limit);
845 if (count($try[0]) === $k) {
846 $res = $try;
847 break;
848 }
849 }
850 }
851 return $res;
852 }
853}