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