Namespaces

  • 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

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