org.eclipse.jdt.core/search/org/eclipse/jdt/internal/core/nd/field/FieldList.java - gerrit/aspectj/org.aspectj.shadows - Git at Google

 /*******************************************************************************
  * 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.
  */
 public class FieldList<T> extends BaseField implements IDestructableField {
 	/**
 	 * 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.
 	 */
 	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 {@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 {@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 {@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 {@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;
 		}
 	}
 }
	/*******************************************************************************
	* 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.
	*/
	public class FieldList<T> extends BaseField implements IDestructableField {
	/**
	* 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.
	*/
	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 {@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 {@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 {@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 {@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;
	}
	}
	}