|
1
24 package org.objectweb.jalisto.se.query.btree;
25
26 import org.objectweb.jalisto.se.impl.LogicalOid;
27 import org.objectweb.jalisto.se.impl.InFileAddress;
28 import org.objectweb.jalisto.se.api.query.FielComparator;
29 import org.objectweb.jalisto.se.api.query.Operator;
30 import org.objectweb.jalisto.se.query.exception.QueryEngineException;
31 import org.objectweb.jalisto.se.impl.server.DataWrapperImpl;
32 import org.objectweb.jalisto.se.query.operator.OperatorFactory;
33
34 import java.util.ArrayList  ;
35 import java.util.List ;
36 import java.util.Set ;
37
38 public class BTreeNode extends DataWrapperImpl {
39 public BTreeNode(BTree tree, InFileAddress fatherIfa) {
40 this.cells = new ArrayList ();
41 this.fatherIfa = fatherIfa;
42 this.tree = tree;
43 this.overSize = tree.getFieldDescription().getIndexDescription().getNodeSize();
44 if ((overSize % 2) != 0) {
45 overSize++;
46 }
47 setIfa(tree.getIndexManager().getNewNodeIfaAndInsert(tree, this));
48 }
49
50 public InFileAddress getOidsIfa(Object value, FielComparator comparator) {
51 for (int i = 0; i < cells.size(); i++) {
52 BTreeCell cell = (BTreeCell) cells.get(i);
53 if (equal.executeSingle(comparator, value, cell.getValue())) {
54 return cell.getOidsIfa();
55 } else if (greater.executeSingle(comparator, value, cell.getValue())) {
56 InFileAddress subIfa = cell.getSubIfa();
57 if (subIfa != null) {
58 BTreeNode node = tree.getIndexManager().readNodeInBase(tree, subIfa);
59 return node.getOidsIfa(value, comparator);
60 } else { return null;
62 }
63 }
64 }
65 return null;
66 }
67
68 public void insertOid(FielComparator comparator, Object value, LogicalOid floid) {
69 if (cells.isEmpty()) {
70 createAndAddNewCell(0, floid, value);
71 } else {
72 boolean isInserted = false;
73 for (int i = 0; i < cells.size(); i++) {
74 BTreeCell cell = (BTreeCell) cells.get(i);
75 if (equal.executeSingle(comparator, value, cell.value)) {
76 OidCollection oids = tree.getIndexManager().readOidsInBase(tree, cell.oidsIfa);
77 oids.addOid(floid);
78 tree.getIndexManager().updateLeaf(oids);
79 return;
80 } else if (greater.executeSingle(comparator, value, cell.value)) {
81 if (cell.getSubIfa() != null) { BTreeNode subNode = tree.getIndexManager().readNodeInBase(tree, cell.getSubIfa());
83 subNode.insertOid(comparator, value, floid);
84 return;
85 }
86 createAndAddNewCell(i, floid, value);
88 isInserted = true;
89 i = cells.size();
90 }
91 }
92 if (!isInserted) { OidCollection oids = new OidCollection();
94 oids.addOid(floid);
95 InFileAddress oidsIfa = tree.getIndexManager().getNewOidsCollIfaAndInsert(tree, oids);
96 changeMaxValueDown(value, oidsIfa, comparator);
97 return;
98 }
99 if (cells.size() >= overSize) {
100 split(comparator);
101 }
102 }
103 tree.getIndexManager().updateNode(this);
104 }
105
106 public void removeOid(Object value, LogicalOid oid, FielComparator comparator) {
107 for (int i = 0; i < cells.size(); i++) {
108 BTreeCell cell = (BTreeCell) cells.get(i);
109 if (equal.executeSingle(comparator, value, cell.getValue())) {
110 OidCollection oids = tree.getIndexManager().readOidsInBase(tree, cell.getOidsIfa());
111 oids.removeOid(oid);
112 if (oids.isEmpty()) {
113 tree.getIndexManager().removeLeaf(tree, oids.getIfa());
114 getNode(value, comparator).removeCell(value, comparator);
115 } else {
116 tree.getIndexManager().updateLeaf(oids);
117 }
119 return;
120 } else if (greater.executeSingle(comparator, value, cell.getValue())) {
121 InFileAddress subIfa = cell.getSubIfa();
122 if (subIfa != null) {
123 BTreeNode node = tree.getIndexManager().readNodeInBase(tree, subIfa);
124 node.removeOid(value, oid, comparator);
125 return;
126 } else { throw new QueryEngineException("remove oid for a non existing value : " + value);
128 }
129 }
130 }
131 }
132
133 public InFileAddress getKeys(Set in) {
134 for (int i = 0; i < cells.size(); i++) {
135 BTreeCell cell = (BTreeCell) cells.get(i);
136 if (cell.getSubIfa() == null) {
137 in.add(cell.getValue());
138 }
139 }
140 return nextIfa;
141 }
142
143 public void deleteYourself() {
144 for (int i = 0; i < cells.size(); i++) {
145 BTreeCell cell = (BTreeCell) cells.get(i);
146 if (cell.getSubIfa() != null) {
147 BTreeNode node = tree.getIndexManager().readNodeInBase(tree, cell.getSubIfa());
148 node.deleteYourself();
149 } else {
150 tree.getIndexManager().removeLeaf(tree, cell.getOidsIfa());
151 }
152 }
153 tree.getIndexManager().removeNode(tree, ifa);
154 }
155
156
159
160 public BTreeNode getNode(Object value, FielComparator comparator) {
161 for (int i = 0; i < cells.size(); i++) {
162 BTreeCell cell = (BTreeCell) cells.get(i);
163 if (equal.executeSingle(comparator, value, cell.getValue())) {
164 InFileAddress subIfa = cell.getSubIfa();
165 if (subIfa != null) {
166 BTreeNode node = tree.getIndexManager().readNodeInBase(tree, subIfa);
167 return node.getNode(value, comparator);
168 } else { return this;
170 }
171 } else if (greater.executeSingle(comparator, value, cell.getValue())) {
172 InFileAddress subIfa = cell.getSubIfa();
173 if (subIfa != null) {
174 BTreeNode node = tree.getIndexManager().readNodeInBase(tree, subIfa);
175 return node.getNode(value, comparator);
176 } else { return null;
178 }
179 }
180 }
181 return null;
182 }
183
184 private void split(FielComparator comparator) {
185 BTreeNode newNode = new BTreeNode(tree, fatherIfa);
186 InFileAddress newIfa = newNode.getIfa();
187
188 if (ifa.equals(tree.getFirstIfa())) {
190 tree.setFirstIfa(newIfa);
191 }
192
193 for (int i = 0; i < overSize / 2; i++) {
195 BTreeCell c = (BTreeCell) cells.remove(0); newNode.cells.add(c);
197 if (c.getSubIfa() != null) { tree.getIndexManager().readNodeInBase(tree, c.getSubIfa()).setFatherIfa(newIfa);
199 }
200 }
201
202 if (lastIfa != null) {
204 tree.getIndexManager().readNodeInBase(tree, lastIfa).setNextIfa(newIfa);
205 newNode.setLastIfa(lastIfa);
206 }
207 newNode.setNextIfa(ifa);
208 lastIfa = newIfa;
209
210 if (fatherIfa != null) {
211 BTreeNode fatherNode = tree.getIndexManager().readNodeInBase(tree, fatherIfa);
212 BTreeCell c = newNode.getLastCell();
213 fatherNode.insertCell(c.value, c.oidsIfa, newIfa, comparator); tree.getIndexManager().updateNode(fatherNode);
216 } else { BTreeNode newRootNode = new BTreeNode(tree, null);
218 InFileAddress newRootIfa = newRootNode.getIfa();
219 fatherIfa = newRootIfa;
220 newNode.setFatherIfa(newRootIfa);
221 BTreeCell c = newNode.getLastCell();
222 newRootNode.insertCell(c.value, c.oidsIfa, newIfa, comparator);
223 c = getLastCell();
224 newRootNode.insertCell(c.value, c.oidsIfa, ifa, comparator);
225 tree.setRootIfa(newRootIfa);
226 tree.getIndexManager().updateNode(newRootNode);
227 }
228 }
229
230 private void createAndAddNewCell(int i, LogicalOid floid, Object value) {
231 OidCollection oids = new OidCollection();
232 oids.addOid(floid);
233 InFileAddress oidsIfa = tree.getIndexManager().getNewOidsCollIfaAndInsert(tree, oids);
234 BTreeCell newCell = new BTreeCell();
235 newCell.setValue(value);
236 newCell.setOidsIfa(oidsIfa);
237 cells.add(i, newCell);
238 }
239
240 private void insertCell(Object value, InFileAddress oidsIfa, InFileAddress subIfa, FielComparator comparator) {
241 BTreeCell newCell = new BTreeCell();
242 newCell.setValue(value);
243 newCell.setOidsIfa(oidsIfa);
244 newCell.setSubIfa(subIfa);
245 for (int i = 0; i < cells.size(); i++) {
246 BTreeCell cell = (BTreeCell) cells.get(i);
247 if (greater.executeSingle(comparator, value, cell.value)) {
248 cells.add(i, newCell);
249 return;
250 }
251 }
252 cells.add(newCell);
253 }
254
255 private void removeCell(Object value, FielComparator comparator) {
256 BTreeCell cell = getCellForValue(value, comparator);
257 if (cell == null) {
258 throw new QueryEngineException("no cell for value " + value);
259 }
260 int index = cells.indexOf(cell);
261 if (index != -1) {
262 int size = cells.size();
263 cells.remove(index);
264 if (size == 1) { if (nextIfa != null) {
266 BTreeNode nextCell = tree.getIndexManager().readNodeInBase(tree, nextIfa);
267 nextCell.setLastIfa(lastIfa);
268 tree.getIndexManager().updateNode(nextCell);
269 }
270 if (lastIfa != null) {
271 BTreeNode lastCell = tree.getIndexManager().readNodeInBase(tree, lastIfa);
272 lastCell.setNextIfa(nextIfa);
273 tree.getIndexManager().updateNode(lastCell);
274 }
275 if (tree.getFirstIfa().equals(ifa)) {
276 if (nextIfa != null) {
277 tree.setFirstIfa(nextIfa);
278 } else if (fatherIfa != null) {
279 tree.setFirstIfa(fatherIfa);
280 } }
282 if (fatherIfa != null) {
283 BTreeNode father = tree.getIndexManager().readNodeInBase(tree, fatherIfa);
284 father.removeCell(value, comparator);
285 tree.getIndexManager().removeNode(tree, ifa); }
287 } else if (index == (size - 1)) { if (fatherIfa != null) {
289 BTreeNode father = tree.getIndexManager().readNodeInBase(tree, fatherIfa);
290 BTreeCell last = getLastCell();
291 father.changeMaxValueUp(cell.getValue(), last.getValue(),
292 cell.getOidsIfa(), last.getOidsIfa(), comparator);
293 }
294 }
295 }
296 tree.getIndexManager().updateNode(this);
297 }
298
299 private BTreeCell getCellForValue(Object value, FielComparator comparator) {
300 for (int i = 0; i < cells.size(); i++) {
301 BTreeCell cell = (BTreeCell) cells.get(i);
302 if (equal.executeSingle(comparator, value, cell.value)) {
303 return cell;
304 }
305 }
306 return null;
307 }
308
309 private void changeMaxValueDown(Object value, InFileAddress oidsIfa, FielComparator comparator) {
310 BTreeCell cell = getLastCell();
311 InFileAddress subIfa = cell.getSubIfa();
312 if (subIfa != null) {
313 cell.setValue(value);
314 cell.setOidsIfa(oidsIfa);
315 tree.getIndexManager().updateNode(this);
316 tree.getIndexManager().readNodeInBase(tree, subIfa).changeMaxValueDown(value, oidsIfa, comparator);
317 } else {
318 BTreeCell newCell = new BTreeCell();
319 newCell.setValue(value);
320 newCell.setOidsIfa(oidsIfa);
321 cells.add(newCell);
322 if (cells.size() >= overSize) {
323 split(comparator);
324 }
325 tree.getIndexManager().updateNode(this);
326 }
327 }
328
329 private void changeMaxValueUp(Object oldValue, Object newValue,
330 InFileAddress oldOidsIfa, InFileAddress newOidsIfa,
331 FielComparator comparator) {
332 BTreeCell cell = getCellForValue(oldValue, comparator);
333 if (cell == null) {
334 throw new QueryEngineException("don't find cell with value " + oldValue);
335 }
336 BTreeCell last = getLastCell();
337 if (last.equals(cell)) {
338 if (fatherIfa != null) {
339 BTreeNode father = tree.getIndexManager().readNodeInBase(tree, fatherIfa);
340 father.changeMaxValueUp(oldValue, newValue,
341 oldOidsIfa, newOidsIfa, comparator);
342 }
343 }
344 cell.setValue(newValue);
345 cell.setOidsIfa(newOidsIfa);
346 tree.getIndexManager().updateNode(this);
347
348 }
349
350
353
354 public InFileAddress getLastIfa() {
355 return lastIfa;
356 }
357
358 public void setLastIfa(InFileAddress lastIfa) {
359 this.lastIfa = lastIfa;
360 }
361
362 public InFileAddress getNextIfa() {
363 return nextIfa;
364 }
365
366 public void setNextIfa(InFileAddress nextIfa) {
367 this.nextIfa = nextIfa;
368 }
369
370 public BTreeCell getLastCell() {
371 return (BTreeCell) cells.get(cells.size() - 1);
372 }
373
374 public InFileAddress getFatherIfa() {
375 return fatherIfa;
376 }
377
378 public void setFatherIfa(InFileAddress fatherIfa) {
379 this.fatherIfa = fatherIfa;
380 }
381
382 public void setTree(BTree tree) {
383 this.tree = tree;
384 }
385
386 public InFileAddress getIfa() {
387 return ifa;
388 }
389
390 public void setIfa(InFileAddress ifa) {
391 this.ifa = ifa;
392 }
393
394 public String toString() {
395 return "BTreeNode(" + cells.size() + ")";
396 }
397
398 public String toFullString(List nodes, List oids) {
399 StringBuffer sb = new StringBuffer ();
400 sb.append(ifa).append(" : ");
401 sb.append("BTree(");
402 sb.append("lastIfa(").append(lastIfa).append("),");
403 sb.append("nextIfa(").append(nextIfa).append("),");
404 sb.append("fatherIfa(").append(fatherIfa).append("),");
405 sb.append("cells:").append(cells).append(")\n");
406 for (int i = 0; i < cells.size(); i++) {
407 BTreeCell cell = (BTreeCell) cells.get(i);
408 if (cell.getSubIfa() != null) {
409 nodes.add(cell.getSubIfa());
410 } else {
411 oids.add(cell.getOidsIfa());
412 }
413 }
414 return sb.toString();
415 }
416
417
418 protected short overSize; protected ArrayList cells;
420 private InFileAddress fatherIfa;
421 protected transient BTree tree;
422
423 private InFileAddress lastIfa;
424 private InFileAddress nextIfa;
425 private InFileAddress ifa;
426
427 protected static final Operator greater = OperatorFactory.getGreaterOperator();
428 protected static final Operator equal = OperatorFactory.getEqualOperator();
429 }
430 |
Popular Tags |
Java API By Example, From Geeks To Geeks.