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