Gömülü Proje - Single Linked List

removeLast metodu
Şöyle yaparız.

function removeLast() {

  // Edge case when there is only 1 element in the queue.
  if (head == tail) {                   // O(1)
    value = head.value                // O(1)
    head = null                       // O(1)
    tail = null                       // O(1)

    return value                      // O(1)
  }

  // Searching for the new tail.
  newTail = head                        // O(1)
  while (newTail.next != tail) {        // O(n)
    newTail = newTail.next            // O(1)
  }

  value = tail.value                    // O(1)
  newTail.next = null                   // O(1)
  tail = newTail                        // O(1)

  return tail                           // O(1)    
}

Gömülü Proje - BitStream

Giriş
Gömülü projelerde o kadar çok bitlerden oluşan veri var ki bir tane BitStream sınıfı her zaman lazım oluyor.

Dahili Metodlar

BoundaryCheck metodu
Okuma veya yazma işleminden önce bellek alanında taşma olmadığını kontrol etmek içindir.

Bellek Metodları
GetBuffer metodu
BitStream'e verilen belleği döndürür.

GetBufferSize metodu
BitStream'e verilen belleğin büyüklüğünü döndürür.

Konum Metodları

SetBitPosition metodu
Belirtilen bit konumuna gitmeli. Örneğin 15. bit'e git denilebilmeli. Kendi içine kaçıncı byte ve bit olduğunu hesaplamalı. Bu konumdan itibaren okuma yazma işlemi yapılabilir. Bellek alanını aşılıyorsa exception atmalı.

GetBytePosition metodu
Özellikle yazma işleminden sonra kaç byte yazıldığını almak için kullanılır.

SetBytePosition metodu
Belirtilen byte konumuna gitmeli. Bu konumdan itibaren okuma yazma işlemi yapılabilir. Bellek alanını aşıyorsa exception atmalı.

Okuma Metodları

PadBits metodu
Bazen bit alanlarını byte'a tamamlamak gerekir.

ReadNBits metodu
Belirtilen değer kadar bit okur. Okuma konumu bellek alanı dışına taşarak bir sonraki byte'a taşabilir. Bu bir sorun değil.

ReadNBytes metodu
Bit mesajları payload içerebildiği için 8 byte'a kadar bir değer okumak mümkün olmalı. Tabi işleme başlamadan önce okuma konumu byte başını göstermeli.

WriteNBytes metodu
Bit mesajları payload içerebildiği için 8 byte'a kadar bir değer yazmak mümkün olmalı. Tabi işleme başlamadan önce yazma konumu byte başını göstermeli.

Gömülü Proje - Fixed Rate Timer

Giriş
Amacımız belli bir süreden önce (örneğin 30 saniye) yenilenmesi gereken nesneleri yönetmek. Eğer belirtilen süre içinde yenilenmezse o nesne için kurulan TimerHandler nesne için belirtilen TimerKey ile çağrılır. Eğer nesne yenilenirse timer bir kere daha 30 saniye sonrasına kurulur.

FixedRateTimerManager nesnesi Component veya Manager içinde yaşar. Bu nesneler ana thread tarafından çalıştırılır. Böylece timer nesnesi de sürülmüş olur.
Main Thread-->Component -->Manager -->FixedRateTimerManager

Tasarım
TimerKey, ITimerHandler, FixedRateTimer, FixedRateTimerManager sınıflarından oluşur.

TimerKey
3 tane unsigned int alan bir yapı olsun. Bu yapı tasarımdaki önemli noktalardan birisi.

Bazı tasarımlarda, timer key alanı olmadan çalışır. Örneğin amaç 30 saniyede bir liste üzerinde yürümektir. Bu amaç için key alanı saklamak gerekmez.

Bazı tasarımlarda, her timer nesnesinin bir ID alanı vardır. Timer tetiklenince ID bilgisini de verir. Kod yazan kişi ID üzerinden haricen yönettiği state bilgisine erişir ve bir işlem yapar. Ancak bu da zor bir tasarım çünkü timer ile haricen tutulan "map" veri yapısını birlikte yönetmek gerekir.

Benim seçtiğim yöntemde timer tetiklenirken state bilgisini de sağlıyor. Böylece her şey daha kolay bir hale geliyor. State her zaman int tipi olduğu için sorun olmadı.

Bir diğer yöntem ise state bilgisini handler içinde saklamak. Handler yaşam döngüsü heap üzerinde olabilir. Timer bitince handler da silinebilir. Ancak gömülü ortamda malloc/new yapmamak için bu yöntemi seçmedim.

ITimerHandler
ITimerHandler isimli bir arayüzümüz olsun. Bu arayüzün TimerKey nesnesi alan OnTimeOut metodu olsun.
void OnTimeOut (TimerKey& key);

FixedRateTimer
Intrusive bir yapı. pNextTimer, pPrevTimer,isPeriodic,ExpirationTime,isActive alanları olsun.

FixedRateTimerManager
FixedRateTimerManager isimli bir sınıfımız olsun. Bu sınıf tüm FixedRateTimer nesnelerini iki veri yapısı kullanarak yönetsin.

İlk yapı bir "double linked list" olsun. Bu yapı nesneleri absolute timeout zamanına göre sıralı saklasın. Yani bitme zamanı en yakın olan nesne en başta,  bitme zamanı en uzak olan nesne ise en sonda olsun. Absolute time kullanabilmek için sistemde sürekli artan bir monotonic zaman kaynağı olması yeterli.

İkinci yapı ise bir "hashmap" olsun. Belirtilen TimerKey değerine sahip TimerHandler nesnesi silinebilsin, tekrar kurulabilsin.

FixedRateTimerManager belirtilen bir TimerKey nesnesi için bir TimerHandler eklerken her iki yapıyı da kullansın.

FixedRateTimerManager yönettiği belli bir TimerKey için yeniden kurma imkanı sağlasın. Yeniden kurulan timer listenin en sonuna taşınır. Aslında burası en kritik nokta. Tüm nesnelerin aynı timeout süresini kullandığını bildiğim için liste içinde dolaşarak timer nesnesini doğru yere yerleştirmekle uğraşmıyorum. Yani liste kendiliğinden sıralı oluyor.
Elimdeki liste şöyle olsun

A (30) , B (60) , C (60)

Şu anki saat ise 30 olsun. A nesnesi tekrar kurulunca liste şöyle olur.

B (60), C (60), A (90)

FixedRateTimerManager (TimeSpan& rate);
Kullanılacak sabit süre belirtilir.

void RunTimers () metodu çağrılınca liste dolaşılır.  Biten FixedRateTimer nesnesi tetiklenir. Eğer nesne periyodik ise bir sonraki tetiklenme zamanı aranir ve listenin en sonuna taşınır. Eğer nesne "single shot" ise listeden silinir.

bool StopTimer (TimerKey & key);
Belirtilen anahtar değerine sahip timer listeden silinir.

bool StartOrRescheduleTimer (TimerKey & key, ITimerHandler* pHandler);
Eğer belirtilen timer yoksa yeni bir timer başlatılır. Varsa 30 saniye sonrası için tekrar kurulur.

Gömülü Proje Örnekleri

Giriş
Gömülü projelerde kullanılan bazı tasarımları aşağıda not aldım. Bu tasarımların en önemli özellikleri dinamin bellek kullanmamaları.

Unique_Ptr
Gömülü projelerde std::unique_ptr kullanamıyoruz. Bu yüzden kendi sınıfımızı yazmak gerekiyor. Aşağıda küçük bir örnek var.

Object<---(has)ObjectPtr<-----------(has)ObjectPtrList
                            |
                            |
                ObjectPoolTable
                            |
                            |
                    ObjectPool

ObjectPtr::Assign ()
ObjectPtr::Release () metodları Object nesnesini ait olduğu ObjectPool'a geri verir. ObjectPool array, list, set, tree gibi herhangi bir veriyapısı üzerine kurulu olabilir.


Parser

Konuyu Gömülü Proje Örnekleri - Parser başlıklı yazıya taşıdım.

Transmission
Konuyu Gömülü Proje Örnekleri - TransmissionQueue başlıklı yazıya taşıdım.

Reception
Aşağıda zarflanan mesajları açarak internal yapılara çeviren bir tasarım var.

Formatlı mesaj işlemede en önemli adımlardan bir tanesi gelen mesajın hangi mesaj olduğunun belirlenmesi. İşlenecek mesajlar genellikle bir enum ile sıralanırlar. Verinin bir veya daha fazla alanı okunarak, bir tablo vasıtasıyla mesajın kimliği belirlenir.

Mesajlar gerekirse bir Accumalator içinde biriktiriliyor ve daha sonra IMessage dizisi şeklinde kullanılıyorlar.

 

Gömülü Proje - HashMap HashSet

Giriş
Bir çok programlama dilinde HashMap, HashSet gibi veri yapıları hazır geliyor. Gömülü ortamlarda ise bu veriyapılarını kodlamak gerekebiliyor. Aşağıda bu tür veriyapılarını geliştirirken aldığım notlar var

HashMap
Mükemmel hash fonksiyonu olmadığı için iki farklı değerin aynı hash sonucunu üretmesi çok mümkün. Bu durumda Çarpışma Çözümü (Collision Resolution) yapmak gerekiyor. Çözüm olarak iki farklı yöntem yaygınca kullanılıyor. İlki Open Addressing ve Separate Chaining.

OpenAddressing
Bu yöntem lookup tablosu gibi salt okunur veriyapılarında kullanışlı. Eğer bucket dolu ise bir sonraki boş bucket aranır. Kodlaması kolaydır. HashMap bucket büyüklüğü yeterince büyük tutulursa çok fazla çakışma olmayacağı için performansı da iyidir.

Separate Chaining
Bu yöntem eğer veriyapısı salt okunur değilse tercih etmek lazım. Ekleme silme işlemlerini daha iyi yerine getirir. Hash metodunun denk geldiği bucket bir LinkedList tutar. Yeni veri liste üzerinde yürünerek sona eklenir. Çarpışma Çözümü (Collision Resolution) için ikili ağaç (binary tree) kullanılabileceği de yazılı ancak ben hiç denk gelmedim.

HashSet
HashSet -> Buckets ->LinkedList ->ListNode şeklinde Separate Chaining kullanılır. Eğer Object Oriented bir yöntem izlenirse nesnenin HashValue() ve Equals metodları da olması beklenir.

Gömülü Proje - TransmissionQueue

Giriş
TransmissionQueue gönderme amacına göre birçok farklı şekil alabilen bir bileşen. Aşağıda bazı sınıflandırmalarda bulunmaya çalıştım.

Genel Tasarım
TransmissionQueue --(has)--TransmissionList--(has)--TransmissionNode--(has)--Data

TransmissionList bir LinkedList (ortadan silinen kuyruklar için) veya Dequeue (FIFO kuyruklar için) olabilir.

Gönderim Sırasına Göre
Periyodik Kuyruklar
Bir timer XGenerator sınıfını periyodik olarak tetikler. XGenerator TransmissionQueue kuyruğunu baştan sonra dolaşır ve zamanı gelen mesajları gönderir. Bu tür kuyruklar her 2 saniyede bir X gönderilecektir türündeki işler için kullanılır.

FIFO Kuyruklar
Kuyruğun sonuna yerleşen mesaj sırası gelince XGenerator tarafından kuyruktan çekilir ve hemen gönderilir.

Verinin Kopya veya Referans Olarak Kullanım Şekline Göre
Kopya Alan Kuyruk
Bazı kuyruklar eklenen verinin kopyasını alırlar. Böylece veri güncellenirse bir önce hali ile karşılaştırıp gönderim kuralını değiştirmeleri mümkün olur.

Reference Counting Yapan Kuyruk
Bazı kuyruklar reference counting yaparlar. Böylece verinin kopyasını almaya gerek kalmaz. Kuyrukta bekleyen veri değiştirilebilir.

Verinin Serialize Edilmesi
Gönderilecek veri bir XProtocolConverter sınıfına verilerek serialize edilir.

Periyodik Kuyruk aşağıdaki gibi olabilir
XProtocolConverter protocol (channel);
transmissionQueue.Walk (protocol);

FIFO kuyruğun serialize edilmesi aşağıdaki gibi olabilir. Eğer gönderilecek veri yoksa XProtocolConverter veri olmadığını belli eden bir mesaj gönderilir.

XProtocolConverter protocol;
TransmissionItem item = transmissionQueue.PopHead ();
if (item != NULL) {
  protocol.Serialize (stream, item);
}
else {
 protocol.SerializeEmptyMsg (stream);
}
channel.Send (stream);

Örnek
Aşağıda, serialization işlemini ve gönderim kuyruğunu gösteren basit bir tasarım örneği var.

Gönderilmek İstenen Mesajın Alınması
Gönderilmek istenen DomainObject, OutgoingMessageListener tarafından alınır. TransmissionQueue nesnesine verilir. 

Gönderilme Kurallarının Hazırlanması
Bu kuyruk, DomainObject nesnesinin nasıl parçalanması, kaç defa gönderilmesi gerektiğine karar veren bir Scheduler nesnesine verilir. Bu bilgiler TransmissionItem nesnesinde saklanır. 

Gönderme Zamanı
Kuyruğu periyodik olarak dolaş bir thread, gönderme zamanı gelen TransmissionItem nesnesini alır ve serialization işleminden geçirerek, kanaldan gönderir.

Veriyi TranmissionItem nesnesinin içine koyarak veriyi zarflama veya çalışılan platforma göre Big Endian, Little Endian göndermek gibi imkanlara da kavuşabiliriz.