ÜST SEVİYE STRINGLER Baris Simsek simsek at enderunix.org http://www.enderunix.org/simsek 2007, Istanbul Tanım Stringler, son karakteri NULL olan karakter dizileridir. Bu haliyle işimizi gör- melerine karşın iki önemli sakıncası vardır: 1. String boyunu hesaplamak için NULL aranır. Bu da string boyuna bağlı olarak zaman alır. 2. Standart kütüphaneler stringlerin değişebileceğini varsayar. Dolaysıyla stringleri kullanan veya çağıran fonksiyonlar string sonuçları için alan tahsis etmek zorundadır. Halbuki stringleri değiştirmeyen uygulamalarda bu tahsislerin pek çoğu gereksizdir. Bu makalede bu iki sakıncayı bertaraf edecek bir string gösterimi tanımlayaca- ğız. String boyları sabit bir zamanda hesaplanacak. Bunun için string ve boyutu- nu beraber tutacağız. Bellek tahsisi ise yalnız gerektiğinde olacak. Tanımlaya- cağımız gösterimde stringler değiştirilemez olacaktır ve içerisinde NULL karak- terler içerebilecekler. Bu işlemleri yapabilemek için bazı fonksiyonlar gelişti- receğiz. Bu fonksiyonlar tanımlayacağımız gösterim ile C stilinde stringler ara- sında dönüşümü sağlayacaktır. Bu fonksiyonlar stringler için tanımlayacağımız a- rayüzün tek bedeli olacaktır. Bundan böyle NULL ile sonlandırılmış normal stringlere string, arayüzünü tanım- layacağımız stringlere ise üst seviye string diyeceğiz. Arayüz Tanımlayacağımız arayüze Text ismini vereceğiz. Text arayüzü bir stringi iki bi- leşen ile gösterecektir: 1. String boyu 2. Stringin ilk karakterini gösteren bir işaretçi. typedef struct Text { int len; const char *str; } Text; str işaretçisi ile gösterilen string NULL ile sonlandırılmamıştır. Tanımını ya- parken de bahsettiğimiz gibi içerisinde NULL içerebilmektedir. Standart C kütüp- hanesinde string NULL içermez; NULL görüldüğü yerde string sonlandırılır. Text arayüzündeki string dışarıdan bir müdahale ile değiştirilemez olacağından stringler üzerinde işlem yapmak için arayüzümüze uygun fonksiyonlar tanımlayaca- ğız. Herhangi bir hata durumunda negatif len değeri veya NULL str değeri ile bu- nu bildireceğiz. Ayrıca fonksiyonlarımız gerekli gördüklerinde kendileri bellek tahsis edecek, kullanacak ve serbest bırakacatır. Text arayüzünü kullananların bellek tahsis etmesine (alloc) veya belleği serbest bırakmasına (free) gerek yoktur. Böyle bir istek çalışma zamanında hata oluşmasına neden olacaktır. Fonksiyonlar: extern Text TPut(const char *str); extern char *TGet(char *str, Text s, int size); extern Text TBuild(const char *str, int len); TPut, normal str stringini yüksek seviye stringe atar ve yeni oluşturulan yüksek seviye stringin tanımlayıcısını geri döndürür. Hata durumunda yüksek str NULL olarak set edilir. TGet, s ile verilen üst seviye stringi, str[0..size-2] ile verilen stringe kop- yalar ve str stringini geri döndürür. size değerinin len+1'den küçük olup olma- dığı hata olasılığına karşı kontrol edilecektir. Eğer str NULL ise TGet size'ı gözardı eder. len+1 byte bellek tahsis eder ve str stringini bu alana kopyalar. Dönüş değeri olarak bu alanın başlangıcını karakter işaretçisi olarak verir. TBuild ise verilen sabit bir stringi kullanarak üst seviye bir string oluşturur. Ve bu stringin kendisini -işaretçisini değil- geri döndürür. TPut, üst seviyeli stringi kendi oluşturur, onun için alanı kendisi tahsis eder. TBuild ise alan tahsisini kendisi yapmaz. Sadece biçimlenmemiş olarak verilen veriyi biçimlendi- rip döndürür. static char copyright[] = "(c) 2007, EnderUNIX SDT @ Tr"; ... Text msg = TBuild(copyright, sizeof(copyright)-1); Uygulama En basit fonksiyonlarımızdan birisi TPut olacak. String için alan tahsisi yapmak üzere alloc() fonksiyonunu çağırır. Text TPut(const char *str) { Text text; assert(str); text.len = strlen(str); text.str = memcpy(alloc(text.len), str, text.len); return text; } strcpy() yerine memcpy() kullanma nedenimiz, strcpy() 'nin string sonuna NULL karakter koymasıdır. Tanımladığımız yüksek seviyeli string arayüzünde null son- landırma kavramı yoktur. TGet ise yukardakinin tersi olacak. Yüksek seviyeli stringten stringi alıp nor- mal stringe kopyalayacaktır. Eğer normal string NULL ise öncelikle onun için a- lan tahsis edilir ve string kopyalamadan sonra null ile sonlandırılır. char *TGet(char *str, Text s, int size) { assert(s.len >= 0 && s.str); if (str == NULL) str = malloc(s.len + 1); else assert(size >= s.len + 1); memcpy(str, s.str, s.len); str[s.len] = '\0'; return str; } String içerisinde bulunan null karakterleri de kopyalayabilmek için strcpy() ye- rine memcpy() kullandık. Hatırlanacağı üzere standart C kütüphanesinde string i- çinde null karakter olamaz. Çünkü null görüldüğünde string sonlanır. strcpy() gi- bi standart kütüphane fonksiyonları da null görüklerinde işlemini bitirir. Text TBuild(const char *str, int len) { Text text; assert(str); assert(len >= 0); text.str = str; text.len = len; return text; } Bu fonksiyonlar istediğimiz manevraları yapabilmemiz için yeterli değildir. Bu nedenle ilave fonksiyonlar tanımlamalıdır. Standart C kütüphanesinde bulunan strcpy(), strdup(), strstr(), strchr(), strcat(), strcmp() gibi fonksiyonların yüksek seviyeli string kütüphanesi için yeniden yorumlanmasına ihtiyaç vardır. Text *TDup(Text s); Text *TCat(Text s1, Text s2); int TCmp(Text s1, Text s2); Text TReverse(Text s); Tüm bunları yazarken yukarıda tanımladığımız arayüzü göz önünde bulundurmak ge- rekir. Arayüzde hatırlanması gereken en önemli iki nokta şunlardır: 1. Yüksek seviyeli stringler içerisinde null karakter içerebilir ve null karak- ter ile sonlanmak zorunda değil. 2. Yüksek seviyeli stringler basit veri yapısı olmayıp hem stringi hem de boyu- tunu tutan özel bir yapıdır. Bu makalede bu fonksiyonların içeriğini yazmayacağız. Makale sadece okuyucuya fikir vermek için kaleme alınmıştır. Bellek Yönetimi Yüksek seviyeli stringler için gerekli bellek yönetimi işlemlerini tanımladığı- mız arayüz yerine getirecektir. Text arayüzü kendi bellek tahsis ve belleği ser- best bırakma fonksiyonlarına sahip olacaktır. Yüksek seviyeli stringleri bağlı liste halindeki büyük alanların içerisinde sak- layacağız. Bu büyük ayrılmış alanlara chunk ismini vereceğiz: static struct chunk { char *avail; char *eoc; struct chunk *next; }; struct chunk head = {NULL, NULL, NULL}; *current = &head; avail, chunk içerisindeki serbest alanın başını gösterir. Bellek tahsisi artık bu chunk içerisindeki serbest alanlardan yapılacaktır. eoc, chunk'ın sonuncu alanından bir sonraki alanı gösterir. End-of-chunk anla- mında olup chunk'ın bittiği noktayı gösterir. İlk chunk'ın başlangıç noktasını yani kendi özel belleğimizin başlangıcını gös- termek üzere head tanımlandı. current her zaman üzerinde işlem yapılan chunk'ı gösterir. İlk başta chunk'ın en başını gösterir. next ise bir sonraki chunk'ı gösterir. head -->+------+ current -->+------+ next -->+------+ |XXXXXX| |XXXXXX| | | |XXXXXX| |XXXXXX| | | |XXXXXX| |XXXXXX| | | |XXXXXX| |XXXXXX| | | |XXXXXX| ... avail -->+------+ | | |XXXXXX| | | | | |XXXXXX| | | | | |XXXXXX| | | | | |XXXXXX| | | | | |XXXXXX| | | | | +------+ eoc -->+------+ +------+ Chunk 1 Chunk n Chunk n+1 Stringler için bellek ihtiyacımızı tanımladığımız bu chunk'lardan sağlayacağız. static char *Calloc(int len) { assert(len >= 0); if (current->avail + len > current->eoc) { current = alloc(sizeof(*current) + 10*1024 + len); current->avail = (char *) (current + 1) current->eoc = current->avail + 10*1024 + len; current->next = NULL; } current->avail = current->avail + len; return current->avail - len; } Eğer s chunk'ın sonunda yer alan üst seviye bir string ise: s.str + s.len = current->avail olacaktır. Sondaki stringin kendisinden sonra (yani len kadar ileride) avail ya- ni boş alanın olması doğal sonuçtur. Bu eşitlik ileride kullanabileceğimiz aşa- ğıdaki isatend makrosunu tanımlayabileceğimizi gösterir. Bu makro verilen string in chunk'a yazılan son string olup olmadığını ve chunk'ta n byte boş alan olup olmadığını test eder. Bu makro ileride yazacağımız fonksiyonlarda işimize çok yarayacaktır. #define isatend(s, n) ((s).str+(s).len == current->avail \ && current->avail + (n) <= current->eoc) Örnek olarak TReverse dfonksiyonunu yazalım. Bu fonksiyon verilen stringin ka- rakterlerini ters sırada döndürür. Text TReverse(Text s) { Text t; char *p; int i = s.len; assert(s.len >= 0 && s.str); if (s.len == 0) return NULL; else if (s.len == 1) return s; else { t.len = s.len; t.str = p = Calloc(s.len); while (--i >= 0) *p++ = s.str[i]; return t; } } Tek karakterlik bir stringin tersi kendisine eşittir. İki stringi birleştiren TCat fonksiyonu şu şekilde olacaktır: Text TCat(Text s1, Text s2) { Text t; char *p; assert(s1.len >= 0 && s1.str); assert(s2.len >= 0 && s2.str); if (s1.len == 0) return s2; if (s2.len == 0) return s1; /* Zaten birleşik durumda iseler */ if (s1.str + s1.len == s2.str) { s1.len = s1.len + s2.len; return s1; } t.len = s1.len + s2.len; /* Chunk'daki son string ise */ if (isatend(s1, s2.len)) { t.str = s1.str; memcpy(Calloc(s2.len), s2.str, s2.len); } else { t.str = p = Calloc(s1.len + s2.len); memcpy(p, s1.str, s1.len); memcpy(p + s1.len, s2.str, s2.len); } return t; } Eğer s1 stringi chunk'a yerleştirilen son string ise ve chunk'ın sonunda s2.len kadar boş alan var ise s1 ve s2'yi birleştirmek, yalnızca s2 için bellek tahsis edip onu s1'in hemen ardından yerleştirmekten ibaret olacaktır. Bitirirken Bu makale size yüksek seviyeli stringlerle ilgili tüm işlemleri yapabilecek ka- dar fonksiyon sunmamaktadır. Arayüz için gerekli teori oluşturulmuş ve en önemli işlemler için gereken kodla yazılmıştır. Bu nedenle yüksek seviyeli stringlerle kodlama yapmak isteyen geliştiricinin ihtiaç duyacağı tüm fonksiyonları yazması gerekmektedir. En iyisi bunları bir defa yazıp kütüphane haline getirmektir. Da- ha sonra gerektikçe bu kütüphane bağlanarak (link) fonksiyonlara erişilir. Burada anlatılan yüksek seviyeli stringler SNOBOL4 (Griswold 192) 'te kullanılan stringlere benzemektedir. SNOBOL4 string işleme için yazılmış olup burada anla- tılan arayüze benzer bir string yapısına zaten sahiptir. Kaynaklar C Interfaces and Implementations, David R. Hanson, Addison-Wesley 0-201-49841-3