Tutorial Categories:

HTML/CSS JavaScript/AJAX Server-Side Marketing General Comp-Sci

A System to Dynamically-Allocate Memory With Minimal Fragmentation

By Justin Poirier

Introduction

Computer systems have approached memory addressing in two prominent ways. In systems with only segmentation, memory is arranged into segments, and memory addresses are expressed using two numbers: the segment base address and the offset from that base address. On systems with virtual memory, all addresses are communicated as locations in terms of an imaginary address space, and then each is converted to its corresponding address in real memory just before use. No spatial relationship can be assumed between a virtual address and its corresponding real address. For details on memory addressing, see Classroom306's articles on Pentium modes for memory addressing and virtual memory.

This article will present a solution to cases where it is desired that a region of memory be used to store arbitrary data items, which come and go at arbitrary times, with no individual item required to be stored at a particular address. Within the systems described above, there are several scenarios where such a solution is needed.

Dynamically-allocated memory refers to the data items of a program which do not have memory reserved for them until runtime. In both of the above types of systems, a process is typically given a block of memory (the heap1) to use for this - it just so happens that on virtual memory systems, this block is within virtual address space. The inner contents of the heap itself are one example of where an allocation system is needed.

On systems without virtual memory, the heap as a whole, and for that matter a program's entire memory block, have to be allocated (on systems with virtual memory, this usually not necessary since a process has its own address space). Additional heap segments also must be allocated, for cases where a process uses up its entire heap. These problems of the distribution of processes throughout memory, are another area where the system presented here could be used.

On small or embedded systems, the segmentation may not double as memory protection. In this case, the allocation system detailed here has the added benefit that it could be used as an alternative form of memory protection, as described below.

On these small/embedded systems, a process's heap may actually not be contained within a block initially allocated for the process. Run-time requests for memory from all processes might be treated no differently than newly-executed programs requiring memory allocation, with each being allocated memory from anywhere in memory that the operating system can find room. Here again, an allocation system like ours would be needed.

General Overview and Comparison to Existing Systems

The system is comprised of a user-defined type (implemented as the struct "BlockInfo" in the C code used below) and several procedures that work together to manage memory. If, out of the possible uses described above, the system is used for memory within a process's heap, the programming language operators and functions used to allocate and free memory would make use of the procedures provided. This includes "new", "delete", "malloc()" and "free()".

The region of memory in which allocation will take place is divided into blocks, which are arbitrary collections of contiguous memory locations, and instances of BlockInfo. BlockInfo instances are used to keep track of blocks. For each block there is exactly one BlockInfo instance. A block may be a chunk of memory that has been allocated, or a chunk of free memory neighboured on either side by an allocated block. Our system uses a doubly-linked list of BlockInfo instances to find free blocks, to be used for allocation requests. Allocated blocks are not initialized, and retain whatever data is already stored in them.

The BlockInfo instance pointing to a block need not be at any particular location in memory relative to the block itself. This is in contrast to the prominent strategies that are actually used in practice to manage memory within a heap, like the First Fit and Buddy Allocation techniques, by which the info about a block is the first part of the block itself, called the header. Our approach requires more work for certain allocations, but allowing a block and its BlockInfo to be stored in different locations decreases the amount of contiguous space needed slightly, which offers a unique way of optimizing memory usage for systems with limited space.

Of the heap management strategies in use, ours is most like First Fit, however there are additional differences. First Fit generally only keeps track of free blocks, not used blocks. Also, First Fit implementations usually attempt to order the linked list of free blocks (the "free list") in some way that will make parts of the system more effective; our system does not do this.

When a block is freed, we always check whether there are free blocks on either side of it. If so, the block and the free neighbour(s) are combined into one large free block. We know that a free neighbour's other neighbour (on the opposite side) can not also be free, or the two would have been coalesced when the latter of the two became free. This immediate coalescence of neighbouring free blocks allows us to assume that there will never be any adjacent free blocks in memory. That would be a form of external fragmentation, the term used when an allocation system like ours allows free memory to be divided into multiple free blocks, leaving individual blocks insufficient for large allocation requests. Existing systems vary in this regard, with some coalescing all neighbouring free blocks and others only doing so in certain cases. A system may also delay coalescing until some time has passed since both blocks became free.

In our system blocks of any size can be allocated. This is in contrast to existing systems, most of which only allow allocation of certain sizes. Each allocation request is given a memory block of the smallest allowed size equal to or greater than that requested. This saves time for certain components of the system in a way that our system does not benefit from, but it allows internal fragmentation, which is when space within an allocated block goes unused. Note that with our system, a block larger than the minimum size known to be required can still be allocated, in cases where the requesting process can find ways to use the extra space. This would be the case when, as mentioned above, our system is used on the operating system level that organizes memory as a whole. Processes can be given heaps or stacks of arbitrarily large size.

Our system is fairly rare in that BlockInfo's are used throughout as the exclusive handles for allocated blocks, in lieu of the actual starting addresses of blocks. The "allocate()" procedure returns the address of a BlockInfo, and this is the only information the calling process has about the block. Any attempt to dereference the address (which from the program's viewpoint refers to the block itself, but actually points to the BlockInfo) causes the "access()" procedure to be called. access() checks what process allocated the block, and only returns the actual address of the block if it was the calling process. In this way the system provides a basic form of memory protection, which could be used on small or embedded systems where paging or segmentation did not offer memory protection. It would require either hardware support, or a special operating system design whereby only programs that have first been run through a specialized compiler would be allowed to run. The compiler would replace any dereference with a call to access().

System Requirements

There are certain criteria that any system for dynamically-allocated memory must meet. First of all, we note that dynamic allocation of memory is a very basic part of computing and will be required repeatedly by nearly every process running on the system - probably a great number of times per second. For this reason, any code used to implement such a system must be maximally efficient.

Second, we must remember that since the procedures we are designing will provide the very ability to dynamically allocate memory, our code must not itself require dynamically-allocated memory. The C code below makes no calls to malloc().

Another criteria that was treated as necessity, was that the helper procedures in the code could be converted from functions to macros. Functions are typically implemented on systems using a stack data structure for each process, which at all times contains an entry for each partially-executed function of that process. Each such function will have suspended execution because a call to the next-higher function on the stack will have appeared in the source code, with the exception of the function on top of the stack which is the one currently executing. The entry for a function contains its local variables (including parametres) and the address to return to after it has finished executing. Since there is no general way of knowing how many consecutive function calls may be made during a program's execution before any of the functions in the sequence return, it can be seen that the stack could get indefinitely large. On existing systems, a relatively large block (the stack segment) is typically given to each process to be used for the stack. It is usually implemented such that each level of the stack comes immediately after the level before it in memory, requiring no memory allocation; and the segment is large enough that the process will never use it all up unless there is a bug in the code. However it may be desired that we eliminate completely the possibility of a stack overflow in our system, being such an important part of the operating system. It might also be desired that our system work even on operating systems where functions are not implemented via a stack, instead requiring dynamically-allocated memory (which won't be available to our system's process, since dynamic-allocation is what our system implements!). For these reasons, it was ensured that all of our system's helper procedures could be converted to macros.

This only poses difficulty for the "deleteFromFreeBlocks()" and "deleteFromUsedBlocks()" functions, which call themselves recursively. Recursion can introduce the possibility of an indefinite number of function calls. However, in both of these functions the recursive call is the last line that would be executed. Therefore the functions could actually be converted to loops (which could then be defined as macros) using the following pattern:

Function:

void function1 (params...) {
	// variable def's...
	// misc code section #1...
	function1(params...); // Function returns after this, because either no code exists after, "return;" appears immediately after, or code after is for conditional cases that do not apply.
	// misc code section #2...
}

Corresponding loop:

// Variable def's, including additional ones corresponding to the function's params...
while (1) {
	// misc code section #1...
	// code setting variables created for params
	continue;
	// misc code section #2...
	exit;
}

Details of the System

C syntax has been used to illustrate our system, but C is simply the high-level language that was chosen out of many possibilities. We wanted to use some high-level language as opposed to pseudo-code, so that we could show our algorithms more precisely using pointers, etc. Interspersed throughout the code are comments that will provide additional description of how the algorithms work.

To make our code more readable, we define the identifiers 'true' and 'false', and an enumeration type 'boolean', as follows.

#define true 1
#define false 0
enum boolean {
	false,
	true
};

Several global variables are used to keep track of the free and used block linked lists.

struct BlockInfo * headFreeBlockInfo, tailFreeBlockInfo, headUsedBlockInfo, tailUsedBlockInfo;

The BlockInfo type is defined as follows. The "next" and "previous" pointers are used, respectively, to point to the BlockInfos that come before and after this one in the free or used block list (whichever this block happens to belong to). "start" refers to the very first address in memory of the block that this BlockInfo keeps track of. "size" refers to the number of bytes long the block is.

"isNextToBlock" represents whether or not the BlockInfo is to the immediate right of the block itself, which as we will see, is useful knowledge. This variable makes use of the boolean enum. Note that an enum is a larger data type than actually needed to represent a boolean. In an implementation of our system on a 64-bit architecture, we could avoid using an enum. A 64-bit address space far exceeds the amount of memory that systems will have in the foreseeable future, so the 64 bits used for the previous, next, start and size variables would undoubtedly have some redundant zero bits at the beginning, one of which could be used to implement the isNextToBlock boolean.

Finally, we include a member called parentPID for the process identifier of the process that allocated the block. We will assume that the operating system maintains a variable called activeProcess pointing at all times to the Process Control Block of the process being executed, and that the implementation of Process Control Blocks in the operating system includes an unsigned int member called PID for the process identifier. access() and allocate() will make reference to this hypothetical activeProcess variable.

struct BlockInfo {
	struct BlockInfo * previous, next;
	unsigned int start;
	unsigned int size;
	enum boolean isNextToBlock;
	unsigned int parentPID;
};

The "initialize()" function is meant to be called when the system is first assigned the job of handling dynamic allocation for a section of memory. If the system is used, as described above, to manage memory as a whole, the section of memory passed will be the entire section of main memory available to application programs and operating system dynamic allocations. The two arguments passed define the boundaries of the section.

enum boolean initialize (unsigned int start, unsigned int end) {
	struct BlockInfo * BlockInfoOfBlockConstructed = (struct BlockInfo *)(end - sizeof(BlockInfo) + 1);
	if ((start >= end) || (start < 0) || (end < 0)) // In an actual implementation we would also check whether either argument is beyond the actual address space of the system
		return false;
	headUsedBlockInfo = tailUsedBlockInfo = NULL;
	headFreeBlockInfo = tailFreeBlockInfo = BlockInfoOfBlockConstructed;
	BlockInfoOfBlockConstructed->previous = BlockInfoOfBlockConstructed->next = true;
	BlockInfoOfBlockConstructed->isNextToBlock = true;
	BlockInfoOfBlockConstructed->start = start;
	BlockInfoOfBlockConstructed->size = end - start + 1;
	return true;
}

The function which is called when a process attempts to dereference a memory block is called "access()". This is where the potential use of our system as memory protection is implemented. access() will only return the start address of the block if it belongs to the calling process.

void * access (struct BlockInfo * blockToAccess) {
	// We must check that the block belongs to the active process, and only return the start address if it does. Here we assume that the implementation of Process Control Blocks in the operating system includes a member called PID for the process identifier.
	if (blockToAccess->parentPID == activeProcess->PID)
		return blockToAccess->start;
	return NULL;
}

"allocate()" adds a new BlockInfo, pointing to a block of the requested size, to the used block list. If by chance a free block is found of the exact size requested, it's BlockInfo can simply be moved to the used block list. Otherwise a used block will have to be carved out of a larger free block. In this case we will also have to allocate memory for a new BlockInfo object to point to the used block, since the free block's BlockInfo cannot be used for this as it is still pointing to the free block. A second search of the free block list is conducted for this purpose. This search favours finding a BlockInfo that is pointing to itself. This is a special type of BlockInfo that will be discussed shortly. If the free block found is not such a self-pointing BlockInfo, then the BlockInfo will be created by taking space from a regular free block. If the free block is already the exact size we need, then its BlockInfo will no longer be needed (BlockInfos don't have have other BlockInfos pointing to them) and will have to be deleted. A special version of delete() called "deleteFromFreeBlocks()" is used for this.

struct BlockInfo * allocate (unsigned int size) {
struct BlockInfo * currentBlockInfo = headFreeBlockInfo;
struct BlockInfo * BlockInfoOfBlockConstructed;
struct BlockInfo * freeBlockUsed;
if (currentBlockInfo == NULL)
	return NULL;
while (1) {
	if ((currentBlockInfo != currentBlockInfo->start) && (currentBlockInfo->size >= size)) {
		exit;
	} else if (currentBlockInfo->next != NULL) {
		currentBlockInfo = currentBlockInfo->next;
		continue;
	}
	return NULL;
}
if (currentBlockInfo->size == size) {
	// We must set the field of the block that specifies its parent's process identifier.
	currentBlockInfo->parentPID = activeProcess->PID;
	unlinkFromFreeBlocks(currentBlockInfo);
	addToUsedBlocksWithEmptyCheck(currentBlockInfo);
	return currentBlockInfo;
} else {
	freeBlockUsed = currentBlockInfo;
	freeBlockUsed->start += size;
	freeBlockUsed->size -= size;
	// We search for another free block (perhaps what remains of the same one) in which to store the block info of the new block. This time we can eliminate the check of whether the list is empty, as we know from the first time we searched it that it is not.
	currentBlockInfo = headFreeBlockInfo;
	while (1) {
		if (currentBlockInfo == currentBlockInfo->start) {
			currentBlockInfo->start = freeBlockUsed->start - size;
			currentBlockInfo->size = size;
			currentBlockInfo->isNextToBlock = false;
			currentBlockInfo->parentPID = activeProcess->PID;
			unlinkFromFreeBlocks(currentBlockInfo);
			addToUsedBlocksWithEmptyCheck(currentBlockInfo);
			return currentBlockInfo;
		} else if (currentBlockInfo->size >= sizeof(BlockInfo)) {
			BlockInfoOfBlockConstructed = (struct BlockInfo *)(currentBlockInfo->start);
			currentBlockInfo->start += sizeof(BlockInfo);
			currentBlockInfo->size -= sizeof(BlockInfo);
			BlockInfoOfBlockConstructed->start = freeBlockUsed->start - size;
			BlockInfoOfBlockConstructed->size = size;
			BlockInfoOfBlockConstructed->isNextToBlock = (freeBlockUsed == BlockInfoOfBlockConstructed);
			BlockInfoOfBlockConstructed->parentPID = activeProcess->PID;
			addToUsedBlocksWithEmptyCheck(BlockInfoOfBlockConstructed);
			if (currentBlockInfo->size == 0)
				deleteFromFreeBlocks(currentBlockInfo);
			return BlockInfoOfBlockConstructed;
		} else {
			currentBlockInfo = currentBlockInfo->next;
			continue;
		}
		// If we make it to this point in the loop, the free block list did not contain a block big enough to store the block info. We must undo the changes we made to the free block we initially found for the block we were attempting to allocate itself, and return.
		freeBlockUsed->start -= size;
		freeBlockUsed->size += size;
		return NULL;
	}
}
return NULL;
}

The function delete() removes a BlockInfo from the used block list, and adds the space somewhere in the free block list. This function takes account of the fact that blocks with their BlockInfo being directly on their right will probably be common in our system, due to the way allocate() works. As described above, unless allocate() finds a block with the exact size of the requested allocation, it must find a second free block in which to place the BlockInfo of the first allocated block. It can be imagined that this second search will often return what remains of the free block found by the first search. It will have been resized such that the allocated block itself takes up the space that was previously the first portion of it, and its start has been shifted later in memory to make room for the allocated block.

We incorporate a feature into our system looks for this situation. The BlockInfo type includes the member isNextToBlock to represent whether this situation exists between the BlockInfo and its block. If this boolean is true for the block to be deleted, delete() adds the space of the BlockInfo to the region under consideration. Otherwise, it only considers the block itself. After establishing this region, it searches for free blocks on either side of the region, or a free block that is on the left of the region and only separated from it by its own BlockInfo. If each of the block to delete and its free neighbour(s) has its BlockInfo right next to it, we simply use the rightmost BlockInfo (if need be, unlinking it from the used block list and linking it to the free block list), and make the block dimensions include the entire remaining area, including memory that was previously BlockInfo for one of the involved blocks. If only one of the involved blocks has BlockInfo not adjacent to it, we use that BlockInfo for the new block and coalesce the rest of the area. If more than one of the blocks has BlockInfo not adjacent to it, then things become more complicated. We use one of the non-adjacent BlockInfos, and the other(s) must be freed, ie. the memory taken up by the BlockInfo objects themselves must be added somewhere in the free block list. Note that this is different from deleting a block, which will always have a corresponding BlockInfo pointing to it. Deleting a BlockInfo has unique challenges. The functions deleteFromFreeBlocks() and deleteFromUsedBlocks() are used for this purpose.

These functions work much like delete(), except that BlockInfo objects don't have other BlockInfo objects pointing to them. In the case where free neighbours are found, the BlockInfo of one of the neighbours can be used to point to the coalesced block (note that if their are two free neighbours and neither have their BlockInfo right next to them, only one of their BlockInfos will be needed and the other will have to be deleted by a recursive call). If there are no free neighbours, the BlockInfo is made to refer to itself. This is the special situation that was referred to in the description of allocate(). BlockInfos that point to themselves are available for use, and allocate() will use them to point to newly-allocated blocks if it has to. One disadvantage of such BlockInfos is that they represent the one way in which external fragmentation is inevitable in our system.

Note that a similar situation to that described above, in which a block's BlockInfo is directly on its left, can happen in our system. We do not check for this situation and it will not cause problems. Likewise, situations can arise where a block's BlockInfo is directly on its right but this is not reported by isNextToBlock. This will not cause a problem in our system either.

enum boolean delete (struct BlockInfo * blockToDelete) {
struct BlockInfo * currentBlockInfo = headUsedBlockInfo;
unsigned int rightmostAddress, rightmostAddressOfCurrent;
struct BlockInfo * leftNeighbour = NULL;
struct BlockInfo * rightNeighbour = NULL;
enum boolean leftNeighbourFound = false;
enum boolean rightNeighbourFound = false;
if ((blockToDelete == NULL) || (headUsedBlockInfo == NULL))
	return false;
// We must search the used block list for the BlockInfo object passed, to ensure it exists.
while (1) {
	if (currentBlockInfo == blockToDelete) {
		// When we find the matching BlockInfo object, we must confirm that the process it belongs to is the same process that called this delete function.
		if (currentBlockInfo->parentPID != activeProcess->PID)
			return false;
		exit;
	} else if (currentBlockInfo->next != NULL) {
		currentBlockInfo = currentBlockInfo->next;
		continue;
	}
	return false;
}
// Then we search for neighbouring free blocks:
currentBlockInfo = headFreeBlockInfo;
if (currentBlockInfo == NULL) {
	unlinkFromUsedBlocks(blockToDelete);
	addToFreeBlocksWithEmptyCheck(blockToDelete);
	return true;
}
rightmostAddress = (blockToDelete->isNextToBlock)? (unsigned int)&blockToDelete + sizeof(BlockInfo) - 1 : blockToDelete->start + blockToDelete->size - 1;
do {
	if (!leftNeighbourFound) {
		if (currentBlockInfo->isNextToBlock)
			rightmostAddressOfCurrent = (unsigned int)¤tBlockInfo + sizeof(BlockInfo) - 1;
		else
			rightmostAddressOfCurrent = currentBlockInfo->start + currentBlockInfo->size - 1;
		if (rightmostAddressOfCurrent == (blockToDelete->start - 1)) {
			leftNeighbourFound = true;
			leftNeighbour = currentBlockInfo;
			if (rightNeighbourFound)
				exit;
			currentBlockInfo = currentBlockInfo->next;
			continue;
		}
	}
	if (!rightNeighbourFound) {
		if ((currentBlockInfo->start) == rightmostAddress) {
			rightNeighbourFound = true;
			rightNeighbour = currentBlockInfo;
			if (leftNeighbourFound)
				exit;
		}
	}
	currentBlockInfo = currentBlockInfo->next;
} while (currentBlockInfo != NULL);

// Then we remove the block from the used block list and add it to the free block list, which may include coalescing with neighbouring free blocks.

/**************************************************************************************************************
Note that in an analysis of this algorithm, all conditional statements in the following block that evaluate the expressions leftNeighbourFound, rightNeighbourFound, blockToDelete->isNextToBlock and leftNeighbour->isNextToBlock could be left out. These expressions are already evaluated in earlier code, so in an actual implementation the code handling the various cases below could be moved up. For this to work, all code in between the initial evaluation of an expression and the evaluation being eliminated, would also have to be moved up, creating a duplicate copy of it. The pattern this follows is illustrated below:
Unoptimized version:
if (condition1) {
	// misc code section #1...
// misc code section #2...
if (condition1)
	// misc code section #3...

Optimized version with 2nd evaluation of condition1 eliminated:
if (condition1) {
	// misc code section #1...
	// misc code section #2...
	// misc code section #3...
} else {
	// misc code section #2...
}

This is only the most basic pattern that would be followed. The actual optimization of the following code would be further complicated by the fact that most of the earlier evaluations of the expressions occur within the loop that finds neighbouring free blocks. In cases where the loop is expected to proceed after the evaluation is handled, the code added to the blocks handling outcomes of the evaluation must complete all tasks that completion of the loop would have carried out, as well as tasks carried out after the loop but before the code below. After this the code moved up from below will appear, as well as all remaining tasks in the function. The function then returns. This is as per the following pattern:
Assume condition1 = whether or not the code in the loop still cares about condition2
Unoptimized version:
condition1 = true;
do {
	// misc code section #1...
	if (condition1) {
		if (condition2) {
			condition1 = false;
			// misc code section #2...
		}
	}
	// misc code section #3...
	linkedListPointer1 = linkedListedPointer1->next;
} while (linkedListedPointer1 != NULL);
// misc code section #4...
if (condition2)
	// misc code section #5...
// misc code section #6... (rest of function)

Optimized version:
do {
	// misc code section #1...
	if (condition2) {
		// misc code section #2...
		// misc code section #3...
		linkedListPointer1 = linkedListedPointer1->next;
		do {
			// misc code section #1...
			// misc code section #3...
			linkedListPointer1 = linkedListedPointer1->next;
		} while (linkedListedPointer1 != NULL);
		// misc code section #4...
		// misc code section #5...
		// misc code section #6...
		return;
	}
	// misc code section #3...
	linkedListPointer1 = linkedListedPointer1->next;
} while (linkedListedPointer1 != NULL);
// misc code section #4...
// misc code section #6...
***************************************************************************************************************/

if (leftNeighbourFound) {
	// Both a left and right neighbour found:
	if (rightNeighbourFound) {
		if (blockToDelete->isNextToBlock) {
			if (leftNeighbour->isNextToBlock) {
				// Left neighbour, block we're deleting, and right neighbour all adjacent to their block infos (note this could be combined with the "else" case for optimization):
				if (rightNeighbour->isNextToBlock) {
					// We must generate block info for the new free block being created by combining the 3 blocks.
					// We will store the block info in the location currently occupied by the right neighbour's block info.
					rightNeighbour->start = leftNeighbour->start;
					// For the size of the new block, we add the size of each component going into it, from left to right:
					rightNeighbour->size = leftNeighbour->size + sizeof(BlockInfo) + blockToDelete->size + sizeof(BlockInfo) + rightNeighbour->size;
					// Then we un-link the left neighbour from the free block list, and the block we're deleting from the used block list:
					unlinkFromFreeBlocks(leftNeighbour);
					unlinkFromUsedBlocks(blockToDelete);
				}
				// Left neighbour and block we're deleting are adjacent to their block infos, right neighbour points to self.
				else if (rightNeighbour->start == (unsigned int)rightNeighbour) {
					rightNeighbour->start = leftNeighbour->start;
					rightNeighbour->size = leftNeighbour->size + sizeof(BlockInfo) + blockToDelete->size + sizeof(BlockInfo);
					rightNeighbour->isNextToBlock = true;
					unlinkFromFreeBlocks(leftNeighbour);
					unlinkFromUsedBlocks(blockToDelete);
				}
				// Left neighbour and block we're deleting are adjacent to their block infos:
				else {
					rightNeighbour->start = leftNeighbour->start;
					rightNeighbour->size = leftNeighbour->size + sizeof(BlockInfo) + blockToDelete->size + sizeof(BlockInfo) + rightNeighbour->size;
					unlinkFromFreeBlocks(leftNeighbour);
					unlinkFromUsedBlocks(blockToDelete);
				}
			}
			else if (leftNeighbour->start == (unsigned int)leftNeighbour) {
				// Left neighbour points to self, block we're deleting and right neighbour are adjacent to block infos (note this could be combined with the "else" case for optimization):
				if (rightNeighbour->isNextToBlock) {
					rightNeighbour->start = leftNeighbour->start;
					rightNeighbour->size = sizeof(BlockInfo) + blockToDelete->size + sizeof(BlockInfo) + rightNeighbour->size;
					unlinkFromFreeBlocks(leftNeighbour);
					unlinkFromUsedBlocks(blockToDelete);
				}
				// Left neighbour points to self, block we're deleting is adjacent to block info, and right neighbour points to self:
				else if (rightNeighbour->start == (unsigned int)rightNeighbour) {
					rightNeighbour->start = leftNeighbour->start;
					rightNeighbour->size = sizeof(BlockInfo) + blockToDelete->size + sizeof(BlockInfo);
					rightNeighbour->isNextToBlock = true;
					unlinkFromFreeBlocks(leftNeighbour);
					unlinkFromUsedBlocks(blockToDelete);
				}
				// Left neighbour points to self, block we're deleting is adjacent to block info:
				else {
					rightNeighbour->start = leftNeighbour->start;
					rightNeighbour->size = sizeof(BlockInfo) + blockToDelete->size + sizeof(BlockInfo) + rightNeighbour->size;
					unlinkFromFreeBlocks(leftNeighbour);
					unlinkFromUsedBlocks(blockToDelete);
				}
			}
			else {
				// Block we're deleting and right neighbour are adjacent to block infos:
				if (rightNeighbour->isNextToBlock) {
					leftNeighbour->size = leftNeighbour->size + blockToDelete->size + sizeof(BlockInfo) + rightNeighbour->size + sizeof(BlockInfo);
					unlinkFromFreeBlocks(rightNeighbour);
					unlinkFromUsedBlocks(blockToDelete);
				}
				// Block we're deleting is adjacent to block info, and right neighbour points to self:
				else if (rightNeighbour->start == (unsigned int)rightNeighbour) {
					leftNeighbour->size = leftNeighbour->size + blockToDelete->size + sizeof(BlockInfo) + sizeof(BlockInfo);
					unlinkFromFreeBlocks(rightNeighbour);
					unlinkFromUsedBlocks(blockToDelete);
				}
				// Block we're deleting is adjacent to block info:
				else {
					rightNeighbour->start = leftNeighbour->start;
					rightNeighbour->size = leftNeighbour->size + blockToDelete->size + sizeof(BlockInfo) + rightNeighbour->size;
					// These 2 lines can change order:
					deleteFromFreeBlocks(leftNeighbour);
					unlinkFromUsedBlocks(blockToDelete);
				}
			}
		} else {
			if (leftNeighbour->isNextToBlock) {
				// Left neighbour and right neighbour are adjacent to their block infos.
				if (rightNeighbour->isNextToBlock) {
					blockToDelete->start = leftNeighbour->start;
					blockToDelete->size = leftNeighbour->size + sizeof(BlockInfo) + blockToDelete->size + rightNeighbour->size + sizeof(BlockInfo);
					unlinkFromUsedBlocks(blockToDelete);
					addToFreeBlocks(blockToDelete); // We call this and not addToFreeBlocksWithEmptyCheck because we know that the left/right neighbours still exist in the free blocks list.
					unlinkFromFreeBlocks(leftNeighbour);
					unlinkFromFreeBlocks(rightNeighbour);
				}
				// Left neighbour is adjacent to block info, right neighbour points to self.
				else if (rightNeighbour->start == (unsigned int)rightNeighbour) {
					blockToDelete->start = leftNeighbour->start;
					blockToDelete->size = leftNeighbour->size + sizeof(BlockInfo) + blockToDelete->size + sizeof(BlockInfo);
					unlinkFromUsedBlocks(blockToDelete);
					addToFreeBlocks(blockToDelete); // We call this and not addToFreeBlocksWithEmptyCheck because we know that the left/right neighbours still exist in the free blocks list.
					unlinkFromFreeBlocks(leftNeighbour);
					unlinkFromFreeBlocks(rightNeighbour);
				}
				// Left neighbour adjacent to its block info:
				else {
					rightNeighbour->start = leftNeighbour->start;
					rightNeighbour->size = leftNeighbour->size + sizeof(BlockInfo) + blockToDelete->size + rightNeighbour->size;
					// These 2 lines must remain in this order:
					unlinkFromFreeBlocks(leftNeighbour);
					deleteFromUsedBlocks(blockToDelete);
				}
			}
			else if (leftNeighbour->start == (unsigned int)leftNeighbour) {
				// Left neighbour points to self and right neighbour is adjacent to block info:
				if (rightNeighbour->isNextToBlock) {
					blockToDelete->start = leftNeighbour->start;
					blockToDelete->size = sizeof(BlockInfo) + blockToDelete->size + rightNeighbour->size + sizeof(BlockInfo);
					unlinkFromUsedBlocks(blockToDelete);
					addToFreeBlocks(blockToDelete); // We call this and not addToFreeBlocksWithEmptyCheck because we know that the left/right neighbours still exist in the free blocks list.
					unlinkFromFreeBlocks(leftNeighbour);
					unlinkFromFreeBlocks(rightNeighbour);
				}
				// Left neighbour and right neighbour point to self:
				else if (rightNeighbour->start == (unsigned int)rightNeighbour) {
					blockToDelete->start = leftNeighbour->start;
					blockToDelete->size = sizeof(BlockInfo) + blockToDelete->size + sizeof(BlockInfo);
					unlinkFromUsedBlocks(blockToDelete);
					addToFreeBlocks(blockToDelete); // We call this and not addToFreeBlocksWithEmptyCheck because we know that the left/right neighbours still exist in the free blocks list.
					unlinkFromFreeBlocks(leftNeighbour);
					unlinkFromFreeBlocks(rightNeighbour);
				}
				// Left neighbour points to self:
				else {
					rightNeighbour->start = leftNeighbour->start;
					rightNeighbour->size = sizeof(BlockInfo) + blockToDelete->size + rightNeighbour->size;
					// These 2 lines must remain in this order:
					unlinkFromFreeBlocks(leftNeighbour);
					deleteFromUsedBlocks(blockToDelete);
				}
			}
			else {
				// Right neighbour is adjacent to block info:
				if (rightNeighbour->isNextToBlock) {
					leftNeighbour->size = leftNeighbour->size + blockToDelete->size + rightNeighbour->size + sizeof(BlockInfo);
					// These 2 lines must remain in this order:
					unlinkFromFreeBlocks(rightNeighbour);
					deleteFromUsedBlocks(blockToDelete);
				}
				// Right neighbour points to self:
				else if (rightNeighbour->start == (unsigned int)rightNeighbour) {
					leftNeighbour->size = leftNeighbour->size + blockToDelete->size + sizeof(BlockInfo);
					// These 2 lines must remain in this order:
					unlinkFromFreeBlocks(rightNeighbour);
					deleteFromUsedBlocks(blockToDelete);
				}
				// None of the 3 blocks are adjacent to block info or point to self:
				else {
					leftNeighbour->size = leftNeighbour->size + blockToDelete->size + rightNeighbour->size;
					// These 2 lines must remain in this order:
					deleteFromFreeBlocks(rightNeighbour);
					deleteFromUsedBlocks(blockToDelete);
				}
			}
		}
	}
	// Only a left neighbour found:
	else {
		if (blockToDelete->isNextToBlock) {
			// Left neighbour and block we're deleting are adjacent to block infos:
			if (leftNeighbour->isNextToBlock) {
				blockToDelete->start = leftNeighbour->start;
				blockToDelete->size = leftNeighbour->size + sizeof(BlockInfo) + blockToDelete->size;
				unlinkFromUsedBlocks(blockToDelete);
				addToFreeBlocks(blockToDelete); // We call this and not addToFreeBlocksWithEmptyCheck because we know that the left neighbour still exists in the free blocks list.
				unlinkFromFreeBlocks(leftNeighbour);
			}
			// Left neighbour points to self and block we're deleting is adjacent to block info:
			else if (leftNeighbour->start == (unsigned int)leftNeighbour) {
				blockToDelete->start = leftNeighbour->start;
				blockToDelete->size = sizeof(BlockInfo) + blockToDelete->size;
				unlinkFromUsedBlocks(blockToDelete);
				addToFreeBlocks(blockToDelete); // We call this and not addToFreeBlocksWithEmptyCheck because we know that the left neighbour still exists in the free blocks list.
				unlinkFromFreeBlocks(leftNeighbour);
			}
			// Block we're deleting is adjacent to block info:
			else {
				leftNeighbour->size = leftNeighbour->size + blockToDelete->size + sizeof(BlockInfo);
				unlinkFromUsedBlocks(blockToDelete);
			}
		} else {
			// Left neighbour is adjacent to block info:
			if (leftNeighbour->isNextToBlock) {
				blockToDelete->start = leftNeighbour->start;
				blockToDelete->size = leftNeighbour->size + sizeof(BlockInfo) + blockToDelete->size;
				unlinkFromUsedBlocks(blockToDelete);
				addToFreeBlocks(blockToDelete); // We call this and not addToFreeBlocksWithEmptyCheck because we know that the left neighbour still exists in the free blocks list.
				unlinkFromFreeBlocks(leftNeighbour);
			}
			// Left neighbour points to self:
			else if (leftNeighbour->start == (unsigned int)leftNeighbour) {
				blockToDelete->start = leftNeighbour->start;
				blockToDelete->size = sizeof(BlockInfo) + blockToDelete->size;
				unlinkFromUsedBlocks(blockToDelete);
				addToFreeBlocks(blockToDelete); // We call this and not addToFreeBlocksWithEmptyCheck because we know that the left neighbour still exists in the free blocks list.
				unlinkFromFreeBlocks(leftNeighbour);
			}
			// Neither neighbour nor block we're deleting are adjacent to block info or point to self:
			else {
				leftNeighbour->size = leftNeighbour->size + blockToDelete->size;
				deleteFromUsedBlocks(blockToDelete);
			}
		}
	}
} else {
	// Only a right neighbour found:
	if (rightNeighbourFound) {
		if (blockToDelete->isNextToBlock) {
			// Block we're deleting and right neighbour are adjacent to block infos (note this could be combined with the "else" case for optimization):
			if (rightNeighbour->isNextToBlock) {
				rightNeighbour->start = blockToDelete->start;
				rightNeighbour->size = blockToDelete->size + sizeof(BlockInfo) + rightNeighbour->size;
				unlinkFromUsedBlocks(blockToDelete);
			}
			// Block we're deleting is adjacent to block info and right neighbour points to self:
			else if (rightNeighbour->start == (unsigned int)rightNeighbour) {
				rightNeighbour->start = blockToDelete->start;
				rightNeighbour->size = blockToDelete->size + sizeof(BlockInfo);
				rightNeighbour->isNextToBlock = true;
				unlinkFromUsedBlocks(blockToDelete);
			}
			// Block we're deleting is adjacent to block info:
			else {
				rightNeighbour->start = blockToDelete->start;
				rightNeighbour->size = blockToDelete->size + sizeof(BlockInfo) + rightNeighbour->size;
				unlinkFromUsedBlocks(blockToDelete);
			}
		} else {
			// Right neighbour is adjacent to block info:
			if (rightNeighbour->isNextToBlock) {
				blockToDelete->size = blockToDelete->size + rightNeighbour->size + sizeof(BlockInfo);
				unlinkFromUsedBlocks(blockToDelete);
				addToFreeBlocks(blockToDelete); // We call this and not addToFreeBlocksWithEmptyCheck because we know that the right neighbour still exists in the free blocks list.
				unlinkFromFreeBlocks(rightNeighbour);
			}
			// Right neighbour points to self:
			else if (rightNeighbour->start == (unsigned int)rightNeighbour) {
				blockToDelete->size = blockToDelete->size + sizeof(BlockInfo);
				unlinkFromUsedBlocks(blockToDelete);
				addToFreeBlocks(blockToDelete); // We call this and not addToFreeBlocksWithEmptyCheck because we know that the right neighbour still exists in the free blocks list.
				unlinkFromFreeBlocks(rightNeighbour);
			}
			// Neither neighbour nor block we're deleting are adjacent to block info or point to self:
			else {
				blockToDelete->size = blockToDelete->size + rightNeighbour->size;
				unlinkFromUsedBlocks(blockToDelete);
				addToFreeBlocks(blockToDelete); // We call this and not addToFreeBlocksWithEmptyCheck because we know that the right neighbour still exists in the free blocks list.
				deleteFromFreeBlocks(rightNeighbour);
			}
		}
	}
	// Neither a left nor right neighbour found:
	else {
		unlinkFromUsedBlocks(blockToDelete);
		addToFreeBlocksWithEmptyCheck(blockToDelete);
	}
return true;
}
}
void deleteFromFreeBlocks(struct BlockInfo * blockToDelete) {
struct BlockInfo * currentBlockInfo = headFreeBlockInfo;
unsigned int rightmostAddress, rightmostAddressOfCurrent;
struct BlockInfo * leftNeighbour = NULL;
struct BlockInfo * rightNeighbour = NULL;
enum boolean leftNeighbourFound = false;
enum boolean rightNeighbourFound = false;
// Note that we eliminate the check for whether or not the arg is NULL or the block list is empty, as was done in delete(). This function is only ever called by the operating system so we can ensure this will never be the case.
// We must search the free block list for the BlockInfo object passed.
while (1) {
	if (currentBlockInfo == blockToDelete)
		// We can also eliminate the check for whether or not the arg's parent process is the active process.
		exit;
	// Additionally, we can eliminate the check for whether this loop has gone past the last block in the list, since we can ensure that no input will make it do so.
	currentBlockInfo = currentBlockInfo->next;
}
// Then we search for neighbouring free blocks:
currentBlockInfo = headFreeBlockInfo;
// We eliminate the check for whether the free block list is empty, since any time this function is called, delete() has already ran and created a free block.
do {
	if (!leftNeighbourFound) {
		if (currentBlockInfo->isNextToBlock)
			rightmostAddressOfCurrent = (unsigned int)¤tBlockInfo + sizeof(BlockInfo) - 1;
		else
			rightmostAddressOfCurrent = currentBlockInfo->start + currentBlockInfo->size - 1;
		if (rightmostAddressOfCurrent == (blockToDelete->start - 1)) {
			leftNeighbourFound = true;
			leftNeighbour = currentBlockInfo;
			if (rightNeighbourFound)
				exit;
			currentBlockInfo = currentBlockInfo->next;
			continue;
		}
	}
	if (!rightNeighbourFound) {
		if ((currentBlockInfo->start) == (blockToDelete->start + sizeof(BlockInfo) - 1)) {
			rightNeighbourFound = true;
			rightNeighbour = currentBlockInfo;
			if (leftNeighbourFound)
				exit;
		}
	}
	currentBlockInfo = currentBlockInfo->next;
} while (currentBlockInfo != NULL);

// Then we add the block to the free block list, which may include coalescing with neighbouring free blocks.
// As with delete(), conditional statements could be eliminated.

if (leftNeighbourFound) {
	// Both a left and right neighbour found:
	if (rightNeighbourFound) {
		if (leftNeighbour->isNextToBlock) {
			// Left neighbour and right neighbour are adjacent to their block infos (note this could be combined with the "else" case for optimization):
			if (rightNeighbour->isNextToBlock) {
				// We must generate block info for the new free block being created by combining the 3 blocks.
				// We will store the block info in the location currently occupied by the right neighbour's block info.
				rightNeighbour->start = leftNeighbour->start;
				// For the size of the new block, we add the size of each component going into it, from left to right:
				rightNeighbour->size = leftNeighbour->size + sizeof(BlockInfo) + sizeof(BlockInfo) + rightNeighbour->size;
				// Then we un-link the left neighbour from the free block list:
				unlinkFromFreeBlocks(leftNeighbour);
				unlinkFromFreeBlocks(blockToDelete);
			}
			// Left neighbour adjacent to block info, right neighbour points to self.
			else if (rightNeighbour->start == (unsigned int)rightNeighbour) {
				rightNeighbour->start = leftNeighbour->start;
				rightNeighbour->size = leftNeighbour->size + sizeof(BlockInfo) + sizeof(BlockInfo);
				rightNeighbour->isNextToBlock = true;
				unlinkFromFreeBlocks(leftNeighbour);
				unlinkFromFreeBlocks(blockToDelete);
			}
			// Left neighbour adjacent to block info:
			else {
				rightNeighbour->start = leftNeighbour->start;
				rightNeighbour->size = leftNeighbour->size + sizeof(BlockInfo) + sizeof(BlockInfo) + rightNeighbour->size;
				unlinkFromFreeBlocks(leftNeighbour);
				unlinkFromFreeBlocks(blockToDelete);
			}
		}
		else if (leftNeighbour->start == (unsigned int)leftNeighbour) {
			// Left neighbour points to self, right neighbour adjacent to block info (note this could be combined with the "else" case for optimization):
			if (rightNeighbour->isNextToBlock) {
				rightNeighbour->start = leftNeighbour->start;
				rightNeighbour->size = sizeof(BlockInfo) + sizeof(BlockInfo) + rightNeighbour->size;
				unlinkFromFreeBlocks(leftNeighbour);
				unlinkFromFreeBlocks(blockToDelete);
			}
			// Left neighbour and right neighbour point to self:
			else if (rightNeighbour->start == (unsigned int)rightNeighbour) {
				rightNeighbour->start = leftNeighbour->start;
				rightNeighbour->size = sizeof(BlockInfo) + sizeof(BlockInfo);
				rightNeighbour->isNextToBlock;
				unlinkFromFreeBlocks(leftNeighbour);
				unlinkFromFreeBlocks(blockToDelete);
			}
			// Left neighbour points to self:
			else {
				rightNeighbour->start = leftNeighbour->start;
				rightNeighbour->size = sizeof(BlockInfo) + sizeof(BlockInfo) + rightNeighbour->size;
				unlinkFromFreeBlocks(leftNeighbour);
				unlinkFromFreeBlocks(blockToDelete);
			}
		}
		else {
			// Right neighbour adjacent to block info:
			if (rightNeighbour->isNextToBlock) {
				leftNeighbour->size = leftNeighbour->size + sizeof(BlockInfo) + rightNeighbour->size + sizeof(BlockInfo);
				unlinkFromFreeBlocks(rightNeighbour);
				unlinkFromFreeBlocks(blockToDelete);
			}
			// Right neighbour points to self:
			else if (rightNeighbour->start == (unsigned int)rightNeighbour) {
				leftNeighbour->size = leftNeighbour->size + sizeof(BlockInfo) + sizeof(BlockInfo);
				unlinkFromFreeBlocks(rightNeighbour);
				unlinkFromFreeBlocks(blockToDelete);
			}
			// Neither left neighbour nor right neighbour is adjacent to block info or points to self:
			else {
				rightNeighbour->start = leftNeighbour->start;
				rightNeighbour->size = leftNeighbour->size + sizeof(BlockInfo) + rightNeighbour->size;
				// These 2 lines must remain in this order:
				unlinkFromFreeBlocks(blockToDelete);
				deleteFromFreeBlocks(leftNeighbour);
			}
		}
	}
	// Only a left neighbour found:
	else {
		// Left neighbour adjacent to block info:
		if (leftNeighbour->isNextToBlock) {
			blockToDelete->start = leftNeighbour->start;
			blockToDelete->size = leftNeighbour->size + sizeof(BlockInfo);
			blockToDelete->isNextToBlock = true;
			unlinkFromFreeBlocks(leftNeighbour);
		}
		// Left neighbour points to self:
		else if (leftNeighbour->start == (unsigned int)leftNeighbour) {
			blockToDelete->start = leftNeighbour->start;
			blockToDelete->size = sizeof(BlockInfo);
			blockToDelete->isNextToBlock = true;
			unlinkFromFreeBlocks(leftNeighbour);
		}
		// Left neighbour is not adjacent to block info or pointing to self:
		else {
			leftNeighbour->size = leftNeighbour->size + sizeof(BlockInfo);
			unlinkFromFreeBlocks(blockToDelete);
		}
	}
} else {
	// Only a right neighbour found:
	if (rightNeighbourFound) {
			// Right neighbour adjacent to block info (note this could be combined with the "else" case for optimization):
			if (rightNeighbour->isNextToBlock) {
				rightNeighbour->start = blockToDelete->start;
				rightNeighbour->size = sizeof(BlockInfo) + rightNeighbour->size;
				unlinkFromFreeBlocks(blockToDelete);
			}
			// Right neighbour points to self:
			else if (rightNeighbour->start == (unsigned int)rightNeighbour) {
				rightNeighbour->start = blockToDelete->start;
				rightNeighbour->size = sizeof(BlockInfo) + sizeof(BlockInfo);
				rightNeighbour->isNextToBlock = true;
				unlinkFromFreeBlocks(blockToDelete);
			}
			// Right neighbour is neither adjacent to block info nor pointing to self:
			else {
				rightNeighbour->start = blockToDelete->start;
				rightNeighbour->size = sizeof(BlockInfo) + rightNeighbour->size;
				unlinkFromFreeBlocks(blockToDelete);
			}
	}
	// Neither a left nor right neighbour found:
	else {
		blockToDelete->start = (unsigned int)blockToDelete;
		blockToDelete->size = sizeof(BlockInfo);
		blockToDelete->isNextToBlock = false;
	}
}
}
void deleteFromUsedBlocks(struct BlockInfo * blockToDelete) {
struct BlockInfo * currentBlockInfo = headUsedBlockInfo;
unsigned int rightmostAddress, rightmostAddressOfCurrent;
struct BlockInfo * leftNeighbour = NULL;
struct BlockInfo * rightNeighbour = NULL;
enum boolean leftNeighbourFound = false;
enum boolean rightNeighbourFound = false;
// Note that we eliminate the check for whether or not the arg is NULL or the list is empty, as was done in delete(). This function is only ever called by the operating system so we can ensure this will never be the case.
// We must search the used block list for the BlockInfo object passed.
while (1) {
	if (currentBlockInfo == blockToDelete)
		// We can also eliminate the check for whether or not the arg's parent process is the active process.
		exit;
	// Additionally, we can eliminate the check for whether this loop has gone past the last block in the list, since we can ensure that no input will make it do so.
	currentBlockInfo = currentBlockInfo->next;
}
// Then we search for neighbouring free blocks:
currentBlockInfo = headFreeBlockInfo;
// We eliminate the check for whether the free block list is empty, since any time this function is called, delete() has already ran and created a free block.
do {
	if (!leftNeighbourFound) {
		if (currentBlockInfo->isNextToBlock)
			rightmostAddressOfCurrent = (unsigned int)¤tBlockInfo + sizeof(BlockInfo) - 1;
		else
			rightmostAddressOfCurrent = currentBlockInfo->start + currentBlockInfo->size - 1;
		if (rightmostAddressOfCurrent == (blockToDelete->start - 1)) {
			leftNeighbourFound = true;
			leftNeighbour = currentBlockInfo;
			if (rightNeighbourFound)
				exit;
			currentBlockInfo = currentBlockInfo->next;
			continue;
		}
	}
	if (!rightNeighbourFound) {
		if ((currentBlockInfo->start) == (blockToDelete->start + sizeof(BlockInfo) - 1)) {
			rightNeighbourFound = true;
			rightNeighbour = currentBlockInfo;
			if (leftNeighbourFound)
				exit;
		}
	}
	currentBlockInfo = currentBlockInfo->next;
} while (currentBlockInfo != NULL);

// Then we add the block to the free block list, which may include coalescing with neighbouring free blocks.
// As with delete(), conditional statements could be eliminated.

if (leftNeighbourFound) {
	// Both a left and right neighbour found:
	if (rightNeighbourFound) {
		if (leftNeighbour->isNextToBlock) {
			// Left neighbour and right neighbour are adjacent to their block infos (note this could be combined with the "else" case for optimization):
			if (rightNeighbour->isNextToBlock) {
				// We must generate block info for the new free block being created by combining the 3 blocks.
				// We will store the block info in the location currently occupied by the right neighbour's block info.
				rightNeighbour->start = leftNeighbour->start;
				// For the size of the new block, we add the size of each component going into it, from left to right:
				rightNeighbour->size = leftNeighbour->size + sizeof(BlockInfo) + sizeof(BlockInfo) + rightNeighbour->size;
				// Then we un-link the left neighbour from the free block list:
				unlinkFromFreeBlocks(leftNeighbour);
				unlinkFromUsedBlocks(blockToDelete);
			}
			// Left neighbour adjacent to block info, right neighbour points to self.
			else if (rightNeighbour->start == (unsigned int)rightNeighbour) {
				rightNeighbour->start = leftNeighbour->start;
				rightNeighbour->size = leftNeighbour->size + sizeof(BlockInfo) + sizeof(BlockInfo);
				rightNeighbour->isNextToBlock = true;
				unlinkFromFreeBlocks(leftNeighbour);
				unlinkFromUsedBlocks(blockToDelete);
			}
			// Left neighbour adjacent to block info:
			else {
				rightNeighbour->start = leftNeighbour->start;
				rightNeighbour->size = leftNeighbour->size + sizeof(BlockInfo) + sizeof(BlockInfo) + rightNeighbour->size;
				unlinkFromFreeBlocks(leftNeighbour);
				unlinkFromUsedBlocks(blockToDelete);
			}
		}
		else if (leftNeighbour->start == (unsigned int)leftNeighbour) {
			// Left neighbour points to self, right neighbour adjacent to block info (note this could be combined with the "else" case for optimization):
			if (rightNeighbour->isNextToBlock) {
				rightNeighbour->start = leftNeighbour->start;
				rightNeighbour->size = sizeof(BlockInfo) + sizeof(BlockInfo) + rightNeighbour->size;
				unlinkFromFreeBlocks(leftNeighbour);
				unlinkFromUsedBlocks(blockToDelete);
			}
			// Left neighbour and right neighbour point to self:
			else if (rightNeighbour->start == (unsigned int)rightNeighbour) {
				rightNeighbour->start = leftNeighbour->start;
				rightNeighbour->size = sizeof(BlockInfo) + sizeof(BlockInfo);
				rightNeighbour->isNextToBlock = true;
				unlinkFromFreeBlocks(leftNeighbour);
				unlinkFromUsedBlocks(blockToDelete);
			}
			// Left neighbour points to self:
			else {
				rightNeighbour->start = leftNeighbour->start;
				rightNeighbour->size = sizeof(BlockInfo) + sizeof(BlockInfo) + rightNeighbour->size;
				unlinkFromFreeBlocks(leftNeighbour);
				unlinkFromUsedBlocks(blockToDelete);
			}
		}
		else {
			// Right neighbour adjacent to block info:
			if (rightNeighbour->isNextToBlock) {
				leftNeighbour->size = leftNeighbour->size + sizeof(BlockInfo) + rightNeighbour->size + sizeof(BlockInfo);
				unlinkFromFreeBlocks(rightNeighbour);
				unlinkFromUsedBlocks(blockToDelete);
			}
			// Right neighbour points to self:
			else if (rightNeighbour->start == (unsigned int)rightNeighbour) {
				leftNeighbour->size = leftNeighbour->size + sizeof(BlockInfo) + sizeof(BlockInfo);
				unlinkFromFreeBlocks(rightNeighbour);
				unlinkFromUsedBlocks(blockToDelete);
			}
			// Neither left neighbour nor right neighbour is adjacent to block info or points to self:
			else {
				rightNeighbour->start = leftNeighbour->start;
				rightNeighbour->size = leftNeighbour->size + sizeof(BlockInfo) + rightNeighbour->size;
				// These 2 lines must remain in this order:
				unlinkFromUsedBlocks(blockToDelete);
				deleteFromFreeBlocks(leftNeighbour);
			}
		}
	}
	// Only a left neighbour found:
	else {
		// Left neighbour adjacent to block info:
		if (leftNeighbour->isNextToBlock) {
			blockToDelete->start = leftNeighbour->start;
			blockToDelete->size = leftNeighbour->size + sizeof(BlockInfo);
			blockToDelete->isNextToBlock = true;
			unlinkFromUsedBlocks(blockToDelete);
			addToFreeBlocks(blockToDelete); // We call this and not addToFreeBlocksWithEmptyCheck because we know that the left neighbour still exists in the free blocks list.
			unlinkFromFreeBlocks(leftNeighbour);
		}
		// Left neighbour points to self:
		else if (leftNeighbour->start == (unsigned int)leftNeighbour) {
			blockToDelete->start = leftNeighbour->start;
			blockToDelete->size = sizeof(BlockInfo);
			blockToDelete->isNextToBlock = true;
			unlinkFromUsedBlocks(blockToDelete);
			addToFreeBlocks(blockToDelete); // We call this and not addToFreeBlocksWithEmptyCheck because we know that the left neighbour still exists in the free blocks list.
			unlinkFromFreeBlocks(leftNeighbour);
		}
		// Left neighbour is not adjacent to block info or pointing to self:
		else {
			leftNeighbour->size = leftNeighbour->size + sizeof(BlockInfo);
			unlinkFromUsedBlocks(blockToDelete);
		}
	}
} else {
	// Only a right neighbour found:
	if (rightNeighbourFound) {
			// Right neighbour adjacent to block info (note this could be combined with the "else" case for optimization):
			if (rightNeighbour->isNextToBlock) {
				rightNeighbour->start = blockToDelete->start;
				rightNeighbour->size = sizeof(BlockInfo) + rightNeighbour->size;
				unlinkFromUsedBlocks(blockToDelete);
			}
			// Right neighbour points to self:
			else if (rightNeighbour->start == (unsigned int)rightNeighbour) {
				rightNeighbour->start = blockToDelete->start;
				rightNeighbour->size = sizeof(BlockInfo) + sizeof(BlockInfo);
				rightNeighbour->isNextToBlock = true;
				unlinkFromUsedBlocks(blockToDelete);
			}
			// Right neighbour is neither adjacent to block info nor pointing to self:
			else {
				rightNeighbour->start = blockToDelete->start;
				rightNeighbour->size = sizeof(BlockInfo) + rightNeighbour->size;
				unlinkFromUsedBlocks(blockToDelete);
			}
	}
	// Neither a left nor right neighbour found:
	else {
		unlinkFromUsedBlocks(blockToDelete);
		addToFreeBlocksWithEmptyCheck(blockToDelete);
		blockToDelete->isNextToBlock = true;
	}
}
}

There are several helper functions used by allocate() and delete(). Care had to be taken with regard to the order in which these were called. A block must be removed from one list before being added to another.


// This version does not check if the free block list is empty. Only use if you know it is not.
void addToFreeBlocks (Block * blockToFree) {
	tailFreeBlockInfo->next = blockToFree;
	blockToFree->previous = tailFreeBlockInfo;
	blockToFree->next = NULL;
	tailFreeBlockInfo = blockToFree;
}
// This version checks if the free block list is empty.
void addToFreeBlocksWithEmptyCheck (Block * blockToFree) {
	if (tailFreeBlockInfo != NULL)
		tailFreeBlockInfo->next = blockToFree;
	else // otherwise, tailFreeBlockInfo is NULL and therefore so is headFreeBlockInfo.
		headFreeBlockInfo = blockToFree;
	blockToFree->previous = tailFreeBlockInfo;
	blockToFree->next = NULL;
	tailFreeBlockInfo = blockToFree;
}
// This function for adding to the used block list also checks if it is empty.
void addToUsedBlocksWithEmptyCheck (Block * blockToAdd) {
	if (tailUsedBlockInfo != NULL)
		tailUsedBlockInfo->next = blockToAdd;
	else // otherwise, tailUsedBlockInfo is NULL and therefore so is headUsedBlockInfo.
		headUsedBlockInfo = blockToAdd;
	blockToAdd->previous = tailUsedBlockInfo;
	blockToAdd->next = NULL;
	tailUsedBlockInfo = blockToAdd;
}
void unlinkFromUsedBlocks (struct BlockInfo * blockToRemove) {
	if (blockToRemove->previous == NULL) {
		headUsedBlockInfo = blockToRemove->next;
	} else {
		blockToRemove->previous->next = blockToRemove->next;
	}
	if (blockToRemove->next == NULL) {
		tailUsedBlockInfo = blockToRemove->previous;
	} else {
		blockToRemove->next->previous = blockToRemove->previous;
	}
}
void unlinkFromFreeBlocks (struct BlockInfo * blockToRemove) {
	if (blockToRemove->previous == NULL) {
		headFreeBlockInfo = blockToRemove->next;
	} else {
		blockToRemove->previous->next = blockToRemove->next;
	}
	if (blockToRemove->next == NULL) {
		tailFreeBlockInfo = blockToRemove->previous;
	} else {
		blockToRemove->next->previous = blockToRemove->previous;
	}
}
1The heap used for dynamically-allocated memory is not an actual heap data structure. The two uses of the term are unrelated.