|
1
21 package com.db4o.inside.ix;
22
23 import com.db4o.*;
24 import com.db4o.foundation.Tree;
25
26
27
30 class IxFileRangeReader {
31
32 private int _baseAddress;
33 private int _baseAddressOffset;
34 private int _addressOffset;
35
36 private final Indexable4 _handler;
37
38 private int _lower;
39 private int _upper;
40 private int _cursor;
41
42 private final YapReader _reader;
43
44 final int _slotLength;
45
46 final int _linkLegth;
47
48 IxFileRangeReader(Indexable4 handler) {
49 _handler = handler;
50 _linkLegth = handler.linkLength();
51 _slotLength = _linkLegth + YapConst.INT_LENGTH;
52 _reader = new YapReader(_slotLength);
53 }
54
55 Tree add(IxFileRange fileRange, final Tree newTree) {
56 setFileRange(fileRange);
57 YapFile yf = fileRange.stream();
58 Transaction trans = fileRange.trans();
59 while (true) {
60 _reader.read(yf, _baseAddress, _baseAddressOffset + _addressOffset);
61 _reader._offset = 0;
62
63 int cmp = compare(trans);
64
65 if (cmp == 0) {
66 int parentID = _reader.readInt();
67 cmp = parentID - ((IxPatch) newTree)._parentID;
68 }
69 if (cmp > 0) {
70 _upper = _cursor - 1;
71 if (_upper < _lower) {
72 _upper = _lower;
73 }
74 } else if (cmp < 0) {
75 _lower = _cursor + 1;
76 if (_lower > _upper) {
77 _lower = _upper;
78 }
79 } else {
80 if (newTree instanceof IxRemove) {
81 if (_cursor == 0) {
82 newTree._preceding = fileRange._preceding;
83 if (fileRange._entries == 1) {
84 newTree._subsequent = fileRange._subsequent;
85 return newTree.balanceCheckNulls();
86 }
87 fileRange._entries--;
88 fileRange.incrementAddress(_slotLength);
89 fileRange._preceding = null;
90 newTree._subsequent = fileRange;
91 } else if (_cursor + 1 == fileRange._entries) {
92 newTree._preceding = fileRange;
93 newTree._subsequent = fileRange._subsequent;
94 fileRange._subsequent = null;
95 fileRange._entries--;
96 } else {
97 return insert(fileRange, newTree, _cursor, 0);
98 }
99 fileRange.calculateSize();
100 return newTree.balanceCheckNulls();
101 }
102 if (_cursor == 0) {
103 newTree._subsequent = fileRange;
104 return newTree.rotateLeft();
105 } else if (_cursor == fileRange._entries) {
106 newTree._preceding = fileRange;
107 return newTree.rotateRight();
108 }
109 return insert(fileRange, newTree, _cursor, cmp);
110 }
111 if (!adjustCursor()) {
112 if (_cursor == 0 && cmp > 0) {
113 return fileRange.add(newTree, 1);
114 }
115 if (_cursor == fileRange._entries - 1 && cmp < 0) {
116 return fileRange.add(newTree, -1);
117 }
118 return insert(fileRange, newTree, _cursor, cmp);
119 }
120 }
121 }
122
123 private boolean adjustCursor() {
124 if (_upper < _lower) {
125 return false;
126 }
127 int oldCursor = _cursor;
128 _cursor = _lower + ((_upper - _lower) / 2);
129 if (_cursor == oldCursor && _cursor == _lower && _lower < _upper) {
130 _cursor++;
131 }
132 _addressOffset = _cursor * _slotLength;
133 return _cursor != oldCursor;
134 }
135
136 int compare(IxFileRange fileRange, int[] matches) {
137
138 setFileRange(fileRange);
139 YapFile yf = fileRange.stream();
140 Transaction trans = fileRange.trans();
141
142 int res = 0;
143
144 while (true) {
145 _reader.read(yf, _baseAddress, _baseAddressOffset + _addressOffset);
146 _reader._offset = 0;
147 int cmp = compare(trans);
148 if (cmp > 0) {
149 _upper = _cursor - 1;
150 } else if (cmp < 0) {
151 _lower = _cursor + 1;
152 } else {
153 break;
154 }
155 if (!adjustCursor()) {
156 if(_cursor <= 0){
157 if( ! (cmp < 0 && fileRange._entries > 1) ){
158 res = cmp;
159 }
160 }else if(_cursor >= (fileRange._entries - 1 ) ){
161 if(cmp < 0){
162 res = cmp;
163 }
164 }
165 break;
166 }
167 }
168
169 matches[0] = _lower;
170 matches[1] = _upper;
171
172 if (_lower > _upper) {
173 return res;
174 }
175
176 int tempCursor = _cursor;
177 _upper = _cursor;
178 adjustCursor();
179 while (true) {
180 _reader.read(yf, _baseAddress, _baseAddressOffset + _addressOffset);
181 _reader._offset = 0;
182 int cmp = compare(trans);
183 if (cmp == 0) {
184 _upper = _cursor;
185 } else {
186 _lower = _cursor + 1;
187 if (_lower > _upper) {
188 matches[0] = _upper;
189 break;
190 }
191 }
192 if (!adjustCursor()) {
193 matches[0] = _upper;
194 break;
195 }
196 }
197 _upper = matches[1];
198 _lower = tempCursor;
199 if (_lower > _upper) {
200 _lower = _upper;
201 }
202 adjustCursor();
203 while (true) {
204 _reader.read(yf, _baseAddress, _baseAddressOffset + _addressOffset);
205 _reader._offset = 0;
206 int cmp = compare(trans);
207 if (cmp == 0) {
208 _lower = _cursor;
209 } else {
210 _upper = _cursor - 1;
211 if (_upper < _lower) {
212 matches[1] = _lower;
213 break;
214 }
215 }
216 if (!adjustCursor()) {
217 matches[1] = _lower;
218 break;
219 }
220 }
221 return res;
222 }
223
224 private final int compare(Transaction trans) {
225 return _handler.compareTo(_handler
226 .comparableObject(trans, _handler.readIndexEntry(_reader)));
227 }
228
229 private Tree insert(IxFileRange fileRange, Tree a_new, int a_cursor, int a_cmp) {
230 int incStartNewAt = a_cmp <= 0 ? 1 : 0;
231 int newAddressOffset = (a_cursor + incStartNewAt) * _slotLength;
232 int newEntries = fileRange._entries - a_cursor - incStartNewAt;
233 if (Deploy.debug) {
234 if (newEntries == 0) {
235 throw new RuntimeException  ("No zero new entries permitted here.");
241 }
242 }
243
244 fileRange._entries = a_cmp < 0 ? a_cursor + 1 : a_cursor;
245 IxFileRange ifr = new IxFileRange(fileRange._fieldTransaction, _baseAddress,
246 _baseAddressOffset + newAddressOffset, newEntries);
247 ifr._subsequent = fileRange._subsequent;
248 fileRange._subsequent = null;
249 a_new._preceding = fileRange.balanceCheckNulls();
250 a_new._subsequent = ifr.balanceCheckNulls();
251 return a_new.balance();
252 }
253
254 private void setFileRange(IxFileRange a_fr) {
255 _lower = 0;
256 _upper = a_fr._entries - 1;
257 _baseAddress = a_fr._address;
258 _baseAddressOffset = a_fr._addressOffset;
259 adjustCursor();
260 }
261 } |
Popular Tags |
Java API By Example, From Geeks To Geeks.