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