logo elektroda
logo elektroda
X
logo elektroda
REKLAMA
REKLAMA
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.

[AVR][ATmega128][C] - Kolejka FIFO z usuwaniem elementów

czmi3l 20 Lip 2012 01:25 1956 6
REKLAMA
  • #1 11124725
    czmi3l
    Poziom 14  
    Cześć, rzadko się ostatnio udzielam ale chciałbym poprosić wyjadaczy o radę.
    Chce zaimplementować kolejkę FIFO (w C), dla której będzie możliwość usuwania elementów z jej środka. Jak najłatwiej się za to zabrać?
    Mam następujące pomysły:
    1. Deklaruję zwykłą tablicę x elementową, oraz zmienną informującą o ilości zapisanych danych. Dodawanie kolejnych elementów jest trywialne, problem pojawia się gdy chcę usunąć element ze środka. Mogę po prostu zmniejszyć licznik danych o 1 a następnie:
    a) przesuwać dane w tablicy począwszy od usuniętego elementu a skończywszy na ostatniej danej w kolejce,
    b) zastosować fcje memcpy - i zrealizować przy jej użyciu przesunięcie w tablicy danych o 1 w lewo

    2. Stosuje funkcje malloc oraz free i robię kolejkę książkową dla struktury
    typedef struct QueeElement_Tag
    {
    uint16 message;
    QueeElement_T * head;
    QueeElement_T * tail;
    } QueeElement_T;
    Do tego jestem niechętnie nastawiony, nie bardzo lubię zabawy z alokacją pamięci na AVRkach.

    3. Jakieś wasze proste i sprawdzone propozycje?
    Z góry bardzo serdecznie dziękuję za pomoc.
  • REKLAMA
  • #2 11124750
    McMonster
    Poziom 32  
    Osobiście poleciłbym klasyczną listę wiązaną. Implementację można łatwo znaleźć w sieci i dostosować, więc nie trzeba się przejmować tym, że się zrobi błąd i pamięć wycieknie. No i zwykle jest oszczędniejsza pamięciowo. Szczególnie, jeśli to nie będzie kolejka o ustalonej długości, bo dostosowywanie rozmiaru tablicy zajmuje dużo czasu lub pamięci.
  • REKLAMA
  • REKLAMA
  • #4 11125131
    czmi3l
    Poziom 14  
    Czuję się pouczony, od dzisiaj będę na to mówił lista dwukierunkowa.
  • #5 11130732
    tmf
    VIP Zasłużony dla elektroda
    Dla formalności, niekoniecznie jest to też lista dwukierunkowa :)
    Co do twojego pytania - znasz maksymalną liczbę elementów? Jeśli możesz sobie pozwolić na zastosowanie tablicy wskaźników to oczywiście usuwanie elementu przez przesunięcie wszystkich indeksów wyższych niż dany element za pomocą memcpy jest najefektywniejsze. Tu nie ma co kombinować, jeśli tablica jest sporawa to dodatkowo warto ją zaimplementować jako formę bufora pierścieniowego, ze wskaźnikami na pierwszy i ostatni element. Dzięki temu przy zdejmowaniu elementu nie trzeba kopiować całej tablicy, co przyśpiesza operację. Jeśli tablica wskaźników odpada, to można wykorzystać listy jedno lub dwukierunkowe, lub stogi. W sieci jest pełno implementacji takich struktur, więc nie ma co kombinować. Implementację FIFO (ale FIFO, a nie czegoś a la FIFO) masz też gotową w AS6, wystarczy dodać do projektu.
  • REKLAMA
  • #6 11130799
    czmi3l
    Poziom 14  
    Dziękuję za odpowiedź tmf.

    Mam wymyśloną taką strukturę:


    Kod: C / C++
    Zaloguj się, aby zobaczyć kod


    50 elementów uint16 dla ATmegi128 to nie jest duża tablica.
    Usuwanie elemtów o danym msg rozwiązałem w ten sposób:

    Kod: C / C++
    Zaloguj się, aby zobaczyć kod


    Czy można to jeszcze zoptymalizować tym przypadku?
    Co to jest AS6?
  • Pomocny post
    #7 11130986
    tmf
    VIP Zasłużony dla elektroda
    Jeśli wiadomości o danym typie jest więcej niż jedna i nie można ich sortować to IMHO nic więcej nie zoptymalizujesz. A przynajmniej nie warto będzie optymalizować dla tablicy 50-elementowej.

    Dodano po 44 [sekundy]:

    BTW, AS6 to Atmel Studio 6. Jako jeden ze składników ASF (Atmel Software Framework) masz FIFO.
REKLAMA