Gömülü Proje - ByteStream

Örnek

Şöyle yaparız

class buffer { 
  std::vector<uint8_t> &data;
  std::vector<uint8_t>::iterator pos;
public:
  buffer(std::vector<uint8_t> &data) 
    : data(data)
    , pos(data.cbegin()) 
  {}

  void read(char *dest, size_t len) {
    std::copy_n(pos, dest, len);        
    pos += len;
  }

  void read(uint16_t &dest) {
    dest = *pos++;
    dest |= *pos++ << 8;
  }
};

Gömülü Proje - HashMap Yazmak

Giriş
Gömülü bir projede hashmap yazmamız gerekti. Hashmap yazmak için gerekli bazı bilgiler şöyle.

Buradaki bilgiler concurrent (eş zamanlılık) olmayan bir HashMap için

Çakışma Collision
Mükemmel hash fonksiyonu olmadığı için anahtarların çakışması durumundan kaçınmak mümkün değildir. Aşağıda çakışma durumunda kullanılabilecek iki yöntemin açıklaması var.

1. Çakışma Durumunda Chaining Yöntemi
Chaining aynı zamanda closed addressing olarak ta anılır. Bucket adresi bir kere bulunduktan sonra tekrar hesaplanmaz. Chain işlemi için farklı veriyapıları tercih edilebilir.

1.1 Separate Chaining With Linked Lists Yöntemi
Bu yöntemde hash veri yapısındaki her eleman içinde liste bulunduran bir array yapısına işaret eder. Çakışma olması durumunda array'deki listeye yeni bir ekleme yapılır.

1.2 Java 8 ve HashMap
Java 8'e kadar olan HashMap çakışmadan kurtulmak için Separate chaining with linked lists yöntemini kullanıyor. Bu yöntemde aynı hash değerine sahip sınıflar liste şeklinde sıralanıyorlar.

Java 8'den sonra ise ise Separate Chaining With Other Data Structures yöntemi benimsenmiş. Linked List'in boyu 8'i geçerse, binary tree veriyapısına geçiyor.

1.3 Guava
Performance of Guava's ImmutableSet.contains sorusunda sürekli çakışmaların yaşanması yüzünden ImmutableSet'in performansının bazı durumlar için çok iyi olmadığını anlatılıyor

2. Çakışma Durumunda Open Addressing Yöntemi
Bu yöntemde hash veri yapısındaki her eleman tek bir array yapısına işaret eder.

Separate Chaining yönteminin aksine array'deki her bir eleman liste değildir. Çakışma durumunda ya array büyütmek ya da array'de yeni bir boşluk bulmak gerekir.

2.1 Open Addressing With Linear Probing Yöntemi
Yeni bir boşluk bulmak için kullanılabilen yöntemlerden birisi ise Linear probing. Yani hash değerini bir sabit değer kullanarak artırmak. Java'daki IdentityHashMap sınıfı bu yöntemi kullanıyor. Açıklaması şöyle

Open addressing means that the key-value pairs are stored in a single array. The index to store a key-value pair is given by the hash code modulo the array size.

Linear probing means that if this array element is already occupied, we use the next array element. And so on, until we have found an empty slot.

3. Çakışma Varsa HashMap Neden O(1) Kabul Edilir?
Çakışmalar yüzünden her hash kullanan veri yapısında bir miktar O(1)'den fazla işlem yapar ancak Amortized Analysis yöntemince zamana yayılan kullanımda limiti alınan denklem sonsuzda O(1)' yakınsar. Bu yüzden O(1) kabul edilir.

Şu şekilde unordered_map ile map arasındaki farkı görmek mümkün. Amortized algortimaları anlamak için buradaki cümle önemli:

Amortized algorithms and data structures usually perform additional house keeping tasks which "amortize" for the performance costs of other operations.

4. Bucket Boyunun Dizisinin Değişmesi - ReHashing
Eğer bucket boyutunu değiştirirsek elemanların hash değerinin tekrar hesaplanarak yeni yerlerine yerleştirmek gerekir, dolayısıyla O(n) bir işlem yapılır.

Büyüme durumunda yeni boyutun (eski boyut * 2) 'nin üstteki en yakın asal sayıya yuvarlanması kullanılabilir.

Gömülü Proje - Parser

Giriş
ParserFacade stack üzerinde yaratılan bir bellek üzerinde yürüyerek, mesajları çıkarıyor ve Message sınıfına atıyor. Mesaj sınıfı şöyle. Sadece veriyi taşır. Veriyi anlamlandırmaya çalışmaz.

Message {
 ushort m_Length;
 byte* m_pData;
}

ParserFacade şöyle

ParserFacade::Parse (byte* pData, Message& m, EnumMessageType messageType) {

  IParser* pParser = ParserFactor::GetParser (messageType);

  byte* pDataStart = pParser->Parse (&length);

  if (pDataStart != NULL) {

    m.SetLength (length);

    m.SetData (pDataStart);

    return true;

  }
  return false;
}

ParserFacade'ı kullanmak için şöyle yaparız

byte* data = //...

Message m;

ParserFacade facade;

while (facade.Parse (data,m)){ 

  ProcessMessage m);

}

Gömülü Proje Linked List

Constructor
List head ve tail için null veya boş node'lar kullanabilir.

private final Node<T> head = new Node<>(null);
private final Node<T> tail = new Node<>(null);
private int size = 0;

public List() {
  head.right = tail;
  tail.left  = head;
}

GetFirst metodu
Şöyle yaparız

Node* rest(){
  Node* nextToHead = head -> right; 
  return nextToHead;
}

GetHead metodu
Şöyle yaparız

Node* pNode = list.GetHead ();
int listSize = list.Size ();
for (int index = 0; index < listSize; index++) {
  MyData* pData = pNode->GetData ();
  if (pData->IsValid ()){

    //...Do something

    pNodex = list.GetNext (pNode);

  }

  else {

    Node* pTemp = pNode;

    pNode = list.GetNext (pNode);

    list.Delete (pTemp);

  }

}

GetHead metodu - Node
Şöyle yaparız.

public static <E> Node<E> GetHead(Node<E> current) {
  Node<E> head = null;
  while (current != null) {
    head = current;
    current = current.left;
  }
  return head;
}

Iterator
C++'taki gibi iterator kullanılmasa bile veriyapısını yöneten sınıfa iteration metodlarını koymak doğru olmaz. Mümkünse ayrı bir iterator sınıfı yazmak daha iyi.

Gömülü Proje - LSB BitStream

Giriş
Bu sınıfı sağdan sola doğru okuma ve yazma işlemi yapar. Çok nadiren de olsa soldan sağa doğru kullanılan BitStream sınıfları da gördüm.

Bit Mask
Açıklaması şöyle

A bit mask is used to mask some bits of a bit field while exposing others.
initial value: 011011001
bit mask.....: 111110000
result value.: 011010000

MASK'lar şöyledir

const unsigned int MASKS      [] = {0,           //0

                                                        0x1,      //1

                                                        0x3,      //2

                                                        0x7,      //3

                                                        0xf,       //4

                                                        0x1f,     //5

                                                        0x3f,     //6

                                                        0x7f,     //7

                                                        0xff,      //8

                                                       }

Header
Şöyle yaparız.

class BitStream {
  uint32_t m_BitPosition;
  uint32_t m_BytePosition;
  uint8_t* m_pBuffer;
  uint32_t m_SizeInBytes;

}

Constructor
Şöyle yaparız.

BitStream(uint8_t* pBuffer,uint32_t sizeInBytes){

  m_BitPosition      = 0;

  m_ BytePosition = 0;

  m_pBuffer            = pBuffer;

  m_SizeInBytes     = sizeInBytes;

}

setPosition metodu
Şöyle yaparız.

void setPosition (uint32_t bitPosition){

  m_BytePosition = bitPosition /  8;

  m_BitPosition = bitPosition % 8;

}

read metodu
Şöyle yaparız. Bu metod içinde buffer overflow kontrolü yok ancak kolaylıkla yapılabilir.
//1 ile işaretli yerde mask zaten okunmuş bit sayısı kadar kaydırılır. Böylece doğru mask elde edilir. Buffer'dan istenilen bit sayısı okunduktan sonra elde edilen değer tekrar sağa kaydırılır.
//2 ile işaretli yerde okunan değer toplam okunan bit sayısı kadar kaydırılı ve sonuca dahil edilir.

uint32_t read (uint8_t numberOfBits){
  uint32_t result = 0;

  uint8_t bitsRead = 0;
    while (numberOfBits > 0) {
      uint8_t bitsToRead = numberOfBits;
      bool nextByte = false;

   

      if (numberOfBits + m_BitPosition) > 8) {

        bitsToRead = 8 - m_BitPosition;

        nextWord = true;

      }

      numberOfBits -= bitsToRead;

      //1

      uint8_t buf = ((MASKS [bitsToRead] << m_BitPosition) & m_pBuffer [m_BytePosition]) >> m_BitPosition;

      if (nextByte){

        m_BytePosition ++;

        m_BitPosition = 0;

      }

      else {

        m_BitPosition +=   bitsToRead;

      }

    //2

    result |= (buf << bitsRead);

    bitsRead += bitsToRead;

  } //while

  return result;

}

write metodu
Şöyle yaparız. Bu metod içinde buffer overflow kontrolü yok ancak kolaylıkla yapılabilir.
//1 ile işaretli yerde buffer'daki alan temizlenir
//2 ile işaretli yerde data yazılır
//3 ile işaretli yerde data'nın yazılan bitleri atılır.

void write (uint32_t data, uint8_t numberOfBits){

  while (numberOfBits > 0) {
    uint8_t bitsToWrite = numberOfBits;
    bool nextByte = false;

   

    if (numberOfBits + m_BitPosition) >= 8) {

      bitsToWrite = 8 - m_BitPosition;

      nextByte = true;

    }

    numberOfBits -= bitsToWrite;

    //1

    m_pBuffer [m_BytePosition] &= ~(data & (MASKS [bitsToWrite] << m_BitPosition);

    //2

    m_pBuffer [m_BytePosition] |= (data & (MASKS [bitsToWrite] << m_BitPosition);

    if (nextByte){

      m_BytePosition ++;

      m_BitPosition = 0;

    }

    else {

      m_BitPosition +=   bitsToWrite;

    }

    //3

    data = (data >> bitsToWrite);

  }

};

Gömülü Proje - Component

Giriş
Gömülü bir projede kullanılan yapı hakkında notlarım

Component Sınıfı
Component denince insanın aklına modül gelebiliyor. Component modülden daha üst seviyede. Belki birçok modülü de içerebilir.

initialize metodu
Initialize metodu ile tüm kaynaklar, bellek alınır.

activate metodu
activate veya start metodu ile sonsuz döngü, thread'ler başlatılır.

deactivate metodu
deactivate veya stop ile sonsuz döngü, thread' bitirilir.

getState ve setState metodu
Bileşenin durumu atanır. State değer olarak "Off", "Stanby", "Operational",  "Degraded" gibi değerler alabilir.

setMode metodu
Bileşenin modu atanır. Mode değer olarak "RX_Only", "TX_RX", "Radio_Silent" gibi değerler alabilir.

Diğer

Component kendisine gelen mesajları ilgili Manager sınıfına iletir. Eğer asenkron çalışması gerekiyorsa içindeki "iş kuyruğuna" ekler.

Application Sınıfı
Bu sınıfı aslında QApplicatin'dan esinlendi. Bu sınıf uygulamadaki tüm Component'leri içerir. 

activate metodu
Tüm componentlerin activate metodunu çağırır.

deactivate metodu
Tüm componentlerin deactivate metodunu çağırır.

getInstance metodu
Application nesnesine global olarak erişimi sağlar.

getConfiguration metodu
Configuration nesnesini döndürür.

readConfiguration metodu
Uygulamanın çalışması için gerek dosyaları okur ve Configuration nesnesinde saklar.

getXComponent metodu
X isimli ilgili componenti döner.

Mediator Sınıfı
Componentler arası haberleşme içindir.Çağrı silsilesi şöyledir. Çağrılar genellikle asenkron çağrılardır.

XManager --> Mediator--> Component --> YManager

XMediator Sınıfı
Component içindeki Manager sınıfları birbirleri ile mesajlaşmak isteyebilir. Bu durumda mediator örüntüsü kullanılır. ComponentMediator ve Component arasındaki ilişki şöyledir.

Component <---> XMediator

XMediator gelen mesajı Component'in getXManager metodunu kullanarak elde ettiği manager nesnelerine paslar.
XManager Sınıfı
Bu sınıfların kendi işleyiş mantıkları ve veri modelleri vardır. Her manager Mediator nesnesini bildiği için başka component'ler ve kardeş Manager nesneleri ile mesajlaşabilir. Çağrı silsilesi şöyledir. Çağrılar senkron çağrılardır.

XManager --> XMediator--> Component --> YManager

XContext Sınıfı
Bu sınıfın varlığı beni herzaman rahatsız etti. Amacı Component içindeki herkesin kullandığı ortak verileri saklamak. Global veriye kolay erişim sağlar.

Ancak prensip olarak her verinin bir sahibinin olması gerekir. Context mantığı ile verinin sahibini kaybediyoruz. Veriyi güncelleme mantığı da zamanla context içine taşınabiliyor. Dolayısıyla sanki sadece salt okunur veriyi saklamak için kullanmak daha mantıklı.

Örneğin component'in ismi, numarası vs. gibi şeyler tutulabilir.

Veri Modeli
Veri modeli ile ilgili iki seçenek var.

Global Veri Model
Global veri modelini en iyi anlatan temsili örnek sanırım Data Distribution System (DDS)
Global veri modeli güncellenince modeli dinleyen processor sınıfının oncreate (), onUpdate (), onDelete() gibi metodları tetiklenir.

Component ilklenirken DDS'in ilgili topiclerini dinleyecek Processor nesneleri yaratılır ve bağlanır
DDS indeksleme mekanizmasını sağladığı için sadece veri ile ilgilenilir. Her veriye birincil anahtar veya indeks ile erişlir. Topicler'in yani verinin ortak bir ata sınıftan kalıtması gerekir. DDS altyapısıını zorladığı kalıtım hiyerarşisi takip edilir. Ayrıca DDS verimodeline erişim için ortak metodlar sunar.


Lokal Veri Modeli
Bu yöntemde programcı kod yazar. Veri modelinde kullanılacak veri yapısı (list, map vs.) seçilir ve veri güncellenince event/signal yötemi ile modeli dinleyen sınıflar tetiklenir. Yani klasik observer örüntüsü kullanılır.

Veri modeli ihtiyaca göre

Clear (), DeleteByKey (...), DeleteByIndex (,,,.indexID), GetAll(), GetFirst (), GetNewest(), GetOldest(), GetSize (), IsEmpty (), AddOrUpdate (), AddProcessor() gibi bir sürü API sağlar.

Soyut bir veri modeli sınıfı tanımlayıp bundan kalıtmak ta mümkün.

Dağıtık Sistemler
Yukarıdaki Global Veri Modeli ve Lokal Veri Modelinin karışımı kullanılır.

Gömülü Proje - Finite State Machine

FSM
Bu sınıfları tasarlarken iki tane daha önce yaptığım projeden faydalandım.

İlk projede FSM sadece dışarıdan gelen mesajlarla tetikleniyordu. Her state gelen mesajı işlerken bir sonraki state'i bir enum olarak dönüyordu. FSM bir sonraki state current state değerinden farklı ise bir sonraki state'e geçebiliyordu.

Aşağıdaki örnekte biraz daha farklı bir durum var. State'ler içinde timer'lar çalıştırmak gerekiyordu. Bu yüzden State kendi kendine FSM'yi tetikleyerek başka State'e geç emri verebiliyor. Dolayısıyla

State <-->> FSM

şeklinde çift yönlü bir ilişki var

1. Context Sınıfı
FSM'nin çalışması için gerekli bilgileri saklar.

2. BaseState Sınıfı
Bu sınıf std::enable_shared_from_this sınıfından kalıtır. Böylece Bir state FSM'yi başka state'e geçmek için tetikleyince nesnemiz yaşamaya devam edebilir.

m_pFSMPtr Alanı
FSM ile olan çift yönlü ilişki. Bir State FSM'nin başka bir State'e geçmesini istiyorsa önce

auto pState = shared_from_this ();

ile kendinin silinmemesini sağlar.Daha sonra

m_FSMPtr->gotoXState ();

şeklinde bir metod çağrı yapar.

onEnter metodu
Her state ilk girişte yapacağı şeyleri onEnter () metodu içinde yapar. State'ten çıkarken yapılacak işler onExit() metodunda yapar diye düşünmüştük anca bu metoda ihtiyaç olmadı.

setContext metodu
State yaratılırken context nesnesi atanır.

processMessage metodu
Bu metod bir template. Dışarıdan gelen mesajları kalıtan State nesnelerine geçmek için kullanlır. İçin şöyledir.

template <class T>

void processMessage (const T& msg)

{

  processInternal (msg)

}

Bu template metodu şöyle iç metodlara dağıtım yapar.

virtual processInternal (const A& msg)

{

}

virtual processInternal (const B& msg)

{

}

Bu metodlar boştur. Böylece sadece  mesaj ile ilgilenen State gerekli metodu override eder.

3. FSM Sınıfı
Bu sınfın gotoStateA (); gotoStateB () gibi metodları vardır. Bu metodlar çağrılınca
1. m_CurrentState enum değişkeni güncellenir.
2. Eski State nesnesinin onExit() metodu çağrılır.
3. Yeni State nesnesi yaratılır ve onEnter() metodu çağrılır. onEnter metodu en son çağrılan şey olmalı yoksa bir State hemen bir başka State'e geçişi tetiklerse ortalık karışabilir.

isXState metodu
FSM sınıfı dışarından hangi state içinde olduğunun sorgulanabilmesi için isXState() gibi metodlar sunar.

processMessage metodu
Şöyledir

template <class T>

void processMessage (const T& msg)

{

  m_pCurrentState->processMessage (msg)

}

Gömülü Proje - ArraySegment

Giriş
Gömülü projelerde C#'taki ArraySegment sınıfına benzer bir sınıf çok işe yarıyor. Gereksiz kopyalama yapmadan bir bellek alanının başını ve sonunu tek bir nesne halinde geçebiliyoruz.

Eğer C++20 kullanıyorsak std::span sınıfını kullanmak daha iyi

Örnek
Şöyle yaparız.

template<class T>
struct span_t {
  T* b =0;
  T* e =0;
  T* begin() const { return b; }
  T* end() const { return e; }
  std::size_t size() const { return end()-begin(); }
  bool empty() const { return size()==0; }
  T& operator[](std::size_t i) const { return b[i]; }
  span_t()=default;
  span_t(span_t const&)=default;
  span_t& operator=(span_t const&)=default;
  span_t( T* s, T* f ):b(s),e(f) {}
  span_t( T* s, std::size_t l):span_t(s, s+l) {}
};

Örnek
Şöyle yaparız.

#include <cstdint>

template<typename T>
class array_view {
   T* ptr_;
   std::size_t len_;
public:
   array_view(T* ptr, std::size_t len) noexcept: ptr_{ptr}, len_{len} {}

   T& operator[](int i) noexcept { return ptr_[i]; }
   T const& operator[](int i) const noexcept { return ptr_[i]; }
   auto size() const noexcept { return len_; }

   auto begin() noexcept { return ptr_; }
   auto end() noexcept { return ptr_ + len_; }
};

Örnek
Şöyle yaparız.

template<typename T>
class span {
   T* ptr_;
   std::size_t len_;

public:
  span(T* ptr, std::size_t len) noexcept
    : ptr_{ptr}, len_{len}
  {}

  T& operator[](int i) noexcept {
    return *ptr_[i];
  }

  T const& operator[](int i) const noexcept {
    return *ptr_[i];
  }

  std::size_t size() const noexcept {
    return len_;
  }

  T* begin() noexcept {
    return ptr_;
  }

  T* end() noexcept {
    return ptr_ + len_;
  }
};