DeleteResult delete()

in mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java [149:318]
111 lines of code
13 McCabe index (conditional complexity)

    /* no qualifier */DeleteResult<K, V> delete( K key, V value, long revision, Page<K, V> parent, int parentPos )
        throws IOException
    {
        // Check that the leaf is not empty
        if ( nbElems == 0 )
        {
            // Empty leaf
            return NotPresentResult.NOT_PRESENT;
        }

        // Find the key in the page
        int pos = findPos( key );

        if ( pos >= 0 )
        {
            // Not found : return the not present result.
            return NotPresentResult.NOT_PRESENT;
        }

        // Get the removed element
        Tuple<K, V> removedElement = null;

        // flag to detect if a key was completely removed
        boolean keyRemoved = false;

        int index = -( pos + 1 );

        boolean isNotSubTree = ( btree.getType() != PERSISTED_SUB );

        ValueHolder<V> valueHolder = null;

        if ( isNotSubTree )
        {
            valueHolder = values[index];
        }
        else
        // set value to null, just incase if a non-null value passed while deleting a key from from sub-btree
        {
            value = null;
        }

        if ( value == null )
        {
            // we have to delete the whole value
            removedElement = new Tuple<K, V>( keys[index].getKey(), value ); // the entire value was removed
            keyRemoved = true;
        }
        else
        {
            if ( valueHolder.contains( value ) )
            {
                keyRemoved = ( valueHolder.size() == 1 );

                removedElement = new Tuple<K, V>( keys[index].getKey(), value ); // only one value was removed
            }
            else
            {
                return NotPresentResult.NOT_PRESENT;
            }
        }

        PersistedLeaf<K, V> newLeaf = null;

        if ( keyRemoved )
        {
            // No value, we can remove the key
            newLeaf = new PersistedLeaf<K, V>( btree, revision, nbElems - 1 );
        }
        else
        {
            // Copy the page as we will delete a value from a ValueHolder
            newLeaf = new PersistedLeaf<K, V>( btree, revision, nbElems );
        }

        // Create the result
        DeleteResult<K, V> defaultResult = new RemoveResult<K, V>( newLeaf, removedElement );

        // If the parent is null, then this page is the root page.
        if ( parent == null )
        {
            // Just remove the entry if it's present, or replace it if we have more than one value in the ValueHolder
            copyAfterRemovingElement( keyRemoved, value, newLeaf, index );

            // The current page is added in the copied page list
            defaultResult.addCopiedPage( this );

            return defaultResult;
        }
        else if ( keyRemoved )
        {
            // The current page is not the root. Check if the leaf has more than N/2
            // elements
            int halfSize = btree.getPageSize() / 2;

            if ( nbElems == halfSize )
            {
                // We have to find a sibling now, and either borrow an entry from it
                // if it has more than N/2 elements, or to merge the two pages.
                // Check in both next and previous page, if they have the same parent
                // and select the biggest page with the same parent to borrow an element.
                int siblingPos = selectSibling( parent, parentPos );
                PersistedLeaf<K, V> sibling = ( PersistedLeaf<K, V> ) ( ( ( PersistedNode<K, V> ) parent )
                    .getPage( siblingPos ) );

                if ( sibling.getNbElems() == halfSize )
                {
                    // We will merge the current page with its sibling
                    DeleteResult<K, V> result = mergeWithSibling( removedElement, revision, sibling,
                        ( siblingPos < parentPos ), index );

                    return result;
                }
                else
                {
                    // We can borrow the element from the left sibling
                    if ( siblingPos < parentPos )
                    {
                        DeleteResult<K, V> result = borrowFromLeft( removedElement, revision, sibling, index );

                        return result;
                    }
                    else
                    {
                        // Borrow from the right sibling
                        DeleteResult<K, V> result = borrowFromRight( removedElement, revision, sibling, index );

                        return result;
                    }
                }
            }
            else
            {
                // The page has more than N/2 elements.
                // We simply remove the element from the page, and if it was the leftmost,
                // we return the new pivot (it will replace any instance of the removed
                // key in its parents)
                copyAfterRemovingElement( true, value, newLeaf, index );

                // The current page is added in the copied page list
                defaultResult.addCopiedPage( this );

                return defaultResult;
            }
        }
        else
        {
            // Last, not least : we can copy the full page
            // Copy the keys and the values
            System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
            System.arraycopy( values, 0, newLeaf.values, 0, nbElems );

            // Replace the ValueHolder now
            try
            {
                ValueHolder<V> newValueHolder = valueHolder.clone();
                newValueHolder.remove( value );

                newLeaf.values[pos] = newValueHolder;
            }
            catch ( CloneNotSupportedException e )
            {
                throw new RuntimeException( e );
            }

            // The current page is added in the copied page list
            defaultResult.addCopiedPage( this );

            return defaultResult;
        }
    }