001: /*
002:
003: Derby - Class org.apache.derby.impl.store.access.sort.SortBuffer
004:
005: Licensed to the Apache Software Foundation (ASF) under one or more
006: contributor license agreements. See the NOTICE file distributed with
007: this work for additional information regarding copyright ownership.
008: The ASF licenses this file to you under the Apache License, Version 2.0
009: (the "License"); you may not use this file except in compliance with
010: the License. You may obtain a copy of the License at
011:
012: http://www.apache.org/licenses/LICENSE-2.0
013:
014: Unless required by applicable law or agreed to in writing, software
015: distributed under the License is distributed on an "AS IS" BASIS,
016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017: See the License for the specific language governing permissions and
018: limitations under the License.
019:
020: */
021:
022: package org.apache.derby.impl.store.access.sort;
023:
024: import org.apache.derby.iapi.services.sanity.SanityManager;
025: import org.apache.derby.iapi.error.StandardException;
026: import org.apache.derby.iapi.store.access.SortObserver;
027:
028: import org.apache.derby.iapi.types.DataValueDescriptor;
029:
030: /**
031:
032: This class implements an in-memory ordered set
033: based on the balanced binary tree algorithm from
034: Knuth Vol. 3, Sec. 6.2.3, pp. 451-471.
035: Nodes are always maintained in order,
036: so that inserts and deletes can be intermixed.
037: <P>
038: This algorithm will insert/delete N elements
039: in O(N log(N)) time using O(N) space.
040:
041: **/
042:
043: class SortBuffer {
044: /**
045: Returned from insert when the row was inserted
046: without incident.
047: **/
048: public static final int INSERT_OK = 0;
049:
050: /**
051: Returned from insert when the row which was
052: inserted was a duplicate. The set will have
053: aggregated it in.
054: **/
055: public static final int INSERT_DUPLICATE = 1;
056:
057: /**
058: Returned from insert when the row was not able to be
059: inserted because the set was full.
060: **/
061: public static final int INSERT_FULL = 2;
062:
063: /**
064: The sort this set is associated with.
065: **/
066: private MergeSort sort;
067:
068: /**
069: Where to allocate nodes from.
070: **/
071: private NodeAllocator allocator = null;
072:
073: /**
074: Special head node for the tree. Head.rightLink is the
075: root of the tree.
076: **/
077: private Node head = null;
078:
079: /**
080: The current height of the tree.
081: **/
082: private int height = 0;
083:
084: /**
085: Set, as a side effect of deleteLeftMost (only), to the
086: key from the node that was deleted from the tree. This
087: field is only valid after a call to deleteLeftMost.
088: **/
089: private DataValueDescriptor[] deletedKey;
090:
091: /**
092: Set, as a side effect of deleteLeftMost and rotateRight,
093: if the subtree they're working on decreased in height.
094: This field is only valid after a call to deleteLeftMost
095: or rotateRight.
096: **/
097: private boolean subtreeShrunk;
098:
099: /**
100: Set by the setNextAux() method. This value is stuffed
101: into the aux field of the next node that's allocated.
102: **/
103: private int nextAux;
104:
105: /**
106: Read by the getLastAux() method. This value is read out
107: of the last node that was deallocated from the tree.
108: **/
109: private int lastAux;
110:
111: /**
112: Arrange that the next node allocated in the tree have
113: it's aux field set to the argument.
114: **/
115: public void setNextAux(int aux) {
116: nextAux = aux;
117: }
118:
119: /**
120: Retrieve the aux value from the last node deallocated
121: from the tree.
122: **/
123: public int getLastAux() {
124: return lastAux;
125: }
126:
127: /**
128: Construct doesn't do anything, callers must call init
129: and check its return code.
130: **/
131: public SortBuffer(MergeSort sort) {
132: this .sort = sort;
133: }
134:
135: /**
136: Initialize. Returns false if the allocator
137: couldn't be initialized.
138: **/
139: public boolean init() {
140: allocator = new NodeAllocator();
141:
142: boolean initOK = false;
143:
144: if (sort.sortBufferMin > 0)
145: initOK = allocator.init(sort.sortBufferMin,
146: sort.sortBufferMax);
147: else
148: initOK = allocator.init(sort.sortBufferMax);
149:
150: if (initOK == false) {
151: allocator = null;
152: return false;
153: }
154: reset();
155: return true;
156: }
157:
158: public void reset() {
159: allocator.reset();
160: head = allocator.newNode();
161: height = 0;
162: }
163:
164: public void close() {
165: if (allocator != null)
166: allocator.close();
167: allocator = null;
168: height = 0;
169: head = null;
170: }
171:
172: /**
173: Grow by a certain percent if we can
174: */
175: public void grow(int percent) {
176: if (percent > 0)
177: allocator.grow(percent);
178: }
179:
180: /**
181: Return the number of elements this sorter can sort.
182: It's the capacity of the node allocator minus one
183: because the sorter uses one node for the head.
184: **/
185: public int capacity() {
186: if (allocator == null)
187: return 0;
188: return allocator.capacity() - 1;
189: }
190:
191: /**
192: Insert a key k into the tree. Returns true if the
193: key was inserted, false if the tree is full. Silently
194: ignores duplicate keys.
195: <P>
196: See Knuth Vol. 3, Sec. 6.2.3, pp. 455-457 for the algorithm.
197: **/
198: public int insert(DataValueDescriptor[] k) throws StandardException {
199: int c;
200: Node p, q, r, s, t;
201:
202: if (head.rightLink == null) {
203: if ((sort.sortObserver != null)
204: && ((k = sort.sortObserver.insertNonDuplicateKey(k)) == null)) {
205: return INSERT_DUPLICATE;
206: }
207:
208: q = allocator.newNode();
209: q.key = k;
210: q.aux = nextAux;
211: head.rightLink = q;
212: height = 1;
213: return INSERT_OK;
214: }
215:
216: // [A1. Initialize]
217: t = head;
218: p = s = head.rightLink;
219:
220: // Search
221: while (true) {
222: // [A2. Compare]
223: c = sort.compare(k, p.key);
224: if (c == 0) {
225: // The new key compares equal to the
226: // current node's key.
227:
228: // See if we can use the aggregators
229: // to get rid of the new key.
230: if ((sort.sortObserver != null)
231: && ((k = sort.sortObserver.insertDuplicateKey(
232: k, p.key)) == null)) {
233: return INSERT_DUPLICATE;
234: }
235:
236: // Keep the duplicate key...
237: // Allocate a new node for the key.
238: q = allocator.newNode();
239: if (q == null)
240: return INSERT_FULL;
241: q.aux = nextAux;
242:
243: // Link the new node onto the current
244: // node's duplicate chain. The assumption
245: // is made that a newly allocated node
246: // has null left and right links.
247: q.key = k;
248: q.dupChain = p.dupChain;
249: p.dupChain = q;
250:
251: // From the caller's perspective this was
252: // not a duplicate insertion.
253: return INSERT_OK;
254: }
255:
256: if (c < 0) {
257: // [A3. Move left]
258: q = p.leftLink;
259: if (q == null) {
260: q = allocator.newNode();
261: if (q == null)
262: return INSERT_FULL;
263: q.aux = nextAux;
264: p.leftLink = q;
265: break;
266: }
267: } else // c > 0
268: {
269: // [A4. Move right]
270: q = p.rightLink;
271: if (q == null) {
272: q = allocator.newNode();
273: if (q == null)
274: return INSERT_FULL;
275: q.aux = nextAux;
276: p.rightLink = q;
277: break;
278: }
279: }
280:
281: if (q.balance != 0) {
282: t = p;
283: s = q;
284: }
285: p = q;
286: }
287:
288: /*
289: * [A5. Insert]
290: * Node has been allocated and placed for k.
291: * Initialize it.
292: */
293:
294: if ((sort.sortObserver != null)
295: && ((k = sort.sortObserver.insertNonDuplicateKey(k)) == null)) {
296: return INSERT_DUPLICATE;
297: }
298: q.key = k;
299:
300: /*
301: * [A6. Adjust balance factors for nodes between
302: * s and q]
303: */
304:
305: c = sort.compare(k, s.key);
306: if (c < 0)
307: r = p = s.leftLink;
308: else
309: r = p = s.rightLink;
310:
311: while (p != q) {
312: if (sort.compare(k, p.key) < 0) {
313: p.balance = -1;
314: p = p.leftLink;
315: } else // sort.compare(k, p.key) > 0
316: {
317: p.balance = 1;
318: p = p.rightLink;
319: }
320: }
321:
322: // [A7. Balancing act]
323:
324: int a = (c > 0 ? 1 : ((c == 0) ? 0 : -1));
325:
326: if (s.balance == 0) {
327: //debug("A7 (i). The tree has gotten higher");
328: s.balance = a;
329: height++;
330: return INSERT_OK;
331: }
332:
333: if (s.balance == -a) {
334: //debug("A7 (ii). The tree has gotten more balanced");
335: s.balance = 0;
336: return INSERT_OK;
337: }
338:
339: //debug("A7 (iii). The tree has gotten more out of balance");
340:
341: // s.balance == a
342: if (r.balance == a) {
343: //debug("A8. Single rotation");
344: p = r;
345: s.setLink(a, r.link(-a));
346: r.setLink(-a, s);
347: s.balance = 0;
348: r.balance = 0;
349: } else // r.balance == -a
350: {
351: //debug("A8. Double rotation");
352: p = r.link(-a);
353: r.setLink(-a, p.link(a));
354: p.setLink(a, r);
355: s.setLink(a, p.link(-a));
356: p.setLink(-a, s);
357:
358: if (p.balance == a) {
359: s.balance = -a;
360: r.balance = 0;
361: } else if (p.balance == 0) {
362: s.balance = 0;
363: r.balance = 0;
364: } else // p.balance == -a
365: {
366: s.balance = 0;
367: r.balance = a;
368: }
369:
370: p.balance = 0;
371: }
372:
373: // [A10. Finishing touch]
374: if (s == t.rightLink)
375: t.rightLink = p;
376: else
377: t.leftLink = p;
378:
379: return INSERT_OK;
380: }
381:
382: /**
383: Return the lowest key and delete it from
384: the tree, preserving the balance of the tree.
385: **/
386: public DataValueDescriptor[] removeFirst() {
387: if (head.rightLink == null)
388: return null;
389: head.rightLink = deleteLeftmost(head.rightLink);
390: if (this .subtreeShrunk)
391: height--;
392: return this .deletedKey;
393: }
394:
395: /**
396: Delete the node with the lowest key from the subtree defined
397: by 'thisNode', maintaining balance in the subtree. Returns
398: the node that should be the new root of the subtree. This
399: method sets this.subtreeShrunk if the subtree of thisNode
400: decreased in height. Saves the key that was in the deleted
401: node in 'deletedKey'.
402: **/
403: private Node deleteLeftmost(Node this Node) {
404: // If this node has no left child, we've found the
405: // leftmost one, so delete it.
406: if (this Node.leftLink == null) {
407:
408: // See if the current node has duplicates. If so, we'll
409: // just return one of them and not change the tree.
410: if (this Node.dupChain != null) {
411: Node dupNode = this Node.dupChain;
412:
413: //System.out.println("deleteLeftmost(" + thisNode + "): found dup: " + dupNode);
414:
415: // Return the key from the duplicate. Note that even
416: // though the keys compare equal they may not be equal,
417: // depending on how the column ordering was specified.
418: this .deletedKey = dupNode.key;
419: lastAux = dupNode.aux;
420:
421: // Unlink the dup node and free it.
422: this Node.dupChain = dupNode.dupChain;
423: allocator.freeNode(dupNode);
424: dupNode = null;
425:
426: // Tree is not changing height since we're just removing
427: // a node from the duplicate chain.
428: this .subtreeShrunk = false;
429:
430: // Preserve the current node as the root of this subtree..
431: return this Node;
432: } else // thisNode.dupChain == null
433: {
434: //System.out.println("deleteLeftmost(" + thisNode + "): found key");
435:
436: // Key to return is this node's key.
437: this .deletedKey = this Node.key;
438: lastAux = this Node.aux;
439:
440: // We're removing this node, so it's subtree is shrinking
441: // from height 1 to height 0.
442: this .subtreeShrunk = true;
443:
444: // Save this node's right link which might be cleared
445: // out by the allocator.
446: Node newRoot = this Node.rightLink;
447:
448: // Free the node we're deleting.
449: allocator.freeNode(this Node);
450:
451: // Rearrange the tree to put this node's right subtree where
452: // this node was.
453: return newRoot;
454: }
455: }
456:
457: // Since this wasn't the leftmost node, delete the leftmost
458: // node from this node's left subtree. This operation may
459: // rearrange the subtree, including the possiblility that the
460: // root note changed, so set the root of the left subtree to
461: // what the delete operation wants it to be.
462: this Node.leftLink = deleteLeftmost(this Node.leftLink);
463:
464: // If the left subtree didn't change size, then this subtree
465: // could not have changed size either.
466: if (this .subtreeShrunk == false)
467: return this Node;
468:
469: // If the delete operation shrunk the subtree, we may have
470: // some rebalancing to do.
471:
472: if (this Node.balance == 1) {
473: // Tree got more unbalanced. Need to do some
474: // kind of rotation to fix it. The rotateRight()
475: // method will set subtreeShrunk appropriately
476: // and return the node that should be the new
477: // root of this subtree.
478: return rotateRight(this Node);
479: }
480:
481: if (this Node.balance == -1) {
482: // Tree became more balanced
483: this Node.balance = 0;
484:
485: // Since the left subtree was higher, and it
486: // shrunk, then this subtree shrunk, too.
487: this .subtreeShrunk = true;
488: } else // thisNode.balance == 0
489: {
490: // Tree became acceptably unbalanced
491: this Node.balance = 1;
492:
493: // We had a balanced tree, and just the left
494: // subtree shrunk, so this subtree as a whole
495: // has not changed in height.
496: this .subtreeShrunk = false;
497: }
498:
499: // We have not rearranged this subtree.
500: return this Node;
501: }
502:
503: /**
504: Perform either a single or double rotation, as appropriate,
505: to get the subtree 'thisNode' back in balance, assuming
506: that the right subtree of 'thisNode' is higher than the
507: left subtree. Returns the node that should be the new
508: root of the subtree.
509: <P>
510: These are the cases depicted in diagrams (1) and (2) of
511: Knuth (p. 454), and the node names reflect these diagrams.
512: However, in deletion, the single rotation may encounter
513: a case where the "beta" and "gamma" subtrees are the same
514: height (b.balance == 0), so the resulting does not always
515: shrink.
516: <P>
517: Note: This code will not do the "mirror image" cases.
518: It only works when the right subtree is the higher one
519: (this is the only case encountered when deleting leftmost
520: nodes from the tree).
521: **/
522: private Node rotateRight(Node this Node) {
523: Node a = this Node;
524: Node b = this Node.rightLink;
525:
526: if (b.balance >= 0) {
527: // single rotation
528:
529: a.rightLink = b.leftLink;
530: b.leftLink = a;
531:
532: if (b.balance == 0) {
533: a.balance = 1;
534: b.balance = -1;
535: this .subtreeShrunk = false;
536: } else // b.balance == 1
537: {
538: a.balance = 0;
539: b.balance = 0;
540: this .subtreeShrunk = true;
541: }
542:
543: return b;
544: } else // b.balance == -1
545: {
546: // double rotation
547:
548: Node x = b.leftLink;
549:
550: a.rightLink = x.leftLink;
551: x.leftLink = a;
552: b.leftLink = x.rightLink;
553: x.rightLink = b;
554:
555: if (x.balance == 1) {
556: a.balance = -1;
557: b.balance = 0;
558: } else if (x.balance == -1) {
559: a.balance = 0;
560: b.balance = 1;
561: } else // x.balance == 0
562: {
563: a.balance = 0;
564: b.balance = 0;
565: }
566: x.balance = 0;
567:
568: this .subtreeShrunk = true;
569:
570: return x;
571: }
572: }
573:
574: public void check() {
575: if (SanityManager.DEBUG) {
576: String error = null;
577: if (head.rightLink == null) {
578: if (height != 0)
579: error = "empty tree with height " + height;
580: } else {
581: if (depth(head.rightLink) != height)
582: error = "tree height " + height + " != depth "
583: + depth(head.rightLink);
584: else
585: error = checkNode(head.rightLink);
586: }
587: if (error != null) {
588: System.out.println("ERROR: " + error);
589: print();
590: System.exit(1);
591: }
592: }
593: }
594:
595: private String checkNode(Node n) {
596: if (SanityManager.DEBUG) {
597: if (n == null)
598: return null;
599: int ld = depth(n.leftLink);
600: int rd = depth(n.rightLink);
601: if (n.balance != (rd - ld))
602: return "node " + n + ": left height " + ld
603: + " right height " + rd;
604:
605: String e;
606: e = checkNode(n.rightLink);
607: if (e == null)
608: e = checkNode(n.leftLink);
609: return e;
610: } else {
611: return (null);
612: }
613: }
614:
615: private int depth(Node n) {
616: int ld = 0;
617: int rd = 0;
618: if (n == null)
619: return 0;
620: if (n.leftLink != null)
621: ld = depth(n.leftLink);
622: if (n.rightLink != null)
623: rd = depth(n.rightLink);
624: if (rd > ld)
625: return rd + 1;
626: else
627: return ld + 1;
628: }
629:
630: public void print() {
631: Node root = head.rightLink;
632: System.out.println("tree height: " + height + " root: "
633: + ((root == null) ? -1 : root.id));
634: if (root != null)
635: printRecursive(root, 0);
636: }
637:
638: private void printRecursive(Node n, int depth) {
639: if (n.rightLink != null)
640: printRecursive(n.rightLink, depth + 1);
641: for (int i = 0; i < depth; i++)
642: System.out.print(" ");
643: System.out.println(n);
644: if (n.leftLink != null)
645: printRecursive(n.leftLink, depth + 1);
646: }
647:
648: private void debug(String s) {
649: if (SanityManager.DEBUG) {
650: System.out.println(" === [" + s + "] ===");
651: }
652: }
653: }
|