Tietorakenteet¶

Osaamistavoitteet: Tietorakenteiden käyttö C-kielessä ja käyttötapauksia sulautettujen järjestelmien ohjelmoinnissa.

C-kielen struct (tietue) (engl. struct, suomeksi tietue) on useasta muuttujasta laadittu looginen rakenne/yhdistelmä/kooste, johon toisiinsa liittyvää tietoa voidaan ryhmitellä yhteistä käsittelyä varten. Tietorakenteet ovat hyvin yleinen ohjelmoinnin konsepti ja niillä on käyttötapauksensa myös sulautettujen ohjelmoinnissa, joten katsotaanpas miten niitä C-kielessä käytetään.

C-kielessä tietorakenteen esittelylle on varattu sana struct ja tietorakenne esitellään lohkona seuraavasti. Tietorakenteen jäsenet voivat C-kielessä olla mitä tahansa muuttujatyyppejä.

struct tietorakenteen_tyyppinimi { 
   jäsenten esittelyt;
};

Esimerkiksi. Esitellään tietorakenne tyyppiä point, jossa on jäseninä x- ja y-koordinaatit ja koordinaattipisteen nimi merkkijonona. Esitellään heti perään toinen tietorakenne rect, joka koostuu point-tyypin tietorakenteista.

struct point {
   uint16_t x; 
   uint16_t y; 
   char nimi[16]; 
}; 

struct rect {
   struct point max; 
   struct point min;
   struct point all_points[10]; 
};

Yllä oleva määrittely kuvaa uuden tietuetyypin nimeltä struct point; se ei vielä luo muuttujaa. Myöhemmin voimme luoda tämän tyyppisiä muuttujia:

struct point piste1;
struct point piste2 = {100, 200, "Piste"};

Tietorakenne C-ohjelmassa¶

Tietorakenteen jäsenten käyttöön ohjelmassa tarvitaan kaksi uutta operaattoria:

Jäseniin viitataan .-operaattorilla kuin mihin tahansa muuttujiin.
Kun käytössämme on osoitin tietorakenteeseen, käytämme ->-operaattoria.

Esimerkki.

// Tietorakenteiden esittely
struct point {
   uint16_t x;
   uint16_t y;
};

struct rect {
   struct point max;
   struct point min;
   struct point all_points[10];
};
// Muuttujat ja alustus
struct point min_pt;
min_pt.x = 100;
min_pt.y = 100;

struct rect laatikko;
laatikko.max.x = 320;
laatikko.max.y = 200;

printf("%d,%d", laatikko.max.x, laatikko.max.y);

Esittely ja alustus¶

Syntaktisesti tietorakenteen esittely ja alustus voidaan tehdä kuten mille tahansa muuttujalle. Tässä C-kielen syntaksi on joustava ja alustukseen on useita tapoja.

// Muuttujan esittely tietorakenteen esittelyn perässä
// tässä piste1
struct point {
   uint16_t x;
   uint16_t y;
   char nimi[20];
} piste1;

piste1.x = 320;
piste1.y = 200;
char keskipiste[] = "Keskipiste";
// Käytetään string-kirjaston funktioita!
strncpy(piste1.nimi, keskipiste, strlen(keskipiste)+1); 

// Erikseen muuttujana
struct point piste2; 
piste2.x = 320; 
piste2.y = 200;
strncpy(piste2.nimi, keskipiste, strlen(keskipiste)+1); 
	
struct point piste3 = { 320, 200, "Keskipiste" };

Huomaa, että kun tietorakennemuuttuja on määritelty, emme voi sijoittaa uutta merkkijonoa suoraan merkkitaulukkojäsenelle =-operaattorilla. Sen sijaan voimme kopioida merkkijonon taulukkoon strncpy-funktiolla. strncpy-funktion avulla voimme kopioida yhden merkkijonon sisällön (esimerkiksi "Keskipiste") tietorakenteessa määriteltyyn merkkitaulukkoon (nimi).

Hox! strlen palauttaa merkkijonon merkkien määrän, mutta se ei laske mukaan merkkijonon lopussa olevaa nollamerkkiä '\0'. Siksi käytämme arvoa strlen(keskipiste) + 1, jotta strncpy kopioi myös merkkijonon lopettavan nollamerkin. Tässä esimerkissä tiedämme, että kohteena oleva taulukko on riittävän suuri koko merkkijonolle.

Muitakin tapoja tietorakenteen alustukseen ja esittelyyn on, mutta yllä selkeimmät.

Tietorakenteita voi myös sijoittaa toisiinsa, jolloin jokainen jäsen kopioidaan.

min_pt = max_pt;

Osoittimet ja tietorakenteet¶

Kun tietorakenteita käytetään funktion parametreina, kuten aiemmin selitimme, ne välitetään tyypillisesti osoittimien avulla, koska kun välitämme argumentin funktiolle, tietorakenteesta luodaan kopio, ja haluamme säästää muistia

Tietorakenteen jäsentä käsitellään osoittimen kautta ->-operaattorilla. Se yhdistää kaksi operaatiota: osoittimen dereferoinnin ja tietorakenteen jäsenen käsittelyn.

Esimerkiksi:

osoitin_r->piste.x;        // Helpompi merkintätapa
(*osoitin_r).piste.x;      // Vastaava lauseke

Alla koodiesimerkki sen käytöstä.

#include <stdio.h>
#include <inttypes.h>

struct point {
	uint16_t x;
	uint16_t y;
} piste = { 160, 100 };

int main() {

   struct point *osoitin_piste = &piste;	
	
   printf("x=%d y=%d\n", piste.x, piste.y);
   printf("x=%d y=%d\n", osoitin_piste->x, osoitin_piste->y);	
	
   // sijoitus jäseneen a.y osoittimen kautta
   osoitin_piste->y=103; 
   printf("x=%d y=%d\n", piste.x, piste.y);	
    
   return 0;
}

Kun sisäkkäisten tietorakenteiden jäseniä käsitellään osoittimen kautta, käytettävä operaattori riippuu siitä, mitä käsittelemme. Tässä esimerkissä osoitin_r on osoitin struct rect-tietorakenteeseen, joten käytämme ensin ->-operaattoria. Jäsen piste on puolestaan tietorakenne, joten sen jäseniin viitataan .-operaattorilla.

#include <stdio.h>
#include <inttypes.h>

struct rect {
   struct point {
      uint16_t x;
      uint16_t y;
   } piste; 
} r = { .piste.x = 101, .piste.y = 102};

int main() {

   struct rect *osoitin_r = &r;	
	
   // Käsitellään tietorakenteen jäseniä osoittimen osoitin_r kautta operaattorilla ->
   // Käsitellään sisäkkäisen point-tietorakenteen jäseniä operaattorilla .
   printf("x=%d y=%d\n", osoitin_r->piste.x, osoitin_r->piste.y);	
	
   return 0;
}

Hox! Katso myös string-kirjaston funktio memcpy, jolla voidaan kopioida kokonaisia muistilohkoja. Toisinsanoen, tietorakenteen sisältö voidaan kopioida toiseen niin että kopioidaankin osoittimien avulla tietorakenteelle varattu muistialue sellaisenaan. C-kielen laiteläheinen muistimalli mahdollistaa datan käsittelyn myös tällä tavalla.

#include <stdio.h>
#include <stdint.h>
#include <string.h>  // memcpy-funktiota varten

// struct point -tietorakenteen määrittely
struct point {
    uint16_t x;
    uint16_t y;
    char nimi[20];
};

int main() {
    // Esitellään ja alustetaan p1
    struct point p1 = {320, 200, "Keskipiste"};

    // Esitellään toinen struct, johon sisältö kopioidaan
    struct point p2;

    // Kopioidaan p1:n sisältö p2:een memcpy-funktiolla
    memcpy(&p2, &p1, sizeof(struct point));

    // Tulostetaan molemmat tietorakenteet, jotta nähdään niiden olevan nyt identtiset
    printf("p1: x = %d, y = %d, nimi = %s\n", p1.x, p1.y, p1.nimi);
    printf("p2: x = %d, y = %d, nimi = %s\n", p2.x, p2.y, p2.nimi);

    return 0;
}

Hox! memcpy kopioi tietorakenteen muistiesityksen. Jos tietorakenne sisältää osoittimia, osoittimien arvot kopioidaan, mutta niiden osoittamaa dataa ei kopioida.

Tietorakenteiden vertailu¶

Tietorakenteita ei voida vertailla kokonaisuutena suoraan vertailuoperaattoreilla. Sen sijaan haluttuja jäseniä voidaan verrata erikseen. Tässä esimerkissä käsittelemme tietorakenteita osoittimien kautta ja vertaamme niiden x-jäseniä.

Esimerkki. Funktio siis palauttaa osoittimen siihen tietorakenteeseen, jossa on suurempi arvo jäsenessä x.

#include <stdio.h>
#include <inttypes.h>

struct point {
	uint16_t x;
	uint16_t y;
};

// Funktio joka palauttaa tietorakenteen osoittimen
struct point *kumpi_isompi(struct point *a, struct point *b);

int main() {

   struct point eka = { 320, 200}, toka = { 321, 201 };
   struct point *isompi = kumpi_isompi(&eka, &toka);
   printf("x=%d y=%d\n", isompi->x, isompi->y);

   return 0;
}

struct point *kumpi_isompi(struct point *a, struct point *b) {

  if (a->x > b->x) {
      return a;
   } else {
      return b;
   }
}

Alkaa olla tämä osoitintouhu jo suht korkealentoista tavaraa..

Sulautetut tietorakenteet¶

Kuten aiemmin todettiin, tietorakenne on kätevä tapa sitoa toisiinsa liittyvää informaatiota loogisesti yhteenkuuluvaksi paketiksi. Sulautetuissa järjestelmissä tällainen paketti voisi olla samalla mittaushetkellä kerätty anturidata tai vaikkapa oheislaitteen asetusparametrit tai langattoman tiedonsiirron viestinvälityksen asetukset. Koska anturidataa useimmiten analysoidaan aikasarjana, on oleellista tietää tarkka mittaushetki. Monet sovellukset myös hyödyntävät esimerkiksi älykkäämpien palveluiden toteutuksessa usealta eri anturilta samanaikaisesti kerättyä dataa, jolloin mittaushetki sitoo erityyppiset data yhteen.

struct sensor_data {
   uint32_t timestamp;
   float temperature;
   float humidity;
};

Ja, kun data on nätisti paketissa tietorakenteessa, siitä voidaan helposti saada CSV-muotoinen merkkijono, joka sitten langattomasti lähetetään talteen IoT-taustajärjestelmään.

Kunhan kurssilla päästään laitteistoja ohjelmointiin asti, huomataan että monet laitteen käyttöjärjestelmän valmiit ohjelmistokomponentit itseasiassa haluavat asetusparametrinsä tietorakenteena.

Harjoitellaan. Laadi tietorakenne nimeltä sensor_data, johon jäseneksi allakuvatut muttujat, joista jokainen kuvaa jonkin sensorin dataa:

kiihtyvyysanturi: accelerometer, liukuluku kolme akselia (x,y,z) taulukko
asentoanturi: gyro, liukuluku kolme akselia (x,y,z) taulukko
lämpötila: temperature, liukuluku
ilmankosteus: humidity, liukuluku
valoisuus: light, 16-bittinen etumerkitön kokonaisluku
ilmanpaine: pressure, liukuluku

Liukulukuina käytämme yksinkertaisen tarkkuuden liukulukuja. Voisi olla hyvä ajatus kuvata akselit taulukkona.

Vastaukseen pelkästään luotu tietorakenne.

Hox! Kääntäjä voi lisätä tietorakenteen jäsenten väliin käyttämättömiä täytetavuja (engl. padding) muistinkohdistusvaatimusten vuoksi. Tämän vuoksi tietorakenteen koko ei aina ole täsmälleen sen jäsenten kokojen summa.

Omat muuttujatyypit¶

Tietorakenteiden lisäksi C-kielessä voimme määritellä omia tyyppinimiä typedef-avainsanan avulla. typedef voi antaa uuden nimen olemassa olevalle tyypille, kuten yksinkertaiselle tietotyypille, taulukolle, osoittimelle tai tietorakenteelle. Näin ohjelmassa käytettäville tyypeille voidaan antaa niitä paremmin kuvaavia nimiä.

Esimerkiksi voimme määritellä tyypin, joka vastaa 10 tavun taulukkoa:

typedef uint8_t RegisterBytes[10];

RegisterBytes reg;

Tässä RegisterBytes on vaihtoehtoinen nimi taulukolle, joka sisältää 10 uint8_t-arvoa.

Sen avulla voidaan myös korvata muiden tyyppien nimiä, esimerkiksi:

// Määritellään Length uint16_t-tyypin aliakseksi
typedef uint16_t Length; 
Length len = 100;
printf("%d\n", len);

typedef is very commonly combined with structures. For example:

typedef struct {
    uint16_t x;
    uint16_t y;
} Point;

Point p1 = {100, 200};

Now Point is a type name for this structure, so we do not need to write struct point when declaring variables.

Sulautetuissa järjestelmissä (ja joskus myös C-ohjelmoinnissa työasemalla) typedef:iä käytetään usein helpottamaan koodin siirtämistä laitealustalta toiselle. Sovelluskohtaisten tyyppinimien avulla alustasta riippuvat tyyppivalinnat voidaan keskittää yhteen paikkaan. Kun koodi siirretään toiselle alustalle, vastaavia taustalla olevia tyyppejä voidaan tarvittaessa muuttaa. Tämä ominaisuus on erittäin hyödyllinen juurikin monimutkaisempien tietorakenteiden käytössä, mutta on standardoitujen muuttujatyyppienkin uudelleennimeämisestä joskus hyötyä. Esimerkiksi uint16_t tarjoaa taatun 16-bittisen etumerkittömän kokonaisluvun kaikilla alustoilla

Käytämme samaa tapaa myöhemmin kurssin laiteohjelmointiosuudessa. Monet laitteistokirjastot ja rajapinnat määrittelevät asetustietonsa tietorakenteiden ja omien tyyppinimien avulla, joten struct- ja typedef-rakenteiden ymmärtäminen helpottaa näiden rajapintojen lukemista ja käyttöä. Perusteluna on tietysti yhteensopivuus ja helppo koodin siirtäminen valmistajan omilta laitteilta toiselle, niin kaikki koodi toimii laitteesta riippumatta halutusti valmistajan omassa sulautettujen käyttöjärjestelmässä.

Lopuksi¶

Tässä materiaalissa esitettyjä kaikkia tietorakenteiden esittely- ja alustustapoja ei tarvitse opetella ulkoa. Opettele ensin yksi selkeä tapa ja käytä sitä johdonmukaisesti. Muut tavat on kuitenkin hyvä tunnistaa, kun niitä tulee vastaan olemassa olevassa C-koodissa.

Anna palautetta

Kommentteja materiaalista?