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