"vector_func's.hhf"
// vector_func's.hhf // 2012-08-21 //
#includeOnce ( "vector.hhf" )
type
pVec: pointer to Vec;
#if( !@defined( pMyCmp ) )
static
pMyCmp: procedure( a: dword in esi; b: dword in edi ); @returns( "eax" );
#endif
// re. isort ... note: cmp func is a < b
// re. msort ... note: cmp func is a <= b
procedure isortVec( var v: Vec );
static
rcmp: Rec;
tmpReg: dword;
begin isortVec;
push( eax ); push( ebx ); push( ecx ); push( edx ); push( esi ); push( edi );
//int i, j; // i in eax, j in edx
// start with an array of just the first 2 elements (if exists) ...
// for( i = 1; i < cv->size; ++i )
cld();
mov( v, ebx );
for( mov( 1, eax ); eax < (type Vec [ebx]).size; inc( eax ) ) do
// update this cmp Rec on each outer loop
//memcpy( &cmp, &cv->ary[i], sizeof(Rec) );
mov( &rcmp, edi );
intmul( @size(Rec), eax, esi );
add( (type Vec [ebx]).ary, esi );
mov( @size(Rec), ecx ); // get # bytes to copy in a Rec ... into ecx
rep.movsb(); // ok ... got copy into rcmp ...
// get index of element just to the left of the above 'cmp' to start comparisons
mov( eax, edx ); // j = i
dec( edx ); // --j // i.e. j = i-1; //
while( (type int32 edx) >= 0 ) do // while( j >= 0 && myCmp(&cmp, &cv->ary[j]) < 0 )
intmul( @size(Rec), edx, edi ); // get offset into edi ..
add( (type Vec [ebx]).ary, edi );
mov( &rcmp, esi );
//breakif( !pMyCmp(esi, edi) ); // 'copy up' // but first ...
mov( eax, tmpReg ); // get copy of loop counter in eax
pMyCmp( esi, edi );
if( eax ) then
mov( tmpReg, eax );
else
mov( tmpReg, eax );
break;
endif;
// Now ... 'copy up' ...
//memcpy( &cv->ary[j+1], &cv->ary[j], sizeof(Rec) );
intmul( @size(Rec), edx, esi );
add( (type Vec [ebx]).ary, esi );
mov( esi, edi );
add( @size(Rec), edi ); // to inc( j ) add size //
mov( @size(Rec), ecx ); // get # bytes to copy in a Rec into ecx
rep.movsb();
dec( edx ); //--j; // --j to prepare for next inner loop
endwhile;
// insert pointer at index j+1 (since j was decremented above ...
//memcpy( &cv->ary[j+1], &cmp, sizeof(Rec) );
inc( edx ); // ++j
mov( &rcmp, esi );
intmul( @size(Rec), edx, edi );
add( (type Vec [ebx]).ary, edi );
mov( @size(Rec), ecx ); // get # bytes to copy in a Rec into ecx
rep.movsb();
endfor;
pop( edi ); pop( esi ); pop( edx ); pop( ecx ); pop( ebx ); pop( eax );
end isortVec; // size hasn't changed ...
////////////////////////////////////////////////////////////////////////////
// re. msort ... note: cmp func is a <= b
procedure mergeVec( pv: pVec in ebx; bot: int32; top: int32; ptmp: pVec in edx );
var
mid: int32; // set to (bot+top)/2
sz: int32; // set to top-bot+1 // size of the range to be merged
j: int32;
tmpReg: dword;
begin mergeVec;
//push( eax ); push( ecx ); push( esi ); push( edi );
//int mid = (bot+top)/2;
mov( top, eax );
add( bot, eax );
shr( 1, eax ); // divide by 2
mov( eax, mid );
//int sz = top - bot + 1; // size of the range to be merged
mov( top, eax );
sub( bot, eax );
inc( eax );
mov( eax, sz );
mov( 0, j ); // int j = 0; // next open index in tmp
mov( bot, eax ); // int h1 = bot; // next index to consider in 1st half
mov( mid, ecx ); // int h2 = mid + 1; // next index to consider in 2nd half
inc( ecx );
// while indexes h1 and h2 are not past their ends ...
cld();
while( eax <= mid && ecx <= top ) do // while( h1 <= mid && h2 <= top )
// move the smaller element into the tmp vec 'next' ...
// if( myCmp( &(cv->ary[h1]), &(cv->ary[h2]) ) <= 0 )
intmul( @size(Rec), eax, esi );
add( (type Vec [ebx]).ary, esi );
intmul( @size(Rec), ecx, edi );
add( (type Vec [ebx]).ary, edi );
mov( eax, tmpReg );
pMyCmp( esi, edi ); // if( myCmp(...) <= 0 )
if( eax ) then // if( myCmp(...) <= 0 )
//tmp->ary[j++] = cv->ary[h1++];
mov( tmpReg, eax ); // restore eax
intmul( @size(Rec), eax, esi );
add( (type Vec [ebx]).ary, esi );
intmul( @size(Rec), j, edi );
add( (type Vec [edx]).ary, edi );
mov( ecx, tmpReg );
mov( @size(Rec), ecx );
rep.movsb(); // tmp->ary[j++] = cv->ary[h1++];
mov( tmpReg, ecx );
inc( eax ); // ++h1
inc( j );
else
//tmp->ary[j++] = cv->ary[h2++];
mov( tmpReg, eax ); // restore eax
intmul( @size(Rec), ecx, esi ); // ecx holds h2
add( (type Vec [ebx]).ary, esi );
intmul( @size(Rec), j, edi );
add( (type Vec [edx]).ary, edi );
mov( ecx, tmpReg );
mov( @size(Rec), ecx );
rep.movsb(); // tmp->ary[j++] = cv->ary[h2++];
mov( tmpReg, ecx );
inc( ecx ); // ++h2
inc( j );
endif;
endwhile;
// Note: only one (at most) of the two 'while's' below is executed ...
//while( h1 <= mid ) // copy any remaining entries (1st half)
//tmp->ary[j++] = cv->ary[h1++];
while( eax <= mid ) do
intmul( @size(Rec), eax, esi );
add( (type Vec [ebx]).ary, esi );
intmul( @size(Rec), j, edi );
add( (type Vec [edx]).ary, edi );
mov( ecx, tmpReg );
mov( @size(Rec), ecx );
rep.movsb(); // tmp->ary[j++] = cv->ary[h1++];
mov( tmpReg, ecx );
inc( eax ); // ++h1
inc( j );
endwhile;
//while( h2 <= top ) // copy any remaining entries (2nd half)
//tmp->ary[j++] = cv->ary[h2++];
while( ecx <= top ) do
intmul( @size(Rec), ecx, esi );
add( (type Vec [ebx]).ary, esi );
intmul( @size(Rec), j, edi );
add( (type Vec [edx]).ary, edi );
mov( ecx, tmpReg );
mov( @size(Rec), ecx );
rep.movsb(); // tmp->ary[j++] = cv->ary[h2++];
mov( tmpReg, ecx );
inc( ecx ); // ++h2
inc( j );
endwhile;
//for( j = 0; j < sz; ++j ) // copy back sorted tmp vec...
//cv->ary[bot+j] = tmp->ary[j];
mov( (type Vec [edx]).ary, esi );
//mov( bot, edi );
intmul( @size(Rec), bot, edi );
add( (type Vec [ebx]).ary, edi );
//mov( sz, ecx );
intmul( @size(Rec), sz, ecx );
rep.movsb();
/*
for( mov( 0, ecx ); ecx < sz; inc( ecx ) ) do
intmul( @size(Rec), ecx, esi );
add( (type Vec [edx]).ary, esi );
mov( bot, eax );
add( ecx, eax );
intmul( @size(Rec), eax, edi );
add( (type Vec [ebx]).ary, edi );
mov( ecx, tmpReg );
mov( @size(Rec), ecx );
rep.movsb(); // cv->ary[bot+j] = tmp->ary[j];
mov( tmpReg, ecx );
endfor;
*/
//pop( edi ); pop( esi ); pop( ecx ); pop( eax );
end mergeVec;
procedure my_msortVec( pv: pVec in ebx; bot: int32; top: int32; ptmp: pVec in edx );
var
mid: int32;
begin my_msortVec;
mov( top, eax );
if( bot < eax ) then
add( bot, eax ); // NOW EAX HOLDS top + bot
shr( 1, eax ); // divide by 2 ...
mov( eax, mid ); // mid = ( bot + top ) / 2;
my_msortVec( ebx, bot, mid, edx ); // sort the first half ...
inc( mid ); // now mid = mid +1
my_msortVec( ebx, mid, top, edx ); // and the second half
mergeVec( ebx, bot, top, edx ); // now merge 2 sorted chunks
endif;
end my_msortVec;
procedure msortVec( var v: Vec );
var
Rega: dword;
Regb: dword;
Regc: dword;
Regd: dword;
Regesi: dword;
Regedi: dword;
tmp: Vec;
begin msortVec;
mov( eax, Rega ); mov( ebx, Regb ); mov( ecx, Regc ); mov( edx, Regd );
mov( esi, Regesi ); mov( edi, Regedi );
mov( v, ebx );
mov( (type Vec [ebx]).size, eax );
if( eax > 1 ) then
initVec( tmp );
reserveVec( tmp, eax ); // Note: resets cap... BUT tmp size still 0
dec( eax );
lea( edx, tmp ); // get address of new tmp Vec into edx ...
my_msortVec( ebx, 0, eax, edx );
// NOW done ... BUT only free ary mem that held copies of pointers
mem.free( tmp.ary );
endif;
mov( Regedi, edi ); mov( Regesi, esi );
mov( Regd, edx ); mov( Regc, ecx ); mov( Regb, ebx ); mov( Rega, eax );
end msortVec;
// returns index if string present, else -1 ...
procedure findVec( var v: Vec; var r: Rec ); @returns( "eax" );
begin findVec;
push( ebx ); push( ecx ); push( esi ); push( edi );
mov( v, ebx );
for( mov( 0, ecx ); ecx < (type Vec [ebx]).size; inc( ecx ) ) do
//if( myCmp(&cv->ary[i], r) == 0 )
intmul( @size(Rec), ecx, esi );
add( (type Vec [ebx]).ary, esi );
mov( r, edi );
pMyCmp( esi, edi ); // need an 'eq' cmp here ...
breakif( eax ); // i.e. break if equal ...
endfor;
// now check loop end condition ...
if( ecx != (type Vec [ebx]).size ) then
mov( ecx, eax ); // found
else
mov( -1, eax ); // NOT found
endif;
pop( edi ); pop( esi ); pop( ecx ); pop( ebx );
end findVec;
// if int index valid, erases element there ...
procedure eraseVec( var v: Vec; index: uns32 in eax );
var
tmpReg: dword;
begin eraseVec;
push( ebx ); push( ecx ); push( esi ); push( edi );
mov( v, ebx );
if( (type int32 eax) >= 0 && (type int32 eax) < (type Vec [ebx]).size ) then
mov( eax, tmpReg );
intmul( @size(Rec), eax );
add( (type Vec [ebx]).ary, eax );
//freeVrec( &(cv->ary[index]) );
freeRec( eax ); // must pass in eax, needed here if dynamic memory
mov( tmpReg, eax );
//if( index < cv->size-1 )
//memcpy(&cv->ary[index], &cv->ary[index+1], (cv->size-1-index)*sizeof(Rec));
mov( (type Vec [ebx]).size, ecx );
dec( ecx ); // ecx holds size-1
if( eax < ecx ) then
sub( eax, ecx ); // ecx now holds (cv->size-1-index)
intmul( @size(Rec), ecx ); // ecx now holds bytes to copy ...
intmul( @size(Rec), eax, edi );
add( (type Vec [ebx]).ary, edi );
mov( edi, esi );
add( @size(Rec), esi );
rep.movsb();
endif;
// now update size and return by reference (since address passed in)
dec( (type Vec [ebx]).size );
else
mov( (type Vec [ebx]).size, ecx );
dec( ecx ); // ecx holds size-1
stdout.put( nl, "ERROR! Index ", index, " out of range 0..", (type int32 ecx), nl);
endif;
pop( edi ); pop( esi ); pop( ecx ); pop( ebx );
end eraseVec;
#if ( false )
// isort ///////////////////////////////////////////////////////////////////
void isortCvec( Cvec* cv, int (*myCmp) (const Rec* a, const Rec* b) )
{
int i, j;
Rec cmp;
for( i = 1; i < cv->size; ++i ) /* start with an array of just the first 2 elements (if exists) */
{
memcpy( &cmp, &cv->ary[i], sizeof(Rec) ); /* get new cmp on each outer loop */
j = i-1; /* get index of element just to the left of 'cmp' to start comparisons */
while( j >= 0 && myCmp(&cmp, &cv->ary[j]) < 0 )
{
memcpy( &cv->ary[j+1], &cv->ary[j], sizeof(Rec) ); /* 'copy up' */
--j; /* decrement j in preparation for next inner loop ... */
}
memcpy( &cv->ary[j+1], &cmp, sizeof(Rec) ); /* insert cmp at index j+1
(since j was decremented above) */
}
cv->isSorted = 1;
} /* size hasn't changed ... */
// msort ///////////////////////////////////////////////////////////////////
void mergeCvec( Cvec* cv, int bot, int top, Cvec* tmp,
int (*myCmp) (const Rec* a, const Rec* b) )
{
int mid = (bot+top)/2;
int sz = top - bot + 1; // size of the range to be merged
int j = 0; // next open index in tmp
int h1 = bot; // next index to consider in the 1st half
int h2 = mid + 1; // next index to consider in the 2nd half
// while indexes h1 and h2 are not past their ends ...
while( h1 <= mid && h2 <= top )
{ // move the smaller element into the tmp vec next ...
if( myCmp( &(cv->ary[h1]), &(cv->ary[h2]) ) <= 0 )
tmp->ary[j++] = cv->ary[h1++];
else
tmp->ary[j++] = cv->ary[h2++];
}
// Note: only one of the two 'while's' below is executed ...
while( h1 <= mid ) // copy any remaining entries (1st half)
tmp->ary[j++] = cv->ary[h1++];
while( h2 <= top ) // copy any remaining entries (2nd half)
tmp->ary[j++] = cv->ary[h2++];
for( j = 0; j < sz; ++j ) // copy back sorted tmp vec...
cv->ary[bot+j] = tmp->ary[j];
}
void my_msortCvec( Cvec* cv, int bot, int top, Cvec* tmp,
int (*myCmp) (const Rec* a, const Rec* b) )
{
if( bot == top ) return;
else
{
int mid = ( bot + top ) / 2;
my_msortCvec( cv, bot, mid, tmp, myCmp ); // sort the first ...
my_msortCvec( cv, mid+1, top, tmp, myCmp ); // and the second half
mergeCvec( cv, bot, top, tmp, myCmp ); // now merge 2 sorted chunks
}
}
/* *NOTE* Calling msortCvec sets the returned by ref Cvec to *** isSorted *** */
void msortCvec( Cvec* cv, int (*myCmp) (const Rec* a, const Rec* b) )
{
if( cv->size > 1 )
{
Cvec tmp;
initCvec( &tmp );
reserveCvec( &tmp, cv->size ); /* Note: resets cap, BUT size still 0 */
my_msortCvec( cv, 0, cv->size-1, &tmp, myCmp );
cv->isSorted = 1;
free( tmp.ary ); /* only free ary mem that held copies of pointers */
}
}
// find ////////////////////////////////////////////////////////////////////
/* returns index if string present, else -1 */
int findCvec( Cvec* cv, const Rec* r, int (*myCmp) (const Rec* a, const Rec* b) )
{
int i;
for( i = 0; i < cv->size; ++i )
if( myCmp(&cv->ary[i], r) == 0 ) return i;
/* else if reach here ... */
return -1;
}
// erase ///////////////////////////////////////////////////////////////////
/* if int index valid, erases element there */
void eraseCvec( Cvec* cv, int index )
{
//int i;
if( index < 0 || index >= cv->size )
{ printf( "\nERROR! Index %d out of range 0..%d\n", index, cv->size-1 );
return; }
freeVrec( &(cv->ary[index]) ); /* needed here for dynamic memory types */
/* copy each (set of pointers above) down one index */
//for( i = index; i < cv->size-1; ++i )
//memcpy(&cv->ary[i], &cv->ary[i+1], sizeof(Rec));
if( index < cv->size-1 )
memcpy(&cv->ary[index], &cv->ary[index+1], (cv->size-1-index)*sizeof(Rec));
/* now update size and return (by reference, since address passed in) */
-- cv->size;
}
#endif
