File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\mvstore\ChangeCursor.java.html

1 /*
2 * Copyright 2004-2011 H2 Group. Multiple-Licensed under the H2 License,
3 * Version 1.0, and under the Eclipse Public License, Version 1.0
4 * (http://h2database.com/html/license.html).
5 * Initial Developer: H2 Group
6 */
7 package org.h2.mvstore;
8
9 import java.util.Iterator;
10
11 /**
12 * A cursor to iterate over all keys in new pages.
13 *
14 * @param <K> the key type
15 * @param <V> the value type
16 */
17 public class ChangeCursor<K, V> implements Iterator<K> {
18
19 private final MVMap<K, V> map;
20 private final Page root1, root2;
21
22 /**
23 * The state of this cursor.
24 * 0: not initialized
25 * 1: reading from root1
26 * 2: reading from root2
27 * 3: closed
28 */
29 private int state;
30 private CursorPos pos1, pos2;
31 private K current;
32
33 ChangeCursor(MVMap<K, V> map, Page root1, Page root2) {
34 this.map = map;
35 this.root1 = root1;
36 this.root2 = root2;
37 }
38
39 public K next() {
40 K c = current;
41 fetchNext();
42 return c;
43 }
44
45 public boolean hasNext() {
46 if (state == 0) {
47 pos1 = new CursorPos(root1, 0, null);
48 pos1 = min(pos1);
49 state = 1;
50 fetchNext();
51 }
52 return current != null;
53 }
54
55 public void remove() {
56 throw new UnsupportedOperationException();
57 }
58
59 private void fetchNext() {
60 while (fetchNextKey()) {
61 if (pos1 == null || pos2 == null) {
62 break;
63 }
64 @SuppressWarnings("unchecked")
65 V v1 = (V) map.binarySearch(root1, current);
66 @SuppressWarnings("unchecked")
67 V v2 = (V) map.binarySearch(root2, current);
68 if (!v1.equals(v2)) {
69 break;
70 }
71 }
72 }
73
74 private boolean fetchNextKey() {
75 while (true) {
76 if (state == 3) {
77 return false;
78 }
79 if (state == 1) {
80 // read from root1
81 pos1 = fetchNext(pos1);
82 if (pos1 == null) {
83 // reached the end of pos1
84 state = 2;
85 pos2 = null;
86 continue;
87 }
88 pos2 = find(root2, current);
89 if (pos2 == null) {
90 // not found in root2
91 return true;
92 }
93 if (!pos1.page.equals(pos2.page)) {
94 // the page is different,
95 // so the entry has possibly changed
96 return true;
97 }
98 while (true) {
99 pos1 = pos1.parent;
100 if (pos1 == null) {
101 // reached end of pos1
102 state = 2;
103 pos2 = null;
104 break;
105 }
106 pos2 = pos2.parent;
107 if (pos2 == null || !pos1.page.equals(pos2.page)) {
108 if (pos1.index + 1 < map.getChildPageCount(pos1.page)) {
109 pos1 = new CursorPos(pos1.page.getChildPage(++pos1.index), 0, pos1);
110 pos1 = min(pos1);
111 break;
112 }
113 }
114 }
115 }
116 if (state == 2) {
117 if (pos2 == null) {
118 // init reading from root2
119 pos2 = new CursorPos(root2, 0, null);
120 pos2 = min(pos2);
121 }
122 // read from root2
123 pos2 = fetchNext(pos2);
124 if (pos2 == null) {
125 // reached the end of pos2
126 state = 3;
127 current = null;
128 continue;
129 }
130 pos1 = find(root1, current);
131 if (pos1 != null) {
132 // found a corresponding record
133 // so it was not deleted
134 // but now we may need to skip pages
135 if (!pos1.page.equals(pos2.page)) {
136 // the page is different
137 pos1 = null;
138 continue;
139 }
140 while (true) {
141 pos2 = pos2.parent;
142 if (pos2 == null) {
143 // reached end of pos1
144 state = 3;
145 current = null;
146 pos1 = null;
147 break;
148 }
149 pos1 = pos1.parent;
150 if (pos1 == null || !pos2.page.equals(pos1.page)) {
151 if (pos2.index + 1 < map.getChildPageCount(pos2.page)) {
152 pos2 = new CursorPos(pos2.page.getChildPage(++pos2.index), 0, pos2);
153 pos2 = min(pos2);
154 break;
155 }
156 }
157 }
158 pos1 = null;
159 continue;
160 }
161 // found no corresponding record
162 // so it was deleted
163 return true;
164 }
165 }
166 }
167
168 private CursorPos find(Page p, K key) {
169 // TODO combine with RangeCursor.min
170 // possibly move to MVMap
171 CursorPos pos = null;
172 while (true) {
173 if (p.isLeaf()) {
174 int x = key == null ? 0 : p.binarySearch(key);
175 if (x < 0) {
176 return null;
177 }
178 return new CursorPos(p, x, pos);
179 }
180 int x = key == null ? -1 : p.binarySearch(key);
181 if (x < 0) {
182 x = -x - 1;
183 } else {
184 x++;
185 }
186 pos = new CursorPos(p, x, pos);
187 p = p.getChildPage(x);
188 }
189 }
190
191 @SuppressWarnings("unchecked")
192 private CursorPos fetchNext(CursorPos p) {
193 while (p != null) {
194 if (p.index < p.page.getKeyCount()) {
195 current = (K) p.page.getKey(p.index++);
196 return p;
197 }
198 p = p.parent;
199 if (p == null) {
200 break;
201 }
202 if (p.index + 1 < map.getChildPageCount(p.page)) {
203 p = new CursorPos(p.page.getChildPage(++p.index), 0, p);
204 p = min(p);
205 }
206 }
207 current = null;
208 return p;
209 }
210
211 private static CursorPos min(CursorPos p) {
212 while (true) {
213 if (p.page.isLeaf()) {
214 return p;
215 }
216 Page c = p.page.getChildPage(0);
217 p = new CursorPos(c, 0, p);
218 }
219 }
220
221 }
222