Halka Arabellek ve Kuyruklar

Önceki ders bir düğümün iki işaretçiden aynı anda görüldüğü ortak sınıfını ölçtü: değişiklik ne zaman okunursa okunsun oradaydı, çünkü paylaşılan nesne kalıcıydı. Bu ders farklı bir yapıyla farklı bir sınıfı ölçüyor: bir üretici bir değeri bir arabelleğe yazıyor, bir tüketici onu okuyor — ama okuma bir alma işlemi, bir bakma değil. Değer bir kez okunduktan sonra arabellekte kalmıyor; ikinci bir okuma boş döner. Bu davranış dört sınıftan aktarım’ı tanımlıyor: değer bir aracıdan geçiyor ve bir okuyucuya ulaşıyor, ama o okuyucudan sonra kalıcı bir görünürlüğü yok.

Halka Arabellek: Sabit Kapasiteli Yazma ve Okuma

Arabellek dört elemanlık sabit bir dizi tutuyor; bas bir sonraki okumanın, son bir sonraki yazmanın index’ini, sayi dolu eleman sayısını taşıyor. halka_yaz arabellek doluysa yazmıyor ve 0 döndürüyor; halka_oku arabellek boşsa okumuyor ve 0 döndürüyor. Her ikisi de başarılıysa 1 döndürüyor.

// halka.h — sabit kapasiteli halka arabellek
#ifndef HALKA_H
#define HALKA_H

#define HALKA_KAPASITE 4

struct Halka {
    int veri[HALKA_KAPASITE];
    int bas;
    int son;
    int sayi;
};

void halka_hazirla(struct Halka *h);
int halka_yaz(struct Halka *h, int deger);
int halka_oku(struct Halka *h, int *hedef);

#endif

// halka.c — halka arabellegin gerceklemesi
#include "halka.h"

void halka_hazirla(struct Halka *h) {
    h->bas = 0;
    h->son = 0;
    h->sayi = 0;
}

int halka_yaz(struct Halka *h, int deger) {
    if (h->sayi == HALKA_KAPASITE) {
        return 0;
    }
    h->veri[h->son] = deger;
    h->son = (h->son + 1) % HALKA_KAPASITE;
    h->sayi = h->sayi + 1;
    return 1;
}

int halka_oku(struct Halka *h, int *hedef) {
    if (h->sayi == 0) {
        return 0;
    }
    *hedef = h->veri[h->bas];
    h->bas = (h->bas + 1) % HALKA_KAPASITE;
    h->sayi = h->sayi - 1;
    return 1;
}

Bir Değerin Arabellekten Tam Bir Kez Geçmesi

Üç değer sırayla yazılıyor, sonra sırayla okunuyor. Sıra korunuyor (ilk yazılan ilk okunuyor), ama asıl ölçüm son iki satırda: aynı değeri ikinci kez okumaya çalışmak boş dönüyor, çünkü değer birinci okumada arabellekten alındı, orada bırakılmadı.

// bir_kez_gecis.c — uc deger yazilip okunuyor, sonra arabellek bos kaliyor
#include <stdio.h>
#include "halka.h"

int main(void) {
    struct Halka h;
    halka_hazirla(&h);

    halka_yaz(&h, 10);
    halka_yaz(&h, 20);
    halka_yaz(&h, 30);

    int deger = 0;
    halka_oku(&h, &deger);
    printf("%s %d\n", "ilk okunan deger", deger);
    halka_oku(&h, &deger);
    printf("%s %d\n", "ikinci okunan deger", deger);
    halka_oku(&h, &deger);
    printf("%s %d\n", "ucuncu okunan deger", deger);

    int basari = halka_oku(&h, &deger);
    printf("%s %d\n", "dorduncu okuma basarili mi", basari);
    printf("%s %d\n", "dorduncu okumadan sonra deger degisti mi", (int)(deger == 30));

    return 0;
}

ilk okunan deger 10
ikinci okunan deger 20
ucuncu okunan deger 30
dorduncu okuma basarili mi 0
dorduncu okumadan sonra deger degisti mi 1

VY4. halka_oku’nun imzası (int halka_oku(struct Halka *h, int *hedef)) bir işaretçinin kim tarafından bırakılacağını söylemediği gibi, aldığı değerin arabellekte kalıp kalmayacağını da söylemiyor — bunu belirleyen h->sayi = h->sayi - 1 satırı, gövdenin kendisi. Üç değer sırayla (10, 20, 30) çıkıyor, çünkü bas her okumada bir ilerliyor ve arabellek ilk giren ilk çıkan sırasını koruyor. Dördüncü çağrı 0 döndürüyor çünkü sayi sıfıra düştü; hedef’e hiçbir şey yazılmadığı için deger bir önceki çağrıdan kalan 30’u taşımaya devam ediyor — bu, deger’in kendisinin değişmediğinin kanıtı, arabellekte yeni bir değer olduğunun değil. Sınıf aktarım: her değer tam bir okuyucuya ulaştı ve o okuyucudan sonra arabellekte bir izi kalmadı; ortak sınıfından farkı burada — orada paylaşılan nesne okunduktan sonra da duruyordu, burada okunan yer boşalıyor.

Üretici ile Tüketicinin Sırayla Çalışması

Yazma ve okuma birbirine karışabiliyor: iki yazma, bir okuma, bir yazma daha, iki okuma. Bu, üretici ile tüketicinin aynı arabelleği farklı hızlarda kullandığı gerçek durumu taklit ediyor. Arabellek en fazla dört eleman tutabildiği için üçüncü yazmadan önceki okuma yer açıyor.

// karisik_sira.c — yazma ve okuma cagrilari ic ice
#include <stdio.h>
#include "halka.h"

int main(void) {
    struct Halka h;
    halka_hazirla(&h);
    int deger = 0;

    halka_yaz(&h, 1);
    halka_yaz(&h, 2);
    halka_oku(&h, &deger);
    printf("%s %d\n", "iki yazmadan sonraki okuma", deger);

    halka_yaz(&h, 3);
    halka_oku(&h, &deger);
    printf("%s %d\n", "uc yazmadan sonraki ikinci okuma", deger);
    halka_oku(&h, &deger);
    printf("%s %d\n", "uc yazmadan sonraki ucuncu okuma", deger);

    int basari = halka_oku(&h, &deger);
    printf("%s %d\n", "dorduncu okuma basarili mi", basari);

    return 0;
}

iki yazmadan sonraki okuma 1
uc yazmadan sonraki ikinci okuma 2
uc yazmadan sonraki ucuncu okuma 3
dorduncu okuma basarili mi 0

VY5. Yazma ve okuma çağrıları ne sırayla iç içe geçerse geçsin, her okuma en eski henüz okunmamış değeri veriyor — bu, bas’ın yalnız okumada ilerlemesinin, son’un yalnız yazmada ilerlemesinin sonucu. İkinci koşum birinciyle aynı üç değeri (bu kez 1, 2, 3) aynı sırayla üretiyor, ama aralarına bir yazma daha girmiş olması sonucu değiştirmiyor: arabellek her an en fazla dört eleman tutabiliyor ve üçüncü yazmadan önceki okuma yer açtığı için taşma hiç gerçekleşmiyor. Bir değerin ne zaman yazıldığı ile ne zaman okunduğu arasındaki bu esneklik, aktarımın ikinci bir özelliği: üretici ile tüketici aynı hızda çalışmak zorunda değil, aralarındaki arabellek bir tampon görevi görüyor — ama kapasitenin üzerinde yazmaya çalışmanın ne olacağı (okunmamış bir değerin üzerine yazılması) bu dersin konusu değil; o soru gözlenmeyen sınıfını ölçen bir sonraki dersin.

Kuyruk: Sınırsız Kapasitede Aynı İlke

Halka arabellek sabit kapasiteli; kuyruk aynı ilk-giren-ilk-çıkan sırasını bağlı düğümlerle, kapasite sınırı olmadan uyguluyor. kuyruk_ekle sona bir düğüm ekliyor, kuyruk_cikar baştaki düğümü çıkarıp değerini döndürüyor ve düğümü bırakıyor — okunan değer burada da kuyrukta kalmıyor.

// kuyruk.h — bagli dugumlerle sinirsiz kapasiteli kuyruk
#ifndef KUYRUK_H
#define KUYRUK_H

struct KuyrukDugumu {
    int deger;
    struct KuyrukDugumu *sonraki;
};

struct Kuyruk {
    struct KuyrukDugumu *bas;
    struct KuyrukDugumu *son;
};

void kuyruk_hazirla(struct Kuyruk *k);
void kuyruk_ekle(struct Kuyruk *k, int deger);
int kuyruk_cikar(struct Kuyruk *k, int *hedef);

#endif

// kuyruk.c — kuyruk islemlerinin gerceklemesi
#include <stdlib.h>
#include "kuyruk.h"

void kuyruk_hazirla(struct Kuyruk *k) {
    k->bas = NULL;
    k->son = NULL;
}

void kuyruk_ekle(struct Kuyruk *k, int deger) {
    struct KuyrukDugumu *yeni = malloc(sizeof *yeni);
    if (yeni == NULL) {
        return;
    }
    yeni->deger = deger;
    yeni->sonraki = NULL;
    if (k->son == NULL) {
        k->bas = yeni;
    } else {
        k->son->sonraki = yeni;
    }
    k->son = yeni;
}

int kuyruk_cikar(struct Kuyruk *k, int *hedef) {
    if (k->bas == NULL) {
        return 0;
    }
    struct KuyrukDugumu *eski = k->bas;
    *hedef = eski->deger;
    k->bas = eski->sonraki;
    if (k->bas == NULL) {
        k->son = NULL;
    }
    free(eski);
    return 1;
}

// kuyruk_gecisi.c — kuyruktan cikan deger de bir kez ulasiyor
#include <stdio.h>
#include "kuyruk.h"

int main(void) {
    struct Kuyruk k;
    kuyruk_hazirla(&k);

    kuyruk_ekle(&k, 100);
    kuyruk_ekle(&k, 200);

    int deger = 0;
    kuyruk_cikar(&k, &deger);
    printf("%s %d\n", "kuyruktan ilk cikan deger", deger);
    kuyruk_cikar(&k, &deger);
    printf("%s %d\n", "kuyruktan ikinci cikan deger", deger);

    int basari = kuyruk_cikar(&k, &deger);
    printf("%s %d\n", "bos kuyruktan cikarma basarili mi", basari);

    return 0;
}

kuyruktan ilk cikan deger 100
kuyruktan ikinci cikan deger 200
bos kuyruktan cikarma basarili mi 0

VY6. Kuyruk, halka arabellekten farklı bir bellek modeli kullanıyor — sabit bir dizi yerine her eleman kendi ayrılmış düğümünde duruyor ve kuyruk_cikar düğümü okuduktan sonra bırakıyor (free(eski)). Ama ölçülen sınıf aynı: her değer tam bir çağrıya ulaşıyor ve o çağrıdan sonra kuyrukta bir izi kalmıyor. Kapasite sınırının olmaması (kuyruk_ekle her zaman başarılı, malloc başarısız olmadıkça) aktarım sınıfını değiştirmiyor; yalnız halka arabellekteki “dolu” durumunu ortadan kaldırıyor.

Dolulukta Reddet ya da Ez Politikası

halka_yaz dolu arabellekte yazmayı reddediyor. Ama bazı üretici/tüketici düzenlerinde en yeni değer en eski değerden daha önemlidir — bu durumda dolulukta reddetmek yerine en eski elemanın üzerine yazmak istenir. İki politika da aynı struct Halka üzerinde çalışabiliyor; farkları yalnız dolulukta ne yaptıklarında.

// halka_ez.h — dolulukta en eskiyi ezen yazma politikasinin bildirimi
#ifndef HALKA_EZ_H
#define HALKA_EZ_H

#include "halka.h"

int halka_yaz_ez(struct Halka *h, int deger);

#endif

// halka_ez.c — dolulukta en eskiyi ezen yazma politikasinin gerceklemesi
#include "halka_ez.h"

int halka_yaz_ez(struct Halka *h, int deger) {
    if (h->sayi == HALKA_KAPASITE) {
        h->bas = (h->bas + 1) % HALKA_KAPASITE;
    } else {
        h->sayi = h->sayi + 1;
    }
    h->veri[h->son] = deger;
    h->son = (h->son + 1) % HALKA_KAPASITE;
    return 1;
}

// doluluk_politikasi.c — reddet ve ez politikalarinin karsilastirilmasi
#include <stdio.h>
#include "halka_ez.h"

int main(void) {
    struct Halka h;
    halka_hazirla(&h);

    halka_yaz(&h, 10);
    halka_yaz(&h, 20);
    halka_yaz(&h, 30);
    halka_yaz(&h, 40);

    int reddedildi_mi = halka_yaz(&h, 50);
    printf("%s %d\n", "dolu arabellege reddet politikasiyla yazma sonucu", reddedildi_mi);

    int ez_sonucu = halka_yaz_ez(&h, 99);
    printf("%s %d\n", "dolu arabellege ez politikasiyla yazma sonucu", ez_sonucu);

    int hedef;
    for (int i = 0; i < HALKA_KAPASITE; i++) {
        halka_oku(&h, &hedef);
        printf("%s %d\n", "ez sonrasi sirayla okunan deger", hedef);
    }

    return 0;
}

dolu arabellege reddet politikasiyla yazma sonucu 0
dolu arabellege ez politikasiyla yazma sonucu 1
ez sonrasi sirayla okunan deger 20
ez sonrasi sirayla okunan deger 30
ez sonrasi sirayla okunan deger 40
ez sonrasi sirayla okunan deger 99

VY15. İki politika da dolu arabellekte farklı bir seçim yapıyor ama ikisi de deterministik: halka_yaz dolulukta hiçbir şey değiştirmeden 0 dönüyor — 50 değeri yapıya hiç girmiyor. halka_yaz_ez ise bas‘ı bir ileri kaydırıp en eski elemanın (10) durduğu index’in üzerine yazıyor; 10 hiçbir okumaya ulaşmadan kayboluyor. Bu, dört sınıftan gözlenmeyen’i tanımlıyor: değer yapıya girdi ama hiçbir okuyucuya ulaşmadan üzerine yazıldı. Reddedilen 50 ile ezilen 10 arasındaki fark önemli — 50 hiç yazılmadı, 10 yazıldı ve sonra kayboldu; ikisi de sonunda okunamıyor ama farklı nedenlerle.

Sınırlayıcı Ölçüm

Bir okuma işlevinin imzası, okuduğu değerin kaynakta kalıp kalmayacağını söylemiyor. int halka_oku(struct Halka *h, int *hedef) ile int liste_toplam(const struct Dugum *bas) (önceki ders) aynı ailede: ikisi de bir yapıyı okuyor. Ama biri okuduğu değeri yapının içinde bırakıyor (liste kalıcı), öteki okuduğu değeri yapıdan çıkarıyor (arabellek boşalıyor). Bu fark parametre tiplerinde, dönüş tipinde, hatta işlev adında görünmüyor; yalnız gövdenin sayi’yi azaltıp azaltmadığına bakılarak ya da art arda iki çağrı yapılıp sonuçları karşılaştırılarak ölçülebiliyor — tıpkı bu derste yapıldığı gibi.

Özet

• Halka arabellek sabit kapasiteli bir dizide, kuyruk bağlı düğümlerde sınırsız kapasitede aynı ilk-giren-ilk-çıkan sırasını uyguluyor.
• Bir değer okunduktan sonra arabellekte ya da kuyrukta kalmıyor; ikinci bir okuma ya da çıkarma boş dönüyor — sınıf aktarım.
• Aktarımın ortak’tan farkı: ortakta paylaşılan nesne okunduktan sonra da duruyor, aktarımda okunan yer boşalıyor ve değer bir daha okunamıyor.
• Üretici ile tüketicinin yazma/okuma sırası iç içe geçebilir; arabellek aralarında bir tampon görevi görüyor.
• Dolulukta reddetme ile en eskiyi ezme iki ayrı politika; reddedilen değer yapıya hiç girmiyor, ezilen değer ise girip hiçbir okumaya ulaşmadan kayboluyor — bu ikincisi gözlenmeyen sınıfı tanımlıyor.
• Bir okuma işlevinin okuduğu değeri kaynakta bırakıp bırakmadığı imzada görünmüyor; yalnız gövde okunarak ya da art arda iki çağrı karşılaştırılarak ölçülebiliyor.

Sonraki Adım

Bu derste bir değerin bir kez okunup arabellekten çıktığını ölçtük. Bir sonraki ders, Karma Tabloları, farklı bir soruyla ilerliyor: bir anahtarla saklanan bir değer, aynı anahtarla tekrar tekrar okunduğunda hep aynı sonucu mu veriyor, yoksa okuma sırasında bir kopyası mı üretiliyor? Orada ölçülen sınıf kopya: tablodan okunan değer, tablonun kendi kopyası değil, çağıranın aldığı bağımsız bir kopya.