// Mon Jun  5 11:14:07 CEST 2000
// Dinko Korunic, 36355514, email: kreator@fly.srk.fer.hr
// Predmet Operacijski sustavi 1 - Zadatak 5

// Opis rjesenja:
//	Funkcije su napisane da koriste algoritam dodjele memorijskih
//	blokova "prvi odgovarajuci". Memorija se dodjeljuje u brojevima
//	zaglavlja. Prazni blokovi su upisani kao negativne duljine u
//	zaglavlju. Funkcija "oslobodi" oslobadja memoriju tako da u listu
//	blokova oznacuje blok slobodan postavljajuci njegovu vrijednost da
//	bude negativna, te pritom i ispituje da li su njegovi susjedni
//	blokovi (prethodni i/ili slijedeci) slobodni, te ako jesu od svih
//	njih ce napraviti jedan jedinstveni blok, i oznaciti ga kao
//	slobodan. Takvim postupkom se postize da nikad nije moguce imati
//	dva slobodna bloka u nizu jedan za drugim, vec ce postojati samo
//	jedinstveni slobodni blokovi u nizu. Funkcija "dodijeli" trazi
//	prvi slobodni blok koji ima dovoljnu duljinu. Ako je slobodni blok
//	veci od potrebnog, od ostatka ce se stvoriti novi blok i oznaciti
//	kao slobodan.

#include <stdlib.h>
#include <unistd.h>
#include <iostream.h>

// struktura
struct Zaglavlje
{
	int BrojZaglavlja;
	Zaglavlje *Slijedece;
};

// glavni pokazivac
Zaglavlje *ptr=NULL;

// ispisuje blokove i njihove velicine
void Dump(void)
{
	Zaglavlje *P=ptr;
	unsigned i=1;
	while (P!=NULL)
	{
		cout << "--> Blok #" << i << ": velicina=" <<
			P->BrojZaglavlja << endl;
		P=P->Slijedece;
		++i;
	}
}

// funkcija za dodjeljivanje memorije
void *Dodijeli(unsigned Velicina)
{
	Zaglavlje *Q;
	Dump();
	Velicina+=sizeof(Zaglavlje);
	cout << "dodijeli: velicina=" << Velicina/sizeof(Zaglavlje)
		<< endl;
	if (ptr==NULL)
	{
		ptr=(Zaglavlje *)sbrk((Velicina/sizeof(Zaglavlje)+1)
			*sizeof(Zaglavlje));
		cout << "dodijeli: izvrsen sbrk za prvu alokaciju" <<
			endl;
		if (ptr==NULL) return NULL;
		ptr->BrojZaglavlja=Velicina/sizeof(Zaglavlje);
		ptr->Slijedece=NULL;
		return ptr+1;
	}
	else
	{
		Zaglavlje *P=ptr;
		while (1)
		{
			if (abs(P->BrojZaglavlja)>=Velicina/sizeof(Zaglavlje)
				 && P->BrojZaglavlja<0)
			{
				if (abs(P->BrojZaglavlja)==Velicina/
					sizeof(Zaglavlje) ||
					P->BrojZaglavlja==-Velicina/
					sizeof(Zaglavlje)-1)
				{
					cout << "dodijeli: pronadjen "
						"prazan blok jednake velicine"
						<< endl;
					P->BrojZaglavlja*=-1;
					return P+1;
				}
				cout << "dodijeli: pronadjen prazan blok,"
					" alociran njegov dio, ostatak"
					" oznacen slobodan" << endl;
				P[Velicina/sizeof(Zaglavlje)+1].BrojZaglavlja=
					abs(P->BrojZaglavlja)-Velicina/
					sizeof(Zaglavlje)-1;
				cout << "dodijeli: velicina slobodnog "
					"bloka=" << P[Velicina/sizeof
					(Zaglavlje)+1].BrojZaglavlja << endl;
				P[Velicina/sizeof(Zaglavlje)+1].
					BrojZaglavlja*=-1;
				P[Velicina/sizeof(Zaglavlje)+1].
					Slijedece=P->Slijedece;
				P->BrojZaglavlja=Velicina/sizeof(Zaglavlje);
				P->Slijedece=&P[Velicina/sizeof(Zaglavlje)+1];
				return P+1;
			}
			if (P->Slijedece==NULL) break;
			P=P->Slijedece;
		}
		Q=(Zaglavlje *)sbrk((Velicina/sizeof(Zaglavlje)+1)
			*sizeof(Zaglavlje));
		cout << "dodijeli: izvrsen sbrk" << endl;
		P->Slijedece=Q;
		Q->BrojZaglavlja=Velicina/sizeof(Zaglavlje);
		Q->Slijedece=NULL;
		return Q+1;
	}
}


// funkcija za oslobadjanje memorije
void Oslobodi(void *kazaljka)
{
	Zaglavlje *P=ptr;
	Dump();
	while (1)
	{
		if (P->Slijedece!=NULL && P->Slijedece==(((Zaglavlje
			*)kazaljka)-1) && P->BrojZaglavlja<0)
		{
			if ((P->Slijedece)->Slijedece!=NULL &&
				((P->Slijedece)->Slijedece)->BrojZaglavlja<0)
			{
				P->BrojZaglavlja=-(abs(P->BrojZaglavlja)+
					abs((P->Slijedece)->BrojZaglavlja)+
					abs(((P->Slijedece)->Slijedece)
						->BrojZaglavlja)+2);
				P->Slijedece=((P->Slijedece)->Slijedece)
					->Slijedece;
				cout << "oslobodi: oslobodjen blok, i"
					" napravljen jedinstveni slobodni"
					" blok zajedno sa prethodnim i "
					"slijedecim slobodnim blokom"
					<< endl;
				return;
			}
			P->BrojZaglavlja=-(abs(P->BrojZaglavlja)
				+abs((P->Slijedece)->BrojZaglavlja)+1);
			P->Slijedece=(P->Slijedece)->Slijedece;
			cout << "oslobodi: oslobodjen blok, i napravljen"
				" jedinstveni slobodni blok zajedno sa"
				" prethodnim slobodnim blokom" << endl;
			return;
		}
		if (P==(((Zaglavlje *)kazaljka)-1) && P->Slijedece!=NULL
			&& (P->Slijedece)->BrojZaglavlja<0)
		{
			P->BrojZaglavlja=-(abs(P->BrojZaglavlja)
				+abs((P->Slijedece)->BrojZaglavlja)+1);
			P->Slijedece=(P->Slijedece)->Slijedece;
			cout << "oslobodi: oslobodjen blok, i napravljen"
				" jedinstveni slobodni blok zajedno sa "
				"slijedecim slobodnim blokom" << endl;
			return;
		}
		if (P==((Zaglavlje *)kazaljka)-1)
		{
			P->BrojZaglavlja*=-1;
			cout << "oslobodi: oslobodjen blok" << endl;
			return;
		}
		if (P->Slijedece==NULL) break;
		P=P->Slijedece;
	}
}

// glavni dio programa
int main(void)
{
	char *t1, *t2, *t3, *t4, *t5;
	int i;
	cout << "t1=dodijeli(10)" << endl;
	t1=(char *)Dodijeli(10);
	cout << "t2=dodijeli(1000000)" << endl;
	t2=(char *)Dodijeli(1000000);
	cout << "upis u t2.." << endl;
	for (i=0; i<1000000; ++i) t2[i]=0xff;
	cout << "t3=dodijeli(10000000)" << endl;
	t3=(char *)Dodijeli(10000000);
	cout << "t4=dodijeli(500000)" << endl;
	t4=(char *)Dodijeli(500000);
	cout << "t5=dodijeli(100)" << endl;
	t5=(char *)Dodijeli(100);
	cout << "oslobodi(t3)" << endl;
	Oslobodi(t3);
	cout << "t3=dodijeli(10000000)" << endl;
	t3=(char *)Dodijeli(10000000);
	cout << "oslobodi(t3)" << endl;
	Oslobodi(t3);
	cout << "t3=dodijeli(300)" << endl;
	t3=(char *)Dodijeli(300);
	cout << "oslobodi(t3)" << endl;
	Oslobodi(t3);
	cout << "oslobodi(t4)" << endl;
	Oslobodi(t4);
	cout << "oslobodi(t5)" << endl;
	Oslobodi(t5);
	cout << "t5 = dodijeli(1000)" << endl;
	t5=(char *)Dodijeli(1000);
	cout << "oslobodi(t5)" << endl;;
	Oslobodi(t5);
	cout << "oslobodi(t1)" << endl;
	Oslobodi(t1);
	cout << "oslobodi(t2)" << endl;
	Oslobodi(t2);              
	Dump();
	return EXIT_SUCCESS;
}