--- /dev/null
+/*\r
+\r
+ Derby - Class org.apache.derby.impl.store.access.sort.SortBuffer\r
+\r
+ Licensed to the Apache Software Foundation (ASF) under one or more\r
+ contributor license agreements. See the NOTICE file distributed with\r
+ this work for additional information regarding copyright ownership.\r
+ The ASF licenses this file to you under the Apache License, Version 2.0\r
+ (the "License"); you may not use this file except in compliance with\r
+ the License. You may obtain a copy of the License at\r
+\r
+ http://www.apache.org/licenses/LICENSE-2.0\r
+\r
+ Unless required by applicable law or agreed to in writing, software\r
+ distributed under the License is distributed on an "AS IS" BASIS,\r
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
+ See the License for the specific language governing permissions and\r
+ limitations under the License.\r
+\r
+ */\r
+\r
+package org.apache.derby.impl.store.access.sort;\r
+\r
+import org.apache.derby.iapi.services.sanity.SanityManager;\r
+import org.apache.derby.iapi.error.StandardException;\r
+\r
+import org.apache.derby.iapi.types.DataValueDescriptor;\r
+\r
+/**\r
+\r
+ This class implements an in-memory ordered set\r
+ based on the balanced binary tree algorithm from\r
+ Knuth Vol. 3, Sec. 6.2.3, pp. 451-471.\r
+ Nodes are always maintained in order,\r
+ so that inserts and deletes can be intermixed.\r
+ <P>\r
+ This algorithm will insert/delete N elements\r
+ in O(N log(N)) time using O(N) space. \r
+\r
+**/\r
+\r
+class SortBuffer\r
+{\r
+ /**\r
+ Returned from insert when the row was inserted\r
+ without incident.\r
+ **/\r
+ public static final int INSERT_OK = 0;\r
+\r
+ /**\r
+ Returned from insert when the row which was\r
+ inserted was a duplicate. The set will have\r
+ aggregated it in.\r
+ **/\r
+ public static final int INSERT_DUPLICATE = 1;\r
+\r
+ /**\r
+ Returned from insert when the row was not able to be\r
+ inserted because the set was full.\r
+ **/\r
+ public static final int INSERT_FULL = 2;\r
+\r
+ /**\r
+ The sort this set is associated with.\r
+ **/\r
+ private MergeSort sort;\r
+\r
+ /**\r
+ Where to allocate nodes from.\r
+ **/\r
+ private NodeAllocator allocator = null;\r
+\r
+ /**\r
+ Special head node for the tree. Head.rightLink is the\r
+ root of the tree.\r
+ **/\r
+ private Node head = null;\r
+\r
+ /**\r
+ The current height of the tree.\r
+ **/\r
+ private int height = 0;\r
+\r
+ /**\r
+ Set, as a side effect of deleteLeftMost (only), to the\r
+ key from the node that was deleted from the tree. This\r
+ field is only valid after a call to deleteLeftMost.\r
+ **/\r
+ private DataValueDescriptor[] deletedKey;\r
+\r
+ /**\r
+ Set, as a side effect of deleteLeftMost and rotateRight,\r
+ if the subtree they're working on decreased in height.\r
+ This field is only valid after a call to deleteLeftMost\r
+ or rotateRight.\r
+ **/\r
+ private boolean subtreeShrunk;\r
+\r
+ /**\r
+ Set by the setNextAux() method. This value is stuffed\r
+ into the aux field of the next node that's allocated.\r
+ **/\r
+ private int nextAux;\r
+\r
+ /**\r
+ Read by the getLastAux() method. This value is read out\r
+ of the last node that was deallocated from the tree.\r
+ **/\r
+ private int lastAux;\r
+\r
+ /**\r
+ Arrange that the next node allocated in the tree have\r
+ it's aux field set to the argument.\r
+ **/\r
+ void setNextAux(int aux)\r
+ {\r
+ nextAux = aux;\r
+ }\r
+\r
+ /**\r
+ Retrieve the aux value from the last node deallocated\r
+ from the tree.\r
+ **/\r
+ int getLastAux()\r
+ {\r
+ return lastAux;\r
+ }\r
+\r
+ /**\r
+ Construct doesn't do anything, callers must call init\r
+ and check its return code.\r
+ **/\r
+ SortBuffer(MergeSort sort)\r
+ {\r
+ this.sort = sort;\r
+ }\r
+\r
+ /**\r
+ Initialize. Returns false if the allocator\r
+ couldn't be initialized.\r
+ **/\r
+ boolean init()\r
+ {\r
+ allocator = new NodeAllocator();\r
+\r
+ boolean initOK = false;\r
+\r
+ if (sort.sortBufferMin > 0)\r
+ initOK = allocator.init(sort.sortBufferMin, sort.sortBufferMax);\r
+ else\r
+ initOK = allocator.init(sort.sortBufferMax);\r
+\r
+ if (initOK == false)\r
+ {\r
+ allocator = null;\r
+ return false;\r
+ }\r
+ reset();\r
+ return true;\r
+ }\r
+\r
+ void reset()\r
+ {\r
+ allocator.reset();\r
+ head = allocator.newNode();\r
+ height = 0;\r
+ }\r
+\r
+ void close()\r
+ {\r
+ if (allocator != null)\r
+ allocator.close();\r
+ allocator = null;\r
+ height = 0;\r
+ head = null;\r
+ }\r
+\r
+ /**\r
+ Grow by a certain percent if we can\r
+ */\r
+ void grow(int percent)\r
+ {\r
+ if (percent > 0)\r
+ allocator.grow(percent);\r
+ }\r
+\r
+\r
+ /**\r
+ Return the number of elements this sorter can sort.\r
+ It's the capacity of the node allocator minus one\r
+ because the sorter uses one node for the head.\r
+ **/\r
+ int capacity()\r
+ {\r
+ if (allocator == null)\r
+ return 0;\r
+ return allocator.capacity() - 1;\r
+ }\r
+\r
+ /**\r
+ Insert a key k into the tree. Returns true if the\r
+ key was inserted, false if the tree is full. Silently\r
+ ignores duplicate keys.\r
+ <P>\r
+ See Knuth Vol. 3, Sec. 6.2.3, pp. 455-457 for the algorithm.\r
+ **/\r
+ int insert(DataValueDescriptor[] k)\r
+ throws StandardException\r
+ {\r
+ int c;\r
+ Node p, q, r, s, t;\r
+\r
+ if (head.rightLink == null)\r
+ {\r
+ if ((sort.sortObserver != null) && \r
+ ((k = sort.sortObserver.insertNonDuplicateKey(k)) == null))\r
+ {\r
+ return INSERT_DUPLICATE;\r
+ }\r
+\r
+ q = allocator.newNode();\r
+ q.key = k;\r
+ q.aux = nextAux;\r
+ head.rightLink = q;\r
+ height = 1;\r
+ return INSERT_OK;\r
+ }\r
+\r
+ // [A1. Initialize]\r
+ t = head;\r
+ p = s = head.rightLink;\r
+\r
+ // Search\r
+ while (true)\r
+ {\r
+ // [A2. Compare]\r
+ c = sort.compare(k, p.key);\r
+ if (c == 0)\r
+ {\r
+ // The new key compares equal to the\r
+ // current node's key.\r
+\r
+ // See if we can use the aggregators\r
+ // to get rid of the new key.\r
+ if ((sort.sortObserver != null) &&\r
+ ((k = sort.sortObserver.insertDuplicateKey(k, p.key)) == null))\r
+ {\r
+ return INSERT_DUPLICATE;\r
+ }\r
+\r
+ // Keep the duplicate key...\r
+ // Allocate a new node for the key.\r
+ q = allocator.newNode();\r
+ if (q == null)\r
+ return INSERT_FULL;\r
+ q.aux = nextAux;\r
+\r
+ // Link the new node onto the current\r
+ // node's duplicate chain. The assumption\r
+ // is made that a newly allocated node \r
+ // has null left and right links.\r
+ q.key = k;\r
+ q.dupChain = p.dupChain;\r
+ p.dupChain = q;\r
+\r
+ // From the caller's perspective this was\r
+ // not a duplicate insertion.\r
+ return INSERT_OK;\r
+ }\r
+\r
+ if (c < 0)\r
+ {\r
+ // [A3. Move left]\r
+ q = p.leftLink;\r
+ if (q == null)\r
+ {\r
+ q = allocator.newNode();\r
+ if (q == null)\r
+ return INSERT_FULL;\r
+ q.aux = nextAux;\r
+ p.leftLink = q;\r
+ break;\r
+ }\r
+ }\r
+ else // c > 0\r
+ {\r
+ // [A4. Move right]\r
+ q = p.rightLink;\r
+ if (q == null)\r
+ {\r
+ q = allocator.newNode();\r
+ if (q == null)\r
+ return INSERT_FULL;\r
+ q.aux = nextAux;\r
+ p.rightLink = q;\r
+ break;\r
+ }\r
+ }\r
+\r
+ if (q.balance != 0)\r
+ {\r
+ t = p;\r
+ s = q;\r
+ }\r
+ p = q;\r
+ }\r
+\r
+ /*\r
+ * [A5. Insert]\r
+ * Node has been allocated and placed for k.\r
+ * Initialize it.\r
+ */\r
+\r
+ if ((sort.sortObserver != null) && \r
+ ((k = sort.sortObserver.insertNonDuplicateKey(k)) == null))\r
+ {\r
+ return INSERT_DUPLICATE;\r
+ }\r
+ q.key = k;\r
+\r
+ /*\r
+ * [A6. Adjust balance factors for nodes between\r
+ * s and q]\r
+ */\r
+\r
+ c = sort.compare(k, s.key);\r
+ if (c < 0)\r
+ r = p = s.leftLink;\r
+ else\r
+ r = p = s.rightLink;\r
+\r
+ while (p != q)\r
+ {\r
+ if (sort.compare(k, p.key) < 0)\r
+ {\r
+ p.balance = -1;\r
+ p = p.leftLink;\r
+ }\r
+ else // sort.compare(k, p.key) > 0\r
+ {\r
+ p.balance = 1;\r
+ p = p.rightLink;\r
+ }\r
+ }\r
+\r
+ // [A7. Balancing act]\r
+\r
+ int a = (c > 0 ? 1 : ((c == 0) ? 0 : -1));\r
+\r
+ if (s.balance == 0)\r
+ {\r
+ //debug("A7 (i). The tree has gotten higher");\r
+ s.balance = a;\r
+ height++;\r
+ return INSERT_OK;\r
+ }\r
+\r
+ if (s.balance == -a)\r
+ {\r
+ //debug("A7 (ii). The tree has gotten more balanced");\r
+ s.balance = 0;\r
+ return INSERT_OK;\r
+ }\r
+\r
+ //debug("A7 (iii). The tree has gotten more out of balance");\r
+\r
+ // s.balance == a\r
+ if (r.balance == a)\r
+ {\r
+ //debug("A8. Single rotation");\r
+ p = r;\r
+ s.setLink(a, r.link(-a));\r
+ r.setLink(-a, s);\r
+ s.balance = 0;\r
+ r.balance = 0;\r
+ }\r
+ else // r.balance == -a\r
+ {\r
+ //debug("A8. Double rotation");\r
+ p = r.link(-a);\r
+ r.setLink(-a, p.link(a));\r
+ p.setLink(a, r);\r
+ s.setLink(a, p.link(-a));\r
+ p.setLink(-a, s);\r
+\r
+ if (p.balance == a)\r
+ {\r
+ s.balance = -a;\r
+ r.balance = 0;\r
+ }\r
+ else if (p.balance == 0)\r
+ {\r
+ s.balance = 0;\r
+ r.balance = 0;\r
+ }\r
+ else // p.balance == -a\r
+ {\r
+ s.balance = 0;\r
+ r.balance = a;\r
+ }\r
+\r
+ p.balance = 0;\r
+ }\r
+\r
+ // [A10. Finishing touch]\r
+ if (s == t.rightLink)\r
+ t.rightLink = p;\r
+ else\r
+ t.leftLink = p;\r
+\r
+ return INSERT_OK;\r
+ }\r
+\r
+ /**\r
+ Return the lowest key and delete it from \r
+ the tree, preserving the balance of the tree.\r
+ **/\r
+ DataValueDescriptor[] removeFirst()\r
+ {\r
+ if (head.rightLink == null)\r
+ return null;\r
+ head.rightLink = deleteLeftmost(head.rightLink);\r
+ if (this.subtreeShrunk)\r
+ height--;\r
+ return this.deletedKey;\r
+ }\r
+\r
+ /**\r
+ Delete the node with the lowest key from the subtree defined\r
+ by 'thisNode', maintaining balance in the subtree. Returns\r
+ the node that should be the new root of the subtree. This\r
+ method sets this.subtreeShrunk if the subtree of thisNode\r
+ decreased in height. Saves the key that was in the deleted\r
+ node in 'deletedKey'.\r
+ **/\r
+ private Node deleteLeftmost(Node thisNode)\r
+ {\r
+ // If this node has no left child, we've found the\r
+ // leftmost one, so delete it.\r
+ if (thisNode.leftLink == null)\r
+ {\r
+\r
+ // See if the current node has duplicates. If so, we'll\r
+ // just return one of them and not change the tree.\r
+ if (thisNode.dupChain != null)\r
+ {\r
+ Node dupNode = thisNode.dupChain;\r
+\r
+ //System.out.println("deleteLeftmost(" + thisNode + "): found dup: " + dupNode);\r
+\r
+ // Return the key from the duplicate. Note that even\r
+ // though the keys compare equal they may not be equal,\r
+ // depending on how the column ordering was specified.\r
+ this.deletedKey = dupNode.key;\r
+ lastAux = dupNode.aux;\r
+\r
+ // Unlink the dup node and free it.\r
+ thisNode.dupChain = dupNode.dupChain;\r
+ allocator.freeNode(dupNode);\r
+ dupNode = null;\r
+\r
+ // Tree is not changing height since we're just removing\r
+ // a node from the duplicate chain.\r
+ this.subtreeShrunk = false;\r
+\r
+ // Preserve the current node as the root of this subtree..\r
+ return thisNode;\r
+ }\r
+ else // thisNode.dupChain == null\r
+ {\r
+ //System.out.println("deleteLeftmost(" + thisNode + "): found key");\r
+\r
+ // Key to return is this node's key.\r
+ this.deletedKey = thisNode.key;\r
+ lastAux = thisNode.aux;\r
+\r
+ // We're removing this node, so it's subtree is shrinking\r
+ // from height 1 to height 0.\r
+ this.subtreeShrunk = true;\r
+\r
+ // Save this node's right link which might be cleared\r
+ // out by the allocator.\r
+ Node newRoot = thisNode.rightLink;\r
+\r
+ // Free the node we're deleting.\r
+ allocator.freeNode(thisNode);\r
+\r
+ // Rearrange the tree to put this node's right subtree where\r
+ // this node was.\r
+ return newRoot;\r
+ }\r
+ }\r
+\r
+ // Since this wasn't the leftmost node, delete the leftmost\r
+ // node from this node's left subtree. This operation may\r
+ // rearrange the subtree, including the possiblility that the\r
+ // root note changed, so set the root of the left subtree to\r
+ // what the delete operation wants it to be.\r
+ thisNode.leftLink = deleteLeftmost(thisNode.leftLink);\r
+\r
+ // If the left subtree didn't change size, then this subtree\r
+ // could not have changed size either.\r
+ if (this.subtreeShrunk == false)\r
+ return thisNode;\r
+\r
+ // If the delete operation shrunk the subtree, we may have\r
+ // some rebalancing to do.\r
+\r
+ if (thisNode.balance == 1)\r
+ {\r
+ // Tree got more unbalanced. Need to do some\r
+ // kind of rotation to fix it. The rotateRight()\r
+ // method will set subtreeShrunk appropriately\r
+ // and return the node that should be the new\r
+ // root of this subtree.\r
+ return rotateRight(thisNode);\r
+ }\r
+\r
+ if (thisNode.balance == -1)\r
+ {\r
+ // Tree became more balanced\r
+ thisNode.balance = 0;\r
+\r
+ // Since the left subtree was higher, and it\r
+ // shrunk, then this subtree shrunk, too.\r
+ this.subtreeShrunk = true;\r
+ }\r
+ else // thisNode.balance == 0\r
+ {\r
+ // Tree became acceptably unbalanced\r
+ thisNode.balance = 1;\r
+\r
+ // We had a balanced tree, and just the left\r
+ // subtree shrunk, so this subtree as a whole\r
+ // has not changed in height.\r
+ this.subtreeShrunk = false;\r
+ }\r
+\r
+ // We have not rearranged this subtree.\r
+ return thisNode;\r
+ }\r
+\r
+ /**\r
+ Perform either a single or double rotation, as appropriate, \r
+ to get the subtree 'thisNode' back in balance, assuming\r
+ that the right subtree of 'thisNode' is higher than the\r
+ left subtree. Returns the node that should be the new\r
+ root of the subtree.\r
+ <P>\r
+ These are the cases depicted in diagrams (1) and (2) of\r
+ Knuth (p. 454), and the node names reflect these diagrams.\r
+ However, in deletion, the single rotation may encounter\r
+ a case where the "beta" and "gamma" subtrees are the same\r
+ height (b.balance == 0), so the resulting does not always\r
+ shrink.\r
+ <P>\r
+ Note: This code will not do the "mirror image" cases.\r
+ It only works when the right subtree is the higher one\r
+ (this is the only case encountered when deleting leftmost\r
+ nodes from the tree).\r
+ **/\r
+ private Node rotateRight(Node thisNode)\r
+ {\r
+ Node a = thisNode;\r
+ Node b = thisNode.rightLink;\r
+\r
+ if (b.balance >= 0)\r
+ {\r
+ // single rotation\r
+\r
+ a.rightLink = b.leftLink;\r
+ b.leftLink = a;\r
+\r
+ if (b.balance == 0)\r
+ {\r
+ a.balance = 1;\r
+ b.balance = -1;\r
+ this.subtreeShrunk = false;\r
+ }\r
+ else // b.balance == 1\r
+ {\r
+ a.balance = 0;\r
+ b.balance = 0;\r
+ this.subtreeShrunk = true;\r
+ }\r
+\r
+ return b;\r
+ }\r
+ else // b.balance == -1\r
+ {\r
+ // double rotation\r
+\r
+ Node x = b.leftLink;\r
+\r
+ a.rightLink = x.leftLink;\r
+ x.leftLink = a;\r
+ b.leftLink = x.rightLink;\r
+ x.rightLink = b;\r
+\r
+ if (x.balance == 1)\r
+ {\r
+ a.balance = -1;\r
+ b.balance = 0;\r
+ }\r
+ else if (x.balance == -1)\r
+ {\r
+ a.balance = 0;\r
+ b.balance = 1;\r
+ }\r
+ else // x.balance == 0\r
+ {\r
+ a.balance = 0;\r
+ b.balance = 0;\r
+ }\r
+ x.balance = 0;\r
+\r
+ this.subtreeShrunk = true;\r
+\r
+ return x;\r
+ }\r
+ }\r
+\r
+ public void check()\r
+ {\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ String error = null;\r
+ if (head.rightLink == null)\r
+ {\r
+ if (height != 0)\r
+ error = "empty tree with height " + height;\r
+ } \r
+ else\r
+ {\r
+ if (depth(head.rightLink) != height)\r
+ error = "tree height " + height + " != depth " + depth(head.rightLink);\r
+ else\r
+ error = checkNode(head.rightLink);\r
+ }\r
+ if (error != null)\r
+ {\r
+ System.out.println("ERROR: " + error);\r
+ print();\r
+ System.exit(1);\r
+ }\r
+ }\r
+ }\r
+\r
+ private String checkNode(Node n)\r
+ {\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ if (n == null)\r
+ return null;\r
+ int ld = depth(n.leftLink);\r
+ int rd = depth(n.rightLink);\r
+ if (n.balance != (rd - ld))\r
+ return "node " + n + ": left height " + ld + " right height " + rd;\r
+ \r
+ String e;\r
+ e = checkNode(n.rightLink);\r
+ if (e == null)\r
+ e = checkNode(n.leftLink);\r
+ return e;\r
+ }\r
+ else\r
+ {\r
+ return(null);\r
+ }\r
+ }\r
+\r
+ private int depth(Node n)\r
+ {\r
+ int ld = 0;\r
+ int rd = 0;\r
+ if (n == null)\r
+ return 0;\r
+ if (n.leftLink != null)\r
+ ld = depth(n.leftLink);\r
+ if (n.rightLink != null)\r
+ rd = depth(n.rightLink);\r
+ if (rd > ld)\r
+ return rd + 1;\r
+ else\r
+ return ld + 1;\r
+ }\r
+\r
+ public void print()\r
+ {\r
+ Node root = head.rightLink;\r
+ System.out.println("tree height: " + height\r
+ + " root: " + ((root == null) ? -1 : root.id));\r
+ if (root != null)\r
+ printRecursive(root, 0);\r
+ }\r
+\r
+ private void printRecursive(Node n, int depth)\r
+ {\r
+ if (n.rightLink != null)\r
+ printRecursive(n.rightLink, depth + 1);\r
+ for (int i = 0; i < depth; i++)\r
+ System.out.print(" ");\r
+ System.out.println(n);\r
+ if (n.leftLink != null)\r
+ printRecursive(n.leftLink, depth + 1);\r
+ }\r
+\r
+ private void debug(String s)\r
+ {\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ System.out.println(" === [" + s + "] ===");\r
+ }\r
+ }\r
+}\r
projects / Benchmarks_CSolver.git / blobdiff