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