001: /*
002: This source file is part of Smyle, a database library.
003: For up-to-date information, see http://www.drjava.de/smyle
004: Copyright (C) 2001 Stefan Reich (doc@drjava.de)
005:
006: This library is free software; you can redistribute it and/or
007: modify it under the terms of the GNU Lesser General Public
008: License as published by the Free Software Foundation; either
009: version 2.1 of the License, or (at your option) any later version.
010:
011: This library is distributed in the hope that it will be useful,
012: but WITHOUT ANY WARRANTY; without even the implied warranty of
013: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: Lesser General Public License for more details.
015:
016: You should have received a copy of the GNU Lesser General Public
017: License along with this library; if not, write to the Free Software
018: Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
019:
020: For full license text, see doc/license/lgpl.txt in this distribution
021: */
022:
023: package drjava.smyle.core;
024:
025: import java.util.*;
026: import java.io.*;
027: import org.artsProject.mcop.*;
028: import drjava.smyle.*;
029:
030: public final class PersistentBTree<A, B> extends BTree<A, B> {
031: final int m;
032: Handles<NodeImpl> handles;
033: Handle<NodeImpl> root;
034: Comparator<A> comparator;
035: MarDemar<A> aMarDemar;
036: MarDemar<B> bMarDemar;
037: ChunkManager cm;
038: ChunkRef handlesChunk, master;
039:
040: static final boolean debug = false;
041:
042: class SplitResult {
043: A key;
044: NodeImpl newNode;
045:
046: SplitResult(A key, NodeImpl newNode) {
047: this .key = key;
048: this .newNode = newNode;
049: }
050: }
051:
052: public class NodeImpl implements BTree<A, B>.Node,
053: Handled<NodeImpl> {
054: // leafs: n keys, n values
055: // non-leafs: n-1 keys, n children
056: ArrayList<A> keys;
057: ArrayList<Handle<NodeImpl>> children;
058: ArrayList<B> values;
059: Handle<NodeImpl> handle;
060:
061: public void setHandle(Handle<NodeImpl> handle) {
062: this .handle = handle;
063: }
064:
065: public boolean isLeaf() {
066: return children == null;
067: }
068:
069: public int numChildren() {
070: return children.size();
071: }
072:
073: public int numValues() {
074: return values.size();
075: }
076:
077: public BTree<A, B>.Node child(int index) {
078: return getChild(index);
079: }
080:
081: NodeImpl getChild(int index) {
082: return children.get(index).get();
083: }
084:
085: public B value(int index) {
086: return values.get(index);
087: }
088:
089: public A key(int index) {
090: return keys.get(index);
091: }
092:
093: NodeImpl(boolean leaf) {
094: keys = new ArrayList<A>();
095: if (leaf)
096: values = new ArrayList<B>();
097: else
098: children = new ArrayList<Handle<NodeImpl>>();
099: }
100:
101: /** returns true if an overflow occurred */
102: boolean put(A key, B value) {
103: int i = find(key);
104: if (isLeaf()) {
105: if (debug)
106: System.out.println("Leaf: inserting " + key
107: + " at " + i + " of " + keys.size());
108: if (i >= 0) {
109: // key exists, replace
110: keys.set(i, key);
111: values.set(i, value);
112: } else {
113: i = ~i;
114: // new key, insert
115: keys.add(i, key);
116: values.add(i, value);
117: }
118: save();
119:
120: return numValues() > m;
121: } else {
122: if (i < 0)
123: i = ~i;
124: else
125: ++i;
126: NodeImpl child = getChild(i);
127: if (debug) {
128: System.out.println("Delegating " + key
129: + " insertion to child " + i + " of "
130: + children.size());
131: if (i != 0)
132: System.out.println("Left key: "
133: + keys.get(i - 1));
134: if (i < keys.size())
135: System.out.println("Right key: " + keys.get(i));
136: }
137: if (child.put(key, value)) {
138: // handle overflow
139: SplitResult sr = child.split();
140: children.add(i + 1, handles.add(sr.newNode));
141: keys.add(i, sr.key);
142: save();
143: }
144:
145: return numChildren() > m;
146: }
147: }
148:
149: /** splits the node in half */
150: SplitResult split() {
151: if (isLeaf()) {
152: NodeImpl newNode = new NodeImpl(true);
153: int n = keys.size();
154: int i = n / 2;
155: if (debug)
156: System.out.println("Leaf splitting (m=" + m + ",n="
157: + n + ")");
158: List<A> subKeys = keys.subList(i, n);
159: List<B> subValues = values.subList(i, n);
160: newNode.keys.addAll(subKeys);
161: newNode.values.addAll(subValues);
162: subKeys.clear();
163: subValues.clear();
164: save();
165: if (debug)
166: System.out.println("L first: " + values.get(0)
167: + ", R first: " + newNode.values.get(0));
168: return new SplitResult(newNode.keys.get(0), newNode);
169: } else {
170: if (debug)
171: System.out.println("Node splitting");
172: NodeImpl newNode = new NodeImpl(false);
173: int n = children.size();
174: int i = n / 2;
175: A splitKey = keys.get(i - 1);
176: List<A> subKeys = keys.subList(i, n - 1);
177: List<Handle<NodeImpl>> subChildren = children.subList(
178: i, n);
179: newNode.keys.addAll(subKeys);
180: newNode.children.addAll(subChildren);
181: keys.subList(i - 1, n - 1).clear();
182: children.subList(i, n).clear();
183: save();
184: return new SplitResult(splitKey, newNode);
185: }
186: }
187:
188: int compare(A key1, A key2) {
189: return comparator != null ? comparator.compare(key1, key2)
190: : ((Comparable) key1).compareTo(key2);
191: }
192:
193: /** returns a non-negative index if key was found;
194: returns the one-complement of best-matching index otherwise */
195: int find(A key) {
196: /*int i = 0, c = -1;
197: while (i < keys.size() && (c = compare(keys.get(i), key)) < 0)
198: ++i;
199: return c == 0 ? i : ~i;*/
200:
201: int low = 0;
202: int high = keys.size() - 1;
203:
204: while (low <= high) {
205: int mid = (low + high) / 2;
206: int cmp = compare(keys.get(mid), key);
207:
208: if (cmp < 0)
209: low = mid + 1;
210: else if (cmp > 0)
211: high = mid - 1;
212: else
213: return mid;
214: }
215:
216: return ~low;
217: }
218:
219: /** returns true if an underflow occurred
220: (also if node was already underfull on method entrance) */
221: boolean remove(A key) {
222: int i = find(key);
223: if (isLeaf()) {
224: if (i >= 0) {
225: if (debug)
226: System.out.println("Leaf: removing " + key
227: + " at " + i + " of " + keys.size());
228: keys.remove(i);
229: values.remove(i);
230: save();
231: } else {
232: i = ~i;
233: if (debug)
234: System.out.println("Leaf: " + key
235: + " not found near " + i + " of "
236: + keys.size());
237: }
238:
239: return numValues() < (m + 1) / 2;
240: } else {
241: if (i >= 0)
242: ++i;
243: else
244: i = ~i;
245: NodeImpl child = getChild(i);
246: if (debug)
247: System.out.println("Delegating " + key
248: + " deletion to child " + i + " of "
249: + children.size());
250: if (child.remove(key)) {
251: // handle underflow
252: NodeImpl rChild;
253: if (i != 0) {
254: rChild = child;
255: child = getChild(--i);
256: } else
257: rChild = getChild(i + 1);
258: child.mergeWith(rChild, keys.get(i));
259: rChild.handle.dispose();
260: children.remove(i + 1);
261: keys.remove(i);
262: if (child.overfull()) {
263: SplitResult sr = child.split();
264: children.add(i + 1, handles.add(sr.newNode));
265: keys.add(i, sr.key);
266: }
267: save();
268: }
269:
270: return numChildren() < (m + 1) / 2;
271: }
272: }
273:
274: boolean overfull() {
275: return isLeaf() ? numValues() > m : numChildren() > m;
276: }
277:
278: void mergeWith(NodeImpl node, A middleKey) {
279: if (isLeaf()) {
280: keys.addAll(node.keys);
281: values.addAll(node.values);
282: } else {
283: keys.add(middleKey);
284: keys.addAll(node.keys);
285: children.addAll(node.children);
286: }
287: save();
288: }
289:
290: Handle save() {
291: handle.invalidate();
292: return handle;
293: }
294:
295: void marshal(Buffer b) {
296: b.writeBoolean(isLeaf());
297: if (isLeaf()) {
298: b.writeLong(values.size());
299: for (int i = 0; i < values.size(); i++) {
300: aMarDemar.marshal(b, keys.get(i));
301: bMarDemar.marshal(b, values.get(i));
302: }
303: } else {
304: b.writeLong(children.size());
305: for (int i = 0; i < children.size(); i++) {
306: if (i != 0)
307: aMarDemar.marshal(b, keys.get(i - 1));
308: children.get(i).marshal(b);
309: }
310: }
311: }
312:
313: NodeImpl(Buffer b) {
314: keys = new ArrayList<A>();
315: if (b.readBoolean()) {
316: values = new ArrayList<B>();
317: int n = b.readLong();
318: for (int i = 0; i < n; i++) {
319: keys.add(aMarDemar.read(b));
320: values.add(bMarDemar.read(b));
321: }
322: } else {
323: children = new ArrayList<Handle<NodeImpl>>();
324: int n = b.readLong();
325: for (int i = 0; i < n; i++) {
326: if (i != 0)
327: keys.add(aMarDemar.read(b));
328: children.add(handles.read(b));
329: }
330: }
331: }
332: }
333:
334: class NodeMarDemar implements MarDemar<NodeImpl> {
335: public void marshal(Buffer b, NodeImpl node) {
336: node.marshal(b);
337: }
338:
339: public NodeImpl read(Buffer b) {
340: return new NodeImpl(b);
341: }
342: }
343:
344: /** @param m maximum number of children per node */
345: public PersistentBTree(int m, Comparator<A> comparator,
346: MarDemar<A> aMarDemar, MarDemar<B> bMarDemar,
347: ChunkManager cm, ChunkRef master) {
348: this .m = m;
349: this .comparator = comparator;
350: this .aMarDemar = aMarDemar;
351: this .bMarDemar = bMarDemar;
352: this .cm = cm;
353: this .master = master;
354:
355: if (master != null) {
356: Buffer b = cm.readChunk(master);
357: handles = new Handles<NodeImpl>(cm, new NodeMarDemar(),
358: new ChunkRef(b));
359: root = handles.read(b);
360: } else {
361: handles = new Handles<NodeImpl>(cm, new NodeMarDemar());
362: root = handles.add(new NodeImpl(true)); // gets handle index 0
363: }
364: }
365:
366: public ChunkRef flush() {
367: ChunkRef chunk = handles.flush();
368: if (!chunk.equals(handlesChunk)) {
369: handlesChunk = chunk;
370: Buffer b = new Buffer();
371: chunk.writeType(b);
372: root.marshal(b);
373: master = cm.createChunk(b);
374: }
375: return master;
376: }
377:
378: public BTree<A, B>.Node root() {
379: return root.get();
380: }
381:
382: public void put(A a, B b) {
383: if (root.get().put(a, b)) {
384: // handle overflow
385: SplitResult sr = root.get().split();
386: NodeImpl newRoot = new NodeImpl(false);
387: newRoot.children.add(root);
388: newRoot.children.add(handles.add(sr.newNode));
389: newRoot.keys.add(sr.key);
390: root = handles.add(newRoot);
391: }
392: }
393:
394: public void remove(A a) {
395: if (root.get().remove(a)) {
396: // only handle extreme underflow case: root only contains one child
397: NodeImpl r = root.get();
398: if (!r.isLeaf() && r.numChildren() == 1) {
399: r.children.get(0).dispose();
400: root.set(r.getChild(0));
401: }
402: }
403: }
404:
405: public B get(A key) {
406: NodeImpl node = root.get();
407:
408: while (!node.isLeaf()) {
409: int i = node.find(key);
410: if (i >= 0)
411: ++i;
412: else
413: i = ~i;
414: node = node.getChild(i);
415: }
416:
417: int i = node.find(key);
418: if (i >= 0) {
419: return node.values.get(i);
420: } else {
421: return null;
422: }
423: }
424:
425: public int m() {
426: return m;
427: }
428:
429: public void clear() {
430: root.set(new NodeImpl(true));
431: }
432:
433: public void collectChunks(BitSet whiteList) {
434: handles.collectChunks(whiteList);
435: if (master != null)
436: whiteList.set(master.index);
437: }
438: }
|