Contoh Dynamic Memory Allocation Dengan Doubly-linked List, First-fit & Auto Left-Right Join [Part 3]

Bagian ini akan khusus membahas tentan proses alokasi ( Malloc() ). Sistematika kerja alokator dalam mengalokasikan memori sudah diketahui dari gambar ilustrasi yang kita lihat sebelumnya. Pada prakteknya, ada sedikit penjabaran yang harus diperhatikan. Alokator melakukan alokasi dari fungsi Malloc() yang kita buat. Pencarian mulai dilakukan dari melihat HCHUNK pertama yang ditunjukkan oleh field first pada HMALLOC dan mengikuti pointer next pada HCHUNK hingga ditemukan hasil. Apabila tidak ada chunk bebas yang memiliki ukuran cukup, fungsi harus mengembalikan 0.

for(HCHUNK *c = m­->first; c != 0; c = c-­>next){
//Check chunk (*c)
}
return 0;

Setiap chunk yang diperiksa melewati beberapa urutan tahap uji sebagai berikut.
1. Jika chunk→magic salah, gagalkan fungsi
2. Jika chunk→state = 1 (allocated), lewati dan lanjutkan memeriksa chunk berikutnya(chunk→next).
3. Jika chunk→size < size yang diminta (not enough), lanjutkan memeriksa chunk berikutnya(chunk→next).
4. Jika chunk→size == size dan chunk→size <= size + sizeof(HCHUNK) (size was fit), langsung alokasikan chunk ini sebagai hasil. Kondisi “chunk→size <= size + ukuran HCHUNK” harus diperiksa, karena jika chunk bebas melebihi yang diminta, kita hanya boleh mengambil sebagian chunk yang cukup, sisanya harus dibuat chunk yang baru (dibuat pada kondisi 5). Sebelum memutuskan buat yang baru, kondisi ini diperiksa untuk memastikan apakah sisa chunk cukup untuk menyimpan header HCHUNK dan minimum chunk sebesar 1 byte. Jika tidak, sebaiknya kita ikutkan saja sisanya sebagai hasil.
5. Apabila tidak masuk kondisi 3 auatupun 4, artinya chunk terlalu besar (size bigger), alokator harus melakukan pemecahan chunk menjadi 2 bagian. Satu bagian sebagai hasil alokasi dan sisanya dibuat untuk dibiarkan dalam kondisi bebas.

void *Malloc(HMALLOC *m,uint size){
for(HCHUNK *c = m-­>first; c != 0; c = c-­>next){
if(c­->magic != CMAGIC){
printf("FATAL:Broken malloc!\n");
return 0;
}
if(c-­>state == 1) continue;
else if(c-­>size < size) continue;
else if((c-­>size >= size) &&
  (c­->size <= size + sizeof(HCHUNK))) {
c-­>state = 1;
return (void*)((ulong)c + sizeof(HCHUNK));
}
else {
HCHUNK *newc;
newc = (HCHUNK*)((ulong)c + sizeof(HCHUNK) + size);
newc­->magic = CMAGIC;
newc­->state = 0;
newc­->size = c­->size - size - sizeof(HCHUNK);
newc­->prev = c;
newc­->next = c-­>next;
c­->next = newc;
c­->size = size;
c­->state = 1;
return (void*)((ulong)c + sizeof(HCHUNK));
}
}
return 0;
}

Periksa kondisi 1
if(c­->magic != CMAGIC){
printf("FATAL:Broken malloc!\n");
return 0;
}

Periksa kondisi 2
if(c-­>state == 1) continue;

Periksa kondisi 3
else if(c­->size < size) continue;

Periksa kondisi 4
else if((c->size >= size) && (c->size <= size + sizeof(HCHUNK))) {
c->state = 1;
return (void*)((ulong)c + sizeof(HCHUNK));
}

Kondisi 5
else {
HCHUNK *newc;
newc = (HCHUNK*)((ulong)c + sizeof(HCHUNK) + size);
newc-­>magic = CMAGIC;
newc­->state = 0;
newc­->size = c->size - size - sizeof(HCHUNK);
newc­->prev = c;
newc­->next = c->next;
c­->next = newc;
c­->size = size;
c-­>state = 1;
return (void*)((ulong)c + sizeof(HCHUNK));
}

Kondisi 5 adalah kondisi yang sedikit membutuhkan logika. Sederhananya, proses untuk menangi kondisi 5 sesuai dengan ilustrasi di bawah ini. Sederhana memang, namun yang sedikit membingungkan adalah mengatur prev dan next agar tetap terhubung satu sama lain.

Sebelum terpecah

Sesudah terpecah