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