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