private static void ResetSections(ref int foundSections, List<Slice> sections, ref MemorySlice startSection, ref long? startSectionId)
 {
     foundSections = 0;
     startSection = null;
     startSectionId = null;
     sections.Clear();
 }

        public FoundPage Find(MemorySlice key)
        {
            for (int i = 0; i < _cache.Length; i++)
            {
                var page = _cache[i];
                if (page == null)
                    continue;

                var first = page.FirstKey;
                var last = page.LastKey;
                
                switch (key.Options)
                {
                    case SliceOptions.BeforeAllKeys:
                        if (first.Options == SliceOptions.BeforeAllKeys)
                            return page;
                        break;
                    case SliceOptions.AfterAllKeys:
                        if (last.Options == SliceOptions.AfterAllKeys)
                            return page;
                        break;
                    case SliceOptions.Key:
                        if ((first.Options != SliceOptions.BeforeAllKeys && key.Compare(first) < 0))
                            continue;
                        if (last.Options != SliceOptions.AfterAllKeys && key.Compare(last) > 0)
                            continue;
                        return page;
                    default:
                        throw new ArgumentException(key.Options.ToString());
                }
            }

            return null;
        }

        public static int NodeEntry(int pageMaxSpace, MemorySlice key, int len)
        {
            if (len < 0)
                return BranchEntry(key);

            return LeafEntry(pageMaxSpace, key, len);
        }

        public byte* AddSeparator(MemorySlice separator, long pageRefNumber, int? nodePos = null)
        {
            var originalLastSearchPositionOfParent = _parentPage.LastSearchPosition;

            if (nodePos == null)
                nodePos = _parentPage.NodePositionFor(separator); // select the appropriate place for this

            var separatorKeyToInsert = _parentPage.PrepareKeyToInsert(separator, nodePos.Value);

            if (_parentPage.HasSpaceFor(_tx, SizeOf.BranchEntry(separatorKeyToInsert) + Constants.NodeOffsetSize + SizeOf.NewPrefix(separatorKeyToInsert)) == false)
            {
                var pageSplitter = new PageSplitter(_tx, _tree, separator, -1, pageRefNumber, NodeFlags.PageRef, 0, _cursor, _tree.State);

                var posToInsert = pageSplitter.Execute();

                ParentOfAddedPageRef = _cursor.CurrentPage;

                var adjustParentPageOnCursor = true;

                for (int i = 0; i < _cursor.CurrentPage.NumberOfEntries; i++)
                {
                    if (_cursor.CurrentPage.GetNode(i)->PageNumber == _currentPage.PageNumber)
                    {
                        adjustParentPageOnCursor = false;
                        _cursor.CurrentPage.LastSearchPosition = i;
                        break;
                    }
                }

                if (adjustParentPageOnCursor)
                {
                    // the above page split has modified the cursor that its first page points to the parent of the leaf where 'separatorKey' was inserted
                    // and it doesn't have the reference to _page, we need to ensure that the actual parent is first at the cursor

                    _cursor.Pop();
                    _cursor.Push(_parentPage);

                    EnsureValidLastSearchPosition(_parentPage, _currentPage.PageNumber, originalLastSearchPositionOfParent);
                }
            #if VALIDATE
                Debug.Assert(_cursor.CurrentPage.GetNode(_cursor.CurrentPage.LastSearchPosition)->PageNumber == _currentPage.PageNumber,
                            "The parent page is not referencing a page which is being split");

                var parentToValidate = ParentOfAddedPageRef;
                Debug.Assert(Enumerable.Range(0, parentToValidate.NumberOfEntries).Any(i => parentToValidate.GetNode(i)->PageNumber == pageRefNumber),
                            "The parent page of a page reference isn't referencing it");
            #endif

                return posToInsert;
            }

            ParentOfAddedPageRef = _parentPage;

            var pos = _parentPage.AddPageRefNode(nodePos.Value, separatorKeyToInsert, pageRefNumber);

            EnsureValidLastSearchPosition(_parentPage, _currentPage.PageNumber, originalLastSearchPositionOfParent);

            return pos;
        }

 public FoundPage(long number, Page page, MemorySlice firstKey, MemorySlice lastKey, long[] cursorPath)
 {
     Number = number;
     Page = page;
     FirstKey = firstKey;
     LastKey = lastKey;
     CursorPath = cursorPath;
 }

        public static int NewPrefix(MemorySlice key)
        {
            var prefixedKey = key as PrefixedSlice;
            if (prefixedKey != null && prefixedKey.NewPrefix != null) // also need to take into account the size of a new prefix that will be written to the page
                return NewPrefix(prefixedKey);

            return 0;
        }

        public static int NodeEntryWithAnotherKey(NodeHeader* other, MemorySlice key)
        {
            var keySize = key == null ? other->KeySize : key.Size;
            var sz = keySize + Constants.NodeHeaderSize;
            if (other->Flags == NodeFlags.Data || other->Flags == NodeFlags.MultiValuePageRef)
                sz += other->DataSize;

            sz += sz & 1;

            return sz;
        }

		public static int NewPrefix(MemorySlice key)
		{
			var prefixedKey = key as PrefixedSlice;

			if (prefixedKey != null && prefixedKey.NewPrefix != null) // also need to take into account the size of a new prefix that will be written to the page
			{
				var size = Constants.PrefixNodeHeaderSize + prefixedKey.NewPrefix.Size;
				size += size & 1;
				
				return size;
			}

			return 0;
		}

        public FoundPage Find(MemorySlice key)
        {
            int position = current;

            int itemsLeft = _cacheSize;
            while ( itemsLeft > 0 )
            {
                var page = _cache[position % _cacheSize];
                if (page == null)
                {
                    itemsLeft--;
                    position++;

                    continue;
                }

                var first = page.FirstKey;
                var last = page.LastKey;

                switch (key.Options)
                {
                    case SliceOptions.Key:
                        if ((first.Options != SliceOptions.BeforeAllKeys && key.Compare(first) < 0))
                            break;
                        if (last.Options != SliceOptions.AfterAllKeys && key.Compare(last) > 0)
                            break;
                        return page;
                    case SliceOptions.BeforeAllKeys:
                        if (first.Options == SliceOptions.BeforeAllKeys)
                            return page;
                        break;
                    case SliceOptions.AfterAllKeys:
                        if (last.Options == SliceOptions.AfterAllKeys)
                            return page;
                        break;
                    default:
                        throw new ArgumentException(key.Options.ToString());
                }

                itemsLeft--;
                position++;
            }

            return null;
        }

        public static int LeafEntry(int pageMaxSpace, MemorySlice key, int len)
        {
            var nodeSize = Constants.NodeHeaderSize;

            if (key.Options == SliceOptions.Key)
                nodeSize += key.Size;
            if (len != 0)
            {
                nodeSize += len;

                if (nodeSize > pageMaxSpace)
                    nodeSize -= len - Constants.PageNumberSize;
            }
            // else - page ref node, take no additional space

            nodeSize += nodeSize & 1;

            return nodeSize;
        }

 public PageSplitter(Transaction tx,
     Tree tree,
     MemorySlice newKey,
     int len,
     long pageNumber,
     NodeFlags nodeType,
     ushort nodeVersion,
     Cursor cursor,
     TreeMutableState treeState)
 {
     _tx = tx;
     _tree = tree;
     _newKey = newKey;
     _len = len;
     _pageNumber = pageNumber;
     _nodeType = nodeType;
     _nodeVersion = nodeVersion;
     _cursor = cursor;
     _treeState = treeState;
     Page page = _cursor.Pages.First.Value;
     _page = tx.ModifyPage(page.PageNumber, _tree, page);
     _cursor.Pop();
 }

        private bool TryCreateNewPrefix(MemorySlice key, int nodeIndex, out PrefixedSlice prefixedSlice)
        {
            if (_prefixSection->NextPrefixId >= PrefixCount || NumberOfEntries == 0)
            {
                prefixedSlice = null;
                return false;
            }

            MemorySlice left;
            MemorySlice right;

            if (nodeIndex > 0 && nodeIndex < NumberOfEntries) // middle
            {
                left = GetNodeKey(nodeIndex - 1);
                right = GetNodeKey(nodeIndex);
            }
            else if (nodeIndex == 0) // first
            {
                left = null;
                right = GetNodeKey(0);
            }
            else if (nodeIndex == NumberOfEntries) // last
            {
                left = GetNodeKey(nodeIndex - 1);
                right = null;
            }
            else
                throw new NotSupportedException("Invalid node index prefix: " + nodeIndex + ". Number of entries: " + NumberOfEntries);

            ushort leftLength = 0;
            ushort rightLength = 0;

            if (left != null && left.Size > 0) // not before all keys
                leftLength = key.FindPrefixSize(left);

            if (right != null)
                rightLength = key.FindPrefixSize(right);

            var minPrefixLength = MinPrefixLength(key);

            if (left != null && leftLength > minPrefixLength && leftLength > rightLength)
            {
                prefixedSlice = new PrefixedSlice(_prefixSection->NextPrefixId, leftLength, key.Skip(leftLength))
                {
                    NewPrefix = new Slice(left.ToSlice(), leftLength)
                };

                return true;
            }

            if (right != null && rightLength > minPrefixLength && rightLength > leftLength)
            {
                prefixedSlice = new PrefixedSlice(_prefixSection->NextPrefixId, rightLength, key.Skip(rightLength))
                {
                    NewPrefix = new Slice(right.ToSlice(), rightLength)
                };

                return true;
            }

            prefixedSlice = null;
            return false;
        }

        private bool TryUseExistingPrefix(MemorySlice key, out PrefixedSlice prefixedSlice)
        {
            if (_prefixSection->NextPrefixId < 1)
            {
                prefixedSlice = null;
                return false;
            }

            BestPrefixMatch bestMatch = null;

            for (byte prefixId = 0; prefixId < _prefixSection->NextPrefixId; prefixId++)
            {
                AssertPrefixNode(prefixId);

                var prefix = new PrefixNode();

                prefix.Set(_base + _prefixSection->PrefixOffsets[prefixId], PageNumber);

                var length = key.FindPrefixSize(new Slice(prefix.ValuePtr, prefix.PrefixLength));
                if (length == 0)
                    continue;

                if (length == prefix.PrefixLength) // full prefix usage
                {
                    prefixedSlice = new PrefixedSlice(prefixId, length, key.Skip(length))
                    {
                        Prefix = prefix
                    };
                    return true;
                }

                // keep on looking for a better prefix

                if (bestMatch == null)
                {
                    bestMatch = new BestPrefixMatch
                    {
                        PrefixId = prefixId,
                        PrefixUsage = length,
                        PrefixNode = prefix
                    };
                }
                else if (length > bestMatch.PrefixUsage)
                {
                    bestMatch.PrefixId = prefixId;
                    bestMatch.PrefixUsage = length;
                    bestMatch.PrefixNode = prefix;
                }
            }

            if (bestMatch != null && bestMatch.PrefixUsage > MinPrefixLength(key))
            {
                prefixedSlice = new PrefixedSlice(bestMatch.PrefixId, bestMatch.PrefixUsage, key.Skip(bestMatch.PrefixUsage))
                {
                    Prefix = bestMatch.PrefixNode
                };
                return true;
            }

            prefixedSlice = null;
            return false;
        }

        public MemorySlice PrepareKeyToInsert(MemorySlice key, int nodeIndex)
        {
            if (KeysPrefixed == false)
                return key;

            if (key.KeyLength == 0)
                return PrefixedSlice.Empty;

            PrefixedSlice prefixedSlice;

            if (TryUseExistingPrefix(key, out prefixedSlice))
                return prefixedSlice;

            if (TryCreateNewPrefix(key, nodeIndex, out prefixedSlice))
                return prefixedSlice;

            return new PrefixedSlice(key);
        }

        /// <summary>
        /// Internal method that is used when splitting pages
        /// No need to do any work here, we are always adding at the end
        /// </summary>
        internal void CopyNodeDataToEndOfPage(NodeHeader* other, MemorySlice key)
        {
            var index = NumberOfEntries;

            Debug.Assert(HasSpaceFor(SizeOf.NodeEntryWithAnotherKey(other, key) + Constants.NodeOffsetSize + SizeOf.NewPrefix(key)));

            var nodeSize = SizeOf.NodeEntryWithAnotherKey(other, key);

            Debug.Assert(IsBranch == false || index != 0 || key.KeyLength == 0);// branch page's first item must be the implicit ref

            var nodeVersion = other->Version; // every time new node is allocated the version is increased, but in this case we do not want to increase it
            if (nodeVersion > 0)
                nodeVersion -= 1;

            var prefixedKey = key as PrefixedSlice;
            if (prefixedKey != null && prefixedKey.NewPrefix != null)
                WritePrefix(prefixedKey.NewPrefix, prefixedKey.Header.PrefixId);

            var newNode = AllocateNewNode(index, nodeSize, nodeVersion);

            newNode->KeySize = key.Size;
            newNode->Flags = other->Flags;

            if(key.Options == SliceOptions.Key &&  key.Size > 0)
                key.CopyTo((byte*)newNode + Constants.NodeHeaderSize);

            if (IsBranch || other->Flags == (NodeFlags.PageRef))
            {
                newNode->PageNumber = other->PageNumber;
                newNode->Flags = NodeFlags.PageRef;
                return;
            }
            newNode->DataSize = other->DataSize;
            Memory.Copy((byte*)newNode + Constants.NodeHeaderSize + key.Size,
                                 (byte*)other + Constants.NodeHeaderSize + other->KeySize,
                                 other->DataSize);
        }

        private NodeHeader* CreateNode(int index, MemorySlice key, NodeFlags flags, int len, ushort previousNodeVersion)
        {
            Debug.Assert(index <= NumberOfEntries && index >= 0);
            Debug.Assert(IsBranch == false || index != 0 || key.KeyLength == 0);// branch page's first item must be the implicit ref
            if (HasSpaceFor(key, len) == false)
                throw new InvalidOperationException(string.Format("The page is full and cannot add an entry, this is probably a bug. Key: {0}, data length: {1}, size left: {2}", key, len, SizeLeft));

            var prefixedKey = key as PrefixedSlice;
            if (prefixedKey != null && prefixedKey.NewPrefix != null)
                WritePrefix(prefixedKey.NewPrefix, prefixedKey.Header.PrefixId);

            // move higher pointers up one slot
            for (int i = NumberOfEntries; i > index; i--)
            {
                KeysOffsets[i] = KeysOffsets[i - 1];
            }

            var nodeSize = SizeOf.NodeEntry(PageMaxSpace, key, len);
            var node = AllocateNewNode(index, nodeSize, previousNodeVersion);

            node->KeySize = key.Size;

            if (key.Options == SliceOptions.Key && key.Size > 0)
                key.CopyTo((byte*)node + Constants.NodeHeaderSize);

            node->Flags = flags;

            return node;
        }

        public byte* AddMultiValueNode(int index, MemorySlice key, int dataSize, ushort previousNodeVersion)
        {
            Debug.Assert(dataSize == sizeof(TreeRootHeader));
            Debug.Assert(key.Options == SliceOptions.Key);

            var node = CreateNode(index, key, NodeFlags.MultiValuePageRef, dataSize, previousNodeVersion);
            node->DataSize = dataSize;

            return (byte*)node + Constants.NodeHeaderSize + key.Size;
        }

		internal bool TryGetMultiValueTree(Tree tree, MemorySlice key, out Tree mvTree)
		{
			mvTree = null;
			if (_multiValueTrees == null)
				return false;
			return _multiValueTrees.TryGetValue(Tuple.Create(tree, key), out mvTree);
		}

 // REVIEW: Removed forced inlining for now until we can see if we improve without needing it. 
 // [MethodImpl(MethodImplOptions.AggressiveInlining)]
 public void SetNodeKey(NodeHeader* node, ref MemorySlice sliceInstance)
 {
     if (KeysPrefixed)
     {
         var slice = (PrefixedSlice)sliceInstance;
         SetNodeKey(node, ref slice);
         sliceInstance = slice;
     }                
     else
     {
         Slice slice = (Slice)sliceInstance;
         SetNodeKey(node, ref slice);
         sliceInstance = slice;
     }
 }

 private bool HasSpaceFor(MemorySlice key, int len)
 {
     return HasSpaceFor(GetRequiredSpace(key, len));
 }