EMMA Coverage Report (generated Wed Jun 28 22:15:27 PDT 2006)
[all classes][org.apache.derby.impl.store.access.sort]

COVERAGE SUMMARY FOR SOURCE FILE [SortBuffer.java]

nameclass, %method, %block, %line, %
SortBuffer.java100% (1/1)67%  (12/18)72%  (645/892)77%  (180.8/234)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class SortBuffer100% (1/1)67%  (12/18)72%  (645/892)77%  (180.8/234)
SortBuffer (MergeSort): void 100% (1/1)100% (15/15)100% (6/6)
capacity (): int 100% (1/1)82%  (9/11)67%  (2/3)
check (): void 0%   (0/1)0%   (0/70)0%   (0/12)
checkNode (Node): String 0%   (0/1)0%   (0/51)0%   (0/10)
close (): void 100% (1/1)100% (16/16)100% (6/6)
debug (String): void 0%   (0/1)0%   (0/13)0%   (0/2)
deleteLeftmost (Node): Node 100% (1/1)100% (90/90)100% (27/27)
depth (Node): int 0%   (0/1)0%   (0/35)0%   (0/11)
getLastAux (): int 100% (1/1)100% (3/3)100% (1/1)
grow (int): void 100% (1/1)100% (7/7)100% (3/3)
init (): boolean 100% (1/1)88%  (35/40)80%  (8/10)
insert (DataValueDescriptor []): int 100% (1/1)98%  (336/342)98%  (86.8/89)
print (): void 0%   (0/1)0%   (0/31)0%   (0/5)
printRecursive (Node, int): void 0%   (0/1)0%   (0/34)0%   (0/8)
removeFirst (): DataValueDescriptor [] 100% (1/1)100% (26/26)100% (6/6)
reset (): void 100% (1/1)100% (12/12)100% (4/4)
rotateRight (Node): Node 100% (1/1)100% (92/92)100% (29/29)
setNextAux (int): void 100% (1/1)100% (4/4)100% (2/2)

1/*
2 
3   Derby - Class org.apache.derby.impl.store.access.sort.SortBuffer
4 
5   Copyright 1997, 2004 The Apache Software Foundation or its licensors, as applicable.
6 
7   Licensed under the Apache License, Version 2.0 (the "License");
8   you may not use this file except in compliance with the License.
9   You may obtain a copy of the License at
10 
11      http://www.apache.org/licenses/LICENSE-2.0
12 
13   Unless required by applicable law or agreed to in writing, software
14   distributed under the License is distributed on an "AS IS" BASIS,
15   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16   See the License for the specific language governing permissions and
17   limitations under the License.
18 
19 */
20 
21package org.apache.derby.impl.store.access.sort;
22 
23import org.apache.derby.iapi.services.sanity.SanityManager;
24import org.apache.derby.iapi.error.StandardException;
25import org.apache.derby.iapi.store.access.SortObserver;
26 
27import org.apache.derby.iapi.types.DataValueDescriptor;
28 
29/**
30 
31  This class implements an in-memory ordered set
32  based on the balanced binary tree algorithm from
33  Knuth Vol. 3, Sec. 6.2.3, pp. 451-471.
34  Nodes are always maintained in order,
35  so that inserts and deletes can be intermixed.
36  <P>
37  This algorithm will insert/delete N elements
38  in O(N log(N)) time using O(N) space. 
39 
40**/
41 
42class SortBuffer
43{
44        /**
45        Returned from insert when the row was inserted
46        without incident.
47        **/
48        public static final int INSERT_OK = 0;
49 
50        /**
51        Returned from insert when the row which was
52        inserted was a duplicate.  The set will have
53        aggregated it in.
54        **/
55        public static final int INSERT_DUPLICATE = 1;
56 
57        /**
58        Returned from insert when the row was not able to be
59        inserted because the set was full.
60        **/
61        public static final int INSERT_FULL = 2;
62 
63        /**
64        The sort this set is associated with.
65        **/
66        private MergeSort sort;
67 
68        /**
69        Where to allocate nodes from.
70        **/
71        private NodeAllocator allocator = null;
72 
73        /**
74        Special head node for the tree.  Head.rightLink is the
75        root of the tree.
76        **/
77        private Node head = null;
78 
79        /**
80        The current height of the tree.
81        **/
82        private int height = 0;
83 
84        /**
85        Set, as a side effect of deleteLeftMost (only), to the
86        key from the node that was deleted from the tree.  This
87        field is only valid after a call to deleteLeftMost.
88        **/
89        private DataValueDescriptor[] deletedKey;
90 
91        /**
92        Set, as a side effect of deleteLeftMost and rotateRight,
93        if the subtree they're working on decreased in height.
94        This field is only valid after a call to deleteLeftMost
95        or rotateRight.
96        **/
97        private boolean subtreeShrunk;
98 
99        /**
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        {
117                nextAux = aux;
118        }
119 
120        /**
121        Retrieve the aux value from the last node deallocated
122        from the tree.
123        **/
124        public int getLastAux()
125        {
126                return lastAux;
127        }
128 
129        /**
130        Construct doesn't do anything, callers must call init
131        and check its return code.
132        **/
133        public SortBuffer(MergeSort sort)
134        {
135                this.sort = sort;
136        }
137 
138        /**
139        Initialize.  Returns false if the allocator
140        couldn't be initialized.
141        **/
142        public boolean init()
143        {
144                allocator = new NodeAllocator();
145 
146                boolean initOK = false;
147 
148                if (sort.sortBufferMin > 0)
149                        initOK = allocator.init(sort.sortBufferMin, sort.sortBufferMax);
150                else
151                        initOK = allocator.init(sort.sortBufferMax);
152 
153                if (initOK == false)
154                {
155                        allocator = null;
156                        return false;
157                }
158                reset();
159                return true;
160        }
161 
162        public void reset()
163        {
164                allocator.reset();
165                head = allocator.newNode();
166                height = 0;
167        }
168 
169        public void close()
170        {
171                if (allocator != null)
172                        allocator.close();
173                allocator = null;
174                height = 0;
175                head = null;
176        }
177 
178        /**
179        Grow by a certain percent if we can
180        */
181        public void grow(int percent)
182        {
183                if (percent > 0)
184                        allocator.grow(percent);
185        }
186 
187 
188        /**
189        Return the number of elements this sorter can sort.
190        It's the capacity of the node allocator minus one
191        because the sorter uses one node for the head.
192        **/
193        public int capacity()
194        {
195                if (allocator == null)
196                        return 0;
197                return allocator.capacity() - 1;
198        }
199 
200        /**
201        Insert a key k into the tree. Returns true if the
202        key was inserted, false if the tree is full.  Silently
203        ignores duplicate keys.
204        <P>
205        See Knuth Vol. 3, Sec. 6.2.3, pp. 455-457 for the algorithm.
206        **/
207        public int insert(DataValueDescriptor[] k)
208                throws StandardException
209        {
210                int c;
211                Node p, q, r, s, t;
212 
213                if (head.rightLink == null)
214                {
215                        if ((sort.sortObserver != null) && 
216                                ((k = sort.sortObserver.insertNonDuplicateKey(k)) == null))
217                        {
218                                return INSERT_DUPLICATE;
219                        }
220 
221                        q = allocator.newNode();
222                        q.key = k;
223                        q.aux = nextAux;
224                        head.rightLink = q;
225                        height = 1;
226                        return INSERT_OK;
227                }
228 
229                // [A1. Initialize]
230                t = head;
231                p = s = head.rightLink;
232 
233                // Search
234                while (true)
235                {
236                        // [A2. Compare]
237                        c = sort.compare(k, p.key);
238                        if (c == 0)
239                        {
240                                // The new key compares equal to the
241                                // current node's key.
242 
243                                // See if we can use the aggregators
244                                // to get rid of the new key.
245                                if ((sort.sortObserver != null) &&
246                                        ((k = sort.sortObserver.insertDuplicateKey(k, p.key)) == null))
247                                {
248                                        return INSERT_DUPLICATE;
249                                }
250 
251                                // Keep the duplicate key...
252                                // Allocate a new node for the key.
253                                q = allocator.newNode();
254                                if (q == null)
255                                        return INSERT_FULL;
256                                q.aux = nextAux;
257 
258                                // Link the new node onto the current
259                                // node's duplicate chain.  The assumption
260                                // is made that a newly allocated node 
261                                // has null left and right links.
262                                q.key = k;
263                                q.dupChain = p.dupChain;
264                                p.dupChain = q;
265 
266                                // From the caller's perspective this was
267                                // not a duplicate insertion.
268                                return INSERT_OK;
269                        }
270 
271                        if (c < 0)
272                        {
273                                // [A3. Move left]
274                                q = p.leftLink;
275                                if (q == null)
276                                {
277                                        q = allocator.newNode();
278                                        if (q == null)
279                                                return INSERT_FULL;
280                                        q.aux = nextAux;
281                                        p.leftLink = q;
282                                        break;
283                                }
284                        }
285                        else // c > 0
286                        {
287                                // [A4. Move right]
288                                q = p.rightLink;
289                                if (q == null)
290                                {
291                                        q = allocator.newNode();
292                                        if (q == null)
293                                                return INSERT_FULL;
294                                        q.aux = nextAux;
295                                        p.rightLink = q;
296                                        break;
297                                }
298                        }
299 
300                        if (q.balance != 0)
301                        {
302                                t = p;
303                                s = q;
304                        }
305                        p = q;
306                }
307 
308                /*
309                 * [A5. Insert]
310                 * Node has been allocated and placed for k.
311                 * Initialize it.
312                 */
313 
314                if ((sort.sortObserver != null) && 
315                        ((k = sort.sortObserver.insertNonDuplicateKey(k)) == null))
316                {
317                        return INSERT_DUPLICATE;
318                }
319                q.key = k;
320 
321                /*
322                 * [A6. Adjust balance factors for nodes between
323                 * s and q]
324                 */
325 
326                c = sort.compare(k, s.key);
327                if (c < 0)
328                        r = p = s.leftLink;
329                else
330                        r = p = s.rightLink;
331 
332                while (p != q)
333                {
334                        if (sort.compare(k, p.key) < 0)
335                        {
336                                p.balance = -1;
337                                p = p.leftLink;
338                        }
339                        else // sort.compare(k, p.key) > 0
340                        {
341                                p.balance = 1;
342                                p = p.rightLink;
343                        }
344                }
345 
346                // [A7. Balancing act]
347 
348                int a = (c > 0 ? 1 : ((c == 0) ? 0 : -1));
349 
350                if (s.balance == 0)
351                {
352                        //debug("A7 (i). The tree has gotten higher");
353                        s.balance = a;
354                        height++;
355                        return INSERT_OK;
356                }
357 
358                if (s.balance == -a)
359                {
360                        //debug("A7 (ii). The tree has gotten more balanced");
361                        s.balance = 0;
362                        return INSERT_OK;
363                }
364 
365                //debug("A7 (iii). The tree has gotten more out of balance");
366 
367                // s.balance == a
368                if (r.balance == a)
369                {
370                        //debug("A8. Single rotation");
371                        p = r;
372                        s.setLink(a, r.link(-a));
373                        r.setLink(-a, s);
374                        s.balance = 0;
375                        r.balance = 0;
376                }
377                else // r.balance == -a
378                {
379                        //debug("A8. Double rotation");
380                        p = r.link(-a);
381                        r.setLink(-a, p.link(a));
382                        p.setLink(a, r);
383                        s.setLink(a, p.link(-a));
384                        p.setLink(-a, s);
385 
386                        if (p.balance == a)
387                        {
388                                s.balance = -a;
389                                r.balance = 0;
390                        }
391                        else if (p.balance == 0)
392                        {
393                                s.balance = 0;
394                                r.balance = 0;
395                        }
396                        else // p.balance == -a
397                        {
398                                s.balance = 0;
399                                r.balance = a;
400                        }
401 
402                        p.balance = 0;
403                }
404 
405                // [A10. Finishing touch]
406                if (s == t.rightLink)
407                        t.rightLink = p;
408                else
409                        t.leftLink = p;
410 
411                return INSERT_OK;
412        }
413 
414        /**
415        Return the lowest key and delete it from 
416        the tree, preserving the balance of the tree.
417        **/
418        public DataValueDescriptor[] removeFirst()
419        {
420                if (head.rightLink == null)
421                        return null;
422                head.rightLink = deleteLeftmost(head.rightLink);
423                if (this.subtreeShrunk)
424                        height--;
425                return this.deletedKey;
426        }
427 
428        /**
429        Delete the node with the lowest key from the subtree defined
430        by 'thisNode', maintaining balance in the subtree.  Returns
431        the node that should be the new root of the subtree.  This
432        method sets this.subtreeShrunk if the subtree of thisNode
433        decreased in height. Saves the key that was in the deleted
434        node in 'deletedKey'.
435        **/
436        private Node deleteLeftmost(Node thisNode)
437        {
438                // If this node has no left child, we've found the
439                // leftmost one, so delete it.
440                if (thisNode.leftLink == null)
441                {
442 
443                        // See if the current node has duplicates.  If so, we'll
444                        // just return one of them and not change the tree.
445                        if (thisNode.dupChain != null)
446                        {
447                                Node dupNode = thisNode.dupChain;
448 
449                                //System.out.println("deleteLeftmost(" + thisNode + "): found dup: " + dupNode);
450 
451                                // Return the key from the duplicate.  Note that even
452                                // though the keys compare equal they may not be equal,
453                                // depending on how the column ordering was specified.
454                                this.deletedKey = dupNode.key;
455                                lastAux = dupNode.aux;
456 
457                                // Unlink the dup node and free it.
458                                thisNode.dupChain = dupNode.dupChain;
459                                allocator.freeNode(dupNode);
460                                dupNode = null;
461 
462                                // Tree is not changing height since we're just removing
463                                // a node from the duplicate chain.
464                                this.subtreeShrunk = false;
465 
466                                // Preserve the current node as the root of this subtree..
467                                return thisNode;
468                        }
469                        else // thisNode.dupChain == null
470                        {
471                                //System.out.println("deleteLeftmost(" + thisNode + "): found key");
472 
473                                // Key to return is this node's key.
474                                this.deletedKey = thisNode.key;
475                                lastAux = thisNode.aux;
476 
477                                // We're removing this node, so it's subtree is shrinking
478                                // from height 1 to height 0.
479                                this.subtreeShrunk = true;
480 
481                                // Save this node's right link which might be cleared
482                                // out by the allocator.
483                                Node newRoot = thisNode.rightLink;
484 
485                                // Free the node we're deleting.
486                                allocator.freeNode(thisNode);
487 
488                                // Rearrange the tree to put this node's right subtree where
489                                // this node was.
490                                return newRoot;
491                        }
492                }
493 
494                // Since this wasn't the leftmost node, delete the leftmost
495                // node from this node's left subtree.  This operation may
496                // rearrange the subtree, including the possiblility that the
497                // root note changed, so set the root of the left subtree to
498                // what the delete operation wants it to be.
499                thisNode.leftLink = deleteLeftmost(thisNode.leftLink);
500 
501                // If the left subtree didn't change size, then this subtree
502                // could not have changed size either.
503                if (this.subtreeShrunk == false)
504                        return thisNode;
505 
506                 // If the delete operation shrunk the subtree, we may have
507                // some rebalancing to do.
508 
509                if (thisNode.balance == 1)
510                {
511                        // Tree got more unbalanced.  Need to do some
512                        // kind of rotation to fix it.  The rotateRight()
513                        // method will set subtreeShrunk appropriately
514                        // and return the node that should be the new
515                        // root of this subtree.
516                        return rotateRight(thisNode);
517                }
518 
519                if (thisNode.balance == -1)
520                {
521                        // Tree became more balanced
522                        thisNode.balance = 0;
523 
524                        // Since the left subtree was higher, and it
525                        // shrunk, then this subtree shrunk, too.
526                        this.subtreeShrunk = true;
527                }
528                else // thisNode.balance == 0
529                {
530                        // Tree became acceptably unbalanced
531                        thisNode.balance = 1;
532 
533                        // We had a balanced tree, and just the left
534                        // subtree shrunk, so this subtree as a whole
535                        // has not changed in height.
536                        this.subtreeShrunk = false;
537                }
538 
539                // We have not rearranged this subtree.
540                return thisNode;
541        }
542 
543        /**
544        Perform either a single or double rotation, as appropriate, 
545        to get the subtree 'thisNode' back in balance, assuming
546        that the right subtree of 'thisNode' is higher than the
547        left subtree.  Returns the node that should be the new
548        root of the subtree.
549        <P>
550        These are the cases depicted in diagrams (1) and (2) of
551        Knuth (p. 454), and the node names reflect these diagrams.
552        However, in deletion, the single rotation may encounter
553        a case where the "beta" and "gamma" subtrees are the same
554        height (b.balance == 0), so the resulting does not always
555        shrink.
556        <P>
557    Note: This code will not do the "mirror image" cases.
558        It only works when the right subtree is the higher one
559        (this is the only case encountered when deleting leftmost
560        nodes from the tree).
561        **/
562        private Node rotateRight(Node thisNode)
563        {
564                Node a = thisNode;
565                Node b = thisNode.rightLink;
566 
567                if (b.balance >= 0)
568                {
569                        // single rotation
570 
571                        a.rightLink = b.leftLink;
572                        b.leftLink = a;
573 
574                        if (b.balance == 0)
575                        {
576                                a.balance = 1;
577                                b.balance = -1;
578                                this.subtreeShrunk = false;
579                        }
580                        else // b.balance == 1
581                        {
582                                a.balance = 0;
583                                b.balance = 0;
584                                this.subtreeShrunk = true;
585                        }
586 
587                        return b;
588                }
589                else // b.balance == -1
590                {
591                        // double rotation
592 
593                        Node x = b.leftLink;
594 
595                        a.rightLink = x.leftLink;
596                        x.leftLink = a;
597                        b.leftLink = x.rightLink;
598                        x.rightLink = b;
599 
600                        if (x.balance == 1)
601                        {
602                                a.balance = -1;
603                                b.balance = 0;
604                        }
605                        else if (x.balance == -1)
606                        {
607                                a.balance = 0;
608                                b.balance = 1;
609                        }
610                        else // x.balance == 0
611                        {
612                                a.balance = 0;
613                                b.balance = 0;
614                        }
615                        x.balance = 0;
616 
617                        this.subtreeShrunk = true;
618 
619                        return x;
620                }
621        }
622 
623        public void check()
624        {
625        if (SanityManager.DEBUG)
626        {
627            String error = null;
628            if (head.rightLink == null)
629            {
630                if (height != 0)
631                    error = "empty tree with height " + height;
632            } 
633            else
634            {
635                if (depth(head.rightLink) != height)
636                    error = "tree height " + height + " != depth " + depth(head.rightLink);
637                else
638                    error = checkNode(head.rightLink);
639            }
640            if (error != null)
641            {
642                System.out.println("ERROR: " + error);
643                print();
644                System.exit(1);
645            }
646        }
647        }
648 
649        private String checkNode(Node n)
650        {
651        if (SanityManager.DEBUG)
652        {
653            if (n == null)
654                return null;
655            int ld = depth(n.leftLink);
656            int rd = depth(n.rightLink);
657            if (n.balance != (rd - ld))
658                return "node " + n + ": left height " + ld + " right height " + rd;
659            
660            String e;
661            e = checkNode(n.rightLink);
662            if (e == null)
663                e = checkNode(n.leftLink);
664            return e;
665        }
666        else
667        {
668            return(null);
669        }
670        }
671 
672        private int depth(Node n)
673        {
674                int ld = 0;
675                int rd = 0;
676                if (n == null)
677                        return 0;
678                if (n.leftLink != null)
679                        ld = depth(n.leftLink);
680                if (n.rightLink != null)
681                        rd = depth(n.rightLink);
682                if (rd > ld)
683                        return rd + 1;
684                else
685                        return ld + 1;
686        }
687 
688        public void print()
689        {
690                Node root = head.rightLink;
691                System.out.println("tree height: " + height
692                        + " root: " + ((root == null) ? -1 : root.id));
693                if (root != null)
694                        printRecursive(root, 0);
695        }
696 
697        private void printRecursive(Node n, int depth)
698        {
699                if (n.rightLink != null)
700                        printRecursive(n.rightLink, depth + 1);
701                for (int i = 0; i < depth; i++)
702                        System.out.print("       ");
703                System.out.println(n);
704                if (n.leftLink != null)
705                        printRecursive(n.leftLink, depth + 1);
706        }
707 
708        private void debug(String s)
709        {
710        if (SanityManager.DEBUG)
711        {
712            System.out.println(" === [" + s + "] ===");
713        }
714        }
715}

[all classes][org.apache.derby.impl.store.access.sort]
EMMA 2.0.5312 (C) Vladimir Roubtsov