// ------------------------------------------------------------------------------------------	
// Linked block implementation
/*	
	Interface:

	// User definable
#define N_LB_ENTRIES		8			// n entries = 2 ^ N_LB_ENTRIES_EXP
#define N_LB_ENTRIES_EXP	3

#ifdef NOT_A_POWER_OF_TWO_ENTRY_SIZE
#define LB_ENTRY_WSIZE		5			// entry size = 5 words (= 5 * 4 bytes)
#else
#define LB_ENTRY_BSIZE		4			// entry size = 2 ^ LB_ENTRY_BSIZE_EXP (in bytes) 
#define LB_ENTRY_BSIZE_EXP	2
#endif
			
#define MAKE_ID(x)			x##_Example

#include "LinkedBlock.c"

	Description:
	The above text creates a linked list of tables. Each table has N_LB_ENTRIES-entries.
	Each entry has size LB_ENTRY_BSIZE. The following routines are available:
	
	Variables:
	MAKE_ID(lb_root)			// ptr to root of list
	
	Subroutines:
	MAKE_ID(lb_init)			// initializes the linked block
	MAKE_ID(lb_alloc_entry)		// allocates entry, OUT: %ecx ptr to newly created entry
	MAKE_ID(lb_index_of_entry)	// gets ptr to indexed entry, IN: %ecx valid zero based index, OUT: %ecx ptr to entry
	MAKE_ID(lb_size)			// computes array size, OUT: %ecx array size
	MAKE_ID(lb_map_array)		// maps on array, IN: %ecx address of map function
*/

// checks; NOT_A_POWER_OF_TWO_ENTRY_SIZE 
#ifdef NOT_A_POWER_OF_TWO_ENTRY_SIZE

#ifdef LB_ENTRY_BSIZE
#error "LinkedBlock: internal error"
#endif

#ifdef LB_ENTRY_BSIZE_EXP
#error "LinkedBlock: internal error"
#endif

#endif 

// LB_ENTRY_BSIZE or LB_ENTRY_BSIZE_EXP
#ifdef LB_ENTRY_BSIZE

#ifdef NOT_A_POWER_OF_TWO_ENTRY_SIZE
#error "LinkedBlock: internal error"
#endif

#endif 

#ifdef LB_ENTRY_BSIZE_EXP

#ifdef NOT_A_POWER_OF_TWO_ENTRY_SIZE
#error "LinkedBlock: internal error"
#endif

#endif 

	// Implementation
	

#ifdef NOT_A_POWER_OF_TWO_ENTRY_SIZE
#define LB_ENTRY_BSIZE	(LB_ENTRY_WSIZE * MACHINE_WORD_BSIZE)
#endif

#define LB_BLOCK_BSIZE	((N_LB_ENTRIES * LB_ENTRY_BSIZE) + 4)
#define LB_BLOCK_WSIZE	(LB_BLOCK_BSIZE / MACHINE_WORD_BSIZE)

#ifdef zzz
	.data
	.align 	4
MAKE_ID(lb_root):
	.long	0							// address of root block
MAKE_ID(lb_current_block):						
	.long	0							// address of current block
MAKE_ID(lb_entry):
	.long	0							// number of next entry to be allocated
MAKE_ID(lb_n_blocks):
	.long	0							// amount of allocated blocks
MAKE_ID(lb_map_array_user_defined_function):
	.long	0							// temp used by lb_map_array

#endif // zzz
		
	.text
	.align 4
MAKE_ID(lb_init)!:
	movl	$0,MAKE_ID(lb_root)
	movl	$0,MAKE_ID(lb_n_blocks)
	ret
	
// IN:
// nothing
// OUT
// - %ecx = ptr to allocated entry
MAKE_ID(lb_alloc_entry)!:
	// a new block needed?
	cmpl	$0,MAKE_ID(lb_root)
	je		MAKE_ID(lb_alloc_entry_new_block)!
	cmpl	$ N_LB_ENTRIES,MAKE_ID(lb_entry)
	je		MAKE_ID(lb_alloc_entry_new_block)!
	
MAKE_ID(lb_alloc_entry_block_allocated)!:
#define temp %ecx
#ifdef NOT_A_POWER_OF_TWO_ENTRY_SIZE
	pushl	%eax
	pushl	%edx

	movl	MAKE_ID(lb_entry),%eax
	movl	$ LB_ENTRY_BSIZE,%edx
	mull 	%edx
	
	movl	%eax,temp
	popl	%edx
	popl	%eax
#else 

	movl	MAKE_ID(lb_entry),temp
	shll	$ LB_ENTRY_BSIZE_EXP,temp

#endif
	addl	MAKE_ID(lb_current_block),temp
	addl	$ 4,temp
#undef temp


	incl	MAKE_ID(lb_entry)
	
	ret	

MAKE_ID(lb_alloc_entry_new_block)!:
	// allocate a new block
	call	MAKE_ID(lb_alloc_block)!
	jmp		MAKE_ID(lb_alloc_entry_block_allocated)!
	
// IN:
// - precondition; lb_entry == N_LB_ENTRIES or lb_root = 0; current block is full
// OUT:
// %ecx = ptr to newly allocated empty block
//
MAKE_ID(lb_alloc_block)!:
	subl 	$ LB_BLOCK_WSIZE,free
	js 		GC_FIXED_STACK
	
#define lb_block %ecx
	movl	$ LB_BLOCK_BSIZE,lb_block
	call	alloc_from_extra_heap!!
	
	movl	$0,(lb_block)						// ptr to next lb_block

	movl	$0,MAKE_ID(lb_entry)				// zero entries in lb_block
	
	incl	MAKE_ID(lb_n_blocks)				// increase block counter
	
	cmpl	$0,MAKE_ID(lb_root)
	je		MAKE_ID(lb_alloc_initial_block)!
	
#define temp %ebx
	pushl	temp
	movl	MAKE_ID(lb_current_block),temp		
	movl	lb_block,(temp)						// make previous block point to current block
	popl	temp
#undef temp

	movl	lb_block,MAKE_ID(lb_current_block)	// make newly allocated block the current one

	ret
	
MAKE_ID(lb_alloc_initial_block)!:
	movl	lb_block,MAKE_ID(lb_root)			// make root point to initial block
	
	movl	lb_block,MAKE_ID(lb_current_block)	// make newly allocated block the current one
	
	ret
#undef lb_block

// IN:
// - %ecx = valid zero-based index
// OUT:
// - %ecx = ptr to entry
MAKE_ID(lb_index_of_entry)!:
#define index %ecx
#define temp %eax
	pushl	temp
	pushl	index
	
	movl	MAKE_ID(lb_root),temp
	cmpl	$0,temp
	je 		MAKE_ID(lb_index_of_entry_internal_error)!
	
	shrl	$ N_LB_ENTRIES_EXP,index

MAKE_ID(lb_index_of_entry_loop)!:
	cmpl	$0,index
	je		MAKE_ID(lb_index_of_entry_found)!
	
	movl	(temp),temp
	
	decl	index
	jmp		MAKE_ID(lb_index_of_entry_loop)!
	
MAKE_ID(lb_index_of_entry_found)!:
	popl	index
	
	andl	$ N_LB_ENTRIES - 1,index
	
#ifdef NOT_A_POWER_OF_TWO_ENTRY_SIZE
	pushl	%eax
	pushl	%edx
	
	movl	index,%eax
	movl	$ LB_ENTRY_BSIZE,%edx
	mull 	%edx
	
	movl	%eax,index
	
	popl	%edx
	popl	%eax
#else
	shll	$ LB_ENTRY_BSIZE_EXP,index
#endif
	addl	temp,index
	addl	$4,index
		
	popl	temp
	
	ret
#undef temp
#undef index

MAKE_ID(lb_index_of_entry_internal_error)!:
	movl	$ lb_index_of_entry_internal_error_string,%ecx
	jmp		abort
	
// IN:
// - precondition: at least one block allocated
// OUT:
// - array size in %ecx
MAKE_ID(lb_size)!:
#define temp %ecx
	cmpl	$0,MAKE_ID(lb_root)
	je		MAKE_ID(lb_size_is_zero)!			// empty list gives zero sized array

	movl	MAKE_ID(lb_n_blocks),temp
	cmpl	$0,temp
	je		MAKE_ID(lb_size2)!
	
	decl	temp								// current non-full block doesn't count
MAKE_ID(lb_size2)!:
	shll	$ N_LB_ENTRIES_EXP,temp
	addl	MAKE_ID(lb_entry),temp
	
	ret

MAKE_ID(lb_size_is_zero)!:
	movl	$0,temp
	ret
#undef temp


// IN:
// - %ecx = address of function operating on a element
// OUT:
// - array has been mapped
// WARNING: only one level map is supported
MAKE_ID(lb_map_array)!:
	pushl	%eax								// backup registers
	pushl	%ebx
	
	movl	%ecx,MAKE_ID(lb_map_array_user_defined_function)
	
#define block_base %eax
	movl	MAKE_ID(lb_root),block_base			// root of linked blocks
	
MAKE_ID(lb_map_array_next_block)!:
	cmpl	$0,block_base						
	je		MAKE_ID(lb_map_array_finished)!		// no next block, finish
	
	cmpl	$0,(block_base)
	je		MAKE_ID(lb_map_in_current_block)!	// block is current block
	
	// block is full and not current
#define counter %ebx
#define entry %ecx
	movl	$0,counter
	leal	4(block_base),entry

MAKE_ID(lb_map_array_next_entry)!:
	cmpl	$ N_LB_ENTRIES,counter
	je		MAKE_ID(lb_map_array1)!

	// %ecx = ptr to array entry
	pushl	block_base
	pushl	counter
	pushl	entry
	call	*(MAKE_ID(lb_map_array_user_defined_function))
	popl	entry
	popl	counter
	popl	block_base
	
	addl	$ LB_ENTRY_BSIZE,entry
	incl	counter
	
	jmp		MAKE_ID(lb_map_array_next_entry)!
	
MAKE_ID(lb_map_array1)!:
	movl	(block_base),block_base
	
	jmp		MAKE_ID(lb_map_array_next_block)!

MAKE_ID(lb_map_in_current_block)!:
	movl	$0,counter
	leal	4(block_base),entry
	
MAKE_ID(lb_map_array_next_entry_within_current_block)!:
	cmpl	MAKE_ID(lb_entry),counter
	je		MAKE_ID(lb_map_array_finished)!

	// %ecx = ptr to array entry
	pushl	counter
	pushl	entry
	call	*(MAKE_ID(lb_map_array_user_defined_function))
	popl	entry
	popl	counter
	
	addl	$ LB_ENTRY_BSIZE,entry
	incl	counter
	
	jmp		MAKE_ID(lb_map_array_next_entry_within_current_block)!	
#undef entry
#undef counter
	
MAKE_ID(lb_map_array_finished)!:	
	popl	%ebx									// restore registers
	popl	%eax
	ret	


#ifdef NOT_A_POWER_OF_TWO_ENTRY_SIZE
#undef LB_ENTRY_BSIZE
#endif



#ifdef zzz
#undef LB_BLOCK_BSIZE
#undef LB_BLOCK_WSIZE

// undef user defined macros
#undef N_LB_ENTRIES
#undef N_LB_ENTRIES_EXP
#undef LB_ENTRY_BSIZE

#ifdef NOT_A_POWER_OF_TWO_ENTRY_SIZE
#undef LB_ENTRY_WSIZE
#undef NOT_A_POWER_OF_TWO_ENTRY_SIZE
#else
#undef LB_ENTRY_BSIZE_EXP
#endif

#undef MAKE_ID
#endif // zzz