You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jena.apache.org by an...@apache.org on 2012/01/05 15:23:49 UTC
svn commit: r1227606 - in /incubator/jena/Scratch/AFS/Dev/trunk/src-lib:
main/java/structure/radix/RadixTree.java
test/java/structure/radix/RadixRun.java
Author: andy
Date: Thu Jan 5 14:23:48 2012
New Revision: 1227606
URL: http://svn.apache.org/viewvc?rev=1227606&view=rev
Log: (empty)
Modified:
incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixTree.java
incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/RadixRun.java
Modified: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixTree.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixTree.java?rev=1227606&r1=1227605&r2=1227606&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixTree.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/main/java/structure/radix/RadixTree.java Thu Jan 5 14:23:48 2012
@@ -226,32 +226,37 @@ public final class RadixTree
node1.prefix = prefix1 ;
node1.lenStart = node.lenStart+N ;
node1.lenFinish = key.length ;
- node1.nodes = null ; // ??
+ node1.nodes = null ;
// This the tail of the original data
RadixNode node2 = RadixNode.alloc(node) ;
node2.prefix = prefix2 ;
node2.lenStart = node.lenStart+N ;
node2.lenFinish = node.lenFinish ;
- // reset parent.
- node2.nodes = node.nodes ;
+ node2.nodes = null ;
+
+ // Alter the node in-place, rather than create a new node and insert node1, node2.
+ // This keeps the root in-place.
if ( node.nodes != null )
{
+ node2.nodes = new ArrayList<RadixNode>(node.nodes) ;
for ( RadixNode n : node.nodes )
{
n.parent = node2 ;
n.parentId = node2.id ;
}
- }
+ }
+
// Swap if necessary
if ( Bytes.compare(prefix1, prefix2) > 0 )
{ RadixNode t = node2 ; node2 = node1 ; node1 = t ; }
- // Alter the node in-place, rather than create a new node and insert node1, node2.
- // This keeps the root in-place.
node.prefix = prefix0 ;
node.lenFinish = prefix0.length+node.lenStart ;
- node.nodes = new ArrayList<RadixNode>() ;
+ if ( node.nodes != null )
+ node.nodes.clear() ;
+ else
+ node.nodes = new ArrayList<RadixNode>() ;
node.nodes.add(node1) ;
node.nodes.add(node2) ;
return node ;
Modified: incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/RadixRun.java
URL: http://svn.apache.org/viewvc/incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/RadixRun.java?rev=1227606&r1=1227605&r2=1227606&view=diff
==============================================================================
--- incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/RadixRun.java (original)
+++ incubator/jena/Scratch/AFS/Dev/trunk/src-lib/test/java/structure/radix/RadixRun.java Thu Jan 5 14:23:48 2012
@@ -51,39 +51,45 @@ public class RadixRun
//TestRadix.afterClass() ;
System.exit(0) ;
}
- // Check/Bug:
- // [0C 08 05] [11 04] [0B 0B 08] [09 02 13 0A] [02 09 04] [05 02 05 01] [0D] [04 00 0D 0B] [] [12 06 08 02] [12 0F 09 04] [0F 0E 01] [05 02 01] [10] [05 0D 09] [05 08] [0C] [12] [12 08] [0C 04] [0B] [0E] [07 0C 12] [13 0E] [03 03] [11 09 04] [05 09 05 0C] [04 02] [09 00] [11 0B 0C] [0B 0C 08 04] [08 03 0E] [06 0B 02] [01 12] [0E 03 03 0F] [02 07] [0E 0A 12] [07 0B 13] [13 11 04 0A] [08 0B 09 03] [09 0E] [10 03 06 0B] [13 04] [0D 0C 0C] [07 0C 0B] [08 06 11] [0D 11] [04 02 0E 10] [0D 10] [0F]
- /*
-Insert--'09 09 08 08'
-Insert--'09 07 04'
-Insert--'07 09 00 03'
-org.openjena.atlas.AtlasException: Found prefix for new inserted key
- at structure.radix.RadixTree.error(RadixTree.java:704)
- at structure.radix.RadixTree$3.exec(RadixTree.java:252)
- at structure.radix.RadixTree.applicator(RadixTree.java:70)
- at structure.radix.RadixTree.insert(RadixTree.java:335)
- at structure.radix.RadixRun.insert(RadixRun.java:214)
- at structure.radix.RadixRun.exec(RadixRun.java:129)
- at structure.radix.RadixRun.main(RadixRun.java:60)
-[09 09 08 08] [09 07 04] [07 09 00 03] [05 00 04 06] [00 01 07 04] [05 02] [] [00] [02] [09]
- */
-
if ( true )
{
RadixTree.logging = false ;
- for ( int i = 0 ; i < 100 ; i++ )
+
+ int nRuns = 1000000 ;
+ int maxLen = 7 ;
+ int nKeys = 20 ;
+ int dotsToCycle = nRuns > 10000 ? 100 : 10 ;
+ int dotsPerLine = 100 ;
+
+ final int ticksPerLine = dotsToCycle*dotsPerLine ;
+
+ System.out.printf("Runs: %d, maxLen=%d, nKeys=%d\n", nRuns, maxLen, nKeys ) ;
+ for ( int i = 0 ; i < nRuns ; i++ )
{
RadixTree trie = new RadixTree() ;
- List<byte[]> x = gen(5, 5) ;
- print(x) ;
- execInsert(trie, x, false) ;
- //trie.printLeaves() ;
+ List<byte[]> x = gen(nKeys, maxLen) ;
List<byte[]> x2 = randomize(x) ;
- print(x2) ;
- execDelete(trie, x2, false) ;
- System.out.println() ;
+
+ if ( i%ticksPerLine == 0 )
+ System.out.printf("%6d: ",i) ;
+ if ( i%dotsToCycle == (dotsToCycle-1) )
+ System.out.print(".") ;
+ if ( i%ticksPerLine == (ticksPerLine-1) )
+ System.out.println() ;
+
+ try {
+ execInsert(trie, x, false) ;
+ execDelete(trie, x2, false) ;
+ } catch (AtlasException ex)
+ {
+ print(x) ;
+ print(x2) ;
+ return ;
+ }
}
+ if ( nRuns%ticksPerLine != 0 )
+ System.out.println() ;
System.out.println("Done") ;
System.exit(0) ;
}
@@ -91,18 +97,15 @@ org.openjena.atlas.AtlasException: Found
RadixTree.logging = true ;
RadixTree trie = new RadixTree() ;
- byte[][] data$ = {
- {0x05,0x04,0x03,0x02}, {0x05,0x08,0x09,0x01}, {0x09,0x05,0x05,0x09}
- //, {0x07,0x09,0x02}
- //, {}
-// , {0x03,0x06,0x01,0x09}, {0x02}, {0x05,0x02,0x05,0x06}, {0x00}, {0x01,0x01,0x05}, {0x01,0x04}
-// , {0x07,0x01,0x00,0x04}, {0x03,0x00}, {0x06,0x06}, {0x02,0x09}, {0x05}, {0x04}
-// , {0x05,0x05,0x09,0x05}, {0x07,0x02,0x00}, {0x09}, {0x00,0x06}, {0x05,0x06,0x04}
-// , {0x04,0x07,0x00}, {0x05,0x06,0x06}, {0x03,0x03,0x06,0x08}
- } ;
- List<byte[]> data = Arrays.asList(data$) ;
- print(data) ;
- execInsert(trie, data, true) ;
+ byte[][] data1$ = { {0x05,0x00,0x06}, {0x05,0x02}, {}, {0x09,0x01,0x01,0x01}, {0x08,0x07} } ;
+ byte[][] data2$ = { {0x09,0x01,0x01,0x01}, {0x05,0x00,0x06}, {0x05,0x02}, {}, {0x08,0x07} } ;
+
+ List<byte[]> x1 = Arrays.asList(data1$) ;
+ List<byte[]> x2 = Arrays.asList(data1$) ;
+ print(x1) ;
+ print(x2) ;
+ execInsert(trie, x1, true) ;
+ execDelete(trie, x2, true) ;
System.out.println("Done") ;
System.exit(0) ;
}
@@ -122,17 +125,17 @@ org.openjena.atlas.AtlasException: Found
}
- // Generate N entries upto to nLen long
- static List<byte[]> gen(int N, int nLen)
+ // Generate nKeys entries upto to nLen long
+ static List<byte[]> gen(int nKeys, int maxLen)
{
List<byte[]> entries = new ArrayList<byte[]>() ;
- for ( int i = 0 ; i < N ; i++)
+ for ( int i = 0 ; i < nKeys ; i++)
{
while(true)
{
- byte[] b = gen1(nLen) ;
+ byte[] b = gen1(maxLen) ;
if ( ! contains(b, entries) )
{
entries.add(b) ;
@@ -196,9 +199,8 @@ org.openjena.atlas.AtlasException: Found
{
System.out.flush() ;
ex.printStackTrace(System.err) ;
- System.err.println(strall(entries)) ;
trie.print() ;
- return ;
+ throw ex ;
}
check(trie, entries) ;
@@ -222,9 +224,8 @@ org.openjena.atlas.AtlasException: Found
{
System.out.flush() ;
ex.printStackTrace(System.err) ;
- System.err.println(strall(entries)) ;
trie.print() ;
- return ;
+ throw ex ;
}
if ( trie.iterator().hasNext() )
{