Packages

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

Classes

  • NDevNullStorage
  • NFileJournal
  • NFileStorage
  • NMemcachedStorage
  • NMemoryStorage
  • NPhpFileStorage

Interfaces

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