Author: shawkins Date: 2010-07-26 22:54:36 -0400 (Mon, 26 Jul 2010) New Revision: 2375 Added: trunk/engine/src/test/java/org/teiid/common/buffer/TestSTree.java Removed: trunk/engine/src/test/java/org/teiid/common/buffer/impl/TestSTree.java Modified: trunk/engine/src/main/java/org/teiid/common/buffer/SPage.java trunk/engine/src/main/java/org/teiid/common/buffer/STree.java Log: TEIID-1167 fixing tree, switching to holding tuplebatches (since that's what our weak references are to), and adding prev for backwards iteration. Modified: trunk/engine/src/main/java/org/teiid/common/buffer/SPage.java =================================================================== --- trunk/engine/src/main/java/org/teiid/common/buffer/SPage.java 2010-07-26 16:57:39 UTC (rev 2374) +++ trunk/engine/src/main/java/org/teiid/common/buffer/SPage.java 2010-07-27 02:54:36 UTC (rev 2375) @@ -24,6 +24,8 @@ import java.util.ArrayList; import java.util.Collections; +import java.util.Iterator; +import java.util.LinkedList; import java.util.List; import java.util.concurrent.atomic.AtomicInteger; @@ -32,6 +34,9 @@ /** * A linked list Page entry in the tree + * + * TODO: return the tuplebatch from getvalues, since that is what we're tracking + * */ @SuppressWarnings("unchecked") class SPage { @@ -41,8 +46,8 @@ static class SearchResult { int index; SPage page; - List values; - public SearchResult(int index, SPage page, List values) { + TupleBatch values; + public SearchResult(int index, SPage page, TupleBatch values) { this.index = index; this.page = page; this.values = values; @@ -53,73 +58,78 @@ STree stree; - protected SPage next; + protected SPage next; + protected SPage prev; protected ManagedBatch managedBatch; - protected List values; + protected TupleBatch values; protected ArrayList<SPage> children; SPage(STree stree, boolean leaf) { this.stree = stree; - this.values = new ArrayList<SPage>(stree.pageSize); + this.values = new TupleBatch(counter.getAndIncrement(), new ArrayList(stree.pageSize/4)); if (!leaf) { children = new ArrayList<SPage>(stree.pageSize/4); } } - static SearchResult search(SPage page, List k, SearchResult parent, List parentKey) throws TeiidComponentException { - SPage previous = null; - List previousValues = null; + static int unnecessaryReads; + + static SearchResult search(SPage page, List k, LinkedList<SearchResult> parent) throws TeiidComponentException { + TupleBatch previousValues = null; for (;;) { - List values = page.getValues(); - int index = Collections.binarySearch(values, k, page.stree.comparator); - int actual = - index - 1; - if (previous != null) { - if (actual == 0) { - if (values.isEmpty()) { - page.remove(); - previous.next = page.next; - } - return new SearchResult(-previousValues.size() - 1, previous, previousValues); + TupleBatch values = page.getValues(); + int index = Collections.binarySearch(values.getTuples(), k, page.stree.comparator); + int flippedIndex = - index - 1; + if (previousValues != null) { + unnecessaryReads++; + if (flippedIndex == 0) { + //systemic weakness of the algorithm + return new SearchResult(-previousValues.getTuples().size() - 1, page.prev, previousValues); } - if (parentKey != null) { - if (page.stree.comparator.compare(parentKey, values.get(0)) >= 0) { - //TODO: the entries after this point may also need moved forward - //TODO: this should be done as part of insert - parent.page.children.set(Math.max(0, -parent.index - 2), page); - } else { - //parentKey < page.keys.get(0) - //TODO: this circumvents the normal probabilistic process, but - //ensures there is an index entry. - page.stree.insert(page.stree.extractKey((List) values.get(0)), parent, page); - parent.index--; + if (parent != null && index != 0) { + //for non-matches move the previous pointer over to this page + SPage childPage = page; + List oldKey = null; + List newKey = page.stree.extractKey(values.getTuples().get(0)); + for (Iterator<SearchResult> desc = parent.descendingIterator(); desc.hasNext();) { + SearchResult sr = desc.next(); + int parentIndex = Math.max(0, -sr.index - 2); + if (oldKey == null) { + oldKey = sr.values.getTuples().set(parentIndex, newKey); + } else if (page.stree.comparator.compare(oldKey, sr.values.getTuples().get(parentIndex)) == 0 ) { + sr.values.getTuples().set(parentIndex, newKey); + } else { + break; + } + sr.page.children.set(parentIndex, childPage); + sr.page.setValues(sr.values); + childPage = sr.page; } } } - if (actual != values.size() || page.next == null) { + if (flippedIndex != values.getTuples().size() || page.next == null) { return new SearchResult(index, page, values); } - previous = page; previousValues = values; page = page.next; } } - protected void setValues(List values) throws TeiidComponentException { + protected void setValues(TupleBatch values) throws TeiidComponentException { if (managedBatch != null) { managedBatch.remove(); } - if (values.size() < MIN_PERSISTENT_SIZE) { + if (values.getTuples().size() < MIN_PERSISTENT_SIZE) { this.values = values; return; } this.values = null; - TupleBatch batch = TupleBatch.directBatch(counter.getAndIncrement(), values); if (children != null) { - batch.setDataTypes(stree.keytypes); + values.setDataTypes(stree.keytypes); } else { - batch.setDataTypes(stree.types); + values.setDataTypes(stree.types); } - managedBatch = stree.manager.createManagedBatch(batch); + managedBatch = stree.manager.createManagedBatch(values); } protected void remove() { @@ -127,17 +137,95 @@ managedBatch.remove(); managedBatch = null; } + values = null; + children = null; } - protected List getValues() throws TeiidComponentException { + protected TupleBatch getValues() throws TeiidComponentException { if (values != null) { return values; } if (managedBatch == null) { - return Collections.emptyList(); + throw new AssertionError("Batch removed"); //$NON-NLS-1$ } - TupleBatch batch = managedBatch.getBatch(true, stree.types); - return batch.getTuples(); + return managedBatch.getBatch(true, stree.types); } + + static void merge(LinkedList<SearchResult> places, TupleBatch nextValues, SPage current, TupleBatch currentValues) + throws TeiidComponentException { + SearchResult parent = places.peekLast(); + if (parent != null) { + correctParents(parent.page, nextValues.getTuples().get(0), current.next, current); + } + currentValues.getTuples().addAll(nextValues.getTuples()); + if (current.children != null) { + current.children.addAll(current.next.children); + } + current.next.remove(); + current.next = current.next.next; + if (current.next != null) { + current.next.prev = current; + } + current.setValues(currentValues); + } + /** + * Remove the usage of page in favor of nextPage + * @param parent + * @param page + * @param nextPage + * @throws TeiidComponentException + */ + static void correctParents(SPage parent, List key, SPage page, SPage nextPage) throws TeiidComponentException { + SearchResult location = SPage.search(parent, key, null); + while (location.index == -1 && location.page.prev != null ) { + parent = location.page.prev; + location = SPage.search(parent, key, null); + } + parent = location.page; + int index = location.index; + if (index < 0) { + index = -index - 1; + } + while (parent != null) { + while (index < parent.children.size()) { + if (parent.children.get(index) != page) { + return; + } + parent.children.set(index++, nextPage); + } + index = 0; + parent = parent.next; + } + } + + @Override + public String toString() { + StringBuilder result = new StringBuilder(); + try { + TupleBatch tb = getValues(); + result.append(tb.getBeginRow()); + if (children == null) { + if (tb.getTuples().size() <= 1) { + result.append(values); + } else { + result.append("[").append(tb.getTuples().get(0)).append(" . ").append(tb.getTuples().size()). //$NON-NLS-1$ //$NON-NLS-2$ + append(" . ").append(tb.getTuples().get(tb.getTuples().size() - 1)).append("]"); //$NON-NLS-1$ //$NON-NLS-2$ + } + } else { + result.append("["); //$NON-NLS-1$ + for (int i = 0; i < children.size(); i++) { + result.append(tb.getTuples().get(i)).append("->").append(children.get(i).getValues().getBeginRow()); //$NON-NLS-1$ + if (i < children.size() - 1) { + result.append(", "); //$NON-NLS-1$ + } + } + result.append("]");//$NON-NLS-1$ + } + } catch (Throwable e) { + result.append("Removed"); //$NON-NLS-1$ + } + return result.toString(); + } + } Modified: trunk/engine/src/main/java/org/teiid/common/buffer/STree.java =================================================================== --- trunk/engine/src/main/java/org/teiid/common/buffer/STree.java 2010-07-26 16:57:39 UTC (rev 2374) +++ trunk/engine/src/main/java/org/teiid/common/buffer/STree.java 2010-07-27 02:54:36 UTC (rev 2375) @@ -23,7 +23,6 @@ package org.teiid.common.buffer; import java.io.IOException; -import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.LinkedList; @@ -34,8 +33,6 @@ import org.teiid.common.buffer.SPage.SearchResult; import org.teiid.core.TeiidComponentException; -@SuppressWarnings("unchecked") - /** * Self balancing search tree using skip list like logic * This has similar performance similar to a B+/-Tree @@ -43,11 +40,15 @@ * TODO: reserve additional memory for delete/update operations * TODO: double link to support desc key access */ +@SuppressWarnings("unchecked") public class STree { private static final Random seedGenerator = new Random(); - private int randomSeed; + protected int randomSeed; + private int mask = 1; + private int shift = 1; + private SPage[] header = new SPage[] {new SPage(this, true)}; protected BatchManager manager; protected Comparator comparator; @@ -64,9 +65,17 @@ int keyLength, String[] types) { randomSeed = seedGenerator.nextInt() | 0x00000100; // ensure nonzero + //randomSeed=-1031212234; this.manager = recman; this.comparator = comparator; this.pageSize = Math.max(pageSize, SPage.MIN_PERSISTENT_SIZE); + pageSize >>>= 4; + while (pageSize > 0) { + pageSize >>>= 1; + shift++; + mask <<= 1; + mask++; + } this.keyLength = keyLength; this.types = types; this.keytypes = Arrays.copyOf(types, keyLength); @@ -89,8 +98,7 @@ x ^= x >>> 17; randomSeed = x ^= x << 5; int level = 0; - int shift = 8; - while ((x & 0xff) == 0xff) { + while ((x & mask) == mask) { ++level; x >>>= shift; } @@ -105,19 +113,19 @@ * @throws IOException * @throws TeiidComponentException */ - private List find(List n, List<SearchResult> places) throws TeiidComponentException { + private List find(List n, LinkedList<SearchResult> places) throws TeiidComponentException { SPage x = null; - List parentKey = null; SearchResult parent = null; for (int i = header.length - 1; i >= 0; i--) { if (x == null) { x = header[i]; } - SearchResult s = SPage.search(x, n, parent, parentKey); + SearchResult s = SPage.search(x, n, places); + parent = s; if (places != null) { places.add(s); } - if ((s.index == -1 && s.page == header[i]) || s.values.isEmpty()) { + if ((s.index == -1 && s.page == header[i]) || s.values.getTuples().isEmpty()) { x = null; continue; //start at the beginning of the next level } @@ -132,17 +140,15 @@ if (!matched) { return null; } - return (List) s.values.get(index); + return s.values.getTuples().get(index); } - parentKey = (List) s.values.get(index); - parent = s; x = x.children.get(index); } return null; } public List find(List k) throws TeiidComponentException { - return find(k, null); + return find(k, new LinkedList<SearchResult>()); } public List insert(List tuple, boolean replace) throws TeiidComponentException { @@ -154,7 +160,7 @@ } SearchResult last = places.getLast(); SPage page = last.page; - last.values.set(last.index, tuple); + last.values.getTuples().set(last.index, tuple); page.setValues(last.values); return match; } @@ -169,16 +175,16 @@ for (int i = 0; i <= level; i++) { if (places.isEmpty()) { SPage newHead = new SPage(this, false); - ArrayList newValues = new ArrayList(); - newValues.add(key); - newHead.setValues(newValues); + TupleBatch batch = newHead.getValues(); + batch.getTuples().add(key); + newHead.setValues(batch); newHead.children.add(page); header[i] = newHead; page = newHead; } else { SearchResult result = places.removeLast(); Object value = (i == 0 ? tuple : page); - page = insert(key, result, value); + page = insert(key, result, places.peekLast(), value); } } return null; @@ -188,19 +194,21 @@ return tuple.subList(0, keyLength); } - SPage insert(List k, SearchResult result, Object value) throws TeiidComponentException { + SPage insert(List k, SearchResult result, SearchResult parent, Object value) throws TeiidComponentException { SPage page = result.page; int index = -result.index - 1; - if (result.values.size() == pageSize) { + if (result.values.getTuples().size() == pageSize) { boolean leaf = !(value instanceof SPage); SPage nextPage = new SPage(this, leaf); - ArrayList nextValues = new ArrayList(result.values.subList(pageSize/2, pageSize)); - result.values.subList(pageSize/2, pageSize).clear(); + TupleBatch nextValues = nextPage.getValues(); + nextValues.getTuples().addAll(result.values.getTuples().subList(pageSize/2, pageSize)); + result.values.getTuples().subList(pageSize/2, pageSize).clear(); if (!leaf) { nextPage.children.addAll(page.children.subList(pageSize/2, pageSize)); page.children.subList(pageSize/2, pageSize).clear(); } nextPage.next = page.next; + nextPage.prev = page; page.next = nextPage; boolean inNext = false; if (index <= pageSize/2) { @@ -211,6 +219,10 @@ } nextPage.setValues(nextValues); page.setValues(result.values); + if (parent != null) { + List min = nextPage.getValues().getTuples().get(0); + SPage.correctParents(parent.page, min, page, nextPage); + } if (inNext) { page = nextPage; } @@ -221,12 +233,12 @@ return page; } - static void setValue(int index, List key, Object value, List values, SPage page) { + static void setValue(int index, List key, Object value, TupleBatch values, SPage page) { if (value instanceof SPage) { - values.add(index, key); + values.getTuples().add(index, key); page.children.add(index, (SPage) value); } else { - values.add(index, value); + values.getTuples().add(index, (List)value); } } @@ -237,43 +249,57 @@ return null; } rowCount.addAndGet(-1); - for (int i = header.length -1; i >=0; i--) { - SearchResult searchResult = places.remove(); + for (int i = 0; i < header.length; i++) { + SearchResult searchResult = places.removeLast(); if (searchResult.index < 0) { continue; } - boolean cleanup = false; - searchResult.values.remove(searchResult.index); - int size = searchResult.values.size(); + searchResult.values.getTuples().remove(searchResult.index); + if (searchResult.page.children != null) { + searchResult.page.children.remove(searchResult.index); + } + int size = searchResult.values.getTuples().size(); if (size == 0) { - if (header[i] == searchResult.page && (i != 0 || header[i].next != null)) { - header[i].remove(); + if (header[i] != searchResult.page) { + searchResult.page.remove(); + if (searchResult.page.next != null) { + searchResult.page.next.prev = searchResult.page.prev; + } + searchResult.page.prev.next = searchResult.page.next; + searchResult.page.next = header[i]; + searchResult.page.prev = null; + continue; + } + header[i].remove(); + if (header[i].next != null) { header[i] = header[i].next; - if (header[i] == null) { - //remove the layer - header = Arrays.copyOf(header, header.length - 1); + header[i].prev = null; + } else { + if (i != 0) { + header = Arrays.copyOf(header, i); + break; } - } else if (i == 0 && header.length > 1) { - cleanup = true; + header[0] = new SPage(this, true); } - } else if (searchResult.page.next != null && size < pageSize/4) { - List nextValues = searchResult.page.next.getValues(); - SPage next = searchResult.page.next; - if (nextValues.size() + size < pageSize/2) { - searchResult.page.next = next.next; - searchResult.values.addAll(nextValues); - nextValues.clear(); - next.remove(); - //any references to toMerge are now invalid - //setting back to the header will self heal - //TODO: this can take advantage of a previous link - next.next = header[i]; + continue; + } else if (size < pageSize/2) { + //check for merge + if (searchResult.page.next != null) { + TupleBatch nextValues = searchResult.page.next.getValues(); + if (nextValues.getTuples().size() < pageSize/4) { + SPage.merge(places, nextValues, searchResult.page, searchResult.values); + continue; + } } + if (searchResult.page.prev != null) { + TupleBatch prevValues = searchResult.page.prev.getValues(); + if (prevValues.getTuples().size() < pageSize/4) { + SPage.merge(places, searchResult.values, searchResult.page.prev, prevValues); + continue; + } + } } searchResult.page.setValues(searchResult.values); - if (cleanup) { - find(key, null); //trigger cleanup - } } return tuple; } @@ -309,7 +335,8 @@ SPage page = header[0]; int index; - List values; + TupleBatch values; + boolean updated; public boolean matchedLower() { return false; @@ -324,11 +351,16 @@ if (values == null) { values = page.getValues(); } - if (index < values.size()) { - return (List) values.get(index++); + if (index < values.getTuples().size()) { + return values.getTuples().get(index++); } + if (updated) { + page.setValues(values); + } + values = null; index = 0; page = page.next; + updated = false; if (page == null) { return null; } @@ -342,8 +374,8 @@ * @throws TeiidComponentException */ public void update(List tuple) throws TeiidComponentException { - values.set(index - 1, tuple); - page.setValues(values); + values.getTuples().set(index - 1, tuple); + updated = true; } /** @@ -354,6 +386,22 @@ } } + @Override + public String toString() { + StringBuffer result = new StringBuffer(); + for (int i = header.length -1; i >= 0; i--) { + SPage page = header[i]; + result.append("Level ").append(i).append(" "); //$NON-NLS-1$ //$NON-NLS-2$ + while (page != null) { + result.append(page); + result.append(", "); //$NON-NLS-1$ + page = page.next; + } + result.append("\n"); //$NON-NLS-1$ + } + return result.toString(); + } + public int getKeyLength() { return keyLength; } Copied: trunk/engine/src/test/java/org/teiid/common/buffer/TestSTree.java (from rev 2371, trunk/engine/src/test/java/org/teiid/common/buffer/impl/TestSTree.java) =================================================================== --- trunk/engine/src/test/java/org/teiid/common/buffer/TestSTree.java (rev 0) +++ trunk/engine/src/test/java/org/teiid/common/buffer/TestSTree.java 2010-07-27 02:54:36 UTC (rev 2375) @@ -0,0 +1,60 @@ +/* + * JBoss, Home of Professional Open Source. + * See the COPYRIGHT.txt file distributed with this work for information + * regarding copyright ownership. Some portions may be licensed + * to Red Hat, Inc. under one or more contributor license agreements. + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301 USA. + */ + +package org.teiid.common.buffer; + +import static org.junit.Assert.*; + +import java.util.Arrays; +import java.util.List; + +import org.junit.Test; +import org.teiid.common.buffer.BufferManager.TupleSourceType; +import org.teiid.core.TeiidComponentException; +import org.teiid.query.sql.symbol.ElementSymbol; + +@SuppressWarnings("nls") +public class TestSTree { + + @Test public void testRemoveAll() throws TeiidComponentException { + BufferManager bm = BufferManagerFactory.getStandaloneBufferManager(); + ElementSymbol e1 = new ElementSymbol("x"); + e1.setType(Integer.class); + ElementSymbol e2 = new ElementSymbol("y"); + e2.setType(String.class); + List elements = Arrays.asList(e1, e2); + STree map = bm.createSTree(elements, "1", TupleSourceType.PROCESSOR, 1); + + for (int i = 20000; i > 0; i--) { + assertNull(map.insert(Arrays.asList(i, String.valueOf(i)), true)); + assertEquals(20000 - i + 1, map.getRowCount()); + } + + for (int i = 20000; i > 0; i--) { + assertNotNull(String.valueOf(i), map.remove(Arrays.asList(i))); + } + + assertEquals(0, map.getRowCount()); + assertNull(map.insert(Arrays.asList(1, String.valueOf(1)), true)); + } + +} Property changes on: trunk/engine/src/test/java/org/teiid/common/buffer/TestSTree.java ___________________________________________________________________ Name: svn:mime-type + text/plain Deleted: trunk/engine/src/test/java/org/teiid/common/buffer/impl/TestSTree.java =================================================================== --- trunk/engine/src/test/java/org/teiid/common/buffer/impl/TestSTree.java 2010-07-26 16:57:39 UTC (rev 2374) +++ trunk/engine/src/test/java/org/teiid/common/buffer/impl/TestSTree.java 2010-07-27 02:54:36 UTC (rev 2375) @@ -1,62 +0,0 @@ -/* - * JBoss, Home of Professional Open Source. - * See the COPYRIGHT.txt file distributed with this work for information - * regarding copyright ownership. Some portions may be licensed - * to Red Hat, Inc. under one or more contributor license agreements. - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. - * - * This library is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA - * 02110-1301 USA. - */ - -package org.teiid.common.buffer.impl; - -import static org.junit.Assert.*; - -import java.io.IOException; -import java.util.Arrays; -import java.util.List; - -import org.junit.Test; -import org.teiid.common.buffer.BufferManager; -import org.teiid.common.buffer.BufferManagerFactory; -import org.teiid.common.buffer.STree; -import org.teiid.common.buffer.BufferManager.TupleSourceType; -import org.teiid.core.TeiidComponentException; -import org.teiid.query.sql.symbol.ElementSymbol; - -public class TestSTree { - - @Test public void testRemoveAll() throws TeiidComponentException, IOException { - BufferManager bm = BufferManagerFactory.getStandaloneBufferManager(); - ElementSymbol e1 = new ElementSymbol("x"); - e1.setType(Integer.class); - ElementSymbol e2 = new ElementSymbol("y"); - e2.setType(String.class); - List elements = Arrays.asList(e1, e2); - STree map = bm.createSTree(elements, "1", TupleSourceType.PROCESSOR, 1); - - for (int i = 20000; i > 0; i--) { - map.insert(Arrays.asList(i, String.valueOf(i)), true); - } - - for (int i = 20000; i > 0; i--) { - map.remove(Arrays.asList(i)); - } - - assertEquals(0, map.getRowCount()); - assertNull(map.insert(Arrays.asList(1, String.valueOf(1)), true)); - } - -}