SharedMemory - Use with the Haxe flash.Memory API for fast (shared) ByteArray access.

SharedMemory.hx

package;

import flash.Memory;
import flash.utils.ByteArray;
import flash.utils.Endian;
import flash.Vector;

/**
 * ...
 * @author Mike Almond - https://github.com/mikedotalmond
 *
 */

 /**
  * SharedMemory - Use with the Haxe flash.Memory API for fast ByteArray access.
  *
  * Uses a single ByteArray and allocates chunks of it as needed.
  * @see http://haxe.org/api/flash/Memory
  *
  *
  * Note:
  *
  * SharedMemory only selects the bytearray for manipulation using Memory.select() once.
  * If you're using Memory.select elsewhere - on a different ByteArray - you'll have to
  * call selectMemory() here before reading/writing with the Memory API
  *
  * However, regularly calling Memory.select is not advised if you're concernerd about performance.
  * Have one instance of SharedMemory and use that to allocate all the bytes you need.
  *
  */

@:final enum MemoryDataTypes {
	Double;
	Float;
	Int32;
	UInt16;
	Byte;
}

@:final class SharedMemory {
	
	static var m:SharedMemory = null;
	
	/**
	 * @param	size - The size in Bytes of the underlying SharedMemory ByteArray. This is the maximum size that can allocated in total, by calls to .alloc()
	 * @param	grow - Can the SharedMemory grow as needed [true], or should it never exceed the size you specify [false]
	 * @throws [ReferenceError]
	 * @return The SharedMemory instance
	 */
	public static function initialise(size:Int = Size_1K, grow:Bool=false):SharedMemory {
		if (m == null) m = new SharedMemory(size, grow);
		else throw '[InitialisationError] The static SharedMemory.instance has already been initialised:\n${m.toString()}';
		return m;
	}
	
	
	/**
	 * Access the static SharedMemory instance
	 * @throws [ReferenceError] if not initialised via SharedMemory.initialise beforhand.
	 */
	public static var instance(get_instance, null):SharedMemory;
	static function get_instance() {
		#if debug
		if (m == null) throw '[ReferenceError] Oops! You need to initialise the static SharedMemory instance first! Call SharedMemory.initialise before trying to access SharedMemory.instance';
		#end
		return m;
	}
	
	
	/**
	 * Release everything. You will need to call initialise again to use SharedMemory
	 */
	public static function dispose() {
		if (m != null) {
			
			m.active 		= null;
			m.free 			= null;
			m.occupancy 	= 0;
		
			// deselect
			Memory.select(null);
			
			if (m.bytes != null) {
				m.bytes.length = 0;
				m.bytes = null;
			}
			
			m = null;
		}
	}
	
	
	// -----------
	
	
	static var BlockId					:UInt = 0; // unique id for each MemoryBlock, keeps incrementing as blocks are allocated
	
	public static inline var Size_1K	:Int = 1 << 10; // This is the minimum size -- 0x400 (1024)
	public static inline var Size_2K	:Int = 2 << 10;
	public static inline var Size_4K	:Int = 4 << 10;
	public static inline var Size_8K	:Int = 8 << 10;
	public static inline var Size_16K	:Int = 16 << 10;
	public static inline var Size_32K	:Int = 32 << 10;
	public static inline var Size_64K	:Int = 64 << 10;
	public static inline var Size_128K	:Int = 128 << 10;
	public static inline var Size_256K	:Int = 256 << 10;
	public static inline var Size_512K	:Int = 512 << 10;
	public static inline var Size_1024K	:Int = 1024 << 10;
	
	var active	:Map<Int, MemoryBlock>;
	var free	:Map<Int, MemoryBlock>;
	
	public var grow(default, null)		:Bool;
	public var bytes(default, null)		:ByteArray;
	public var occupancy(default, null)	:Int;
	
	public var waste(get_waste, null)	:Int;
	function get_waste() { return size - occupancy; }
	
	public var size(get_size, null)		:UInt;
	function get_size() { return bytes==null ? 0 : bytes.length; }
	
	public function toString() {
		return '> [SharedMemory]' + ((m != null)
		? (	'\n>> size:${size}, grow:${grow}' +
			'\n>> occupancy:${occupancy}, waste:${waste}' +
			'\n>> activeBlockCount:${Lambda.count(active)}, freeBlockCount:${Lambda.count(free)}'
		) : 'Uninitialised') ;
	}
	
	
	/**
	 * @private
	 * @param	size 	- Number of bytes to allocate initially. The minimum size is 1K (1024 bytes)
	 * @param	grow	- Allows the bytearray to grow if needed.
	 */
	function new(size:Int = Size_1K, grow:Bool = false) {
		
		if (size < Size_1K) {
			throw "Minimum allocation size is 1K - 1024 bytes";
			size = Size_1K;
		}
		
		bytes 			= new ByteArray();
		bytes.endian 	= Endian.LITTLE_ENDIAN; // Note: "The endian property of the selected ByteArray does not affect the[se] Memory functions. They behave as if it is set to Endian.LITTLE_ENDIAN."
		bytes.length 	= size;
		
		occupancy		= 0;
		
		active			= new Map<Int, MemoryBlock>();
		free			= new Map<Int, MemoryBlock>();
		
		this.grow 		=  grow;
		
		selectMemory();
	}
	
	
	/**
	 * You only need to call this before reading/writing if using Memory.select(someOtherByteArray); elsewhere in your code....
	 * That's not ideal though. If possible try to only use one ByteArray and manage it here.
	 */
	public inline function selectMemory() {
		Memory.select(bytes);
	}
	
	
	/**
	 * Get an allocated MemoryBlock
	 * MemoryBlock contains information about a section of the shared bytearray (id, startIndex, length)
	 *
	 * @param	id
	 * @return	MemoryBlock
	 */
	public function get(id:Int):MemoryBlock {
		if (active.exists(id)) return active.get(id);
		else return null;
	}
	
	
	/**
	 *
	 * @param	size	- Size, in bytes, to allocate
	 * @return	id		- The ID for the block of memory allocated, or -1 if there wasn't enough space left to allocate the requested size (when grow==false)
	 */
	public function alloc(size:Int):Int {
		
		var start = getStartIndex(size);
		if (start == -1) return -1; // no space, and no grow?
		
		occupancy += size;
		
		var block = new MemoryBlock(start, size);
		active.set(block.id, block);
		
		return block.id;
	}
	
	
	// shortcuts
	public inline function allocDouble(count:UInt=1):Int return allocType(MemoryDataTypes.Double, count);
	public inline function allocFloat(count:UInt=1):Int return allocType(MemoryDataTypes.Float, count);
	public inline function allocInt32(count:UInt=1):Int return allocType(MemoryDataTypes.Int32, count);
	public inline function allocUInt16(count:UInt=1):Int return allocType(MemoryDataTypes.UInt16, count);
	
	
	
	/**
	 * Helper that allocates the space needed for <code>count</code> number of <code>type</code> datas
	 * @param	type	Type of data to allocate
	 * @param	count	Number of items to allocate space for
	 * @return	id		The ID for the block of memory allocated, or -1 if there wasn't enough space left to allocate the requested size (when grow==false)
	 */
	function allocType(type:MemoryDataTypes, count:UInt):Int {
		switch(type) {
			
			case MemoryDataTypes.Byte	: // ... 1 byte/value
				return alloc(count);
			
			case MemoryDataTypes.UInt16	:
				return alloc(count << 1); 	// 2 bytes/value
			
			case MemoryDataTypes.Int32,
				 MemoryDataTypes.Float	:
				return alloc(count << 2); 	// 4 bytes/value
			
			case MemoryDataTypes.Double	:
				return alloc(count << 3); 	// 8 bytes/value
		}
		
		return -1;
	}
	
	
	
	/**
	 * Release a block of Memory for re-use
	 * @param	id
	 * @return true if released, or false if that id doesn't exist
	 */
	public function release(id:Int):Bool {
		
		if (active.exists(id)) {
			
			var block = active.get(id);
			
			active.remove(id);
			free.set(block.id, block);
			
			occupancy -= block.size;
			
			return true;
		}
		
		return false;
	}
	
	
	 /**
	  * Move all unallocated blocks to the end of the available memory, making a single contiguous 'free' space at the end of the bytearray.
	  * It's probably not that speedy so don't call too regularly.
	  *
	  * @param	?reduceSize - when true any freespace is trimmed, so size==ocupancy and waste==0
	  */
	public function defrag(?reduceSize:Bool=false) {
		
		if (!Lambda.empty(free)) { // got something to defrag?
			
			var b = new ByteArray(); // temporary copy-buffer
			
			var allBlocks:Vector<MemoryBlock> = Vector.ofArray(Lambda.array(Lambda.concat(free, active)));
			allBlocks.sort(sortBlocksByIndex);
			allBlocks.fixed = true;
			
			var freeBlockIndex:Int = nextBlockIndex(allBlocks, 0, false); // first free block
			var dataBlockIndex:Int = nextBlockIndex(allBlocks, freeBlockIndex, true);
			
			while (freeBlockIndex != -1 && dataBlockIndex != -1 && freeBlockIndex!=dataBlockIndex) {
				
				//trace('freeBlockIndex:${freeBlockIndex} dataBlockIndex:${dataBlockIndex}');
				
				var freeBlock 	= allBlocks[freeBlockIndex];
				var dataBlock	= allBlocks[dataBlockIndex];
					
				b.length = 0;
				b.position = 0;
				
				// read bytes from the active block into temporary buffer
				bytes.position = dataBlock.index; // move bytes pointer to dataBlock start
				bytes.readBytes(b, 0, dataBlock.size);
				
				// b should now contain dataBlock
				
				b.position = 0;
				// read the data block back into bytes at the start position of the free-block
				b.readBytes(bytes, freeBlock.index, dataBlock.size);
				
				// update allocated data start index
				dataBlock.index = freeBlock.index;
				
				// update free block start and size
				freeBlock.index += dataBlock.size;
				freeBlock.size  -= dataBlock.size;
				
				if (freeBlock.size == 0) {
					free.remove(freeBlock.id);
					allBlocks[freeBlockIndex] = null;
				}
					
				while (freeBlockIndex < allBlocks.length - 1 && free.exists(allBlocks[freeBlockIndex + 1].id)) {
					// while next block is also free, consolidate the free-space into a single block
					
					var nextFreeBlock 	= allBlocks[freeBlockIndex + 1];
					
					freeBlock.size 		+= nextFreeBlock.size;
					
					free.remove(nextFreeBlock.id);
					allBlocks[freeBlockIndex + 1] = null;
					
					freeBlockIndex++;
				}
				
				freeBlockIndex 	= nextBlockIndex(allBlocks, freeBlockIndex, false);
				dataBlockIndex 	= nextBlockIndex(allBlocks, freeBlockIndex, true); // next allocated block after free block
			}
			
			
			// all freespace is now at the end of the bytearray
			if (reduceSize) { // remove unused bytes. 1K is the minimum allowed size.
				if (bytes.length - waste >= Size_1K) {
					bytes.length -= waste;
				} else {
					bytes.length = Size_1K;
				}
			}
		}
	}
	
	
	/**
	 *
	 * @param	items
	 * @param	start
	 * @param	allocated
	 * @return
	 */
	function nextBlockIndex(items:Vector<MemoryBlock>, start:Int, allocated:Bool):Int {
		
		if (start != -1) {
			
			for (i in start...items.length) {
				var item = items[i];
				if (item != null && item.size > 0) {
					if (allocated && active.exists(item.id)) {
						return i;
					} else if (!allocated && free.exists(item.id)) {
						return i;
					}
				}
			}
		}
		
		return -1;
	}
	
	
	
	/**
	 *
	 * @param	size
	 * @return	free-block start index, -1 if no free blocks
	 */
	function getStartIndex(size:Int):Int {
		var index 	= occupancy;
		var end 	= index + size;
		
		if (end > cast bytes.length) {
			// have space to fill?
			if (hasFreespace(size)) {
				index = fillFreespace(size);
			} else if (grow) {
				// can grow?
				index = bytes.length;
				bytes.length = end;
			} else {
				// no space, can't alloc
				index = -1;
			}
		}
		
		return index;
	}
	
	
	/**
	 *
	 * @param	size
	 * @return
	 */
	function hasFreespace(size:Int):Bool {
		for (b in free) { if (b.size >= size) return true;  }
		return false;
	}
	
	
	/**
	 *
	 * @param	size
	 * @return
	 */
	function fillFreespace(size:Int):Int {
		
		for (b in free) {
			if (b.size >= size) {
				
				var index = b.index;
				
				b.index += size;
				b.size 	-= size;
				
				if (b.size == 0) free.remove(b.id);
				
				return index;
			}
		}
		
		return -1;
	}
	
	static inline function sortBlocksByIndex(a, b) {
		return (a.index < b.index) ? -1 : (a.index == b.index ? 0 : 1);
	}
}


@:access(mikedotalmond.labs.util.SharedMemory) // get access to SharedMemory privates
@:final class MemoryBlock {
	
	public var id			(default, null):UInt;   // unique id
	public var index		(default, default):Int; // address start index - MemoryBlock indices can change after a call to defrag, so keep a reference to the block (or it's ID) for later if needed.
	public var size			(default, default):Int;
	
	public var end			(get_end, null):Int;
	inline function get_end() { return index + size; }
	
	
	public function new(index:Int, size:Int) {
		id 			= SharedMemory.BlockId;
		this.index 	= index;
		this.size 	= size;
		SharedMemory.BlockId++;
	}
	
	public function toString() {
		return '[MemoryBlock] ${id} - start:${index}, size:${size}, end:${end}';
	}
}