Packages

  • Nette
    • Application
      • Diagnostics
      • Responses
      • Routers
      • UI
    • Caching
      • Storages
    • ComponentModel
    • Config
      • Adapters
      • Extensions
    • Database
      • Diagnostics
      • Drivers
      • Reflection
      • Table
    • DI
      • Diagnostics
    • Diagnostics
    • Forms
      • Controls
      • Rendering
    • Http
    • Iterators
    • Latte
      • Macros
    • Loaders
    • Localization
    • Mail
    • Reflection
    • Security
      • Diagnostics
    • Templating
    • Utils
      • PhpGenerator
  • NetteModule
  • None
  • PHP

Classes

  • DevNullStorage
  • FileJournal
  • FileStorage
  • MemcachedStorage
  • MemoryStorage
  • PhpFileStorage

Interfaces

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