Tampilkan postingan dengan label Algoritma. Tampilkan semua postingan
Tampilkan postingan dengan label Algoritma. Tampilkan semua postingan

Kamis, 01 Juni 2017

Pengertian Spinlock dan Implementasinya

Multitasking adalah tantangan baru bagi programmer sistem operasi. Ada banyak macam resource yang harus digunakan oleh semua thread, namun jumlahnya terbatas, dan tidak mungkin diakses bersamaan. Untuk itu, masing-masing thread harus dapat diatur agar dapat mengaksesnya secara bergiliran secara sinkron.

Dalam hal ini, synchronization primitives adalah metode yang perlu diimplementasikan dalam sebuah sistem operasi. Synchronization primitives yaitu sebutan untuk metode yang dapat menjamin seluruh task dalam sistem multitasking agar dapat berjalan secara sinkron dalam pengaksesan sebuah resource.
 
void putchar(int chr){
   ...
}

void print(char * str){
   while (* str){
      putchar(*str);
      str++;
   }
}

Kode di atas adalah contoh sederhana, dimana programmer harus mulai mempertimbangkan untuk mengimplementasikansynchronization primitive. Bayangkan jika dua task mengakses print() secara hampir bersamaan dalam sistem multitasking. Belum sempat salah satu task mencetak satu per satu karakter dari string, tiba-tiba terjadi task switch ke task lain yang juga ingin menggunakan fungsi print().

task 1:
print (“hello”);
task 2:
print (“world”);

Tanpa sinkronisasi, bisa jadi yang akan tampil di layar terlihat kacau. Misalnya saja, apabila setiap baru saja mencetak sebuah karakter, terburu terjadi task switch, mungkin akan tampil seperti ini.


hweolrllod
Spinlock adalah salah satu metode sinkronisasi dengan menerapkan lock. Contohnya pada fungsi print() yang sudah dimodifikasi di bawah ini. Selama fungsi print() diakses oleh salah satu task, print_lock akan tetap bernilai 1. Task lain yang perlu mengakses print() wajib menunggu hingga task sebelumnya menyelesaikan print dan mengembalikan print_lock sehingga bernilai 0.

char print_lock;
void print(char * str){
   acquire_spinlock(&print_lock);
   while (* str){
      putchar(*str);
      str++;
   }
   release_spinlock(&print_lock);
}

Task yang lebih dahulu memanggil print() akan memanggilacquire_spinlock(). Fungsi ini akan meng-set variabel print_lock = 1 apabila print_lock masih bernilai 0, lalu segera melanjutkan eksekusi. Task lain yang berjalan bersamaan namun sedikit tertinggal, akan mengalami peristiwa busy-waiting ketika memanggil acquire_spinlock(), karena print_lock masih di-set bernilai 1 oleh task sebelumnya. Busy-waiting akan terus berlangsung hingga task sebelumnya memanggil release_spinlock(), sehingga meng-set print_lock = 0.

Algoritma
Acquire Spinlock:
1. Tunggu hingga lock bernilai 0.
2. Jika lock sudah 0, set lock = 1.

Release Spinlock:
1. Set lock = 0.

Implementasi
Sederhananya, acquire_spinlock() bisa saja ditulis dengan kode C semacam ini:
void acquire_spinlock(char * lock ){
   while (* lock != 0){
      //do nothing
      //busy-waiting
   }
   * lock = 1;
}

Akan tetapi, dalam dunia nyata, kode di atas jauh kurang efektif. Apalagi dalam keadaan thread yang cukup padat. Ini karena jika diuraikan, kode while() akan diterjemahkan compiler menjadi serangkaian instruksi assembly yang rumit.

tes:
cmp BYTE PTR [print_lock], 0
jne tes
mov BYTE PTR [print_lock], 1

Misalnya, katakanlah terdapat 3 task yang sama-sama melakukan acquire. Task 1 baru saja melepas print_lock. Sayangnya, setelah itu task 2 dan task 3 secara bersamaan baru saja selesai melakukan instruksi CMP yang memberikan sinyal bahwa print_lock sudah terlepas, namun sama-sama pula terjadi task switch sebelum menjalankan instruksi JNE. Akhirnya, task 2 dan task 3 lolos dari lock lalu mengakses fungsi print() secara bersamaan.
Kondisi seperti itu dapat dihindari dengan memanfaatkan atomic operation, yaitu dengan memanfaatkan instruksi assembly yang dapat melakukan acquire tanpa harus melakukan instruksi pembandingan (CMP) ataupun testing terlebih dahulu. Dalam arsitektur intel, ini bisa dilakukan dengan instruksi XCHG yang diinputkan melalui inline assembly.

tes:
mov al, 1
xchg BYTE PTR [print_lock], al
cmp al,1
je tes

Selama XCHG menghasilkan nilai 1, sudah diketahui bahwa print_lock masih dikuasai task lain, namun jika 0, artinya task sudah berhasil mengambil alih lock. Meskipun terjadi task switch antar banyak task, semuanya tidak akan dapat melewati taktik XCHG.

inline unsigned char _atomic_xchg8(unsigned char* lock, unsigned char x ){
   asm volatile("xchg %1, %0":"=r" (x):"m"(*(volatile unsigned char *)lock),"0" (x):"memory");
   return x;
}

inline void acquire_spinlock(unsigned char *lock){
   while ( 1){
      if ( _atomic_xchg8(lock, 1)== 0) return ;
      while (* lock != 0){
         asm("pause");
      }
   }
}

inline void release_spinlock(unsigned char *lock){
   * lock = 0;
}
Read more

Jumat, 03 Februari 2017

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


Bagian terakhir ini akan membahas tentang pembebasan memori ( Free() ). Fungsi free() sejatinya hanya mengubah field state kembali ke 0. Tapi karena tanggung jawabnya, alokator harus mengurus masalah fragmentasi internal. Ia harus memeriksa field bebas lain di sebelah kiri dan kanan chunk yang sedang dibebaskan. Apabila bebas, salah satu atau keduanya harus segera digabungkan.

int Free(void *addr){
HCHUNK *c,*p,*n;
c = (HCHUNK*)((ulong)addr - sizeof(HCHUNK));
if(c->magic != CMAGIC) return ­1;
if(c->state == 0) return ­2;
c->state = 0;
p = c->prev;
n = c->next;
if(n){
if(n->state == 0){
c->size += sizeof(HCHUNK) + n->size;
c->next = n->next;
if(n->next) n->next->prev = c;
}
}

if(p){
if(p->state == 0){
p->size += sizeof(HCHUNK) + c->size;
p->next = c->next;
if(c->next) c->next->prev = p;
}
}
return 0;
}

Proses pembebasan dan penggabungan dibantu dengan 3 buah variabel pointer

HCHUNK.
HCHUNK *c,*p,*n;

c merujuk pada HCHUNK dari alamat chunk yang sedang dibebaskan; p dan n merujuk ke chunk sebelah kiri (previous) dan kanan (next) dari chunk yang sedang dibebaskan.

Argumen addr dari fungsi ini berupa pointer chunk yang telah dialokasikan oleh Malloc() sebelumnya. Untuk mengetahui HCHUNK dari alamat tersebut, kurangi alamat addr dengan ukuran struktur HCHUNK.

c = (HCHUNK*)((ulong)addr - sizeof(HCHUNK));

Pastikan alamat chunk dari argumen addr adalah benar. Jika salah, dapat dipastikan nilai magic dari HCHUNK tidak akan bernilai valid. Jika jelas validitasnya, lanjut periksa juga field state. Jangan sampai kita menyiakan waktu untuk membebaskan chunk yang sudah bebas (state == 0).

if(c->magic != CMAGIC) return ­1;
if(c->state == 0) return ­2;

Cukup sudah. Sekarang bebaskan chunk ini.

c->state = 0;

2 langkah terakhir adalah prosedur penggabungan. Ambil pointer kedua chunk sampingnya dari field prev dan next.

p = c->prev;
n = c->next;

Mulai penggabungan dari chunk sebelah kanan. Dan lanjutkan dengan chunk sebelah kiri.

if(n){
if(n->state == 0){
c->size += sizeof(HCHUNK) + n->size;
c->next = n->next;
if(n->next) n->next->prev = c;
}
}
if(p){
if(p->state == 0){
p->size += sizeof(HCHUNK) + c->size;
p->next = c->next;
if(c->next) c->next->prev = p;
}
}

Nilai n dapat bernilai 0 apabila chunk yang baru saja dibebaskan adalah chunk terakhir. Jadi sebelum memeriksa state dari chunk n, pastikan dulu n bukan 0. Penggabungan dilakukan dengan 2 tahapan; update ukuran chunk pada field size chunk c dengan menambahkannya ukuran dari chunk n. Karena HCHUNK untuk n tidak terpakai lagi, kita juga menambahkan ukuran sejumlah ukuran struktur HCHUNK ( sizeof(HCHUNK) ) pada ukuran chunk c yang baru; kedua, update field next dari c, sehingga link antar chunk akan menjadi seperti di bawah ini.

Lakukan juga hal sama pada p dengan cara seperti sebelumnya.



Debugging
Untuk keperluan pengecekan, saya sudah buatkan fungsi dumper sederhana untuk mencetak properti semua chunk dalam HMALLOC. Kode ini self-explained, ya.

void HMallocDump(HMALLOC *h){
HCHUNK *c = h->first;
printf("HMALLOC Dump:\n");
while(c){
printf("HCHUNK size 0x%x state %x at 0x%x \
   prev 0x%x next 0x%x\n",
c->size,c->state,c, c->prev,c->next);
c = c->next;
}
}


Contoh Hasil
Hasil berikut adalah contoh implementasi Malloc() di kernel JauraOS.
https://github.com/irvanherz/jaura



Read more

Kamis, 02 Februari 2017

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


Virtual memory dapat dialokasikan untuk menyediakan wilayah memori dalam bentuk blok berukuran tetap, membuat kemungkinan fragmentasi semakin kecil. Sayangnya, banyak program cenderung mengalokasikan kebutuhan memori untuk program mereka dalam jumlah banyak, namun dengan ukuran yang relatif jauh lebih kecil dari ukuran blok page virtual memori. Oleh karena itu, diperlukan mekanisme alokasi yang dapat memenuhi kebutuhan tersebut, agar sistem dapat menjaga efisiensi penggunaan memori.

Jika masih bingung dengan latar beakang tulisan ini, coba sedikit mengingat kapan terakhir kali anda membuat program mengalokasikan memori, Biasanya, kita menggunakan malloc() dan free() di lingkungan pemrograman C. Selain itu, di sistem operasi Windows juga tersedia fungsi API yang serupa dengan kedua API library C tersebut, yaitu HeapAlloc() dan HeapFree(). Fungsi semacam itulah yang akan kita coba implementasikan di sini.

Memori perlu memiliki sistematika alokasi, sehingga apabila suatu program sedang menggunakan wilayah memori untuk menangani tugas tertentu, wilayah tersebut akan lebih aman dari campur tangan pekerjaan dari task lain. Meski demikian, masih ada kemungkinan thread lain dapat menggunakan memori yang sudah diklaim sebelumnya, baik itu sengaja atau tidak sengaja. Oleh karena itu perlu juga adanya mekanisme untuk selalu memeriksa kemungkinan buruk tersebut. Tanpa alokasi memori, masing-masing thread dapat menggunakan memori dengan bebas. Masalahnya mulai timbul ketika sudah mulai banyak memori yang digunakan. Celah fragmentasi akan sulit dilacak.


Mekanisme alokasi memori biasanya dilakukan dengan implementasi linked list. Cara sederhana bisa dilakukan dengan membuat linked-list yang menghubungkan setiap potongan (chunk) daerah memory, mulai awal hingga akhir. Sistem yang lebih profesional bahkan membuat 2 macam linked-list untuk memisahkan daerah memori yang sudah dialokasi dan daerah yang bebas. Hal ini membuat proses alokasi semakin cepat.

Sebuah header berada di bagian awal dari setiap chunk, menyediakan informasi instan mengenai kondisi dan properti chunk, seperti ukuran, status chunk dan beberapa hal spesifik lain terkait alokasi memori. Di dalamnyalah linked list akan disematkan. 


Meski keberadaan linked list membantu, ada sedikit masalah yang perlu diatasi saat proses pembebasan memori. Meski pembebasan memori bisa dilakukan dengan cukup mengubah variabel state pada header, linked list masih masih terpasang untuk menghubungkan blok bebas(free blocks) yang harusnya tiada lagi. Lihat ilustrasinya seperti berikut.

1. Kita bayangkan awal layout chunk memori seperti berikut, dimana blok merah
adalah area teralokasi.

2. Program membebaskan beberapa blok memori, sehingga bisa dialokasikan kembali.

3. Program meminta alokasi memori ke sistem; Alokator mencari daerah bebas yang pas dengan ukuran permintaan. Ternyata pencarian gagal, karena tiap header menunjukkan blok dalam ukuran kecil. Padahal, seharusnya beberapa wilayah yang baru saja dibebaskan cukup untuk menampung request yang sedang diminta.

Oleh karena itu, saat proses pembebasan memori, alokator juga bertanggung jawab mengatasi fragmentasi internal semacam ini dengan mengusahakan penggabungan blok (joining). Jika alokator mampu menangani pembebasan memori dengan baik, maka kenampakannya akan seperti berikut.

***
Masalah belum sampai disitu. Jika hanya dengan singly-linked list, alokator hanya dapat melihat dan memeriksa posisi blok di sebelah arah kanan saja. Ini menyebabkan penggabngan blok kurang maksimal. Contoh kasusnya adalah seperti ilustrasi berikut.

1. Layout awal.

2. Program meminta pembebasan sebuah blok memori. Untungnya saat ini, alokator belum memerlukan penggabungan chunk memori.

3. Program meminta pembebasan memori kembali. Sepertinya alokator harus melakukan penggabungan sekarang. Dia menemukan sebah blok bebas disebelahnya.

Ups, alokator tidak dapat membebaskan memori dengan sempurna. Ini karena
singly linked list tidak mempunyai link pointer ke arah kiri (left/previous). Untuk
sekian kalinya, request memori gagal, alokator tidak mengetahui area kosong yang
sebenarnya masih cukup.

Dari adanya permasalahan tersebut, maka tulisan ini akan lebih banyak membahas mekanisme alokasi memori dengan basis sebuah doubly-linked list.
Read more

Selasa, 31 Januari 2017

Membuat Game HTML5 : Cara Kerja Multi-Player Game (Komunikasi Antara Client Dan Server)


Awalnya terasa terheran ketika melihat semua komputer dapat melihat wajah tampilan yang sama. Padahal, pemainnya ada puluhan sampai ratusan! Bagaimana bisa server melayani klien sebanyak itu dengan biaya pribadi?

Baru-baru ini saya paham, ternyata bayangan mekanisme komunikasi antara klien dan server pada game multiplayer salah tergambar di otak saya. Jadi, bagaimana sebenarnya mekanisme komunikasi antara server dan para kliennya?

Awalnya saya pikir gambar yang muncul di monitor adalah gambar yang sudah diproses di server, lalu dikirim ke kita. Padahal, sebenarnya semua gambar tersebut diproses langsung oleh komputer kita masing-masing. Biar lebih jelas, kita mulai dengan melihat ilustrasi mulai dari awal kita mengklik tombol start pada game multiplayer.

Semua data pemain berada di server dan juga klien, misalnya nama, koordinat pemain dan beberapa aktivitas yang sedan dilakukan oleh pemain. Namun, server mungkin tidak akan membagikan data spesifik yang bersifat privat bagi tiap pemain.

Ketika pemain datang, data pemain baru tersebut akan ditambahkan ke server. Selanjutnya server mengirimkan data pemain lain yang sedang aktif dan sudah memulai terlebih dulu kepadanya. Tidak sampai disitu, pemain lain juga harus tahu, bahwa ada pemain baru, ya. Jadi, server juga perlu mengirim data pemain baru kepada para klien lama-nya.

Sementara itu, proses kontrol player dan semua event yang terjadi dalam permainan juga akan dibagikan secara menyeluruh.

Server sama sekali tidak memproses gambar apapun. Tugas server di sini hanyalah menyiarkan event yang terjadi oleh setiap player. Misalkan kita menekan tombol DOWN, yang terjadi adalah:
- Update data posisi player
- Kirim pemberitahuan ke server
- Update gambar tampilan
- Server menyebarkan pemberitahuan ke yang lain
- Pemain lain mengupdata data posisi kita di komputer mereka
- Update gambar tampilan mereka

Sampai disini sudah cukup terbayang, bukan?
Yap, bagus. Jika sudah, nanti kita akan mulai belajar membuat game multi-player pertama kita. Eits, tapi mimin selesaikan dulu ya, tutorial Node.js dan Socket.io nya.
Read more

Rabu, 21 Desember 2016

Contoh Doubly-Linked List Dengan C Beserta Penjelasannya

doubly linked list illustration

Deretan data dapat disimpan dalam bentuk array. Hal ini mustahil dilakukan jika data tersebar acak (noncontiguous) dalam memori. Array dapat menyimpan data berderet dalam ukuran dan jumlah yang tetap. Jika ingin menyimpan data dalam jumlah yang bervariasi, sebuah array harus disiapkan dengan menyediakn ruang kosong untuk menampung hingga beberapa jumlah elemen.

Apabila jumlah elemen yang akan disimpan dalam deretan tersebut tidak bisa diramalkan, tentu ini akan menjadi masalah. Misalnya array kosong yang disediakan sebanyak 10, namun ternyata sistem harus menyimpan 20 elemen. Saat ini terjadi, sistem bisa mengalokasikan deretan array kosong lagi. Kebalikannya, jika array kosong ada 10, namun sistem hanya perlu menambahkan 2 elemen, ini tak akan menjadi masalah besar. Namun, bagaimanapun manajemen memori harus dilakukan sebaik-baiknya.

Daripada menyimpan elemen dalam linked list, sistem lebih baik mengalokasikan memori cukup sebesar ukuran elemen yang perlu disimpan. Lokasi memori hasil alokasi tentu akan acak (noncontiguous), sehingga setiap elemen perlu dilengkapi dengan pointer untuk menunjukkan dimana alamat memori lokasi elemen sebelumnya dan sesuadahnya disimpan.

doubly linked list vs array


Setiap elemen/node dalam list akan selalu memiliki 2 pointer untuk menunjukkan lokasi elemen sebelum dan sesudahnya; belakang dan depannya; atau sebelah kiri dan kanannya. Oleh karena itu, setiap elemen akan diwakili oleh sebuah DLIST_NODE yang memiliki field pointer untuk menunjukkan lokasi elemen lainnya.

typedef struct _DLIST_NODE{
struct _DLIST_NODE *next;
struct _DLIST_NODE *prev;
int data;
} DLIST_NODE;

Untuk memudahkan pencarian, sebuah data struktur diperlukan sebagai parameter  pengelompok deretan elemen. Kita akan menyebutnya sebagai DLIST.

typedef struct _DLIST {
DLIST_NODE *first;
DLIST_NODE *last;
} DLIST;

Field first akan selalu menujuk pada elemen pertama dalam sebuah list, dan field last menunjuk pada elemen paling terakhir. Saat tidak ada satupun data tersimpan dalam list, kedua field ini harus bernilai 0. Ketika satu buah elemen pertama dimasukkan, kedua field ini akan menunjuk ke satu elemen yang sama, yaitu elemen baru itu sendiri –elemen pertama dan terakhir–.


Menambahkan data ke list
Elemen dapat dimasukkan dalam beberapa metode, antara lain adalah sebagai berikut.
- tambahkan di posisi paling awal (prepend)
- tambahkan di posisi paling akhir (append)
- sisipkan sebelum salah satu elemen (insert before)
- sisipkan sesudah salah satu elemen (insert after)

Prepend
Proses prepend harus diawali dengan memeriksa apakah ada elemen dalam kelompok DLIST. Apabila kita menemukan DLIST→first bernilai 0, elemen baru harus diperlakukan sebagai node pertama sekaligus terakhir. Sehingga first dan last pada DLIST akan menunjuk ke elemen baru. Lalu field prev dan next dari elemen baru harus diset 0 untuk menunjukkan bahwa tidak ada element lain.

elemen pertama = elemen terakhir = elemen baru
elemen baru→sebelumnya = 0
elemen baru→sesudahnya = 0

Namun, jika ditemukan satu atau lebih elemen dalam grup DLIST, yaitu ketika terindikasi DLIST→first ≠ 0; elemen baru harus dikaitkan dengan benar. Elemen pertama diubah menjadi elemen sesudahnya (elemen kedua), lalu elemen baru diubah peranannya sebagai elemen pertama dalam grup DLIST.

elemen baru→sebelumnya = 0
elemen baru→sesudahnya = elemen pertama
elemen pertama→sebelumnya = elemen baru
elemen pertama = elemen baru

HINT : Gambarlah elemen-elemen yang mengalami perubahan dalam secarik kertas untuk memudahkan visualisasi.


Kode:
void DListPrepend(DLIST *list,DLIST_NODE *newNode){
if(!list->first){
list->first = list->last = newNode;
newNode->prev = newNode->next = 0;
}
else{
newNode->prev = 0;
newNode->next = list->first;
list->first->prev = newNode;
list->first = newNode;
}
}

Append
Tidak berbeda jauh dengan prepend, append juga harus memeriksa apakah grup DLIST sudah memiliki elemen. Hal ini dilakukan untuk menentukan apakah elemen baru harus diperlakukan sebagai elemen pertama dan terakhir. Jika bukan:

elemen baru→sesudahnya = 0
elemen baru→sebelumnya = elemen terakhir
elemen terakhir→sesudahnya = elemen baru
elemen terakhir = elemen baru

Kode:
void DListAppend(DLIST *list,DLIST_NODE *newNode){
if(!list->last){
list->last = newNode;
list->first = newNode;
newNode->prev = 0;
newNode->next = 0;
}
else {
newNode->next = 0;
newNode->prev = list->last;
list->last->next = newNode;
list->last = newNode;
}
}

Insert before
Sebelum menyisipkan elemen ke posisi sebelum elemen target, perlu dipastikan apakah elemen target itu ada. Jika tidak, mungkin lebih baik kita menempatkan elemen baru ke posisi awal (prepend).

Jika tidak, lakukan prosedur berikut.

elemen baru→sesudahnya = elemen target
Jika elemen target = elemen pertama:
elemen pertama = elemen baru
Jika bukan:
elemen baru→sebelumnya = elemen target→sebelumnya
elemen target→sebelumnya→sesudahnya = elemen baru
elemen target→sebelumnya = elemen baru

Kode:
void DListInsertBefore(DLIST *list,DLIST_NODE *node,DLIST_NODE *newNode){
if(!node) //nothing? prepend!
{
if(!list->first){
list->first = newNode;
list->last = newNode;
newNode->prev = 0;
newNode->next = 0;
}
else{
newNode->prev = 0;
newNode->next = list->first;
list->first->prev = newNode;
list->first = newNode;
}
return;
}
newNode->next = node;
if(!node->prev){
list->first = newNode;
}
else {
newNode->prev = node->prev;
node->prev->next = newNode;
node->prev = newNode;
}
}

Insert after
Tidak perlu dijelaskan detail. Prosedur ini murni kebalikan dari prosedur insert before. Jika anda sudah paham prosedur tersebut, tentu sangat mudah membaca kode implementasi di bawah ini.

Kode:
void DListInsertAfter(DLIST *list,DLIST_NODE *node,DLIST_NODE *newNode){
if(!node){ //nothing? append!
if(!list->last){
list->last = newNode;
list->first = newNode;
newNode->prev = 0;
newNode->next = 0;
}
else {
newNode->next = 0;
newNode->prev = list->last;
list->last->next = newNode;
list->last = newNode;
}
return;
}
newNode->prev = node;
if(!node->next){
list->last = newNode;
}
else {
newNode->next = node->next;
node->next->prev = newNode;
node->next = newNode;
}
}


Menghapus elemen dari list
Dalam kasus ini, elemen perlu diperiksa apakah ia berperan sebagai elemen pertama. Jika demikian, elemen pertama akan digantikan perannya oleh elemen sesudahnya. Apabila kondisi ini tidak ditemukan, field next dari “elemen sebelum elemen target” harus diarahkan ke “elemen sesudah elemen target”.

Kemudian, elemen target juga dipastikan peranannya sebagai elemen terakhir atau bukan. Jika elemen terakhir, peranan elemen terakhir dgantikan dengan elemen sebelum elemen target. Atau, jika tidak, field prev dari “elemen sesudah elemen target” harus diarahkan pada “elemen sebelum elemen target”.

Untuk menghindari human error saat penggunaan linked list; terakhir, elemen yang baru dilepas sebaiknya dihapus referensi prev dan next nya.

Jika elemen target = elemen pertama:
   elemen pertama = elemen target→sesudahnya
Bukan:
   elemen target→sebelumnya→sesudahnya = elemen target→sesudahnya

Jika elemen target = elemen terakhir:
   elemen terakhir = elemen target→sebelumnya
Bukan:
   elemen target→sesudahnya→sebelumnya = elemen target→sebelumnya

elemen target→sebelumnya = elemen target→sesudahnya = 0

Kode:
void DListUnlink(DLIST *list,DLIST_NODE *node){
if(!node->prev)
list->first = node->next;
else
node->prev->next = node->next;
if(!node->next){
list->last = node->prev;
}
else
node->next->prev = node->prev;
}


Contoh Penggunaan
Dari beberapa fungsi yang telah ditampilkan di atas, kita belum dapat melihat bagaimana keseluruhan fungsi tersebut dengan baik, sebelum mempraktekkannya sendiri. Oleh karena itu, berikut saya sertakan code snippet sederhana :

void DListDump(DLIST *list){
DLIST_NODE *node = list->first;
while(node){
printf("node at %x data: %i prev: %x next: %x\n",node,node->data,node->prev,node->next);
node = node->next;
}
}

DLIST dlist = {0,0};
int main(){
char action;
DLIST_NODE *node;
DLIST_NODE *node_addr;
int node_data;

first:
printf("[a]ppend [p]repend Insert a[f]ter Insert [b]efore [d]ump [r]emove [q]uit:");
scanf("\n%c",&action);
switch (action){
case 'd':
DListDump(&dlist);
break;
case 'a':
node = malloc(sizeof(DLIST_NODE));
printf("Node data:");
scanf("\n%i",&node_data);
node->data = node_data;
DListAppend(&dlist,node);
break;
case 'p':
node = malloc(sizeof(DLIST_NODE));
printf("Node data:");
scanf("\n%i",&node_data);
node->data = node_data;
DListPrepend(&dlist,node);
break;
case 'f':
node = malloc(sizeof(DLIST_NODE));
printf("Node addr (hex):");
scanf("\n%x",&node_addr);
printf("Node data:");
scanf("\n%i",&node_data);
node->data = node_data;
DListInsertAfter(&dlist,node_addr,node);
break;
case 'b':
node = malloc(sizeof(DLIST_NODE));
printf("Node addr (hex):");
scanf("\n%x",&node_addr);
printf("Node data:");
scanf("\n%i",&node_data);
node->data = node_data;
DListInsertBefore(&dlist,node_addr,node);
break;
case 'r':
node = malloc(sizeof(DLIST_NODE));
printf("Node addr (hex):");
scanf("\n%x",&node_addr);
DListUnlink(&dlist,node_addr);
free(node_addr);
break;
case 'q':
goto last;
break;
default:
printf("Invalid option\n");
goto first;
break;
}
goto first;

last:
return 0;
}


Bagaimana hasilnya?
Wow, cool...

linked list


Read more

Rabu, 09 November 2016

Implementasi Red-Black Tree Dalam C – Part 4

Sesuai dengan janji saya sebelumnya, maka untuk tema red-black tree chapter ke empat ini saya akan tunjukkan contoh implementasi red-black tree insertion  secara lengkap. Untuk kalian yang membaca tulisan ini dalam keperluan memenuhi tugas kuliah, jangan abaikan penjelasan part sebelumnya, ya. Copy paste saja tidak cukup, lho.

Kode di luar penjelasan yang telah diberikan sebelum-sebelumnya, di sini saya sertakan kode sederhana untuk keperluan debugging. Kalian tinggal passing argumen ke pointer struktur RBTree, lalu kalian bisa memeriksa nilai masing-masing node dengan mudah.

void RBTreeDump(RBTree *tree){
 char action;
 RBTreeNode *node = tree->root;
 first:
 printf("node data %x color %x left %x right %x\n",
  node->data,
  node->colour,node->left,node->right);
 printf("[u]p [l]eft [r]ight [q]uit:");
 scanf("\n%c",&action);
 switch (action){
  case 'u':
   node = node->parent;
   break;
  case 'l':
   node = node->left;
   break;
  case 'r':
   node = node->right;
   break;
  case 'q':
   goto last;
   break;
  default:
   goto first;
 }
 goto first;
 
 last:
 return;
}

Untuk memeriksa apakah nilai masing-masing node sudah di-fix up dengan benar, masukkan juga data yang baru saja kamu input di...

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

Bandingkan setiap node dengan hasil dump.
Dan, inilah source code lengkap yang sudah kamu tunggu-tunggu. Jangan lupa pesan saya yang di awal, ya.

#include <stdlib.h>
#include <stdio.h>

typedef struct _RBTreeNode {
 int     data;
 int     colour; //0 for black
 struct _RBTreeNode *parent;
 struct _RBTreeNode *left;
 struct _RBTreeNode *right;
} RBTreeNode;

typedef struct RBTree {
 RBTreeNode *root;
} RBTree;


void rotate_left(RBTree *tree, RBTreeNode *x){
 RBTreeNode *y = x->right;
 x->right = y->left;
 
 if(y->left) y->left->parent = x;
  y->parent = x->parent;
 if(x->parent == 0)
  tree->root = y;
 else if(x == x->parent->left)
   x->parent->left = y;
  else
   x->parent->right = y;
 x->parent = y;
 y->left = x;
}

void rotate_right(RBTree *tree, RBTreeNode *x){
 RBTreeNode *y = x->left;
 x->left = y->right;
 
 if(y->right) y->right->parent = x;
  y->parent = x->parent;
 if(x->parent == 0)
  tree->root = y;
 else if(x == x->parent->left)
   x->parent->left = y;
  else
   x->parent->right = y;
 x->parent = y;
 y->right = x;
}

#define IS_RED(x) ((x) ? ((x->colour) ? 1:0):0) 
void insert_fixup(RBTree *tree, RBTreeNode *z){
 RBTreeNode *y;
 while(IS_RED(z->parent)){
  if(z->parent == z->parent->parent->left){
   y = z->parent->parent->right;
   if(IS_RED(y)){
    z->parent->colour = 0;
    y->colour = 0;
    z->parent->parent->colour = 1;
    z = z->parent->parent;
   }
   else{
    if(z == z->parent->right){
     z = z->parent;
     rotate_left(tree,z);
    }
    z->parent->colour = 0;
    z->parent->parent->colour = 1;
    rotate_right(tree,z->parent->parent);
   }
  }
  else { //parent at right
   y = z->parent->parent->left;
   if(IS_RED(y)){
    z->parent->colour = 0;
    y->colour = 0;
    z->parent->parent->colour = 1;
    z = z->parent->parent;
   }
   else {
    if(z == z->parent->left){
     z = z->parent;
     rotate_right(tree,z);
    }
    z->parent->colour = 0;
    z->parent->parent->colour = 1;
    rotate_left(tree,z->parent->parent);
   }
  }
 }
 tree->root->colour = 0;
}

void RBTreeInsert(RBTree *tree, RBTreeNode *z){
 RBTreeNode *y = 0;
 RBTreeNode *x = tree->root;
 
 z->left = 0;
 z->right = 0;
 
 while (x != 0){
  y = x;
  if(z->data < x->data)
   x = x->left;
  else
   x = x->right;
 }
 z->parent = y;
 if(y == 0){
  tree->root = z;
 }
 else{
  if(z->data < y->data)
   y->left = z;
  else {
   y->right = z;
  }
 }
 z->colour = 1; //RED
 insert_fixup(tree,z);
}

void RBTreeDump(RBTree *tree){
 char action;
 RBTreeNode *node = tree->root;
 first:
 printf("node data %d color %d left %x right %x\n",
  node->data,
  node->colour,node->left,node->right);
 printf("[u]p [l]eft [r]ight [q]uit:");
 scanf("\n%c",&action);
 switch (action){
  case 'u':
   node = node->parent;
   break;
  case 'l':
   node = node->left;
   break;
  case 'r':
   node = node->right;
   break;
  case 'q':
   goto last;
   break;
  default:
   goto first;
 }
 goto first;
 
 last:
 return;
}


RBTree rbt = {0};
int main(){
 char action;
 RBTreeNode *node;
 int node_data;
 
 first:
 printf("[i]nsert [d]ump [u]nlink [q]uit:");
 scanf("\n%c",&action);
 switch (action){
  case 'd':
   RBTreeDump(&rbt);
   break;
  case 'i':
   node = (RBTreeNode*)malloc(sizeof(RBTreeNode));
   printf("Node data:");
   scanf("\n%d",&node_data);
   node->data = node_data;
   RBTreeInsert(&rbt,node);
   break;
  case 'q':
   goto last;
   break;
  default:
   printf("Unknown cmd\n");
   goto first;
   break;
 }
 goto first;
 
 last:
 return 0;
}
Hasilnya akan terlihat seperti ini, lho.



Akhirnya, kita telah menyelesaikan chapter tentang red-black tree insertion dengan baik. Untuk operasi red-black tree lain, seperti deletion dan searching; tunggu saja. Just keep in touch with Komputoo.
See you again.
Read more