1: <?php
   2: 
   3: /**
   4:  * This file is part of the Nette Framework (https://nette.org)
   5:  * Copyright (c) 2004 David Grudl (https://davidgrudl.com)
   6:  */
   7: 
   8: namespace Nette\Caching\Storages;
   9: 
  10: use Nette;
  11: use Nette\Caching\Cache;
  12: 
  13: 
  14: /**
  15:  * Btree+ based file journal.
  16:  *
  17:  * @author     Jakub Onderka
  18:  */
  19: class FileJournal extends Nette\Object implements IJournal
  20: {
  21:     /** Filename with journal */
  22:     const FILE = 'btfj.dat';
  23: 
  24:     /** 4 bytes file header magic (btfj) */
  25:     const FILE_MAGIC  = 0x6274666A;
  26: 
  27:     /** 4 bytes index node magic (inde) */
  28:     const INDEX_MAGIC = 0x696E6465;
  29: 
  30:     /** 4 bytes data node magic (data) */
  31:     const DATA_MAGIC  = 0x64617461;
  32: 
  33:     /** Node size in bytes */
  34:     const NODE_SIZE = 4096;
  35: 
  36:     /** Bit rotation for saving data into nodes. BITROT = log2(NODE_SIZE) */
  37:     const BITROT = 12;
  38: 
  39:     /** Header size in bytes */
  40:     const HEADER_SIZE = 4096;
  41: 
  42:     /** Size of 32 bit integer in bytes. INT32_SIZE = 32 / 8 :-) */
  43:     const INT32_SIZE  = 4;
  44: 
  45:     const INFO = 'i',
  46:         TYPE = 't', // TAGS, PRIORITY or DATA
  47:         IS_LEAF = 'il', // TRUE or FALSE
  48:         PREV_NODE = 'p', // Prev node id
  49:         END = 'e',
  50:         MAX = 'm', // Maximal key in node or -1 when is last node
  51:         INDEX_DATA = 'id',
  52:         LAST_INDEX = 'l';
  53: 
  54:     // Indexes
  55:     const TAGS = 't',
  56:         PRIORITY = 'p',
  57:         ENTRIES = 'e';
  58: 
  59:     const DATA = 'd',
  60:         KEY = 'k', // string
  61:         DELETED = 'd'; // TRUE or FALSE
  62: 
  63:     /** Debug mode, only for testing purposes */
  64:     public static $debug = FALSE;
  65: 
  66:     /** @var string */
  67:     private $file;
  68: 
  69:     /** @var resource */
  70:     private $handle;
  71: 
  72:     /** @var int Last complete free node */
  73:     private $lastNode = 2;
  74: 
  75:     /** @var string */
  76:     private $processIdentifier;
  77: 
  78:     /** @var array Cache and uncommitted but changed nodes */
  79:     private $nodeCache = array();
  80: 
  81:     /** @var array */
  82:     private $nodeChanged = array();
  83: 
  84:     /** @var array */
  85:     private $toCommit = array();
  86: 
  87:     /** @var array */
  88:     private $deletedLinks = array();
  89: 
  90:     /** @var array Free space in data nodes */
  91:     private $dataNodeFreeSpace = array();
  92: 
  93:     /** @var array */
  94:     private static $startNode = array(
  95:         self::TAGS     => 0,
  96:         self::PRIORITY => 1,
  97:         self::ENTRIES  => 2,
  98:         self::DATA     => 3,
  99:     );
 100: 
 101: 
 102:     /**
 103:      * @param  string  Directory containing journal file
 104:      */
 105:     public function __construct($dir)
 106:     {
 107:         $this->file = $dir . '/' . self::FILE;
 108:     }
 109: 
 110: 
 111:     /**
 112:      * @return void
 113:      */
 114:     public function __destruct()
 115:     {
 116:         if ($this->handle) {
 117:             $this->headerCommit();
 118:             flock($this->handle, LOCK_UN); // Since PHP 5.3.3 is manual unlock necessary
 119:             fclose($this->handle);
 120:             $this->handle = FALSE;
 121:         }
 122:     }
 123: 
 124: 
 125:     /**
 126:      * Writes entry information into the journal.
 127:      * @param  string
 128:      * @param  array
 129:      * @return void
 130:      */
 131:     public function write($key, array $dependencies)
 132:     {
 133:         $this->lock();
 134: 
 135:         $priority = !isset($dependencies[Cache::PRIORITY]) ? FALSE : (int) $dependencies[Cache::PRIORITY];
 136:         $tags = empty($dependencies[Cache::TAGS]) ? FALSE : (array) $dependencies[Cache::TAGS];
 137: 
 138:         $exists = FALSE;
 139:         $keyHash = crc32($key);
 140:         list($entriesNodeId, $entriesNode) = $this->findIndexNode(self::ENTRIES, $keyHash);
 141: 
 142:         if (isset($entriesNode[$keyHash])) {
 143:             $entries = $this->mergeIndexData($entriesNode[$keyHash]);
 144:             foreach ($entries as $link => $foo) {
 145:                 $dataNode = $this->getNode($link >> self::BITROT);
 146:                 if ($dataNode[$link][self::KEY] === $key) {
 147:                     if ($dataNode[$link][self::TAGS] == $tags && $dataNode[$link][self::PRIORITY] === $priority) { // intentionally ==, the order of tags does not matter
 148:                         if ($dataNode[$link][self::DELETED]) {
 149:                             $dataNode[$link][self::DELETED] = FALSE;
 150:                             $this->saveNode($link >> self::BITROT, $dataNode);
 151:                         }
 152:                         $exists = TRUE;
 153:                     } else { // Already exists, but with other tags or priority
 154:                         $toDelete = array();
 155:                         foreach ($dataNode[$link][self::TAGS] as $tag) {
 156:                             $toDelete[self::TAGS][$tag][$link] = TRUE;
 157:                         }
 158:                         if ($dataNode[$link][self::PRIORITY] !== FALSE) {
 159:                             $toDelete[self::PRIORITY][$dataNode[$link][self::PRIORITY]][$link] = TRUE;
 160:                         }
 161:                         $toDelete[self::ENTRIES][$keyHash][$link] = TRUE;
 162:                         $this->cleanFromIndex($toDelete);
 163: 
 164:                         unset($dataNode[$link]);
 165:                         $this->saveNode($link >> self::BITROT, $dataNode);
 166: 
 167:                         // Node was changed but may be empty, find it again
 168:                         list($entriesNodeId, $entriesNode) = $this->findIndexNode(self::ENTRIES, $keyHash);
 169:                     }
 170:                     break;
 171:                 }
 172:             }
 173:         }
 174: 
 175:         if ($exists === FALSE) {
 176:             // Magical constants
 177:             $requiredSize = strlen($key) + 75;
 178:             if ($tags) {
 179:                 foreach ($tags as $tag) {
 180:                     $requiredSize += strlen($tag) + 13;
 181:                 }
 182:             }
 183:             $requiredSize += $priority ? 10 : 1;
 184: 
 185:             $freeDataNode = $this->findFreeDataNode($requiredSize);
 186:             $data = $this->getNode($freeDataNode);
 187: 
 188:             if ($data === FALSE) {
 189:                 $data = array(
 190:                     self::INFO => array(
 191:                         self::LAST_INDEX => ($freeDataNode << self::BITROT),
 192:                         self::TYPE => self::DATA,
 193:                     )
 194:                 );
 195:             }
 196: 
 197:             $dataNodeKey = $this->findNextFreeKey($freeDataNode, $data);
 198:             $data[$dataNodeKey] = array(
 199:                 self::KEY => $key,
 200:                 self::TAGS => $tags ? $tags : array(),
 201:                 self::PRIORITY => $priority,
 202:                 self::DELETED => FALSE,
 203:             );
 204: 
 205:             $this->saveNode($freeDataNode, $data);
 206: 
 207:             // Save to entries tree, ...
 208:             $entriesNode[$keyHash][$dataNodeKey] = 1;
 209:             $this->saveNode($entriesNodeId, $entriesNode);
 210: 
 211:             // ...tags tree...
 212:             if ($tags) {
 213:                 foreach ($tags as $tag) {
 214:                     list($nodeId, $node) = $this->findIndexNode(self::TAGS, $tag);
 215:                     $node[$tag][$dataNodeKey] = 1;
 216:                     $this->saveNode($nodeId, $node);
 217:                 }
 218:             }
 219: 
 220:             // ...and priority tree.
 221:             if ($priority !== FALSE) {
 222:                 list($nodeId, $node) = $this->findIndexNode(self::PRIORITY, $priority);
 223:                 $node[$priority][$dataNodeKey] = 1;
 224:                 $this->saveNode($nodeId, $node);
 225:             }
 226:         }
 227: 
 228:         $this->commit();
 229:         $this->unlock();
 230:     }
 231: 
 232: 
 233:     /**
 234:      * Cleans entries from journal.
 235:      * @param  array
 236:      * @return array of removed items or NULL when performing a full cleanup
 237:      */
 238:     public function clean(array $conditions)
 239:     {
 240:         $this->lock();
 241: 
 242:         if (!empty($conditions[Cache::ALL])) {
 243:             $this->nodeCache = $this->nodeChanged = $this->dataNodeFreeSpace = array();
 244:             $this->deleteAll();
 245:             $this->unlock();
 246:             return NULL;
 247:         }
 248: 
 249:         $toDelete = array(
 250:             self::TAGS => array(),
 251:             self::PRIORITY => array(),
 252:             self::ENTRIES => array()
 253:         );
 254: 
 255:         $entries = array();
 256: 
 257:         if (!empty($conditions[Cache::TAGS])) {
 258:             $entries = $this->cleanTags((array) $conditions[Cache::TAGS], $toDelete);
 259:         }
 260: 
 261:         if (isset($conditions[Cache::PRIORITY])) {
 262:             $this->arrayAppend($entries, $this->cleanPriority((int) $conditions[Cache::PRIORITY], $toDelete));
 263:         }
 264: 
 265:         $this->deletedLinks = array();
 266:         $this->cleanFromIndex($toDelete);
 267: 
 268:         $this->commit();
 269:         $this->unlock();
 270: 
 271:         return $entries;
 272:     }
 273: 
 274: 
 275:     /**
 276:      * Cleans entries from journal by tags.
 277:      * @param  array
 278:      * @param  array
 279:      * @return array of removed items
 280:      */
 281:     private function cleanTags(array $tags, array & $toDelete)
 282:     {
 283:         $entries = array();
 284: 
 285:         foreach ($tags as $tag) {
 286:             list(, $node) = $this->findIndexNode(self::TAGS, $tag);
 287: 
 288:             if (isset($node[$tag])) {
 289:                 $ent = $this->cleanLinks($this->mergeIndexData($node[$tag]), $toDelete);
 290:                 $this->arrayAppend($entries, $ent);
 291:             }
 292:         }
 293: 
 294:         return $entries;
 295:     }
 296: 
 297: 
 298:     /**
 299:      * Cleans entries from journal by priority.
 300:      * @param  integer
 301:      * @param  array
 302:      * @return array of removed items
 303:      */
 304:     private function cleanPriority($priority, array & $toDelete)
 305:     {
 306:         list(, $node) = $this->findIndexNode(self::PRIORITY, $priority);
 307: 
 308:         ksort($node);
 309: 
 310:         $allData = array();
 311: 
 312:         foreach ($node as $prior => $data) {
 313:             if ($prior === self::INFO) {
 314:                 continue;
 315:             } elseif ($prior > $priority) {
 316:                 break;
 317:             }
 318: 
 319:             $this->arrayAppendKeys($allData, $this->mergeIndexData($data));
 320:         }
 321: 
 322:         $nodeInfo = $node[self::INFO];
 323:         while ($nodeInfo[self::PREV_NODE] !== -1) {
 324:             $nodeId = $nodeInfo[self::PREV_NODE];
 325:             $node = $this->getNode($nodeId);
 326: 
 327:             if ($node === FALSE) {
 328:                 if (self::$debug) {
 329:                     throw new Nette\InvalidStateException("Cannot load node number $nodeId.");
 330:                 }
 331:                 break;
 332:             }
 333: 
 334:             $nodeInfo = $node[self::INFO];
 335:             unset($node[self::INFO]);
 336: 
 337:             foreach ($node as $data) {
 338:                 $this->arrayAppendKeys($allData, $this->mergeIndexData($data));
 339:             }
 340:         }
 341: 
 342:         return $this->cleanLinks($allData, $toDelete);
 343:     }
 344: 
 345: 
 346:     /**
 347:      * Cleans links from $data.
 348:      * @param  array
 349:      * @param  array
 350:      * @return array of removed items
 351:      */
 352:     private function cleanLinks(array $data, array & $toDelete)
 353:     {
 354:         $return = array();
 355: 
 356:         $data = array_keys($data);
 357:         sort($data);
 358:         $max = count($data);
 359:         $data[] = 0;
 360:         $i = 0;
 361: 
 362:         while ($i < $max) {
 363:             $searchLink = $data[$i];
 364: 
 365:             if (isset($this->deletedLinks[$searchLink])) {
 366:                 ++$i;
 367:                 continue;
 368:             }
 369: 
 370:             $nodeId = $searchLink >> self::BITROT;
 371:             $node = $this->getNode($nodeId);
 372: 
 373:             if ($node === FALSE) {
 374:                 if (self::$debug) {
 375:                     throw new Nette\InvalidStateException("Cannot load node number $nodeId.");
 376:                 }
 377:                 ++$i;
 378:                 continue;
 379:             }
 380: 
 381:             do {
 382:                 $link = $data[$i];
 383: 
 384:                 if (isset($this->deletedLinks[$link])) {
 385:                     continue;
 386:                 } elseif (!isset($node[$link])) {
 387:                     if (self::$debug) {
 388:                         throw new Nette\InvalidStateException("Link with ID $searchLink is not in node $nodeId.");
 389:                     }
 390:                     continue;
 391:                 }
 392: 
 393:                 $nodeLink = & $node[$link];
 394:                 if (!$nodeLink[self::DELETED]) {
 395:                     $nodeLink[self::DELETED] = TRUE;
 396:                     $return[] = $nodeLink[self::KEY];
 397:                 } else {
 398:                     foreach ($nodeLink[self::TAGS] as $tag) {
 399:                         $toDelete[self::TAGS][$tag][$link] = TRUE;
 400:                     }
 401:                     if ($nodeLink[self::PRIORITY] !== FALSE) {
 402:                         $toDelete[self::PRIORITY][$nodeLink[self::PRIORITY]][$link] = TRUE;
 403:                     }
 404:                     $toDelete[self::ENTRIES][crc32($nodeLink[self::KEY])][$link] = TRUE;
 405:                     unset($node[$link]);
 406:                     $this->deletedLinks[$link] = TRUE;
 407:                 }
 408:             } while (($data[++$i] >> self::BITROT) === $nodeId);
 409: 
 410:             $this->saveNode($nodeId, $node);
 411:         }
 412: 
 413:         return $return;
 414:     }
 415: 
 416: 
 417:     /**
 418:      * Remove links to deleted keys from index.
 419:      * @param  array
 420:      */
 421:     private function cleanFromIndex(array $toDeleteFromIndex)
 422:     {
 423:         foreach ($toDeleteFromIndex as $type => $toDelete) {
 424:             ksort($toDelete);
 425: 
 426:             while (!empty($toDelete)) {
 427:                 reset($toDelete);
 428:                 $searchKey = key($toDelete);
 429:                 list($masterNodeId, $masterNode) = $this->findIndexNode($type, $searchKey);
 430: 
 431:                 if (!isset($masterNode[$searchKey])) {
 432:                     if (self::$debug) {
 433:                         throw new Nette\InvalidStateException('Bad index.');
 434:                     }
 435:                     unset($toDelete[$searchKey]);
 436:                     continue;
 437:                 }
 438: 
 439:                 foreach ($toDelete as $key => $links) {
 440:                     if (isset($masterNode[$key])) {
 441:                         foreach ($links as $link => $foo) {
 442:                             if (isset($masterNode[$key][$link])) {
 443:                                 unset($masterNode[$key][$link], $links[$link]);
 444:                             }
 445:                         }
 446: 
 447:                         if (!empty($links) && isset($masterNode[$key][self::INDEX_DATA])) {
 448:                             $this->cleanIndexData($masterNode[$key][self::INDEX_DATA], $links, $masterNode[$key]);
 449:                         }
 450: 
 451:                         if (empty($masterNode[$key])) {
 452:                             unset($masterNode[$key]);
 453:                         }
 454:                         unset($toDelete[$key]);
 455:                     } else {
 456:                         break;
 457:                     }
 458:                 }
 459:                 $this->saveNode($masterNodeId, $masterNode);
 460:             }
 461:         }
 462:     }
 463: 
 464: 
 465:     /**
 466:      * Merge data with index data in other nodes.
 467:      * @param  array
 468:      * @return array of merged items
 469:      */
 470:     private function mergeIndexData(array $data)
 471:     {
 472:         while (isset($data[self::INDEX_DATA])) {
 473:             $id = $data[self::INDEX_DATA];
 474:             unset($data[self::INDEX_DATA]);
 475:             $childNode = $this->getNode($id);
 476: 
 477:             if ($childNode === FALSE) {
 478:                 if (self::$debug) {
 479:                     throw new Nette\InvalidStateException("Cannot load node number $id.");
 480:                 }
 481:                 break;
 482:             }
 483: 
 484:             $this->arrayAppendKeys($data, $childNode[self::INDEX_DATA]);
 485:         }
 486: 
 487:         return $data;
 488:     }
 489: 
 490: 
 491:     /**
 492:      * Cleans links from other nodes.
 493:      * @param  int
 494:      * @param  array
 495:      * @param  array
 496:      * @return void
 497:      */
 498:     private function cleanIndexData($nextNodeId, array $links, & $masterNodeLink)
 499:     {
 500:         $prev = -1;
 501: 
 502:         while ($nextNodeId && !empty($links)) {
 503:             $nodeId = $nextNodeId;
 504:             $node = $this->getNode($nodeId);
 505: 
 506:             if ($node === FALSE) {
 507:                 if (self::$debug) {
 508:                     throw new Nette\InvalidStateException("Cannot load node number $nodeId.");
 509:                 }
 510:                 break;
 511:             }
 512: 
 513:             foreach ($links as $link => $foo) {
 514:                 if (isset($node[self::INDEX_DATA][$link])) {
 515:                     unset($node[self::INDEX_DATA][$link], $links[$link]);
 516:                 }
 517:             }
 518: 
 519:             if (isset($node[self::INDEX_DATA][self::INDEX_DATA])) {
 520:                 $nextNodeId = $node[self::INDEX_DATA][self::INDEX_DATA];
 521:             } else {
 522:                 $nextNodeId = FALSE;
 523:             }
 524: 
 525:             if (empty($node[self::INDEX_DATA]) || (count($node[self::INDEX_DATA]) === 1 && $nextNodeId)) {
 526:                 if ($prev === -1) {
 527:                     if ($nextNodeId === FALSE) {
 528:                         unset($masterNodeLink[self::INDEX_DATA]);
 529:                     } else {
 530:                         $masterNodeLink[self::INDEX_DATA] = $nextNodeId;
 531:                     }
 532:                 } else {
 533:                     $prevNode = $this->getNode($prev);
 534:                     if ($prevNode === FALSE) {
 535:                         if (self::$debug) {
 536:                             throw new Nette\InvalidStateException("Cannot load node number $prev.");
 537:                         }
 538:                     } else {
 539:                         if ($nextNodeId === FALSE) {
 540:                             unset($prevNode[self::INDEX_DATA][self::INDEX_DATA]);
 541:                             if (empty($prevNode[self::INDEX_DATA])) {
 542:                                 unset($prevNode[self::INDEX_DATA]);
 543:                             }
 544:                         } else {
 545:                             $prevNode[self::INDEX_DATA][self::INDEX_DATA] = $nextNodeId;
 546:                         }
 547: 
 548:                         $this->saveNode($prev, $prevNode);
 549:                     }
 550:                 }
 551:                 unset($node[self::INDEX_DATA]);
 552:             } else {
 553:                 $prev = $nodeId;
 554:             }
 555: 
 556:             $this->saveNode($nodeId, $node);
 557:         }
 558:     }
 559: 
 560: 
 561:     /**
 562:      * Get node from journal.
 563:      * @param  integer
 564:      * @return array
 565:      */
 566:     private function getNode($id)
 567:     {
 568:         // Load from cache
 569:         if (isset($this->nodeCache[$id])) {
 570:             return $this->nodeCache[$id];
 571:         }
 572: 
 573:         $binary = stream_get_contents($this->handle, self::NODE_SIZE, self::HEADER_SIZE + self::NODE_SIZE * $id);
 574: 
 575:         if (empty($binary)) {
 576:             // empty node, no Exception
 577:             return FALSE;
 578:         }
 579: 
 580:         list(, $magic, $length) = unpack('N2', $binary);
 581:         if ($magic !== self::INDEX_MAGIC && $magic !== self::DATA_MAGIC) {
 582:             if (!empty($magic)) {
 583:                 if (self::$debug) {
 584:                     throw new Nette\InvalidStateException("Node $id has malformed header.");
 585:                 }
 586:                 $this->deleteNode($id);
 587:             }
 588:             return FALSE;
 589:         }
 590: 
 591:         $data = substr($binary, 2 * self::INT32_SIZE, $length - 2 * self::INT32_SIZE);
 592: 
 593:         $node = @unserialize($data); // intentionally @
 594:         if ($node === FALSE) {
 595:             $this->deleteNode($id);
 596:             if (self::$debug) {
 597:                 throw new Nette\InvalidStateException("Cannot unserialize node number $id.");
 598:             }
 599:             return FALSE;
 600:         }
 601: 
 602:         // Save to cache and return
 603:         return $this->nodeCache[$id] = $node;
 604:     }
 605: 
 606: 
 607:     /**
 608:      * Save node to cache.
 609:      * @param  integer
 610:      * @param  array
 611:      * @return void
 612:      */
 613:     private function saveNode($id, array $node)
 614:     {
 615:         if (count($node) === 1) { // Nod contains only INFO
 616:             $nodeInfo = $node[self::INFO];
 617:             if ($nodeInfo[self::TYPE] !== self::DATA) {
 618: 
 619:                 if ($nodeInfo[self::END] !== -1) {
 620:                     $this->nodeCache[$id] = $node;
 621:                     $this->nodeChanged[$id] = TRUE;
 622:                     return;
 623:                 }
 624: 
 625:                 if ($nodeInfo[self::MAX] === -1) {
 626:                     $max = PHP_INT_MAX;
 627:                 } else {
 628:                     $max = $nodeInfo[self::MAX];
 629:                 }
 630: 
 631:                 list(, , $parentId) = $this->findIndexNode($nodeInfo[self::TYPE], $max, $id);
 632:                 if ($parentId !== -1 && $parentId !== $id) {
 633:                     $parentNode = $this->getNode($parentId);
 634:                     if ($parentNode === FALSE) {
 635:                         if (self::$debug) {
 636:                             throw new Nette\InvalidStateException("Cannot load node number $parentId.");
 637:                         }
 638:                     } else {
 639:                         if ($parentNode[self::INFO][self::END] === $id) {
 640:                             if (count($parentNode) === 1) {
 641:                                 $parentNode[self::INFO][self::END] = -1;
 642:                             } else {
 643:                                 end($parentNode);
 644:                                 $lastKey = key($parentNode);
 645:                                 $parentNode[self::INFO][self::END] = $parentNode[$lastKey];
 646:                                 unset($parentNode[$lastKey]);
 647:                             }
 648:                         } else {
 649:                             unset($parentNode[$nodeInfo[self::MAX]]);
 650:                         }
 651: 
 652:                         $this->saveNode($parentId, $parentNode);
 653:                     }
 654:                 }
 655: 
 656:                 if ($nodeInfo[self::TYPE] === self::PRIORITY) { // only priority tree has link to prevNode
 657:                     if ($nodeInfo[self::MAX] === -1) {
 658:                         if ($nodeInfo[self::PREV_NODE] !== -1) {
 659:                             $prevNode = $this->getNode($nodeInfo[self::PREV_NODE]);
 660:                             if ($prevNode === FALSE) {
 661:                                 if (self::$debug) {
 662:                                     throw new Nette\InvalidStateException("Cannot load node number {$nodeInfo[self::PREV_NODE]}.");
 663:                                 }
 664:                             } else {
 665:                                 $prevNode[self::INFO][self::MAX] = -1;
 666:                                 $this->saveNode($nodeInfo[self::PREV_NODE], $prevNode);
 667:                             }
 668:                         }
 669:                     } else {
 670:                         list($nextId, $nextNode) = $this->findIndexNode($nodeInfo[self::TYPE], $nodeInfo[self::MAX] + 1, NULL, $id);
 671:                         if ($nextId !== -1 && $nextId !== $id) {
 672:                             $nextNode[self::INFO][self::PREV_NODE] = $nodeInfo[self::PREV_NODE];
 673:                             $this->saveNode($nextId, $nextNode);
 674:                         }
 675:                     }
 676:                 }
 677:             }
 678:             $this->nodeCache[$id] = FALSE;
 679:         } else {
 680:             $this->nodeCache[$id] = $node;
 681:         }
 682:         $this->nodeChanged[$id] = TRUE;
 683:     }
 684: 
 685: 
 686:     /**
 687:      * Commit all changed nodes from cache to journal file.
 688:      * @return void
 689:      */
 690:     private function commit()
 691:     {
 692:         do {
 693:             foreach ($this->nodeChanged as $id => $foo) {
 694:                 if ($this->prepareNode($id, $this->nodeCache[$id])) {
 695:                     unset($this->nodeChanged[$id]);
 696:                 }
 697:             }
 698:         } while (!empty($this->nodeChanged));
 699: 
 700:         foreach ($this->toCommit as $node => $str) {
 701:             $this->commitNode($node, $str);
 702:         }
 703:         $this->toCommit = array();
 704:     }
 705: 
 706: 
 707:     /**
 708:      * Prepare node to journal file structure.
 709:      * @param  integer
 710:      * @param  array|bool
 711:      * @return bool Successfully committed
 712:      */
 713:     private function prepareNode($id, $node)
 714:     {
 715:         if ($node === FALSE) {
 716:             if ($id < $this->lastNode) {
 717:                 $this->lastNode = $id;
 718:             }
 719:             unset($this->nodeCache[$id]);
 720:             unset($this->dataNodeFreeSpace[$id]);
 721:             $this->deleteNode($id);
 722:             return TRUE;
 723:         }
 724: 
 725:         $data = serialize($node);
 726:         $dataSize = strlen($data) + 2 * self::INT32_SIZE;
 727: 
 728:         $isData = $node[self::INFO][self::TYPE] === self::DATA;
 729:         if ($dataSize > self::NODE_SIZE) {
 730:             if ($isData) {
 731:                 throw new Nette\InvalidStateException('Saving node is bigger than maximum node size.');
 732:             } else {
 733:                 $this->bisectNode($id, $node);
 734:                 return FALSE;
 735:             }
 736:         }
 737: 
 738:         $this->toCommit[$id] = pack('N2', $isData ? self::DATA_MAGIC : self::INDEX_MAGIC, $dataSize) . $data;
 739: 
 740:         if ($this->lastNode < $id) {
 741:             $this->lastNode = $id;
 742:         }
 743:         if ($isData) {
 744:             $this->dataNodeFreeSpace[$id] = self::NODE_SIZE - $dataSize;
 745:         }
 746: 
 747:         return TRUE;
 748:     }
 749: 
 750: 
 751:     /**
 752:      * Commit node string to journal file.
 753:      * @param  integer
 754:      * @param  string
 755:      * @return void
 756:      */
 757:     private function commitNode($id, $str)
 758:     {
 759:         fseek($this->handle, self::HEADER_SIZE + self::NODE_SIZE * $id);
 760:         $written = fwrite($this->handle, $str);
 761:         if ($written === FALSE) {
 762:             throw new Nette\InvalidStateException("Cannot write node number $id to journal.");
 763:         }
 764:     }
 765: 
 766: 
 767:     /**
 768:      * Find right node in B+tree. .
 769:      * @param  string Tree type (TAGS, PRIORITY or ENTRIES)
 770:      * @param  int    Searched item
 771:      * @return array Node
 772:      */
 773:     private function findIndexNode($type, $search, $childId = NULL, $prevId = NULL)
 774:     {
 775:         $nodeId = self::$startNode[$type];
 776: 
 777:         $parentId = -1;
 778:         while (TRUE) {
 779:             $node = $this->getNode($nodeId);
 780: 
 781:             if ($node === FALSE) {
 782:                 return array(
 783:                     $nodeId,
 784:                     array(
 785:                         self::INFO => array(
 786:                             self::TYPE => $type,
 787:                             self::IS_LEAF => TRUE,
 788:                             self::PREV_NODE => -1,
 789:                             self::END => -1,
 790:                             self::MAX => -1,
 791:                         )
 792:                     ),
 793:                     $parentId,
 794:                 ); // Init empty node
 795:             }
 796: 
 797:             if ($node[self::INFO][self::IS_LEAF] || $nodeId === $childId || $node[self::INFO][self::PREV_NODE] === $prevId) {
 798:                 return array($nodeId, $node, $parentId);
 799:             }
 800: 
 801:             $parentId = $nodeId;
 802: 
 803:             if (isset($node[$search])) {
 804:                 $nodeId = $node[$search];
 805:             } else {
 806:                 foreach ($node as $key => $childNode) {
 807:                     if ($key > $search && $key !== self::INFO) {
 808:                         $nodeId = $childNode;
 809:                         continue 2;
 810:                     }
 811:                 }
 812: 
 813:                 $nodeId = $node[self::INFO][self::END];
 814:             }
 815:         }
 816:     }
 817: 
 818: 
 819:     /**
 820:      * Find complete free node.
 821:      * @param  integer
 822:      * @return array|integer Node ID
 823:      */
 824:     private function findFreeNode($count = 1)
 825:     {
 826:         $id = $this->lastNode;
 827:         $nodesId = array();
 828: 
 829:         do {
 830:             if (isset($this->nodeCache[$id])) {
 831:                 ++$id;
 832:                 continue;
 833:             }
 834: 
 835:             $offset = self::HEADER_SIZE + self::NODE_SIZE * $id;
 836: 
 837:             $binary = stream_get_contents($this->handle, self::INT32_SIZE, $offset);
 838: 
 839:             if (empty($binary)) {
 840:                 $nodesId[] = $id;
 841:             } else {
 842:                 list(, $magic) = unpack('N', $binary);
 843:                 if ($magic !== self::INDEX_MAGIC && $magic !== self::DATA_MAGIC) {
 844:                     $nodesId[] = $id;
 845:                 }
 846:             }
 847: 
 848:             ++$id;
 849:         } while (count($nodesId) !== $count);
 850: 
 851:         if ($count === 1) {
 852:             return $nodesId[0];
 853:         } else {
 854:             return $nodesId;
 855:         }
 856:     }
 857: 
 858: 
 859:     /**
 860:      * Find free data node that has $size bytes of free space.
 861:      * @param  integer size in bytes
 862:      * @return integer Node ID
 863:      */
 864:     private function findFreeDataNode($size)
 865:     {
 866:         foreach ($this->dataNodeFreeSpace as $id => $freeSpace) {
 867:             if ($freeSpace > $size) {
 868:                 return $id;
 869:             }
 870:         }
 871: 
 872:         $id = self::$startNode[self::DATA];
 873:         while (TRUE) {
 874:             if (isset($this->dataNodeFreeSpace[$id]) || isset($this->nodeCache[$id])) {
 875:                 ++$id;
 876:                 continue;
 877:             }
 878: 
 879:             $offset = self::HEADER_SIZE + self::NODE_SIZE * $id;
 880:             $binary = stream_get_contents($this->handle, 2 * self::INT32_SIZE, $offset);
 881: 
 882:             if (empty($binary)) {
 883:                 $this->dataNodeFreeSpace[$id] = self::NODE_SIZE;
 884:                 return $id;
 885:             }
 886: 
 887:             list(, $magic, $nodeSize) = unpack('N2', $binary);
 888:             if (empty($magic)) {
 889:                 $this->dataNodeFreeSpace[$id] = self::NODE_SIZE;
 890:                 return $id;
 891:             } elseif ($magic === self::DATA_MAGIC) {
 892:                 $freeSpace = self::NODE_SIZE - $nodeSize;
 893:                 $this->dataNodeFreeSpace[$id] = $freeSpace;
 894: 
 895:                 if ($freeSpace > $size) {
 896:                     return $id;
 897:                 }
 898:             }
 899: 
 900:             ++$id;
 901:         }
 902:     }
 903: 
 904: 
 905:     /**
 906:      * Bisect node or when has only one key, move part to data node.
 907:      * @param  integer Node ID
 908:      * @param  array Node
 909:      * @return void
 910:      */
 911:     private function bisectNode($id, array $node)
 912:     {
 913:         $nodeInfo = $node[self::INFO];
 914:         unset($node[self::INFO]);
 915: 
 916:         if (count($node) === 1) {
 917:             $key = key($node);
 918: 
 919:             $dataId = $this->findFreeDataNode(self::NODE_SIZE);
 920:             $this->saveNode($dataId, array(
 921:                 self::INDEX_DATA => $node[$key],
 922:                 self::INFO => array(
 923:                     self::TYPE => self::DATA,
 924:                     self::LAST_INDEX => ($dataId << self::BITROT),
 925:             )));
 926: 
 927:             unset($node[$key]);
 928:             $node[$key][self::INDEX_DATA] = $dataId;
 929:             $node[self::INFO] = $nodeInfo;
 930: 
 931:             $this->saveNode($id, $node);
 932:             return;
 933:         }
 934: 
 935:         ksort($node);
 936:         $halfCount = ceil(count($node) / 2);
 937: 
 938:         list($first, $second) = array_chunk($node, $halfCount, TRUE);
 939: 
 940:         end($first);
 941:         $halfKey = key($first);
 942: 
 943:         if ($id <= 2) { // Root
 944:             list($firstId, $secondId) = $this->findFreeNode(2);
 945: 
 946:             $first[self::INFO] = array(
 947:                 self::TYPE => $nodeInfo[self::TYPE],
 948:                 self::IS_LEAF => $nodeInfo[self::IS_LEAF],
 949:                 self::PREV_NODE => -1,
 950:                 self::END => -1,
 951:                 self::MAX => $halfKey,
 952:             );
 953:             $this->saveNode($firstId, $first);
 954: 
 955:             $second[self::INFO] = array(
 956:                 self::TYPE => $nodeInfo[self::TYPE],
 957:                 self::IS_LEAF => $nodeInfo[self::IS_LEAF],
 958:                 self::PREV_NODE => $firstId,
 959:                 self::END => $nodeInfo[self::END],
 960:                 self::MAX => -1,
 961:             );
 962:             $this->saveNode($secondId, $second);
 963: 
 964:             $parentNode = array(
 965:                 self::INFO => array(
 966:                     self::TYPE => $nodeInfo[self::TYPE],
 967:                     self::IS_LEAF => FALSE,
 968:                     self::PREV_NODE => -1,
 969:                     self::END => $secondId,
 970:                     self::MAX => -1,
 971:                 ),
 972:                 $halfKey => $firstId,
 973:             );
 974:             $this->saveNode($id, $parentNode);
 975:         } else {
 976:             $firstId = $this->findFreeNode();
 977: 
 978:             $first[self::INFO] = array(
 979:                 self::TYPE => $nodeInfo[self::TYPE],
 980:                 self::IS_LEAF => $nodeInfo[self::IS_LEAF],
 981:                 self::PREV_NODE => $nodeInfo[self::PREV_NODE],
 982:                 self::END => -1,
 983:                 self::MAX => $halfKey,
 984:             );
 985:             $this->saveNode($firstId, $first);
 986: 
 987:             $second[self::INFO] = array(
 988:                 self::TYPE => $nodeInfo[self::TYPE],
 989:                 self::IS_LEAF => $nodeInfo[self::IS_LEAF],
 990:                 self::PREV_NODE => $firstId,
 991:                 self::END => $nodeInfo[self::END],
 992:                 self::MAX => $nodeInfo[self::MAX],
 993:             );
 994:             $this->saveNode($id, $second);
 995: 
 996:             list(,, $parent) = $this->findIndexNode($nodeInfo[self::TYPE], $halfKey);
 997:             $parentNode = $this->getNode($parent);
 998:             if ($parentNode === FALSE) {
 999:                 if (self::$debug) {
1000:                     throw new Nette\InvalidStateException("Cannot load node number $parent.");
1001:                 }
1002:             } else {
1003:                 $parentNode[$halfKey] = $firstId;
1004:                 ksort($parentNode); // Parent index must be always sorted.
1005:                 $this->saveNode($parent, $parentNode);
1006:             }
1007:         }
1008:     }
1009: 
1010: 
1011:     /**
1012:      * Commit header to journal file.
1013:      * @return void
1014:      */
1015:     private function headerCommit()
1016:     {
1017:         fseek($this->handle, self::INT32_SIZE);
1018:         @fwrite($this->handle, pack('N', $this->lastNode));  // intentionally @, save is not necessary
1019:     }
1020: 
1021: 
1022:     /**
1023:      * Remove node from journal file.
1024:      * @param  integer
1025:      * @return void
1026:      */
1027:     private function deleteNode($id)
1028:     {
1029:         fseek($this->handle, 0, SEEK_END);
1030:         $end = ftell($this->handle);
1031: 
1032:         if ($end <= (self::HEADER_SIZE + self::NODE_SIZE * ($id + 1))) {
1033:             $packedNull = pack('N', 0);
1034: 
1035:             do {
1036:                 $binary = stream_get_contents($this->handle, self::INT32_SIZE, (self::HEADER_SIZE + self::NODE_SIZE * --$id));
1037:             } while (empty($binary) || $binary === $packedNull);
1038: 
1039:             if (!ftruncate($this->handle, self::HEADER_SIZE + self::NODE_SIZE * ($id + 1))) {
1040:                 throw new Nette\InvalidStateException('Cannot truncate journal file.');
1041:             }
1042:         } else {
1043:             fseek($this->handle, self::HEADER_SIZE + self::NODE_SIZE * $id);
1044:             $written = fwrite($this->handle, pack('N', 0));
1045:             if ($written !== self::INT32_SIZE) {
1046:                 throw new Nette\InvalidStateException("Cannot delete node number $id from journal.");
1047:             }
1048:         }
1049:     }
1050: 
1051: 
1052:     /**
1053:      * Complete delete all nodes from file.
1054:      * @throws \Nette\InvalidStateException
1055:      */
1056:     private function deleteAll()
1057:     {
1058:         if (!ftruncate($this->handle, self::HEADER_SIZE)) {
1059:             throw new Nette\InvalidStateException('Cannot truncate journal file.');
1060:         }
1061:     }
1062: 
1063: 
1064:     /**
1065:      * Lock file for writing and reading and delete node cache when file has changed.
1066:      * @throws \Nette\InvalidStateException
1067:      */
1068:     private function lock()
1069:     {
1070:         if (!$this->handle) {
1071:             $this->prepare();
1072:         }
1073: 
1074:         if (!flock($this->handle, LOCK_EX)) {
1075:             throw new Nette\InvalidStateException("Cannot acquire exclusive lock on journal file '$this->file'.");
1076:         }
1077: 
1078:         $lastProcessIdentifier = stream_get_contents($this->handle, self::INT32_SIZE, self::INT32_SIZE * 2);
1079:         if ($lastProcessIdentifier !== $this->processIdentifier) {
1080:             $this->nodeCache = $this->dataNodeFreeSpace = array();
1081: 
1082:             // Write current processIdentifier to file header
1083:             fseek($this->handle, self::INT32_SIZE * 2);
1084:             fwrite($this->handle, $this->processIdentifier);
1085:         }
1086:     }
1087: 
1088: 
1089:     /**
1090:      * Open btfj.dat file (or create it if not exists) and load metainformation
1091:      * @throws \Nette\InvalidStateException
1092:      */
1093:     private function prepare()
1094:     {
1095:         // Create journal file when not exists
1096:         if (!file_exists($this->file)) {
1097:             $init = @fopen($this->file, 'xb'); // intentionally @
1098:             if (!$init) {
1099:                 clearstatcache();
1100:                 if (!file_exists($this->file)) {
1101:                     throw new Nette\InvalidStateException("Cannot create journal file '$this->file'.");
1102:                 }
1103:             } else {
1104:                 $written = fwrite($init, pack('N2', self::FILE_MAGIC, $this->lastNode));
1105:                 fclose($init);
1106:                 if ($written !== self::INT32_SIZE * 2) {
1107:                     throw new Nette\InvalidStateException("Cannot write journal header.");
1108:                 }
1109:             }
1110:         }
1111: 
1112:         $this->handle = fopen($this->file, 'r+b');
1113: 
1114:         if (!$this->handle) {
1115:             throw new Nette\InvalidStateException("Cannot open journal file '$this->file'.");
1116:         }
1117: 
1118:         if (!flock($this->handle, LOCK_SH)) {
1119:             throw new Nette\InvalidStateException('Cannot acquire shared lock on journal.');
1120:         }
1121: 
1122:         $header = stream_get_contents($this->handle, 2 * self::INT32_SIZE, 0);
1123: 
1124:         flock($this->handle, LOCK_UN);
1125: 
1126:         list(, $fileMagic, $this->lastNode) = unpack('N2', $header);
1127: 
1128:         if ($fileMagic !== self::FILE_MAGIC) {
1129:             fclose($this->handle);
1130:             $this->handle = FALSE;
1131:             throw new Nette\InvalidStateException("Malformed journal file '$this->file'.");
1132:         }
1133: 
1134:         $this->processIdentifier = pack('N', mt_rand());
1135:     }
1136: 
1137: 
1138:     /**
1139:      * Unlock file and save last modified time.
1140:      * @return void
1141:      */
1142:     private function unlock()
1143:     {
1144:         if ($this->handle) {
1145:             fflush($this->handle);
1146:             flock($this->handle, LOCK_UN);
1147:         }
1148:     }
1149: 
1150: 
1151:     /**
1152:      * @param  int $nodeId
1153:      * @param  array $nodeData
1154:      * @return int
1155:      * @throws \Nette\InvalidStateException
1156:      */
1157:     private function findNextFreeKey($nodeId, array & $nodeData)
1158:     {
1159:         $newKey = $nodeData[self::INFO][self::LAST_INDEX] + 1;
1160:         $maxKey = ($nodeId + 1) << self::BITROT;
1161: 
1162:         if ($newKey >= $maxKey) {
1163:             $start = $nodeId << self::BITROT;
1164:             for ($i = $start; $i < $maxKey; $i++) {
1165:                 if (!isset($nodeData[$i])) {
1166:                     return $i;
1167:                 }
1168:             }
1169:             throw new Nette\InvalidStateException("Node $nodeId is full.");
1170:         } else {
1171:             return ++$nodeData[self::INFO][self::LAST_INDEX];
1172:         }
1173:     }
1174: 
1175: 
1176:     /**
1177:      * Append $append to $array.
1178:      * This function is much faster then $array = array_merge($array, $append)
1179:      * @param  array
1180:      * @param  array
1181:      * @return void
1182:      */
1183:     private function arrayAppend(array & $array, array $append)
1184:     {
1185:         foreach ($append as $value) {
1186:             $array[] = $value;
1187:         }
1188:     }
1189: 
1190: 
1191:     /**
1192:      * Append $append to $array with preserve keys.
1193:      * This function is much faster then $array = $array + $append
1194:      * @param  array
1195:      * @param  array
1196:      * @return void
1197:      */
1198:     private function arrayAppendKeys(array & $array, array $append)
1199:     {
1200:         foreach ($append as $key => $value) {
1201:             $array[$key] = $value;
1202:         }
1203:     }
1204: }
1205: