Example of a linked list in Cypher.

LinkedListTest.java

import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

import org.junit.Rule;
import org.junit.Test;

import org.neo4j.cypher.ExecutionEngine;
import org.neo4j.graphdb.Direction;
import org.neo4j.graphdb.DynamicLabel;
import org.neo4j.graphdb.DynamicRelationshipType;
import org.neo4j.graphdb.GraphDatabaseService;
import org.neo4j.graphdb.Label;
import org.neo4j.graphdb.Node;
import org.neo4j.graphdb.Relationship;
import org.neo4j.graphdb.RelationshipType;
import org.neo4j.graphdb.Transaction;
import org.neo4j.graphdb.factory.GraphDatabaseFactory;
import org.neo4j.kernel.DeadlockDetectedException;
import org.neo4j.kernel.impl.util.StringLogger;
import org.neo4j.test.TargetDirectory;

import static org.hamcrest.Matchers.is;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertThat;
import static org.junit.Assert.assertTrue;

import static org.neo4j.helpers.collection.IteratorUtil.single;

public class LinkedListTest
{
    private static final int LINK_COUNT = 50;
    private static final int N_THREADS = 10;
    private static final Label linkLabel = DynamicLabel.label( "LINK" );
    private static final RelationshipType nextType = DynamicRelationshipType.withName( "NEXT" );
    private static final Map<String, Object> insertOptions = new HashMap<>();
    static {
        insertOptions.put( "list_id", 1 );
    }

    @Rule
    public TargetDirectory.TestDirectory dir = TargetDirectory.cleanTestDirForTest( LinkedListTest.class );

    @Test
    public void linkedList() throws InterruptedException
    {
        GraphDatabaseService db = new GraphDatabaseFactory().newEmbeddedDatabase( dir.absolutePath() );
        try ( Transaction tx = db.beginTx() )
        {
            db.schema().constraintFor( linkLabel ).assertPropertyIsUnique( "list_head_id" ).create();
            tx.success();
        }
        ExecutionEngine cypher = new ExecutionEngine( db, StringLogger.SYSTEM );

        ExecutorService executor = Executors.newFixedThreadPool( N_THREADS );
        for ( int i = 0; i < LINK_COUNT; i++ )
        {
            executor.execute( addLink( db, cypher ) );
        }
        executor.shutdown();

        try
        {
            System.out.println( "Waiting up to 5 minutes for tasks to complete" );
            executor.awaitTermination( 5, TimeUnit.MINUTES );
        }
        catch ( InterruptedException e )
        {
            System.out.println( "Waited too long" );
            e.printStackTrace();
        }

        System.out.println( "Verifying list" );
        verifyLinkedList( db );
        System.out.println( "Done verifying" );
    }

    private Runnable addLink( final GraphDatabaseService db, final ExecutionEngine cypher )
    {
        return new Runnable()
        {
            @Override
            public void run()
            {
                Random rng = new Random(  );
                for (;;)
                {
                    sleep( rng.nextInt( 100 ) ); // random timing offsets reduces the deadlock probability
                    try ( Transaction tx = db.beginTx() )
                    {
                        cypher.execute( "merge (current_head:LINK {list_head_id: {list_id}}) \n" +
                                "on create set current_head.is_sentinel = true \n" +
                                "remove current_head.list_head_id \n" +
                                "create (new_head:LINK {list_head_id: {list_id}})-[:NEXT]->current_head",
                                insertOptions );
                        tx.success();
                    }
                    catch ( DeadlockDetectedException e ) {
                        System.out.println( "retry: " + e.getClass().getSimpleName() );
                        continue;
                    }
                    catch ( RuntimeException e )
                    {
                        e.printStackTrace();
                    }
                    break;
                }
            }
        };
    }

    private void sleep( long millis )
    {
        try
        {
            Thread.sleep( millis );
        }
        catch ( InterruptedException e1 )
        {
            Thread.currentThread().interrupt();
        }
    }

    private void verifyLinkedList( GraphDatabaseService db )
    {
        int count = 0;
        try ( Transaction tx = db.beginTx() )
        {
            Node head = single( db.findNodesByLabelAndProperty(
                    linkLabel, "list_head_id", insertOptions.get( "list_id" ) ) );
            System.out.println( "head = " + head );
            while (!head.hasProperty( "is_sentinel" ) )
            {
                count++;
                assertTrue( head.hasLabel( linkLabel ) );
                // this will throw if there is more than one outgoing relationship:
                Relationship next = head.getSingleRelationship( nextType, Direction.OUTGOING );
                System.out.println( "next = " + next );
                head = next.getEndNode();
                System.out.println( "next head = " + head );
                assertFalse( head.hasProperty( "list_head_id" ) );
            }
            tx.success();
        }
        assertThat( count, is( LINK_COUNT ) );
    }
}