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