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