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