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

Penerapan alokator akan membutuhkan 2 struktur data untuk mentracking seluruh aktivitas alokasi. Struktur yang pertama adalah header HMALLOC. Di dalamnya, terdapat informasi mengenai ukuran dari seluruh blok memori yang tersedia dan potongan chunk memori pertama yang berada dalam blok tersebut. Penempatan HMALLOC akan selalu dilakukan di bagian paling awal dari blok, sebelum deretan chunk beserta headernya. Ukuran blok total dan kapasitas maksimum dari chunk itu sendiri akan kita tentukan saat inisialisasi.

Berikut adalah wujud struktur HMALLOC yang ditulis dalam C.

typedef struct _HMALLOC{
uint size;
HCHUNK *first;
}HMALLOC;

Sementara itu, struktur header yang akan selalu terpasang pada setiap awal chunk akan kita sebut sebagai HCHUNK. Struktur ini mendeskripsikan informasi pokok dari chunk yang diwakilinya.

typedef struct _HCHUNK {
int magic;
uint size;
char state;
struct _HCHUNK *prev,*next;
} HCHUNK;

Bagian unik dari HCHUNK adalah field magic. Nilainya akan selalu sama bagi setiap struktur HCHUNK. Kita akan membuat nilainya seunik mungkin. Nilai ini akan kita didefinisakan sebagai CMAGIC.

#define CMAGIC 0xBEDABEDA

Ketika program mengalami kesalahan saat mengakses blok lain, header dapat ter-overwrite, sehingga tak valid lagi. Jika dibiarkan, alokator justru akan berpotensi merusak sistem. Untuk itu, alokator akan menggagalkan alokasi memori saat ditemukan nilai magic yang salah. Saat program gagal mengalokasikan memori, program biasanya akan selalu memeriksa hasil alokasi dan membuat notifikasi ke user apabila terjadi kegagalan, jadi jangan kawatir.

Selanjutnya, field size adalah ukuran dari chunk memori yang diwakili oleh header. Ingat, hanya ukuran chunk saja, tanpa ukuran header. Lalu, field state bertugas memberitahu alokator, apakah field yang diwakili HCHUNK masih bebas atau sudah teralokasi. Nilainya 0 akan dianggap bebas, atau BUKAN 0 apabila teralokasi. Terakhir, field prev dan next adalah 2 buah pointer doubly-linked list yang akan mengarahkan ke struktur HCHUNK disampingnya. Alokator akan menelusuri pointer ini untuk mencari chunk memori yang dapat dialokasikan.

Inisialisasi
Persiapan dilakukan dengan mengatur nilai HMALLOC di dalam blok. Awalnya, sistem harus menyediakan blok memori untuk keperluan alokasi. Fungsi MallocInit() berikut akan memproses blok dari parameter alamat addr dan ukuran size yang diberikan.

HMALLOC *MallocInit(void *addr, uint size){

HMALLOC *m;

if(size <= sizeof(HMALLOC) + sizeof(HCHUNK))

return 0;

m = (HMALLOC *) addr;

m->first = (HCHUNK*) ((ulong)addr + sizeof(HMALLOC));

m->size = size;

m->first->magic = CMAGIC;

m->first->state = 0;

m->first->size = size - sizeof(HMALLOC) - sizeof(HCHUNK);

m->first->prev = m->first->next = 0;

return m;

}

Pertama, periksa apakah blok yang diberikan sudah cukup untuk menyimpan sebuah HMALLOC dan chunk awal sebesar minimal 1 byte, jangan lupa beserta header HCHUNKnya. Jika tidak, fungsi ini harus mengembalikan error.

if(size <= sizeof(HMALLOC) + sizeof(HCHUNK))

return 0;

Letakkan HMALLOC di bagian paling depan dari blok. Lengkapi juga isi tiap fieldnya. Setelah itu chunk pertama (m->first) juga akan dibuat tepat setelah header HMALLOC.

m = (HMALLOC *) addr;

m->first = (HCHUNK*) ((ulong)addr + sizeof(HMALLOC));

m->size = size;

Lalu atur semua nilai field dari HCHUNK untuk chunk pertama. Tentu saja, chunk ini harus dalam keadaan bebas(state = 0). Ukuran chunk akhirnya diketahui dari ukuran argumen size yang dikurangi dengan ukuran header HMALLOC dan ukuran header HCHUNK pertama.

m->first->magic = CMAGIC;

m->first->state = 0;

m->first->size = size - sizeof(HMALLOC) – sizeof(HCHUNK);

Masih HCHUNK pertama kali, jadi, biarkan field next dan prev kosong dulu.

m->first->prev = m->first->next = 0;

Terakhir, kembalikan pointer ke struktur HMALLOC valid yang sudah dibuat. Karena HMALLOC berada di awal blok, alamat HMALLOC yang berhasil dibuat bisa dipastikan == argumen addr. Nantinya, pointer ini akan dijadikan parameter saat alokasi, sehingga alokator tahu, blok mana yang harus diproses dan dimana ia harus menemukan chunk-chunk nya.

return m;