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