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