/* -------------------------------------------------------------------------- */
/*  Naprogramoval Jan Dvořák z Vozerovic (dvoraj19@fel.cvut.cz)  [dvoraj42]   */
/*  Vytvořeno dne: 1.4.2009, pokus 2, od piky                                 */
/* -------------------------------------------------------------------------- */

void  HeapInit ( void * StartAddr, int Size );
void HeapDone ( int * PendingBlk, int * PendingByte );
void * HeapAlloc ( int Size );
int  HeapFree ( void * Blk );

/* -------------------------------------------------------------------------- */
struct polozka
{
  void *start;
  int velikost;
  polozka *minula;
  polozka *nasledujici;
  int stav;
  int kontrola;
  //stav  ==  0 - nepozivany
  //stav == 1 - pouzivany
};

/* -------------------------------------------------------------------------- */

void *startPameti;
int velikostPameti;

/* -------------------------------------------------------------------------- */
void  HeapInit ( void * StartAddr, int Size )
{
  polozka*pol=(polozka*)StartAddr;
  startPameti=StartAddr;
  velikostPameti=Size;
  //
  pol->stav=0;
  pol->nasledujici=NULL;
  pol->minula=NULL;
  pol->velikost=Size;
  pol->kontrola=6574839;
}

/* -------------------------------------------------------------------------- */
void HeapDone ( int * PendingBlk, int * PendingByte )
{
  polozka*pol=(polozka*)startPameti;
  int b=0,p=0;
  //
  while( (pol->nasledujici)!=NULL )
  {
    if( (pol->stav)==1 )
    {
      b++;
      p+=pol->velikost;
    }
    pol=pol->nasledujici;
  }
  //
  *PendingBlk=b;
  *PendingByte=p;  
}

/* -------------------------------------------------------------------------- */
void * HeapAlloc ( int Size )
{
  polozka* pol=(polozka*)startPameti;
  polozka* pol2;

start:  
  if(pol==NULL)goto nepovedlo; //neni kam vlozit  
  while( (pol->stav)==1 ) pol=pol->nasledujici; //najdeme prvni volny blok

  int vel;  
  if( (pol->nasledujici)==NULL )
  {          
    //nakonec - vejde se?
    vel=(int)(((long)pol)-((long)startPameti)+Size+sizeof(polozka));
    if(vel>velikostPameti)goto nepovedlo; //nevejde se    
    //ocividne vejde
    pol->stav=1; //nastavime na pouzivany
    pol->velikost=Size;
    pol->kontrola=6574839;
      
    pol2=(polozka*) ( ((long)pol)+Size+sizeof(polozka) );    
    pol->nasledujici=pol2;
    pol2->minula=pol;
    pol2->nasledujici=NULL;
      
    return (void*) (((long)pol)+sizeof(polozka));
    
  }else{
    //do mezi bloku
    vel=(int) (((long)pol->nasledujici) - ((long)pol) - sizeof(polozka));
    if(vel<Size)
    {
      //nevejde se , presuneme se na dasi polozku, budeme hledat znovu
      pol=pol->nasledujici;     
      goto start;
    } 
    //vejde se
    pol2=pol->nasledujici;
    
    pol->stav=1; //nastavime na pouzivany
    pol->velikost=Size;

    
    //budeme prerozdelovat?
    if( (vel-((int)sizeof(polozka))) <Size )
    {
      //nebudeme
       return (void*) (((long)pol)+sizeof(polozka));
      
    }else{
      //budeme
      polozka* nova;      
      nova=(polozka*) ( ((long)pol)+sizeof(polozka)+Size );
      //premostime
      pol->nasledujici=nova;
      pol2->minula=nova;
      nova->minula=pol;
      nova->nasledujici=pol2;
      nova->kontrola=6574839;    
      //lze sloucit novy blok s nasledujicim?
      if( (pol2->stav)==0 )
      {
        //ano, provedeme
        nova->nasledujici=pol2->nasledujici;
        if( (pol2->nasledujici)!=NULL ) pol2->nasledujici->minula=nova;
      }
      //
      return (void*) (((long)pol)+sizeof(polozka));
    }       
  }
  
nepovedlo:  
  return (void*)NULL;
}

/* -------------------------------------------------------------------------- */
int  HeapFree ( void * Blk )
{
  polozka* pol=(polozka*) ( (long)(polozka*)Blk-sizeof(polozka) );
  if( (pol->stav)==0 )return 0; //uz uvolneno
  if( (pol->kontrola)!=6574839 )return 0; //nesedi kontrola    
  //uvolnime
  pol->stav=0;
  //kontrola s naslednikem
  if( (pol->nasledujici)!=NULL )
  {
    if( (pol->nasledujici->stav)==0 )
    {
      //sloucime s naslednikem
      polozka* pol2=pol->nasledujici;
      pol->nasledujici=pol2->nasledujici;
      if( (pol2->nasledujici)!=NULL )pol2->nasledujici->minula=pol; 
    }
  }  
  //kontrola s predchudcem
  if( (pol->minula)!=NULL )
  {
    if( (pol->minula->stav)==0 )
    {
       //sloucime s predchudcem
      polozka* pol2=pol->minula;
      pol2->nasledujici=pol->nasledujici;
      if( (pol->nasledujici)!=NULL )pol->nasledujici->minula=pol2;           
    }
  }  
  
  return 1;
}