Copyright (c) 2017 Google, Inc and others.
This program and the accompanying materials
are made available under the terms of the Eclipse Public License 2.0
which accompanies this distribution, and is available at
https://www.eclipse.org/legal/epl-2.0/
SPDX-License-Identifier: EPL-2.0
Contributors:
  Stefan Xenos (Google) - Initial implementation
/*******************************************************************************
 * Copyright (c) 2017 Google, Inc and others.
 *
 * This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License 2.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-2.0/
 *
 * SPDX-License-Identifier: EPL-2.0
 *
 * Contributors:
 *   Stefan Xenos (Google) - Initial implementation
 *******************************************************************************/
package org.eclipse.jdt.internal.core.nd.field;

import java.util.ArrayList;
import java.util.List;

import org.eclipse.jdt.internal.core.nd.ITypeFactory;
import org.eclipse.jdt.internal.core.nd.Nd;
import org.eclipse.jdt.internal.core.nd.db.Database;
import org.eclipse.jdt.internal.core.nd.db.ModificationLog;
import org.eclipse.jdt.internal.core.nd.db.ModificationLog.Tag;
import org.eclipse.jdt.internal.core.nd.util.MathUtils;

Stores a singly-linked list of blocks, each of which contains a variable number of embedded elements.
Each block contains a header containing the size of the block and pointer to the next block, followed
by the embedded elements themselves.
/**
 * Stores a singly-linked list of blocks, each of which contains a variable number of embedded elements.
 * Each block contains a header containing the size of the block and pointer to the next block, followed
 * by the embedded elements themselves.
 */
public class FieldList<T> extends BaseField implements IDestructableField {
	
Pointer to the first block.
/**
	 * Pointer to the first block.
	 */
	public final static FieldPointer FIRST_BLOCK;
	
Pointer to the block where insertions are currently happening. This is only null if there are no allocated
blocks. If there are any blocks containing elements, this points to the last block with a nonzero number of
elements.
/**
	 * Pointer to the block where insertions are currently happening. This is only null if there are no allocated
	 * blocks. If there are any blocks containing elements, this points to the last block with a nonzero number of
	 * elements.
	 */
	public final static FieldPointer LAST_BLOCK_WITH_ELEMENTS;

	@SuppressWarnings("rawtypes")
	private static final StructDef<FieldList> type;
	private static final int LIST_HEADER_BYTES;
	private static final long MAX_BYTES_IN_A_CHUNK = Database.getBytesThatFitInChunks(1);

	private final StructDef<T> elementType;
	private final int elementsPerBlock;
	private final StructDef<?> ownerType;
	private final Tag allocateTag;
	private final Tag appendTag;
	private final Tag destructTag;

	static {
		type = StructDef.createAbstract(FieldList.class);
		FIRST_BLOCK = type.addPointer();
		LAST_BLOCK_WITH_ELEMENTS = type.addPointer();

		type.done();
		LIST_HEADER_BYTES = MathUtils.roundUpToNearestMultipleOfPowerOfTwo(type.size(), Database.BLOCK_SIZE_DELTA);
	}

	private static class BlockHeader {
		// This points to the next block if there is one, or null if not.
		public final static FieldPointer NEXT_BLOCK;
		public final static FieldShort BLOCK_SIZE;
		public final static FieldShort ELEMENTS_IN_USE;
		public static final int BLOCK_HEADER_BYTES;

		@SuppressWarnings("hiding")
		private static final StructDef<BlockHeader> type;

		static {
			type = StructDef.createAbstract(BlockHeader.class);

			NEXT_BLOCK = type.addPointer();
			BLOCK_SIZE = type.addShort();
			ELEMENTS_IN_USE = type.addShort();
			type.done();

			BLOCK_HEADER_BYTES = MathUtils.roundUpToNearestMultipleOfPowerOfTwo(type.size(), Database.BLOCK_SIZE_DELTA);
		}
	}

	private FieldList(StructDef<?> ownerType, StructDef<T> elementType,  int elementsPerBlock) {
		this.elementType = elementType;
		this.elementsPerBlock = elementsPerBlock;
		this.ownerType = ownerType;
		int fieldNumber = ownerType.getNumFields();
		setFieldName("field " + fieldNumber + ", a " + getClass().getSimpleName() //$NON-NLS-1$//$NON-NLS-2$
				+ " in struct " + ownerType.getStructName());//$NON-NLS-1$
		this.allocateTag = ModificationLog.createTag("Allocating elements for " + getFieldName()); //$NON-NLS-1$
		this.appendTag = ModificationLog.createTag("Appending to " + getFieldName()); //$NON-NLS-1$
		this.destructTag = ModificationLog.createTag("Deallocating " + getFieldName()); //$NON-NLS-1$
	}

	
Creates a new FieldList in the given struct which contains elements of the given type. The resulting list will grow by 1 element each time it overflows. 
Params:
ownerStruct –  the struct to which the new list field will be added. Must not have had StructDef.done() invoked on it yet.
elementType – 
           the type of elements that will be contained in the struct.
Returns:
a newly-constructed list field in the given struct./**
	 * Creates a new {@link FieldList} in the given struct which contains elements of the given type. The resulting list
	 * will grow by 1 element each time it overflows.
	 * 
	 * @param ownerStruct
	 *            the struct to which the new list field will be added. Must not have had {@link StructDef#done()}
	 *            invoked on it yet.
	 * @param elementType
	 *            the type of elements that will be contained in the struct.
	 * @return a newly-constructed list field in the given struct.
	 */
	public static <T> FieldList<T> create(StructDef<?> ownerStruct, StructDef<T> elementType) {
		return create(ownerStruct, elementType, 1);
	}

	
Creates a new FieldList in the given struct which contains elements of the given type. The resulting list will grow by the given number of elements each time it overflows. 
Params:
ownerStruct –  the struct to which the new list field will be added. Must not have had StructDef.done() invoked on it yet.
elementType – 
           the type of elements that will be contained in the struct.
elementsPerBlock – 
           the number of elements that will be allocated each time the list overflows.
Returns:
a newly-constructed list field in the given struct./**
	 * Creates a new {@link FieldList} in the given struct which contains elements of the given type. The resulting list
	 * will grow by the given number of elements each time it overflows.
	 * 
	 * @param ownerStruct
	 *            the struct to which the new list field will be added. Must not have had {@link StructDef#done()}
	 *            invoked on it yet.
	 * @param elementType
	 *            the type of elements that will be contained in the struct.
	 * @param elementsPerBlock
	 *            the number of elements that will be allocated each time the list overflows.
	 * @return a newly-constructed list field in the given struct.
	 */
	public static <T> FieldList<T> create(StructDef<?> ownerStruct, StructDef<T> elementType, int elementsPerBlock) {
		FieldList<T> result = new FieldList<>(ownerStruct, elementType, elementsPerBlock);
		ownerStruct.add(result);
		ownerStruct.addDestructableField(result);
		return result;
	}

	private int getElementSize() {
		int recordSize = this.elementType.getFactory().getRecordSize();
		return MathUtils.roundUpToNearestMultipleOfPowerOfTwo(recordSize, Database.BLOCK_SIZE_DELTA);
	}

	@Override
	public int getRecordSize() {
		return LIST_HEADER_BYTES;
	}

	
Returns the contents of the receiver as a List. 
Params:
nd – the database to be queried.
address – the address of the parent struct/**
	 * Returns the contents of the receiver as a {@link List}.
	 * 
	 * @param nd the database to be queried.
	 * @param address the address of the parent struct
	 */
	public List<T> asList(Nd nd, long address) {
		long headerStartAddress = address + this.offset;
		long firstBlockAddress = FIRST_BLOCK.get(nd, headerStartAddress);

		List<T> result = new ArrayList<>();

		long nextBlockAddress = firstBlockAddress;
		while (nextBlockAddress != 0) {
			long currentBlockAddress = nextBlockAddress;
			nextBlockAddress = BlockHeader.NEXT_BLOCK.get(nd, currentBlockAddress);
			int elementsInBlock = BlockHeader.ELEMENTS_IN_USE.get(nd, currentBlockAddress);
			long firstElementInBlockAddress = currentBlockAddress + BlockHeader.BLOCK_HEADER_BYTES;

			readElements(result, nd, firstElementInBlockAddress, elementsInBlock);
		}

		return result;
	}

	private void readElements(List<T> result, Nd nd, long nextElementAddress, int count) {
		ITypeFactory<T> factory = this.elementType.getFactory();

		int size = getElementSize();
		for (; count > 0; count--) {
			result.add(factory.create(nd, nextElementAddress));
			nextElementAddress += size;
		}
	}

	public T append(Nd nd, long address) {
		Database db = nd.getDB();
		db.getLog().start(this.appendTag);
		try {
			long headerStartAddress = address + this.offset;
			long nextBlockAddress = LAST_BLOCK_WITH_ELEMENTS.get(nd, headerStartAddress);
	
			// Ensure that there's at least one block
			long insertionBlockAddress = nextBlockAddress;
			if (nextBlockAddress == 0) {
				long newBlockAddress = allocateNewBlock(nd, this.elementsPerBlock);
				LAST_BLOCK_WITH_ELEMENTS.put(nd, headerStartAddress, newBlockAddress);
				FIRST_BLOCK.put(nd, headerStartAddress, newBlockAddress);
				insertionBlockAddress = newBlockAddress;
			}
	
			// Check if there's any free space in this block
			int elementsInBlock = BlockHeader.ELEMENTS_IN_USE.get(nd, insertionBlockAddress);
			int blockSize = BlockHeader.BLOCK_SIZE.get(nd, insertionBlockAddress);
	
			if (elementsInBlock >= blockSize) {
				long nextBlock = BlockHeader.NEXT_BLOCK.get(nd, insertionBlockAddress);
				if (nextBlock == 0) {
					nextBlock = allocateNewBlock(nd, this.elementsPerBlock);
					BlockHeader.NEXT_BLOCK.put(nd, insertionBlockAddress, nextBlock);
				}
				LAST_BLOCK_WITH_ELEMENTS.put(nd, headerStartAddress, nextBlock);
				insertionBlockAddress = nextBlock;
				elementsInBlock = BlockHeader.ELEMENTS_IN_USE.get(nd, insertionBlockAddress); 
			}
	
			BlockHeader.ELEMENTS_IN_USE.put(nd, insertionBlockAddress, (short) (elementsInBlock + 1));
			int elementSize = getElementSize();
	
			long resultAddress = insertionBlockAddress + BlockHeader.BLOCK_HEADER_BYTES + elementsInBlock * elementSize;
			assert ((resultAddress - Database.BLOCK_HEADER_SIZE) & (Database.BLOCK_SIZE_DELTA - 1)) == 0;
			return this.elementType.getFactory().create(nd, resultAddress);
		} finally {
			db.getLog().end(this.appendTag);
		}
	}

	
Ensures that the receiver will have space for the given number of elements without additional allocation. Callers should invoke this prior to a sequence of append(Nd, long) calls if they know in advance how many elements will be appended. Will create the minimum number of extra blocks needed to the given number of additional elements. /**
	 * Ensures that the receiver will have space for the given number of elements without additional
	 * allocation. Callers should invoke this prior to a sequence of {@link FieldList#append(Nd, long)}
	 * calls if they know in advance how many elements will be appended. Will create the minimum number
	 * of extra blocks needed to the given number of additional elements.
	 */
	public void allocate(Nd nd, long address, int numElements) {
		Database db = nd.getDB();
		db.getLog().start(this.allocateTag);
		try {
			if (numElements == 0) {
				// Not an error, but there's nothing to do if the caller didn't actually ask for anything to be allocated.
				return;
			}
			long headerStartAddress = address + this.offset;
			long nextBlockAddress = LAST_BLOCK_WITH_ELEMENTS.get(nd, headerStartAddress);
	
			int maxBlockSizeThatFitsInAChunk = (int) ((MAX_BYTES_IN_A_CHUNK - BlockHeader.BLOCK_HEADER_BYTES)
					/ getElementSize());

			// Ensure that there's at least one block
			if (nextBlockAddress == 0) {
				int firstAllocation = Math.min(numElements, maxBlockSizeThatFitsInAChunk);
				nextBlockAddress = allocateNewBlock(nd, firstAllocation);
				LAST_BLOCK_WITH_ELEMENTS.put(nd, headerStartAddress, nextBlockAddress);
				FIRST_BLOCK.put(nd, headerStartAddress, nextBlockAddress);
			}
	
			// Check if there's any free space in this block
			int remainingToAllocate = numElements;
			while (true) {
				long currentBlockAddress = nextBlockAddress;
				nextBlockAddress = BlockHeader.NEXT_BLOCK.get(nd, currentBlockAddress);
				int elementsInUse = BlockHeader.ELEMENTS_IN_USE.get(nd, currentBlockAddress);
				int blockSize = BlockHeader.BLOCK_SIZE.get(nd, currentBlockAddress);
	
				remainingToAllocate -= (blockSize - elementsInUse);
				if (remainingToAllocate <= 0) {
					break;
				}
	
				if (nextBlockAddress == 0) {
					nextBlockAddress = allocateNewBlock(nd, Math.min(maxBlockSizeThatFitsInAChunk, numElements));
					BlockHeader.NEXT_BLOCK.put(nd, currentBlockAddress, nextBlockAddress);
				}
			}
		} finally {
			db.getLog().end(this.allocateTag);
		}
	}

	private long allocateNewBlock(Nd nd, int blockSize) {
		short poolId = getMemoryPoolId(nd);
		int elementSize = getElementSize();
		long bytesNeeded = BlockHeader.BLOCK_HEADER_BYTES + blockSize * elementSize;
		// If we're close enough to filling the chunk that we wouldn't be able to fit any more elements anyway, allocate
		// the entire chunk. Although it wastes a small amount of space, it ensures that the blocks can be more easily
		// reused rather than being fragmented. It also allows freed blocks to be merged via the large block allocator.
		if (MAX_BYTES_IN_A_CHUNK - bytesNeeded < elementSize) {
			bytesNeeded = MAX_BYTES_IN_A_CHUNK;
		}
		long result = nd.getDB().malloc(bytesNeeded, poolId);
		BlockHeader.BLOCK_SIZE.put(nd, result, (short) blockSize);
		return result;
	}

	private short getMemoryPoolId(Nd nd) {
		short poolId = Database.POOL_LINKED_LIST;
		if (this.ownerType != null) {
			Class<?> structClass = this.ownerType.getStructClass();
			if (nd.getTypeRegistry().isRegisteredClass(structClass)) {
				poolId = (short) (Database.POOL_FIRST_NODE_TYPE + nd.getNodeType(structClass));
			}
		}
		return poolId;
	}

	@Override
	public void destruct(Nd nd, long address) {
		Database db = nd.getDB();
		db.getLog().start(this.destructTag);
		try {
			short poolId = getMemoryPoolId(nd);
			long headerStartAddress = address + this.offset;
			long firstBlockAddress = FIRST_BLOCK.get(nd, headerStartAddress);
	
			long nextBlockAddress = firstBlockAddress;
			while (nextBlockAddress != 0) {
				long currentBlockAddress = nextBlockAddress;
				nextBlockAddress = BlockHeader.NEXT_BLOCK.get(nd, currentBlockAddress);
				int elementsInBlock = BlockHeader.ELEMENTS_IN_USE.get(nd, currentBlockAddress);
				destructElements(nd, currentBlockAddress + BlockHeader.BLOCK_HEADER_BYTES, elementsInBlock);
				db.free(currentBlockAddress, poolId);
			}
	
			db.clearRange(headerStartAddress, getRecordSize());
		} finally {
			db.getLog().end(this.destructTag);
		} 
	}

	private void destructElements(Nd nd, long nextElementAddress, int count) {
		ITypeFactory<T> factory = this.elementType.getFactory();

		int size = getElementSize();
		while (--count >= 0) {
			factory.destruct(nd, nextElementAddress);
			nextElementAddress += size;
		}
	}
}