YAZILIM

Linux altında C ve Linked List

Öncelikle Linked List’lerin ne olduğunu inceleyelim. Linked Listler, verileri array haricinde birbirine pointer’lar ile bağlayarak kullandığımız yapılardır.

Pointer kullanılan her dilde linked list’lerin yeri vardır ve temel yapı taşlarından birisidir. Ben cache işlemleri için circular linked listler, queue işlemleri için de doubly linked listler kullanmayı tercih ediyorum.

Linux altında program yazarken, ne tarz bir proje olursa olsun, queue işi için ya da basitinden bir veri tutma ya da hafızada saklama işlemlerinde array kullanmıyorum. Daha hızlı olsa bile “ciddi optimizasyon gerektirmeyen” kod bloklarında, eski DOS’dan kalma alışkanlıkla, data segment’in şişmesi işime gelmiyor.

Her programda kullandığınız bir şeyi, kodun içinde de her defasında yazmak akıl karı olmuyor. Linux kernel’de hazır olması lazım diye bakarken BSD 4.4’den gelme queue.h kütüphanesine ulaştım. Header dosyasının içinde Linux kernel (Kernel’de bir module’de FreeBSD’nin queue.h’si var ama sanırım son patch ile kaldırıldı), Mozilla ve daha birçok projede kullanılan hazır macro’lar var. Glibc ile geliyor. Manual dosyasına baktığımda çok da anlaşılır gelmedi. (… yerine düzgün variable’lı örnek gerekiyor) . Macro’ları ilk bakışta anlamak cidden çok zordur bilirsiniz. Aklıma gcc’nin parametreleri geldi. Son kodu gösteren vardı. gcc -E.

1
2
3
4
5
6
7
8
9
10
11
#include <stdlib.h>
#include <sys/queue.h>
 
struct SayiListe {
int deger;
};
 
int main(int argc, char *argv[])
{
return 0;
}

şimdi bunu bir liste haline nasıl çeviriyoruz ona bakalım.

1
2
3
4
struct SayiListe {
    int deger;
    LIST_ENTRY(SayiListe) sayilar;
    }

şimdi bu macro ne yaptı ona bakalım. gcc -E main.c

1
2
3
4
struct SayiListe {
int deger;
struct { struct SayiListe *le_next; struct SayiListe **le_prev; } sayilar;
};

daha düzenli yazacak olursak;

1
2
3
4
5
6
7
struct SayiListe {
int deger;
struct {
struct SayiListe *le_next;
struct SayiListe **le_prev;
} sayilar;
};

gördüğünüz gibi basit bir linked list structure çıkarmış olduk ortaya.

şimdi single linked list yaptığımız bu listenin head’ini tutmak zorundayız. bunun için de struct tanımlamasının hemen altına,

1
LIST_HEAD(SayiListeHead, SayiListe) sayi_liste_head;

giriyoruz. bunun bize oluşturduğu kod ise

1
struct SayiListeHead { struct SayiListe *lh_first; } sayi_liste_head

buraya kadar tanımlama yaptık. şimdi ise ilk eşitlemeyi yapmak için programımızın main kısmına,

1
2
3
int main(int argc, char *argv[])
    {
    LIST_INIT(&sayi;_liste_head);

giriyoruz. bunun sebebi, head’deki first’in, NULL’a eşitlenmesi gerekmesi. Oluşturduğu koda bakalım..

1
{ (&sayi;_liste_head)->lh_first = ((void *)0); };

fazladan { ları gözünüze takmayın. macro yazarken veri tanımlamalarında standart olmuş bir yapıdır. Template veriler, tanımlayabilmenizi ve kodun hata yapmamasını sağlar.

3 satır kod ile bir veri yapısını single linked list haline çevirdik. Bundan sonraki kullanımı ise 3 macro tanımlaması üzerinden dönmekte,

1
2
3
LIST_INSERT_AFTER(LIST_ENTRY *listelm, TYPE *elm, LIST_ENTRY NAME);
LIST_INSERT_HEAD(LIST_HEAD *head, TYPE *elm, LIST_ENTRY NAME);
LIST_REMOVE(TYPE *elm, LIST_ENTRY NAME);

LIST_INSERT_HEAD ile listenin en başına bir veri ekleyebilirsiniz. Örnek kullanımı ise aşağıdaki gibidir.

1
2
3
4
5
6
struct SayiListe *sayi;
LIST_INIT(&sayi;_liste_head);
 
sayi = malloc(sizeof(*sayi));
sayi->deger = 10;
LIST_INSERT_HEAD(&sayi;_liste_head, sayi, sayilar);

LIST_INSERT_AFTER’da ise listede istenilen bir veriden sonrasına ekleme yapabilirsiniz.
Yukarıdaki örnek üzerinden devam edersek,

1
2
3
4
5
6
7
8
9
10
11
struct SayiListe *sayi,*sayi2;
    LIST_INIT(&sayi;_liste_head);
 
    sayi = malloc(sizeof(*sayi));
    sayi->deger = 10;
    LIST_INSERT_HEAD(&sayi;_liste_head, sayi, sayilar);
 
    sayi2 = malloc(sizeof(*sayi2));
 
    sayi2->deger = 9;
    LIST_INSERT_AFTER(sayi, sayi2, sayilar)

Buraya kadar ekleme işlemlerine baktık. şimdi de silme ve almasına bakalım.

Silme işini LIST_REMOVE yapmakta. en basit kullanımı ise aşağıdaki gibidir. silinecek öğe ve liste verilerek silme işini yapar.

1
LIST_REMOVE(sayi, sayilar);

Biraz daha genişletecek örneğin, olursak listedeki tüm verileri silmek için;

1
2
while (sayi_liste_head.lh_first != NULL)
    LIST_REMOVE(sayi_liste_head.lh_first, sayilar);

diyerek tüm verileri temizleyebiliriz.

Sırayla verileri almak için ise header’da hazır bir macro bulunmamaktadır. Bunun yerine

1
2
for (sayi = sayi_liste_head.lh_first; sayi != NULL; sayi = sayi->sayilar.le_next)
printf(“%d\r\n”, sayi->deger);

şeklinde sırayla hepsi listelenebilir. unutulmaması gereken bir şey var ki single linked listler BSD’de SLIST, linux’da LIST olarak geçer. LIFO çalışır, yani son giren ilk çıkar.

Eger FIFO versiyonunu kullanmak istiyorsanız TAILQ desteği vardır. linux’da onu kullanmanız gerekiyor.

1
2
3
4
5
6
7
TAILQ_ENTRY(TYPE);
    TAILQ_HEAD(HEADNAME, TYPE);
    TAILQ_INIT(TAILQ_HEAD *head);
    TAILQ_INSERT_AFTER(TAILQ_HEAD *head, TYPE *listelm, TYPE *elm, TAILQ_ENTRY NAME);
    TAILQ_INSERT_HEAD(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
    TAILQ_INSERT_TAIL(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
    TAILQ_REMOVE(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);

Komut kullanımları ortalama aynı şekildedir. bariz farkları ise, direk kuyruktan veri alabilirsiniz, direk kuyruğa veri atabilirsiniz. Genel olarak kod bakımından dikkat etmemiz gereken dönüşüm farkı ise Head macro’sunun farkıdır.

1
struct SayilarTailHead { struct SayilarTail *tqh_first; struct SayilarTail **tqh_last;} sayilartail_head;

Peki neden Tail Queue daha yetenekli, daha çok iş yapıyor ve normal LIST ‘leri kullanıyoruz?
Performans ve kod büyüklüğü Tail Queue’de %20 normal LIST’lerden daha yavaş çalışır ve %15 oranında kod boyutunu büyütür. Eğer QUEUE ihtiyacınız yoksa SINGLE LINKED LIST kullanmanız daha avantajlıdır.

Başka bir noktası da eğer performanslı bir linked list ihtiyacınız varsa HASH table’lar ile listi, array’lere bölerek overhead’i yok edebilirsiniz. TAIL kullanmanızın anlamı yoktur zaten list’i küçültmüşsünüzdür.

Ya da başka bir şekilde bir thread ara ara bir array’e bookmark şeklinde imler atabilir. gene tail’e ihtiyacınız yoktur, zaten bir thread devamlı bulmaktadır.

Linux glibc queue.h ile bsd’nin queue.h’si yapı olarak ciddi farklılıklar içerse de mantık olarak aynı düzeydedir. Tekini anlarsanız, diğerini de kullanabilirsiniz. Eğer her iki sistem içinde kodunuzun çalışmasını istiyorsanız queue.h’yi kodunuz içerisine dahil etmeniz çok daha mantıklı olacaktır. Hangisini ekleyeceğiniz ise tamamen kişisel tercih. FreeBSD’ninkini incelerseniz çok daha fazla MACRO tanımlaması bulundurduğunu, bazı kolaylıklar içerdiğini ama yapı olarak fazla bir değişim göstermediğini göreceksiniz.

EKLENTİ: Bazı arkadaşlar “neden illa macro” diye sorup, function’ların bu işi yaparken debugging de yapabileceği gibi avantajları öne sürdüler. Function’lar bu iş için uygun sayılmaz. sebebi de function call’lar bedava değildir. Eğer geçici hafıza ayırma işlemimiz olsaydı alloca sebebiyle function’lar avantaj elde edecekti. Hafıza ayırma işlemimiz olmadığında kodun hızlı çalışması için macro’lar daha mantıklıdır. Compiler daha rahat şekilde eğer -Os verirseniz zaten functional hale getirecektir. ama normal şartlarda hız için çalışacaktır. Debugging konusu ise libc malloc hook kabul etmektedir.

İlgili Makaleler

Bir cevap yazın

E-posta hesabınız yayımlanmayacak.

four × 5 =

Başa dön tuşu