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