1: <?php
2:
3: 4: 5: 6: 7: 8: 9: 10:
11:
12: namespace Nette\Caching;
13:
14: use Nette;
15:
16:
17:
18: 19: 20: 21: 22:
23: class FileJournal extends Nette\Object implements ICacheJournal
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 HEADER_SIZE = 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 $lastModTime = NULL;
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: 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 \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 \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 \InvalidStateException("Cannot open journal file '$this->file'.");
136: }
137:
138: if (!flock($this->handle, LOCK_SH)) {
139: throw new \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 \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:
326: private function cleanTags(array $tags, array &$toDelete)
327: {
328: $entries = array();
329:
330: foreach ($tags as $tag) {
331: list($nodeId, $node) = $this->findIndexNode(self::TAGS, $tag);
332:
333: if (isset($node[$tag])) {
334: $ent = $this->cleanLinks($this->mergeIndexData($node[$tag]), $toDelete);
335: $this->arrayAppend($entries, $ent);
336: }
337: }
338:
339: return $entries;
340: }
341:
342:
343:
344: 345: 346: 347: 348: 349:
350: private function cleanPriority($priority, array &$toDelete)
351: {
352: list($nodeId, $node) = $this->findIndexNode(self::PRIORITY, $priority);
353:
354: ksort($node);
355:
356: $allData = array();
357:
358: foreach ($node as $prior => $data) {
359: if ($prior === self::INFO) {
360: continue;
361: } elseif ($prior > $priority) {
362: break;
363: }
364:
365: $this->arrayAppendKeys($allData, $this->mergeIndexData($data));
366: }
367:
368: $nodeInfo = $node[self::INFO];
369: while ($nodeInfo[self::PREV_NODE] !== -1) {
370: $nodeId = $nodeInfo[self::PREV_NODE];
371: $node = $this->getNode($nodeId);
372:
373: if ($node === FALSE) {
374: if (self::$debug) throw new \InvalidStateException("Cannot load node number $nodeId.");
375: break;
376: }
377:
378: $nodeInfo = $node[self::INFO];
379: unset($node[self::INFO]);
380:
381: foreach ($node as $prior => $data) {
382: $this->arrayAppendKeys($allData, $this->mergeIndexData($data));
383: }
384: }
385:
386: return $this->cleanLinks($allData, $toDelete);
387: }
388:
389:
390:
391: 392: 393: 394: 395: 396:
397: private function cleanLinks(array $data, array &$toDelete)
398: {
399: $return = array();
400:
401: $data = array_keys($data);
402: sort($data);
403: $max = count($data);
404: $data[] = 0;
405: $i = 0;
406:
407: while ($i < $max) {
408: $searchLink = $data[$i];
409:
410: if (isset($this->deletedLinks[$searchLink])) {
411: ++$i;
412: continue;
413: }
414:
415: $nodeId = $searchLink >> self::BITROT;
416: $node = $this->getNode($nodeId);
417:
418: if ($node === FALSE) {
419: if (self::$debug) throw new \InvalidStateException('Cannot load node number ' . ($nodeId) . '.');
420: ++$i;
421: continue;
422: }
423:
424: do {
425: $link = $data[$i];
426:
427: if (!isset($node[$link])) {
428: if (self::$debug) throw new \InvalidStateException("Link with ID $searchLink is not in node ". ($nodeId) . '.');
429: continue;
430: } elseif (isset($this->deletedLinks[$link])) {
431: continue;
432: }
433:
434: $nodeLink = &$node[$link];
435: if (!$nodeLink[self::DELETED]) {
436: $nodeLink[self::DELETED] = TRUE;
437: $return[] = $nodeLink[self::KEY];
438: } else {
439: foreach ($nodeLink[self::TAGS] as $tag) {
440: $toDelete[self::TAGS][$tag][$link] = TRUE;
441: }
442: if ($nodeLink[self::PRIORITY] !== FALSE) {
443: $toDelete[self::PRIORITY][$nodeLink[self::PRIORITY]][$link] = TRUE;
444: }
445: $toDelete[self::ENTRIES][crc32($nodeLink[self::KEY])][$link] = TRUE;
446: unset($node[$link]);
447: $this->deletedLinks[$link] = TRUE;
448: }
449: } while (($data[++$i] >> self::BITROT) === $nodeId);
450:
451: $this->saveNode($nodeId, $node);
452: }
453:
454: return $return;
455: }
456:
457:
458:
459: 460: 461: 462:
463: private function cleanFromIndex(array $toDeleteFromIndex)
464: {
465: foreach ($toDeleteFromIndex as $type => $toDelete) {
466: ksort($toDelete);
467:
468: while (!empty($toDelete)) {
469: reset($toDelete);
470: $searchKey = key($toDelete);
471: list($masterNodeId, $masterNode) = $this->findIndexNode($type, $searchKey);
472:
473: if (!isset($masterNode[$searchKey])) {
474: if (self::$debug) throw new \InvalidStateException('Bad index.');
475: unset($toDelete[$searchKey]);
476: continue;
477: }
478:
479: foreach ($toDelete as $key => $links) {
480: if (isset($masterNode[$key])) {
481: foreach ($links as $link => $foo) {
482: if (isset($masterNode[$key][$link])) {
483: unset($masterNode[$key][$link], $links[$link]);
484: }
485: }
486:
487: if (!empty($links) && isset($masterNode[$key][self::INDEX_DATA])) {
488: $this->cleanIndexData($masterNode[$key][self::INDEX_DATA], $links, $masterNode[$key]);
489: }
490:
491: if (empty($masterNode[$key])) {
492: unset($masterNode[$key]);
493: }
494: unset($toDelete[$key]);
495: } else {
496: break;
497: }
498: }
499: $this->saveNode($masterNodeId, $masterNode);
500: }
501: }
502: }
503:
504:
505:
506: 507: 508: 509: 510:
511: private function mergeIndexData(array $data)
512: {
513: while (isset($data[self::INDEX_DATA])) {
514: $id = $data[self::INDEX_DATA];
515: unset($data[self::INDEX_DATA]);
516: $childNode = $this->getNode($id);
517:
518: if ($childNode === FALSE) {
519: if (self::$debug) throw new \InvalidStateException("Cannot load node number $id.");
520: break;
521: }
522:
523: $this->arrayAppendKeys($data, $childNode[self::INDEX_DATA]);
524: }
525:
526: return $data;
527: }
528:
529:
530:
531: 532: 533: 534: 535: 536: 537:
538: private function cleanIndexData($nextNodeId, array $links, &$masterNodeLink)
539: {
540: $prev = -1;
541:
542: while ($nextNodeId && !empty($links)) {
543: $nodeId = $nextNodeId;
544: $node = $this->getNode($nodeId);
545:
546: if ($node === FALSE) {
547: if (self::$debug) throw new \InvalidStateException("Cannot load node number $nodeId.");
548: break;
549: }
550:
551: foreach ($links as $link => $foo) {
552: if (isset($node[self::INDEX_DATA][$link])) {
553: unset($node[self::INDEX_DATA][$link], $links[$link]);
554: }
555: }
556:
557: if (isset($node[self::INDEX_DATA][self::INDEX_DATA])) {
558: $nextNodeId = $node[self::INDEX_DATA][self::INDEX_DATA];
559: } else {
560: $nextNodeId = FALSE;
561: }
562:
563: if (empty($node[self::INDEX_DATA]) || (count($node[self::INDEX_DATA]) === 1 && $nextNodeId)) {
564: if ($prev === -1) {
565: if ($nextNodeId === FALSE) {
566: unset($masterNodeLink[self::INDEX_DATA]);
567: } else {
568: $masterNodeLink[self::INDEX_DATA] = $nextNodeId;
569: }
570: } else {
571: $prevNode = $this->getNode($prev);
572: if ($prevNode === FALSE) {
573: if (self::$debug) throw new \InvalidStateException("Cannot load node number $prev.");
574: } else {
575: if ($nextNodeId === FALSE) {
576: unset($prevNode[self::INDEX_DATA][self::INDEX_DATA]);
577: if (empty($prevNode[self::INDEX_DATA])) {
578: unset($prevNode[self::INDEX_DATA]);
579: }
580: } else {
581: $prevNode[self::INDEX_DATA][self::INDEX_DATA] = $nextNodeId;
582: }
583:
584: $this->saveNode($prev, $prevNode);
585: }
586: }
587: unset($node[self::INDEX_DATA]);
588: } else {
589: $prev = $nodeId;
590: }
591:
592: $this->saveNode($nodeId, $node);
593: }
594: }
595:
596:
597:
598: 599: 600: 601: 602:
603: private function getNode($id)
604: {
605: 606: if (isset($this->nodeCache[$id])) {
607: return $this->nodeCache[$id];
608: }
609:
610: $binary = stream_get_contents($this->handle, self::NODE_SIZE, self::HEADER_SIZE + self::NODE_SIZE * $id);
611:
612: if (empty($binary)) {
613: 614: return FALSE;
615: }
616:
617: list(, $magic, $lenght) = unpack('N2', $binary);
618: if ($magic !== self::INDEX_MAGIC && $magic !== self::DATA_MAGIC) {
619: if (!empty($magic)) {
620: if (self::$debug) throw new \InvalidStateException("Node $id has malformed header.");
621: $this->deleteNode($id);
622: }
623: return FALSE;
624: }
625:
626: $data = substr($binary, 2 * self::INT32_SIZE, $lenght - 2 * self::INT32_SIZE);
627:
628: $node = @unserialize($data); 629: if ($node === FALSE) {
630: $this->deleteNode($id);
631: if (self::$debug) throw new \InvalidStateException("Cannot deserialize node number $id.");
632: return FALSE;
633: }
634:
635: 636: return $this->nodeCache[$id] = $node;
637: }
638:
639:
640:
641: 642: 643: 644: 645: 646:
647: private function saveNode($id, array $node)
648: {
649: if (count($node) === 1) { 650: $nodeInfo = $node[self::INFO];
651: if ($nodeInfo[self::TYPE] !== self::DATA) {
652:
653: if ($nodeInfo[self::END] !== -1) {
654: $this->nodeCache[$id] = $node;
655: $this->nodeChanged[$id] = TRUE;
656: return;
657: }
658:
659: if ($nodeInfo[self::MAX] === -1) {
660: $max = PHP_INT_MAX;
661: } else {
662: $max = $nodeInfo[self::MAX];
663: }
664:
665: list(, , $parentId) = $this->findIndexNode($nodeInfo[self::TYPE], $max, $id);
666: if ($parentId !== -1 && $parentId !== $id) {
667: $parentNode = $this->getNode($parentId);
668: if ($parentNode === FALSE) {
669: if (self::$debug) throw new \InvalidStateException("Cannot load node number $parentId.");
670: } else {
671: if ($parentNode[self::INFO][self::END] === $id) {
672: if (count($parentNode) === 1) {
673: $parentNode[self::INFO][self::END] = -1;
674: } else {
675: end($parentNode);
676: $lastKey = key($parentNode);
677: $parentNode[self::INFO][self::END] = $parentNode[$lastKey];
678: unset($parentNode[$lastKey]);
679: }
680: } else {
681: unset($parentNode[$nodeInfo[self::MAX]]);
682: }
683:
684: $this->saveNode($parentId, $parentNode);
685: }
686: }
687:
688: if ($nodeInfo[self::TYPE] === self::PRIORITY) { 689: if ($nodeInfo[self::MAX] === -1) {
690: if ($nodeInfo[self::PREV_NODE] !== -1) {
691: $prevNode = $this->getNode($nodeInfo[self::PREV_NODE]);
692: if ($prevNode === FALSE) {
693: if (self::$debug) {
694: throw new \InvalidStateException('Cannot load node number ' . $nodeInfo[self::PREV_NODE] . '.');
695: }
696: } else {
697: $prevNode[self::INFO][self::MAX] = -1;
698: $this->saveNode($nodeInfo[self::PREV_NODE], $prevNode);
699: }
700: }
701: } else {
702: list($nextId, $nextNode) = $this->findIndexNode($nodeInfo[self::TYPE], $nodeInfo[self::MAX] + 1, NULL, $id);
703: if ($nextId !== -1 && $nextId !== $id) {
704: $nextNode[self::INFO][self::PREV_NODE] = $nodeInfo[self::PREV_NODE];
705: $this->saveNode($nextId, $nextNode);
706: }
707: }
708: }
709: }
710: $this->nodeCache[$id] = FALSE;
711: } else {
712: $this->nodeCache[$id] = $node;
713: }
714: $this->nodeChanged[$id] = TRUE;
715: }
716:
717:
718:
719: 720: 721: 722:
723: private function commit()
724: {
725: do {
726: foreach ($this->nodeChanged as $id => $foo) {
727: if ($this->prepareNode($id, $this->nodeCache[$id])) {
728: unset($this->nodeChanged[$id]);
729: }
730: }
731: } while (!empty($this->nodeChanged));
732:
733: foreach ($this->toCommit as $node => $str) {
734: $this->commitNode($node, $str);
735: }
736: $this->toCommit = array();
737: }
738:
739:
740:
741: 742: 743: 744: 745: 746:
747: private function prepareNode($id, $node)
748: {
749: if ($node === FALSE) {
750: if ($id < $this->lastNode) {
751: $this->lastNode = $id;
752: }
753: unset($this->nodeCache[$id]);
754: unset($this->dataNodeFreeSpace[$id]);
755: $this->deleteNode($id);
756: return TRUE;
757: }
758:
759: $data = serialize($node);
760: $dataSize = strlen($data) + 2 * self::INT32_SIZE;
761:
762: $isData = $node[self::INFO][self::TYPE] === self::DATA;
763: if ($dataSize > self::NODE_SIZE) {
764: if ($isData) {
765: throw new \InvalidStateException('Saving node is bigger than maximum node size.');
766: } else {
767: $this->bisectNode($id, $node);
768: return FALSE;
769: }
770: }
771:
772: $this->toCommit[$id] = pack('N2', $isData ? self::DATA_MAGIC : self::INDEX_MAGIC, $dataSize) . $data;
773:
774: if ($this->lastNode < $id) {
775: $this->lastNode = $id;
776: }
777: if ($isData) {
778: $this->dataNodeFreeSpace[$id] = self::NODE_SIZE - $dataSize;
779: }
780:
781: return TRUE;
782: }
783:
784:
785:
786: 787: 788: 789: 790: 791:
792: private function commitNode($id, $str)
793: {
794: fseek($this->handle, self::HEADER_SIZE + self::NODE_SIZE * $id);
795: $writen = fwrite($this->handle, $str);
796: if ($writen === FALSE) {
797: throw new \InvalidStateException("Cannot write node number $id to journal.");
798: }
799: }
800:
801:
802:
803: 804: 805: 806: 807: 808:
809: private function findIndexNode($type, $search, $childId = NULL, $prevId = NULL)
810: {
811: $nodeId = self::$startNode[$type];
812:
813: $parentId = -1;
814: while (TRUE) {
815: $node = $this->getNode($nodeId);
816:
817: if ($node === FALSE) {
818: return array(
819: $nodeId,
820: array(
821: self::INFO => array(
822: self::TYPE => $type,
823: self::IS_LEAF => TRUE,
824: self::PREV_NODE => -1,
825: self::END => -1,
826: self::MAX => -1,
827: )
828: ),
829: $parentId,
830: ); 831: }
832:
833: if ($node[self::INFO][self::IS_LEAF] || $nodeId === $childId || $node[self::INFO][self::PREV_NODE] === $prevId) {
834: return array($nodeId, $node, $parentId);
835: }
836:
837: $parentId = $nodeId;
838:
839: if (isset($node[$search])) {
840: $nodeId = $node[$search];
841: } else {
842: foreach ($node as $key => $childNode) {
843: if ($key > $search and $key !== self::INFO) {
844: $nodeId = $childNode;
845: continue 2;
846: }
847: }
848:
849: $nodeId = $node[self::INFO][self::END];
850: }
851: }
852: }
853:
854:
855:
856: 857: 858: 859: 860:
861: private function findFreeNode($count = 1)
862: {
863: $id = $this->lastNode;
864: $nodesId = array();
865:
866: do {
867: if (isset($this->nodeCache[$id])) {
868: ++$id;
869: continue;
870: }
871:
872: $offset = self::HEADER_SIZE + self::NODE_SIZE * $id;
873:
874: $binary = stream_get_contents($this->handle, self::INT32_SIZE, $offset);
875:
876: if (empty($binary)) {
877: $nodesId[] = $id;
878: } else {
879: list(, $magic) = unpack('N', $binary);
880: if ($magic !== self::INDEX_MAGIC && $magic !== self::DATA_MAGIC) {
881: $nodesId[] = $id;
882: }
883: }
884:
885: ++$id;
886: } while (count($nodesId) !== $count);
887:
888: if ($count === 1) {
889: return $nodesId[0];
890: } else {
891: return $nodesId;
892: }
893: }
894:
895:
896:
897: 898: 899: 900: 901:
902: private function findFreeDataNode($size)
903: {
904: foreach ($this->dataNodeFreeSpace as $id => $freeSpace) {
905: if ($freeSpace > $size) {
906: return $id;
907: }
908: }
909:
910: $id = self::$startNode[self::DATA];
911: while (TRUE) {
912: if (isset($this->dataNodeFreeSpace[$id]) || isset($this->nodeCache[$id])) {
913: ++$id;
914: continue;
915: }
916:
917: $offset = self::HEADER_SIZE + self::NODE_SIZE * $id;
918: $binary = stream_get_contents($this->handle, 2 * self::INT32_SIZE, $offset);
919:
920: if (empty($binary)) {
921: $this->dataNodeFreeSpace[$id] = self::NODE_SIZE;
922: return $id;
923: }
924:
925: list(, $magic, $nodeSize) = unpack('N2', $binary);
926: if (empty($magic)) {
927: $this->dataNodeFreeSpace[$id] = self::NODE_SIZE;
928: return $id;
929: } elseif ($magic === self::DATA_MAGIC) {
930: $freeSpace = self::NODE_SIZE - $nodeSize;
931: $this->dataNodeFreeSpace[$id] = $freeSpace;
932:
933: if ($freeSpace > $size) {
934: return $id;
935: }
936: }
937:
938: ++$id;
939: }
940: }
941:
942:
943:
944: 945: 946: 947: 948: 949:
950: private function bisectNode($id, array $node)
951: {
952: $nodeInfo = $node[self::INFO];
953: unset($node[self::INFO]);
954:
955: if (count($node) === 1) {
956: $key = key($node);
957:
958: $dataId = $this->findFreeDataNode(self::NODE_SIZE);
959: $this->saveNode($dataId, array(
960: self::INDEX_DATA => $node[$key],
961: self::INFO => array(
962: self::TYPE => self::DATA,
963: self::LAST_INDEX => ($dataId << self::BITROT),
964: )));
965:
966: unset($node[$key]);
967: $node[$key][self::INDEX_DATA] = $dataId;
968: $node[self::INFO] = $nodeInfo;
969:
970: $this->saveNode($id, $node);
971: return;
972: }
973:
974: ksort($node);
975: $halfCount = ceil(count($node) / 2);
976:
977: list($first, $second) = array_chunk($node, $halfCount, TRUE);
978:
979: end($first);
980: $halfKey = key($first);
981:
982: if ($id <= 2) { 983: list($firstId, $secondId) = $this->findFreeNode(2);
984:
985: $first[self::INFO] = array(
986: self::TYPE => $nodeInfo[self::TYPE],
987: self::IS_LEAF => $nodeInfo[self::IS_LEAF],
988: self::PREV_NODE => -1,
989: self::END => -1,
990: self::MAX => $halfKey,
991: );
992: $this->saveNode($firstId, $first);
993:
994: $second[self::INFO] = array(
995: self::TYPE => $nodeInfo[self::TYPE],
996: self::IS_LEAF => $nodeInfo[self::IS_LEAF],
997: self::PREV_NODE => $firstId,
998: self::END => $nodeInfo[self::END],
999: self::MAX => -1,
1000: );
1001: $this->saveNode($secondId, $second);
1002:
1003: $parentNode = array(
1004: self::INFO => array(
1005: self::TYPE => $nodeInfo[self::TYPE],
1006: self::IS_LEAF => FALSE,
1007: self::PREV_NODE => -1,
1008: self::END => $secondId,
1009: self::MAX => -1,
1010: ),
1011: $halfKey => $firstId,
1012: );
1013: $this->saveNode($id, $parentNode);
1014: } else {
1015: $firstId = $this->findFreeNode();
1016:
1017: $first[self::INFO] = array(
1018: self::TYPE => $nodeInfo[self::TYPE],
1019: self::IS_LEAF => $nodeInfo[self::IS_LEAF],
1020: self::PREV_NODE => $nodeInfo[self::PREV_NODE],
1021: self::END => -1,
1022: self::MAX => $halfKey,
1023: );
1024: $this->saveNode($firstId, $first);
1025:
1026: $second[self::INFO] = array(
1027: self::TYPE => $nodeInfo[self::TYPE],
1028: self::IS_LEAF => $nodeInfo[self::IS_LEAF],
1029: self::PREV_NODE => $firstId,
1030: self::END => $nodeInfo[self::END],
1031: self::MAX => $nodeInfo[self::MAX],
1032: );
1033: $this->saveNode($id, $second);
1034:
1035: list(,, $parent) = $this->findIndexNode($nodeInfo[self::TYPE], $halfKey);
1036: $parentNode = $this->getNode($parent);
1037: if ($parentNode === FALSE) {
1038: if (self::$debug) throw new \InvalidStateException("Cannot load node number $parent.");
1039: } else {
1040: $parentNode[$halfKey] = $firstId;
1041: ksort($parentNode); 1042: $this->saveNode($parent, $parentNode);
1043: }
1044: }
1045: }
1046:
1047:
1048:
1049: 1050: 1051: 1052:
1053: private function headerCommit()
1054: {
1055: fseek($this->handle, self::INT32_SIZE);
1056: @fwrite($this->handle, pack('N', $this->lastNode)); 1057: }
1058:
1059:
1060:
1061: 1062: 1063: 1064: 1065:
1066: private function deleteNode($id)
1067: {
1068: fseek($this->handle, 0, SEEK_END);
1069: $end = ftell($this->handle);
1070:
1071: if ($end <= (self::HEADER_SIZE + self::NODE_SIZE * ($id + 1))) {
1072: $packedNull = pack('N', 0);
1073:
1074: do {
1075: $binary = stream_get_contents($this->handle, self::INT32_SIZE, (self::HEADER_SIZE + self::NODE_SIZE * --$id));
1076: } while (empty($binary) || $binary === $packedNull);
1077:
1078: if (!ftruncate($this->handle, self::HEADER_SIZE + self::NODE_SIZE * ($id + 1))) {
1079: throw new \InvalidStateException('Cannot truncate journal file.');
1080: }
1081: } else {
1082: fseek($this->handle, self::HEADER_SIZE + self::NODE_SIZE * $id);
1083: $writen = fwrite($this->handle, pack('N', 0));
1084: if ($writen !== self::INT32_SIZE) {
1085: throw new \InvalidStateException("Cannot delete node number $id from journal.");
1086: }
1087: }
1088: }
1089:
1090:
1091:
1092: 1093: 1094: 1095:
1096: private function deleteAll()
1097: {
1098: if (!ftruncate($this->handle, self::HEADER_SIZE)) {
1099: throw new \InvalidStateException('Cannot truncate journal file.');
1100: }
1101: }
1102:
1103:
1104:
1105: 1106: 1107: 1108:
1109: private function lock()
1110: {
1111: if (!$this->handle) {
1112: throw new \InvalidStateException('File journal file is not opened');
1113: }
1114:
1115: if (!flock($this->handle, LOCK_EX)) {
1116: throw new \InvalidStateException('Cannot acquire exclusive lock on journal.');
1117: }
1118:
1119: if ($this->lastModTime !== NULL) {
1120: clearstatcache();
1121: if ($this->lastModTime < @filemtime($this->file)) { 1122: $this->nodeCache = $this->dataNodeFreeSpace = array();
1123: }
1124: }
1125: }
1126:
1127:
1128:
1129: 1130: 1131: 1132:
1133: private function unlock()
1134: {
1135: if ($this->handle) {
1136: fflush($this->handle);
1137: flock($this->handle, LOCK_UN);
1138: clearstatcache();
1139: $this->lastModTime = @filemtime($this->file); 1140: }
1141: }
1142:
1143:
1144:
1145: 1146: 1147: 1148: 1149: 1150: 1151:
1152: private function arrayAppend(array &$array, array $append)
1153: {
1154: foreach ($append as $value) {
1155: $array[] = $value;
1156: }
1157: }
1158:
1159:
1160:
1161: 1162: 1163: 1164: 1165: 1166: 1167:
1168: private function arrayAppendKeys(array &$array, array $append)
1169: {
1170: foreach ($append as $key => $value) {
1171: $array[$key] = $value;
1172: }
1173: }
1174:
1175: }
1176: