/// \file
/// \brief \b [Internal] Memory allocation from a fixed predefined block of memory. Not threadsafe, so have one instance per-thread
///
/// This file is part of RakNet Copyright 2003 Kevin Jenkins.
///
/// Usage of RakNet is subject to the appropriate license agreement.
/// Creative Commons Licensees are subject to the
/// license found at
/// http://creativecommons.org/licenses/by-nc/2.5/
/// Single application licensees are subject to the license found at
/// http://www.jenkinssoftware.com/SingleApplicationLicense.html
/// Custom license users are subject to the terms therein.
/// GPL license users are subject to the GNU General Public
/// License as published by the Free
/// Software Foundation; either version 2 of the License, or (at your
/// option) any later version.

#ifndef __RAKNET_ALLOCATOR_H
#define __RAKNET_ALLOCATOR_H 

#include <assert.h>
#include "Export.h"
#include "NativeTypes.h"

/// file and line are only used if MEMORY_HEAP_TRACK_FILE_AND_LINE is defined. This reduces available memory.
//#define MEMORY_HEAP_TRACK_FILE_AND_LINE

/// If set, asserts when an allocation fails due to out of memory
#define RAKNET_ALLOCATOR_ASSERT_ON_ALLOCATION_FAILURE


/// The namespace DataStructures was only added to avoid compiler errors for commonly named data structures
/// As these data structures are stand-alone, you can use them outside of RakNet for your own projects if you wish.
namespace DataStructures
{
class Allocator
{
public:
	Allocator();
	~Allocator();

	/// Given an address, how many bytes would be skipped to reach the first usable address so that the data returned is aligned
	static uint64_t GetStartingAlignmentOffset(char *startingBlock);

	/// Test it out
	static void UnitTest(DataStructures::Allocator *initializedHeap);

	/// Associate the memory-heap with an externally allocated chunk of memory, which will be overwritten
	/// Use GetMinimumRequiredMemory() to find the minimum value to pass to \a availableBytes for the system to work
	bool Init(char *startingBlock, uint64_t availableBytes );

	/// Allocate \a size bytes
	/// Returns 0 on failure, the block of memory on success
	void *Malloc(uint64_t size);
	void *Malloc(uint64_t size, const char *file, unsigned int line);

	/// Reallocates a previously allocated pointer from Malloc or Realloc
	/// If pointer is NULL, acts the same as Malloc
	/// Returns 0 on failure, the block of memory on success
	void *Realloc(void *pointer, uint64_t size);
	void *Realloc(void *pointer, uint64_t size, const char *file, unsigned int line);

	/// Frees a previously allocated pointer from Malloc or Realloc
	void Free(void *pointer);

	/// For a given pointer, return how many bytes were allocated to that pointer
	unsigned int GetAllocatedBytes(char *pointer) const;
	/// For a given pointer, return what file that pointer was last allocated in. Only valid if MEMORY_HEAP_TRACK_FILE_AND_LINE is defined
	const char* GetFile(char *pointer) const;
	/// For a given pointer, return what line that pointer was last allocated in. Only valid if MEMORY_HEAP_TRACK_FILE_AND_LINE is defined
	unsigned short GetLine(char *pointer) const;

	/// Returns the total number of blocks of size CLUSTER_SIZE used internally
	uint64_t GetTotalClusterCount(void) const;

	/// Prints out a visual display of how memory is used
	/// Number of chars to be printed is roughly proportional to GetTotalClusterCount()
	/// _ means unused
	/// U means used
	/// P means permanent bucket, which is more than half used
	/// p means permanent bucket, which is less than half used
	/// B means transient bucket, which is more than half used
	/// b means transient bucket, which is less than half used
	void SprintfFragmentation(char *out, int wrapAtColumn) const;
	void PrintfFragmentation(void) const;

	/// Returns how many bytes have been returned to the user. This includes padding bytes
	uint64_t GetTotalBytesUsed(void) const;
	uint64_t GetMaxBytesUsed(void) const;

protected:

	// Smallest allocation size
	static const uint64_t CLUSTER_SIZE=32;

	// Don't move the data block if realloc wastes less than this when reallocating smaller
	static const uint64_t REALLOC_WASTE_THRESHHOLD=128;

	// A bucket is a suballocation. The smallest bucket is the smallest suballocation that can be performed.
	// Larger buckets are a multiple of 2 of the smallest bucket, up to half the cluster size
	static const uint64_t SMALLEST_BUCKET=32;

	/// How many bytes to align returned values on.
	/// SMALLEST_BUCKET should be a multiple of this
	static const uint64_t ALIGNMENT_BOUNDARY_IN_BYTES=32;

	// Should have one for SMALLEST_BUCKET, and every multiple of 2 thereof, less than CLUSTER_SIZE
	// 32, 64, 128, 256, 512, 1024, 2048
	static const uint64_t NUM_TYPES_OF_BUCKETS=7;

	// Dedicate at least 1/5th of the available clusters to act as buckets.
	// This memory won't be available for big allocations
	// However, small allocations will come from the buckets first, and avoid fragmenting memory.
	// They also allocate faster
	static const uint64_t INVERSE_BUCKET_PROPORTION_OF_TOTAL_MEMORY=5;

	// Bigger because of extra space due to need to pad
	unsigned int actualBucketSizes[NUM_TYPES_OF_BUCKETS];

	// Each pointer returned to the user is prefixed with this structure
	// Usable size of each bucket is reduced by the size of this structure
	// If the address is less than variableClusterStartAddress, this is in a cluster that is fixed (buckets only)
	// If it is greater than or equal to variableClusterStartAddress, this is in a normal cluster (possibly subdivided)
	struct DataPrefix
	{
		inline void Init(void) {nextFree=0; immediatePrev=0; dataBytes=0; isAllocated=false;
#if defined(MEMORY_HEAP_TRACK_FILE_AND_LINE)
		line=-1;
		file[0]=0;
#endif
		}
		inline void Init(DataPrefix *_next, DataPrefix *_prev, unsigned int _dataBytes) {nextFree=_next; immediatePrev=_prev; dataBytes=_dataBytes; isAllocated=false;
#if defined(MEMORY_HEAP_TRACK_FILE_AND_LINE)
		line=-1;
		file[0]=0;
#endif
		}

		DataPrefix* GetImmediatePrev(void) {return immediatePrev;}
		DataPrefix* GetImmediateNext(void) {return (DataPrefix*) ((char*)this + sizeof(DataPrefix) + dataBytes);}

		// nextFree is the next free block. The linked list is not necessarily adjacent
		// immediatePrev is the immediately previous block. It is immediately adjacent
		DataPrefix *nextFree, *immediatePrev;
		unsigned int dataBytes;
		bool isAllocated;
		
#if defined(MEMORY_HEAP_TRACK_FILE_AND_LINE)
		unsigned short line;
		char file[ALIGNMENT_BOUNDARY_IN_BYTES-sizeof(DataPrefix*)*2-sizeof(unsigned int)-sizeof(unsigned short)-sizeof(bool)];
#endif
	};

	// availableBucketList[0] is linked list of available buckets of size SMALLEST_BUCKET
	// availableBucketList[1] is linked list of available buckets of size SMALLEST_BUCKET<<1
	// etc.
	DataPrefix *availableFixedBucketList[NUM_TYPES_OF_BUCKETS];
	DataPrefix *freeList;

	// Address at which the first page starts
	// Addresses before this are clusters of buckets, suffixed with BucketHeader
	// Addresses after or equal to this are normal clusters, suffixed with ClusterGroup
	char *variableClusterStartAddress;
	char *memoryStart;

	// Total number of clusters of size CLUSTER_SIZE allocated
	uint64_t totalClusters;

	// Total number of bytes allocated to the user
	uint64_t totalBytesUsed, maxBytesUsed;

	DataPrefix *end;

	/// Given a user data block, return the internal prefix
	DataPrefix* PrefixFromUserBlock(void *v) const;

	/// Given a user block, write the file and line to the prefix
	void WriteFileAndLineToUserBlock(char *v, const char *file, unsigned short line);

	void ResetVariables(void);
	bool IsFreeListEmpty(void) const {return freeList==0;}
	char *AllocFromFreeList(uint64_t size);
	unsigned int GetBucketIndex(uint64_t size) const;
	void AddToTotalBytesUsed(uint64_t size);
	void SubtractFromTotalBytesUsed(uint64_t size);
	static uint64_t GetBytesToAddToBaseToAlignTo(uint64_t base, uint64_t boundary);
};
}

#endif