1 /*
2 * Copyright (c) 2023, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 package org.openjdk.bench.vm.compiler;
25
26 import org.openjdk.jmh.annotations.Benchmark;
27 import org.openjdk.jmh.annotations.Fork;
28 import org.openjdk.jmh.annotations.Measurement;
29 import org.openjdk.jmh.annotations.OutputTimeUnit;
30 import org.openjdk.jmh.annotations.Scope;
31 import org.openjdk.jmh.annotations.State;
32 import org.openjdk.jmh.annotations.Warmup;
33
34 import java.util.concurrent.TimeUnit;
35
36 /*
37 * This benchmark is used as easy reproducer of JDK-8305995
38 *
39 * This benchmark contains simplified and minimized RB-tree
40 * which is based on fasutils with iterators that jumps.
41 *
42 * At the end it contains a tree serialized as lines, and
43 * maxPattern which is used to search in this tree.
44 */
45 @State(Scope.Thread)
46 @OutputTimeUnit(TimeUnit.MICROSECONDS)
47 @Warmup(iterations = 4, time = 2, timeUnit = TimeUnit.SECONDS)
48 @Measurement(iterations = 4, time = 2, timeUnit = TimeUnit.SECONDS)
49 @Fork(value = 3)
50 public class RBTreeSearch {
51
52 private final Tree pattern;
53
54 private final Tree[] nodes;
55
56 private final Tree root;
57
58 private final int[] idxStack;
59 private final Tree[] objStack;
60
61 public RBTreeSearch() {
62 idxStack = new int[maxPattern];
63
64 objStack = new Tree[maxPattern];
65
66 pattern = new Tree();
67 for (int i = 0; i <= maxPattern; i++) {
68 pattern.put(i, i);
69 }
70
71 nodes = new Tree[directions.length];
72 for (int i = 0; i < directions.length; i++) {
73 if (directions[i] == null) {
74 continue;
75 }
76 Tree kids = new Tree();
77 nodes[i] = kids;
78 for (String pair : directions[i].split(", ")) {
79 String[] kv = pair.split("=>");
80 kids.put(Integer.parseInt(kv[0]), Integer.parseInt(kv[1]));
81 }
82 }
83
84 root = nodes[0];
85 }
86
87 @Benchmark
88 public void search() {
89 Tree.Iterator sliceIt = pattern.keyIterator();
90
91 int stackSize = 0;
92 idxStack[stackSize] = pattern.firstIntKey();
93 objStack[stackSize++] = root;
94
95 while (stackSize > 0) {
96 stackSize--;
97 Tree node = objStack[stackSize];
98
99 final int startPoint = Math.max(idxStack[stackSize], node.firstIntKey()) - 1;
100 final Tree.Iterator rootIt = node.keyIterator(startPoint);
101
102 sliceIt.jump(startPoint);
103 while (sliceIt.hasNext() && rootIt.hasNext()) {
104 final int sliceElem = sliceIt.nextInt();
105 final int rootElem = rootIt.nextInt();
106 if (sliceElem < rootElem) {
107 rootIt.previousInt();
108 if (sliceIt.nextInt() >= rootElem) {
109 sliceIt.previousInt();
110 } else {
111 sliceIt.jump(rootElem - 1);
112 }
113 } else if (sliceElem == rootElem) {
114 final int childrenIdx = node.get(sliceElem);
115 final Tree children = nodes[childrenIdx];
116
117 if (children != null) {
118 idxStack[stackSize] = sliceElem;
119 objStack[stackSize++] = children;
120 }
121 }
122 }
123 }
124 }
125
126 public static class Tree {
127
128 protected transient Entry root;
129
130 protected transient Entry firstEntry;
131
132 protected transient Entry lastEntry;
133
134 private final transient boolean[] dirPath = new boolean[64];
135
136 private final transient Entry[] nodePath = new Entry[64];
137
138 public int put(final int k, final int v) {
139 Entry e = add(k);
140 final int oldValue = e.value;
141 e.value = v;
142 return oldValue;
143 }
144
145 private Entry add(final int k) {
146 int maxDepth = 0;
147 Entry e;
148 if (root == null) {
149 e = root = lastEntry = firstEntry = new Entry(k, 0);
150 }
151 else {
152 Entry p = root;
153 int cmp, i = 0;
154 while(true) {
155 if ((cmp = Integer.compare(k, p.key)) == 0) {
156 while(i-- != 0) nodePath[i] = null;
157 return p;
158 }
159 nodePath[i] = p;
160 if (dirPath[i++] = cmp > 0) {
161 if (p.succ()) {
162 e = new Entry(k, 0);
163 if (p.right == null) lastEntry = e;
164 e.left = p;
165 e.right = p.right;
166 p.right(e);
167 break;
168 }
169 p = p.right;
170 }
171 else {
172 if (p.pred()) {
173 e = new Entry(k, 0);
174 if (p.left == null) firstEntry = e;
175 e.right = p;
176 e.left = p.left;
177 p.left(e);
178 break;
179 }
180 p = p.left;
181 }
182 }
183 maxDepth = i--;
184 while(i > 0 && ! nodePath[i].black()) {
185 if (! dirPath[i - 1]) {
186 Entry y = nodePath[i - 1].right;
187 if (! nodePath[i - 1].succ() && ! y.black()) {
188 nodePath[i].black(true);
189 y.black(true);
190 nodePath[i - 1].black(false);
191 i -= 2;
192 }
193 else {
194 Entry x;
195 if (! dirPath[i]) y = nodePath[i];
196 else {
197 x = nodePath[i];
198 y = x.right;
199 x.right = y.left;
200 y.left = x;
201 nodePath[i - 1].left = y;
202 if (y.pred()) {
203 y.pred(false);
204 x.succ(y);
205 }
206 }
207 x = nodePath[i - 1];
208 x.black(false);
209 y.black(true);
210 x.left = y.right;
211 y.right = x;
212 if (i < 2) root = y;
213 else {
214 if (dirPath[i - 2]) nodePath[i - 2].right = y;
215 else nodePath[i - 2].left = y;
216 }
217 if (y.succ()) {
218 y.succ(false);
219 x.pred(y);
220 }
221 break;
222 }
223 }
224 else {
225 Entry y = nodePath[i - 1].left;
226 if (! nodePath[i - 1].pred() && ! y.black()) {
227 nodePath[i].black(true);
228 y.black(true);
229 nodePath[i - 1].black(false);
230 i -= 2;
231 }
232 else {
233 Entry x;
234 if (dirPath[i]) y = nodePath[i];
235 else {
236 x = nodePath[i];
237 y = x.left;
238 x.left = y.right;
239 y.right = x;
240 nodePath[i - 1].right = y;
241 if (y.succ()) {
242 y.succ(false);
243 x.pred(y);
244 }
245 }
246 x = nodePath[i - 1];
247 x.black(false);
248 y.black(true);
249 x.right = y.left;
250 y.left = x;
251 if (i < 2) root = y;
252 else {
253 if (dirPath[i - 2]) nodePath[i - 2].right = y;
254 else nodePath[i - 2].left = y;
255 }
256 if (y.pred()){
257 y.pred(false);
258 x.succ(y);
259 }
260 break;
261 }
262 }
263 }
264 }
265 root.black(true);
266 while(maxDepth-- != 0) nodePath[maxDepth] = null;
267 return e;
268 }
269
270 private static final class Entry {
271 int key;
272 int value;
273
274 private static final int BLACK_MASK = 1;
275
276 private static final int SUCC_MASK = 1 << 31;
277
278 private static final int PRED_MASK = 1 << 30;
279
280 Entry left, right;
281
282 int info;
283
284 Entry(final int k, final int v) {
285 key = k;
286 value = v;
287 info = SUCC_MASK | PRED_MASK;
288 }
289
290 Entry left() {
291 return (info & PRED_MASK) != 0 ? null : left;
292 }
293
294 Entry right() {
295 return (info & SUCC_MASK) != 0 ? null : right;
296 }
297
298 boolean pred() {
299 return (info & PRED_MASK) != 0;
300 }
301
302 boolean succ() {
303 return (info & SUCC_MASK) != 0;
304 }
305
306 void pred(final boolean pred) {
307 if (pred) info |= PRED_MASK;
308 else info &= ~PRED_MASK;
309 }
310
311 void succ(final boolean succ) {
312 if (succ) info |= SUCC_MASK;
313 else info &= ~SUCC_MASK;
314 }
315
316 void pred(final Entry pred) {
317 info |= PRED_MASK;
318 left = pred;
319 }
320
321 void succ(final Entry succ) {
322 info |= SUCC_MASK;
323 right = succ;
324 }
325
326 void left(final Entry left) {
327 info &= ~PRED_MASK;
328 this.left = left;
329 }
330
331 void right(final Entry right) {
332 info &= ~SUCC_MASK;
333 this.right = right;
334 }
335
336 boolean black() {
337 return (info & BLACK_MASK) != 0;
338 }
339
340 void black(final boolean black) {
341 if (black) info |= BLACK_MASK;
342 else info &= ~BLACK_MASK;
343 }
344
345 Entry next() {
346 Entry next = this.right;
347 if ((info & SUCC_MASK) == 0) while ((next.info & PRED_MASK) == 0) next = next.left;
348 return next;
349 }
350
351 Entry prev() {
352 Entry prev = this.left;
353 if ((info & PRED_MASK) == 0) while ((prev.info & SUCC_MASK) == 0) prev = prev.right;
354 return prev;
355 }
356 }
357
358 public int get(final int k) {
359 Entry e = root;
360 int cmp;
361 while (e != null && (cmp = Integer.compare(k, e.key)) != 0) {
362 e = cmp < 0 ? e.left() : e.right();
363 }
364 return e == null ? 0 : e.value;
365 }
366
367 public int firstIntKey() {
368 return firstEntry.key;
369 }
370
371 interface Iterator {
372 boolean hasNext();
373 int nextInt();
374 int previousInt();
375 void jump(final int fromElement);
376 }
377
378 private class KeyIteratorImpl implements Iterator {
379 Entry prev;
380
381 Entry next;
382
383 Entry curr;
384
385 int index = 0;
386
387 KeyIteratorImpl() {
388 next = firstEntry;
389 }
390
391 @SuppressWarnings("initialization")
392 KeyIteratorImpl(final int k) {
393 if ((next = locateKey(k)) != null) {
394 if (next.key <= k) {
395 prev = next;
396 next = next.next();
397 }
398 else prev = next.prev();
399 }
400 }
401
402 private Entry locateKey(final int k) {
403 Entry e = root, last = root;
404 int cmp = 0;
405 while (e != null && (cmp = Integer.compare(k, e.key)) != 0) {
406 last = e;
407 e = cmp < 0 ? e.left() : e.right();
408 }
409 return cmp == 0 ? e : last;
410 }
411
412 public boolean hasNext() { return next != null; }
413
414 Entry nextEntry() {
415 curr = prev = next;
416 index++;
417 next = next.next();
418 return curr;
419 }
420
421 Entry previousEntry() {
422 curr = next = prev;
423 index--;
424 prev = prev.prev();
425 return curr;
426 }
427 public void jump(final int fromElement) {
428 if ((next = locateKey(fromElement)) != null) {
429 if (next.key <= fromElement) {
430 prev = next;
431 next = next.next();
432 }
433 else prev = next.prev();
434 }
435 }
436
437 public int nextInt() { return nextEntry().key; }
438
439 public int previousInt() { return previousEntry().key; }
440
441 }
442
443 public Iterator keyIterator() {
444 return new KeyIteratorImpl();
445 }
446
447 public Iterator keyIterator(final int from) {
448 return new KeyIteratorImpl(from);
449 }
450 }
451
452 private static final int maxPattern = 39;
453
454 private static final String[] directions = {
455 "0=>1, 1=>4, 2=>2, 4=>3, 7=>5",
456 "13=>628, 14=>627, 15=>626, 17=>629, 18=>630",
457 "13=>473, 14=>472, 15=>471, 17=>474, 18=>475",
458 "13=>318, 14=>317, 15=>316, 17=>319, 18=>320",
459 "13=>163, 14=>162, 15=>161, 17=>164, 18=>165",
460 "13=>8, 14=>7, 15=>6, 17=>9, 18=>10",
461 "22=>135, 23=>134, 24=>132, 26=>133, 27=>131",
462 "22=>105, 23=>104, 24=>102, 26=>103, 27=>101",
463 "22=>75, 23=>74, 24=>72, 26=>73, 27=>71",
464 "22=>45, 23=>44, 24=>42, 26=>43, 27=>41",
465 "22=>15, 23=>14, 24=>12, 26=>13, 27=>11",
466 "31=>38, 32=>39, 33=>36, 34=>40, 35=>37",
467 "31=>33, 32=>34, 33=>31, 34=>35, 35=>32",
468 "31=>28, 32=>29, 33=>26, 34=>30, 35=>27",
469 "31=>23, 32=>24, 33=>21, 34=>25, 35=>22",
470 "31=>18, 32=>19, 33=>16, 34=>20, 35=>17",
471 null,
472 null,
473 null,
474 null,
475 null,
476 null,
477 null,
478 null,
479 null,
480 null,
481 null,
482 null,
483 null,
484 null,
485 null,
486 null,
487 null,
488 null,
489 null,
490 null,
491 null,
492 null,
493 null,
494 null,
495 null,
496 "31=>68, 32=>69, 33=>66, 34=>70, 35=>67",
497 "31=>63, 32=>64, 33=>61, 34=>65, 35=>62",
498 "31=>58, 32=>59, 33=>56, 34=>60, 35=>57",
499 "31=>53, 32=>54, 33=>51, 34=>55, 35=>52",
500 "31=>48, 32=>49, 33=>46, 34=>50, 35=>47",
501 null,
502 null,
503 null,
504 null,
505 null,
506 null,
507 null,
508 null,
509 null,
510 null,
511 null,
512 null,
513 null,
514 null,
515 null,
516 null,
517 null,
518 null,
519 null,
520 null,
521 null,
522 null,
523 null,
524 null,
525 null,
526 "31=>98, 32=>99, 33=>96, 34=>100, 35=>97",
527 "31=>93, 32=>94, 33=>91, 34=>95, 35=>92",
528 "31=>88, 32=>89, 33=>86, 34=>90, 35=>87",
529 "31=>83, 32=>84, 33=>81, 34=>85, 35=>82",
530 "31=>78, 32=>79, 33=>76, 34=>80, 35=>77",
531 null,
532 null,
533 null,
534 null,
535 null,
536 null,
537 null,
538 null,
539 null,
540 null,
541 null,
542 null,
543 null,
544 null,
545 null,
546 null,
547 null,
548 null,
549 null,
550 null,
551 null,
552 null,
553 null,
554 null,
555 null,
556 "31=>128, 32=>129, 33=>126, 34=>130, 35=>127",
557 "31=>123, 32=>124, 33=>121, 34=>125, 35=>122",
558 "31=>118, 32=>119, 33=>116, 34=>120, 35=>117",
559 "31=>113, 32=>114, 33=>111, 34=>115, 35=>112",
560 "31=>108, 32=>109, 33=>106, 34=>110, 35=>107",
561 null,
562 null,
563 null,
564 null,
565 null,
566 null,
567 null,
568 null,
569 null,
570 null,
571 null,
572 null,
573 null,
574 null,
575 null,
576 null,
577 null,
578 null,
579 null,
580 null,
581 null,
582 null,
583 null,
584 null,
585 null,
586 "31=>158, 32=>159, 33=>156, 34=>160, 35=>157",
587 "31=>153, 32=>154, 33=>151, 34=>155, 35=>152",
588 "31=>148, 32=>149, 33=>146, 34=>150, 35=>147",
589 "31=>143, 32=>144, 33=>141, 34=>145, 35=>142",
590 "31=>138, 32=>139, 33=>136, 34=>140, 35=>137",
591 null,
592 null,
593 null,
594 null,
595 null,
596 null,
597 null,
598 null,
599 null,
600 null,
601 null,
602 null,
603 null,
604 null,
605 null,
606 null,
607 null,
608 null,
609 null,
610 null,
611 null,
612 null,
613 null,
614 null,
615 null,
616 "22=>290, 23=>289, 24=>287, 26=>288, 27=>286",
617 "22=>260, 23=>259, 24=>257, 26=>258, 27=>256",
618 "22=>230, 23=>229, 24=>227, 26=>228, 27=>226",
619 "22=>200, 23=>199, 24=>197, 26=>198, 27=>196",
620 "22=>170, 23=>169, 24=>167, 26=>168, 27=>166",
621 "31=>193, 32=>194, 33=>191, 34=>195, 35=>192",
622 "31=>188, 32=>189, 33=>186, 34=>190, 35=>187",
623 "31=>183, 32=>184, 33=>181, 34=>185, 35=>182",
624 "31=>178, 32=>179, 33=>176, 34=>180, 35=>177",
625 "31=>173, 32=>174, 33=>171, 34=>175, 35=>172",
626 null,
627 null,
628 null,
629 null,
630 null,
631 null,
632 null,
633 null,
634 null,
635 null,
636 null,
637 null,
638 null,
639 null,
640 null,
641 null,
642 null,
643 null,
644 null,
645 null,
646 null,
647 null,
648 null,
649 null,
650 null,
651 "31=>223, 32=>224, 33=>221, 34=>225, 35=>222",
652 "31=>218, 32=>219, 33=>216, 34=>220, 35=>217",
653 "31=>213, 32=>214, 33=>211, 34=>215, 35=>212",
654 "31=>208, 32=>209, 33=>206, 34=>210, 35=>207",
655 "31=>203, 32=>204, 33=>201, 34=>205, 35=>202",
656 null,
657 null,
658 null,
659 null,
660 null,
661 null,
662 null,
663 null,
664 null,
665 null,
666 null,
667 null,
668 null,
669 null,
670 null,
671 null,
672 null,
673 null,
674 null,
675 null,
676 null,
677 null,
678 null,
679 null,
680 null,
681 "31=>253, 32=>254, 33=>251, 34=>255, 35=>252",
682 "31=>248, 32=>249, 33=>246, 34=>250, 35=>247",
683 "31=>243, 32=>244, 33=>241, 34=>245, 35=>242",
684 "31=>238, 32=>239, 33=>236, 34=>240, 35=>237",
685 "31=>233, 32=>234, 33=>231, 34=>235, 35=>232",
686 null,
687 null,
688 null,
689 null,
690 null,
691 null,
692 null,
693 null,
694 null,
695 null,
696 null,
697 null,
698 null,
699 null,
700 null,
701 null,
702 null,
703 null,
704 null,
705 null,
706 null,
707 null,
708 null,
709 null,
710 null,
711 "31=>283, 32=>284, 33=>281, 34=>285, 35=>282",
712 "31=>278, 32=>279, 33=>276, 34=>280, 35=>277",
713 "31=>273, 32=>274, 33=>271, 34=>275, 35=>272",
714 "31=>268, 32=>269, 33=>266, 34=>270, 35=>267",
715 "31=>263, 32=>264, 33=>261, 34=>265, 35=>262",
716 null,
717 null,
718 null,
719 null,
720 null,
721 null,
722 null,
723 null,
724 null,
725 null,
726 null,
727 null,
728 null,
729 null,
730 null,
731 null,
732 null,
733 null,
734 null,
735 null,
736 null,
737 null,
738 null,
739 null,
740 null,
741 "31=>313, 32=>314, 33=>311, 34=>315, 35=>312",
742 "31=>308, 32=>309, 33=>306, 34=>310, 35=>307",
743 "31=>303, 32=>304, 33=>301, 34=>305, 35=>302",
744 "31=>298, 32=>299, 33=>296, 34=>300, 35=>297",
745 "31=>293, 32=>294, 33=>291, 34=>295, 35=>292",
746 null,
747 null,
748 null,
749 null,
750 null,
751 null,
752 null,
753 null,
754 null,
755 null,
756 null,
757 null,
758 null,
759 null,
760 null,
761 null,
762 null,
763 null,
764 null,
765 null,
766 null,
767 null,
768 null,
769 null,
770 null,
771 "22=>445, 23=>444, 24=>442, 26=>443, 27=>441",
772 "22=>415, 23=>414, 24=>412, 26=>413, 27=>411",
773 "22=>385, 23=>384, 24=>382, 26=>383, 27=>381",
774 "22=>355, 23=>354, 24=>352, 26=>353, 27=>351",
775 "22=>325, 23=>324, 24=>322, 26=>323, 27=>321",
776 "31=>348, 32=>349, 33=>346, 34=>350, 35=>347",
777 "31=>343, 32=>344, 33=>341, 34=>345, 35=>342",
778 "31=>338, 32=>339, 33=>336, 34=>340, 35=>337",
779 "31=>333, 32=>334, 33=>331, 34=>335, 35=>332",
780 "31=>328, 32=>329, 33=>326, 34=>330, 35=>327",
781 null,
782 null,
783 null,
784 null,
785 null,
786 null,
787 null,
788 null,
789 null,
790 null,
791 null,
792 null,
793 null,
794 null,
795 null,
796 null,
797 null,
798 null,
799 null,
800 null,
801 null,
802 null,
803 null,
804 null,
805 null,
806 "31=>378, 32=>379, 33=>376, 34=>380, 35=>377",
807 "31=>373, 32=>374, 33=>371, 34=>375, 35=>372",
808 "31=>368, 32=>369, 33=>366, 34=>370, 35=>367",
809 "31=>363, 32=>364, 33=>361, 34=>365, 35=>362",
810 "31=>358, 32=>359, 33=>356, 34=>360, 35=>357",
811 null,
812 null,
813 null,
814 null,
815 null,
816 null,
817 null,
818 null,
819 null,
820 null,
821 null,
822 null,
823 null,
824 null,
825 null,
826 null,
827 null,
828 null,
829 null,
830 null,
831 null,
832 null,
833 null,
834 null,
835 null,
836 "31=>408, 32=>409, 33=>406, 34=>410, 35=>407",
837 "31=>403, 32=>404, 33=>401, 34=>405, 35=>402",
838 "31=>398, 32=>399, 33=>396, 34=>400, 35=>397",
839 "31=>393, 32=>394, 33=>391, 34=>395, 35=>392",
840 "31=>388, 32=>389, 33=>386, 34=>390, 35=>387",
841 null,
842 null,
843 null,
844 null,
845 null,
846 null,
847 null,
848 null,
849 null,
850 null,
851 null,
852 null,
853 null,
854 null,
855 null,
856 null,
857 null,
858 null,
859 null,
860 null,
861 null,
862 null,
863 null,
864 null,
865 null,
866 "31=>438, 32=>439, 33=>436, 34=>440, 35=>437",
867 "31=>433, 32=>434, 33=>431, 34=>435, 35=>432",
868 "31=>428, 32=>429, 33=>426, 34=>430, 35=>427",
869 "31=>423, 32=>424, 33=>421, 34=>425, 35=>422",
870 "31=>418, 32=>419, 33=>416, 34=>420, 35=>417",
871 null,
872 null,
873 null,
874 null,
875 null,
876 null,
877 null,
878 null,
879 null,
880 null,
881 null,
882 null,
883 null,
884 null,
885 null,
886 null,
887 null,
888 null,
889 null,
890 null,
891 null,
892 null,
893 null,
894 null,
895 null,
896 "31=>468, 32=>469, 33=>466, 34=>470, 35=>467",
897 "31=>463, 32=>464, 33=>461, 34=>465, 35=>462",
898 "31=>458, 32=>459, 33=>456, 34=>460, 35=>457",
899 "31=>453, 32=>454, 33=>451, 34=>455, 35=>452",
900 "31=>448, 32=>449, 33=>446, 34=>450, 35=>447",
901 null,
902 null,
903 null,
904 null,
905 null,
906 null,
907 null,
908 null,
909 null,
910 null,
911 null,
912 null,
913 null,
914 null,
915 null,
916 null,
917 null,
918 null,
919 null,
920 null,
921 null,
922 null,
923 null,
924 null,
925 null,
926 "22=>600, 23=>599, 24=>597, 26=>598, 27=>596",
927 "22=>570, 23=>569, 24=>567, 26=>568, 27=>566",
928 "22=>540, 23=>539, 24=>537, 26=>538, 27=>536",
929 "22=>510, 23=>509, 24=>507, 26=>508, 27=>506",
930 "22=>480, 23=>479, 24=>477, 26=>478, 27=>476",
931 "31=>503, 32=>504, 33=>501, 34=>505, 35=>502",
932 "31=>498, 32=>499, 33=>496, 34=>500, 35=>497",
933 "31=>493, 32=>494, 33=>491, 34=>495, 35=>492",
934 "31=>488, 32=>489, 33=>486, 34=>490, 35=>487",
935 "31=>483, 32=>484, 33=>481, 34=>485, 35=>482",
936 null,
937 null,
938 null,
939 null,
940 null,
941 null,
942 null,
943 null,
944 null,
945 null,
946 null,
947 null,
948 null,
949 null,
950 null,
951 null,
952 null,
953 null,
954 null,
955 null,
956 null,
957 null,
958 null,
959 null,
960 null,
961 "31=>533, 32=>534, 33=>531, 34=>535, 35=>532",
962 "31=>528, 32=>529, 33=>526, 34=>530, 35=>527",
963 "31=>523, 32=>524, 33=>521, 34=>525, 35=>522",
964 "31=>518, 32=>519, 33=>516, 34=>520, 35=>517",
965 "31=>513, 32=>514, 33=>511, 34=>515, 35=>512",
966 null,
967 null,
968 null,
969 null,
970 null,
971 null,
972 null,
973 null,
974 null,
975 null,
976 null,
977 null,
978 null,
979 null,
980 null,
981 null,
982 null,
983 null,
984 null,
985 null,
986 null,
987 null,
988 null,
989 null,
990 null,
991 "31=>563, 32=>564, 33=>561, 34=>565, 35=>562",
992 "31=>558, 32=>559, 33=>556, 34=>560, 35=>557",
993 "31=>553, 32=>554, 33=>551, 34=>555, 35=>552",
994 "31=>548, 32=>549, 33=>546, 34=>550, 35=>547",
995 "31=>543, 32=>544, 33=>541, 34=>545, 35=>542",
996 null,
997 null,
998 null,
999 null,
1000 null,
1001 null,
1002 null,
1003 null,
1004 null,
1005 null,
1006 null,
1007 null,
1008 null,
1009 null,
1010 null,
1011 null,
1012 null,
1013 null,
1014 null,
1015 null,
1016 null,
1017 null,
1018 null,
1019 null,
1020 null,
1021 "31=>593, 32=>594, 33=>591, 34=>595, 35=>592",
1022 "31=>588, 32=>589, 33=>586, 34=>590, 35=>587",
1023 "31=>583, 32=>584, 33=>581, 34=>585, 35=>582",
1024 "31=>578, 32=>579, 33=>576, 34=>580, 35=>577",
1025 "31=>573, 32=>574, 33=>571, 34=>575, 35=>572",
1026 null,
1027 null,
1028 null,
1029 null,
1030 null,
1031 null,
1032 null,
1033 null,
1034 null,
1035 null,
1036 null,
1037 null,
1038 null,
1039 null,
1040 null,
1041 null,
1042 null,
1043 null,
1044 null,
1045 null,
1046 null,
1047 null,
1048 null,
1049 null,
1050 null,
1051 "31=>623, 32=>624, 33=>621, 34=>625, 35=>622",
1052 "31=>618, 32=>619, 33=>616, 34=>620, 35=>617",
1053 "31=>613, 32=>614, 33=>611, 34=>615, 35=>612",
1054 "31=>608, 32=>609, 33=>606, 34=>610, 35=>607",
1055 "31=>603, 32=>604, 33=>601, 34=>605, 35=>602",
1056 null,
1057 null,
1058 null,
1059 null,
1060 null,
1061 null,
1062 null,
1063 null,
1064 null,
1065 null,
1066 null,
1067 null,
1068 null,
1069 null,
1070 null,
1071 null,
1072 null,
1073 null,
1074 null,
1075 null,
1076 null,
1077 null,
1078 null,
1079 null,
1080 null,
1081 "22=>755, 23=>754, 24=>752, 26=>753, 27=>751",
1082 "22=>725, 23=>724, 24=>722, 26=>723, 27=>721",
1083 "22=>695, 23=>694, 24=>692, 26=>693, 27=>691",
1084 "22=>665, 23=>664, 24=>662, 26=>663, 27=>661",
1085 "22=>635, 23=>634, 24=>632, 26=>633, 27=>631",
1086 "31=>658, 32=>659, 33=>656, 34=>660, 35=>657",
1087 "31=>653, 32=>654, 33=>651, 34=>655, 35=>652",
1088 "31=>648, 32=>649, 33=>646, 34=>650, 35=>647",
1089 "31=>643, 32=>644, 33=>641, 34=>645, 35=>642",
1090 "31=>638, 32=>639, 33=>636, 34=>640, 35=>637",
1091 null,
1092 null,
1093 null,
1094 null,
1095 null,
1096 null,
1097 null,
1098 null,
1099 null,
1100 null,
1101 null,
1102 null,
1103 null,
1104 null,
1105 null,
1106 null,
1107 null,
1108 null,
1109 null,
1110 null,
1111 null,
1112 null,
1113 null,
1114 null,
1115 null,
1116 "31=>688, 32=>689, 33=>686, 34=>690, 35=>687",
1117 "31=>683, 32=>684, 33=>681, 34=>685, 35=>682",
1118 "31=>678, 32=>679, 33=>676, 34=>680, 35=>677",
1119 "31=>673, 32=>674, 33=>671, 34=>675, 35=>672",
1120 "31=>668, 32=>669, 33=>666, 34=>670, 35=>667",
1121 null,
1122 null,
1123 null,
1124 null,
1125 null,
1126 null,
1127 null,
1128 null,
1129 null,
1130 null,
1131 null,
1132 null,
1133 null,
1134 null,
1135 null,
1136 null,
1137 null,
1138 null,
1139 null,
1140 null,
1141 null,
1142 null,
1143 null,
1144 null,
1145 null,
1146 "31=>718, 32=>719, 33=>716, 34=>720, 35=>717",
1147 "31=>713, 32=>714, 33=>711, 34=>715, 35=>712",
1148 "31=>708, 32=>709, 33=>706, 34=>710, 35=>707",
1149 "31=>703, 32=>704, 33=>701, 34=>705, 35=>702",
1150 "31=>698, 32=>699, 33=>696, 34=>700, 35=>697",
1151 null,
1152 null,
1153 null,
1154 null,
1155 null,
1156 null,
1157 null,
1158 null,
1159 null,
1160 null,
1161 null,
1162 null,
1163 null,
1164 null,
1165 null,
1166 null,
1167 null,
1168 null,
1169 null,
1170 null,
1171 null,
1172 null,
1173 null,
1174 null,
1175 null,
1176 "31=>748, 32=>749, 33=>746, 34=>750, 35=>747",
1177 "31=>743, 32=>744, 33=>741, 34=>745, 35=>742",
1178 "31=>738, 32=>739, 33=>736, 34=>740, 35=>737",
1179 "31=>733, 32=>734, 33=>731, 34=>735, 35=>732",
1180 "31=>728, 32=>729, 33=>726, 34=>730, 35=>727",
1181 null,
1182 null,
1183 null,
1184 null,
1185 null,
1186 null,
1187 null,
1188 null,
1189 null,
1190 null,
1191 null,
1192 null,
1193 null,
1194 null,
1195 null,
1196 null,
1197 null,
1198 null,
1199 null,
1200 null,
1201 null,
1202 null,
1203 null,
1204 null,
1205 null,
1206 "31=>778, 32=>779, 33=>776, 34=>780, 35=>777",
1207 "31=>773, 32=>774, 33=>771, 34=>775, 35=>772",
1208 "31=>768, 32=>769, 33=>766, 34=>770, 35=>767",
1209 "31=>763, 32=>764, 33=>761, 34=>765, 35=>762",
1210 "31=>758, 32=>759, 33=>756, 34=>760, 35=>757",
1211 null,
1212 null,
1213 null,
1214 null,
1215 null,
1216 null,
1217 null,
1218 null,
1219 null,
1220 null,
1221 null,
1222 null,
1223 null,
1224 null,
1225 null,
1226 null,
1227 null,
1228 null,
1229 null,
1230 null,
1231 null,
1232 null,
1233 null,
1234 null,
1235 null
1236 };
1237 }