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