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