Datastrukturer i C
-----------

"Data dominates. If you've chosen the right data structures and organized
things well, the algorithms will almost always be self-evident.
Data structures, not algorithms, are central to programming."

                    -- Rob Pike's fifth rule of programming

Följande artikel riktar sig till personer med baskunskap i C, som förstår
pekarkonceptet men som inte har erfarenhet av datavetenskap och datastrukturer
sen tidigare.

Då och då ser man program där programmeraren ska behandla en viss mängd data.
Han vet inte hur mycket data det rör sig om, så han allokerar en större mängd
minne statiskt och hoppas på att det ska räcka, istället för att allokera minne
dynamiskt efterhand som det behövs. Oftast valideras inte indatan heller,
så om den överstiger den mängd minne som är statiskt allokerat skrivs datan
förbi bufferten och det uppstår en sk. buffer overflow.

För en tid sen visade en vän en bit kod för mig. Han hade börjat att lära sig
C++, och just detta program var ett glosprogram för japanska. Som det såg ut
just då så öppnade det en fil, om filen var OK läste den innehållet till minnet
och sedan skrev den ut gloskombinationerna till skärmen. Det skulle ta en del
minne vid större glosfiler, men det skulle bli både snabbare och lättare att
hantera än om den hade hämtat glosa för glosa. Han skulle senare bygga vidare
på detta, med inmatning från användare etc.

Glosorna sparades i minnet i två stringfält, i stil med:

string sv[99];
string jp[99];

Jag nämnde att det inte var så bra att ha orden i ett statiskt allokerad fält
men i övrigt tyckte jag det var ett bra program. Lite senare på kvällen, efter
ett par öl hamnade jag med projektet i hand. Jag är ganska lättpåverkad när
det kommer till alkohol, och jag var aningen slö i skallen vid tillfället.
Jag tänkte att jag istället skulle lägga in alla orden i en map, men efter
att ha skrivit isönder hans program så fick jag det inte att fungera. Artikelns
första läxa: koda aldrig under alkoholpåverkan. Det är ingen ursäkt för dålig
kod även om det kan vara orsaken till det.

Så, hur ska man göra istället? I C++ kan man göra det enkelt för sig. Istället
för stringfält kan man använda sig av datastrukturen vector:

std::vector<string> sv;
std::vector<string> jp;

eller list:

std::list<string> sv;
std::list<string> jp;

vector och list hanterar minnesallokeringen dynamiskt, och transperent mot
programmeraren. Han slipper bry sig om minnet eftersom dessa datastrukturer gör
det åt honom automatiskt. Skillnaden mellan de båda datastrukturerna är sättet
de lagrar sitt innehåll i minnet. Ett listelement består, något förenklat, av
datan den ska hålla (string i det här fallet) och en pekare till nästa element.

När man vill röra sig i en lista måste man därför gå igenom alla element från
start till det element man vill nå. Man säger att förflyttning i en lista är
O(N), där O är en funktion för att uttrycka algoritmens hastighet, och N är
antalet dataelement som hanteras. Detta kallas på engelska "big-O notation".
Jag rekommenderar läsaren att kolla upp detta på eget håll. Engelska Wikipedia
har en bra artikel som tar upp det.

I en vektor däremot, så ligger dataelementen på rad i minnet. Man vet var
det första elementet är och man vet att man vill ha det femte. Om ett element
är 4 byte stort vet man att det femte elementet börjar 12 byte efter det första
elementets slut. Att röra sig i en vektor är därför O(1), det tar lika lång tid
för dig att komma åt det tredje elementet som det tar för dig att komma åt det
tjugosjunde. Tiden är, i teorin, konstant.

Insättning av dataelement i en vektor är däremot en smutsig historia. Om man
vill sätta in ett element i mitten av en vektor allokerar man mer minne,
flyttar all data framför insättningspositionen ett steg framåt och sätter in
dataelementet på insättningspositionen. Det går därför snabbast att sätta in
dataelement på slutet av vektorn. Insättning av dataelement i en lista
är en ren historia däremot, det är bara att kasta om pekarna till elementen.

En vektor är därför bra om du vill lagra en stor mängd data som du inte
ska flytta runt men som du vill ha snabb åtkomst till. En lista är bättre om
du har en mindre mängd data (allting är relativt) som ändras kontinuerligt.
I teorin förstås, i praktiken beror det till största delen på implementeringen.
Bara för att du har en O(1) algoritm betyder det inte att den är snabbare än
en O(N) algoritm. Allt det talar om för dig är tillväxten på tiden utefter
antalet dataelement. Det är därför viktigt att klocka sitt program om man är
ute efter så snabb åtkomsttid som möjligt. På minnessidan så är en vektor mer
effektiv, då den inte behöver spara en massa pekare till nästa element.

Det finns olika implementeringar av dessa datastrukturer och även olika
varianter. Det jag kommer att gå igenom i denna artikel är de mest elementära
lösningarna. Jag uppmanar dig därför att, efter du har läst artikeln och
fortfarande är intresserad, kolla upp dessa datastrukturer (och andra) på
Internet.

I C++ är det mesta inkapslat i de båda datastrukturerna som innefattas av
standardbiblioteket. I C däremot, får man skriva dessa datastrukturer själv
efter behov. Och det är vad jag tänker ägna resten av artikeln åt.

Men först en genomgång i dynamisk minnesallokering. I ANSI C sköts dynamisk
minnesallokering av funktionen malloc():

void *malloc(size_t size);

Man ger storleken på minnet man vill ha som argument, och malloc returnerar
en pekare till det första elementet i det allokerade minnet, eller NULL vid
mysslyckande. Man kan typomvandla från void* till passande pekartyp, men
det är bättre att låta kompilatorn göra detta. Glömmer man att inkludera
stdlib.h så kan det förutsättas att malloc() returnerar en int, och att detta
heltal sedan omvandlas till en adress. Detta kan ge väldigt missvisande
felmeddelanden, så därför är det bättre att låta typomvandlingen ske implicit.

Implementeringen av malloc är starkt beroende av systemarkitekturen och
operativsystemet. Detta behöver man i regel inte bry sig om, men om man vill
undvika minnesfragmentering eller allokering av större mängd minne än
nödvändigt så kan det vara en bra idé att kolla upp hur malloc är implementerat
på det system man kodar för.

När man väl har allokerat en viss mängd minne, men behöver mer (eller mindre)
till exempel för att lägga till ett nytt element i en vektor, så finns
funktionen realloc():

void *realloc(void *ptr, size_t size);

realloc tar det allokerade minnet vid ptr och ändrar dess storlek till size
bytes. De gamla minnet är oförändrat upp till den gamla storleken, eller om
size är mindre än det allokerade minnet var, upp till size bytes. Det nya
minnet är oinitierat.

Till skillnad från statiskt allokerat minne så frigörs inte det allokerade
minnet från minnesallokeringsfunktionerna efter det att funktionen är klar.
Glömmer man frigöra minnet efter man använt det, kan det leda till
minnesläckage. Detta påverkar programmets (och systemets) prestanda negativt.
För att frigöra dynamiskt allokerat minne använder man funktionen free():

void free(void *ptr);

där ptr är en pekare till det tidigare allokerade minnet.

Låt oss nu ta bort kåpan och ta oss in i maskineriet. Låt oss skita ner
händerna. Låt oss implementera en vektor och en länkad lista i C. Nu kan vara
rätt tillfälle att friska upp minnet när det gäller pekararitmetik. Det kan bli
smutsigt.

Vi ska börja med att göra en vektor och olika funktioner för att hantera
datan i vektorn. Vi behöver en sammansatt datatyp för att representera vår
datastruktur. I C gör man som bekant samansatta datatyper med struct. Vår
vektor kommer alltså att vara representeras enligt följande:

typedef struct {
  int *el;
  unsigned int elc;
} s_vec;

Där el är en pekare till första elementet i vektorn, och elc är antalet
element i vektorn. Implementeringen av en vektor kan som sagt se olika ut, och
ovanstående datatyp är bara ett exempel av många. I vårt exempel är vektorn
till för att spara heltal, det kan generaliseras med void-pekare så att
strukturen kan hålla en godtycklig datatyp.  Hela källkoden är bifogad som
appendix, det gäller även den kommande koden för länkade listor.

En lista ser något annorlunda ut. Som tidigare nämnts ligger dataelementen inte
efter varandra i minnet, utan varje listelement innehåller en referens till
nästa element. I C görs detta genom att listelementet har en pekare som håller
adressen till nästa element. Datatypen för en lista kan därför se ut såhär:

typedef struct _list {
  int el;
  struct _list *next;
} list;

Listelementen allokeras dynamiskt med hjälp av malloc(), och frigörs med
free().

Datastrukturer är viktiga. Som namnet antyder ger de struktur till den data
som ska behandlas och det i sin tur leder (förhoppningsvis) till
välstrukturerade program som arbetar på ett effektivt sätt. Men i slutändan är
det upp till programmeraren. Han (eller hon) måste välja ett passande sätt att
hantera programmets in- och utdata för jobbet. På samma sätt som man kan
skriva dåliga program utan datastrukturer kan man även skriva dåliga program
med dem. Datastrukturer tar upp jämförelsevis mycket minne, och det är inte
alltid önskvärt. Ibland räcker det att läsa data till en statiskt allokerad
buffer och tolka den för att sedan läsa in nästa stycke istället för att läsa
in allt på en gång till en lista. En avvägning måste alltid göras mellan
minnesanvändning och snabbhet. Om du är osäker på om du behöver strukturera
din data så gör ett testprogram som testar de möjligheter du har för att
hantera din data.

/*
  An implementation of a vector structure in ANSI C. It creates a vector,
  stores ten random values in it, print them all to stdout and free's the
  memory.

  Leaky abstraction, but practical.
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct {
  int *el;
  unsigned int elc;
} s_vec;

s_vec *vector_new();
s_vec *vector_insert_last(s_vec *v, int val);
void vector_free(s_vec *v);

int main()
{
  s_vec *v = vector_new();
  int i, j, *iptr;

  srand(time(NULL));
  printf("inserting values:\n");
  for(i = 0; i<10; i++) { /* inserting random values in vector */
    j = rand();
    if (vector_insert_last(v, j) == NULL) {
      printf("insert error, i=%d\n", i);
      free(v);
      return -1;
    }
    printf("pos %d: %d\n", i, j);
  }

  printf("\nlisting values:\n");
  for(i=0; i<v->elc; i++) { /* print vector values to screen */
    iptr = v->el + i;
    j = *iptr;
    printf("vec %d: %d\n", i, j);
  }

  vector_free(v); /* free the allocated memory */
  return 0;
}

s_vec *vector_new()
{
  s_vec *v = malloc(sizeof(s_vec));
  if (v == NULL)
    return NULL;

  v->el = NULL;
  v->elc = 0;
  return v;
}

s_vec *vector_insert_last(s_vec *v, int val)
{
  int *iptr;

  if (v == NULL)
    return NULL;

  if (v->el == NULL) { /* first element in vector */
    v->el = malloc(sizeof(int));
    if (v->el == NULL)
      return NULL;
    *v->el = val;
    v->elc++;
  }
  else {
    iptr = realloc(v->el, sizeof(int) * (v->elc+1));
    if (iptr == NULL)
      return NULL;
    v->el = iptr;
    iptr = v->el + v->elc;
    *iptr = val;
    v->elc++;
  }
  return v;
}

void vector_free(s_vec *v)
{
  free(v->el);
  free(v);
}

#include <stdio.h>
#include <stdlib.h>

typedef struct _list {
  int el;
  struct _list *next;
} list;

int main()
{
  /*
    Det här är inte så representativt över hur man bör använda en länkad lista.
    Det är mer PoC kod för att visa hur man hanterar den. Låtsas att vi inte
    vet antalet element lagrade i data.
  */

  int data[4] = {0, 1221, 510, 2}, i;
  list l, *lp, *lp2;
  lp = &l;

  for(i=0; i<4; i++) { //Lägger till indatan lagrad i data till listan l
    lp->el = data[i];
    if (i<3) {
      lp->next = malloc(sizeof(list));
      if (lp->next == NULL) {
    fprintf(stderr, "malloc: out of memory\n");
    return -1;
      }
      lp = lp->next;
    }
    else
      lp->next = NULL;
  }
  
  // Då har vi indatan från data lagrad i vår lista, låt oss skriva den
  // till stdout
  for(lp = &l; lp!=NULL; lp = lp->next)
    printf("%d\n", lp->el);

  //Och så frigör vi det allokerade minnet
  for(lp = &l; lp != NULL; lp = lp2) {
    lp2 = lp;
    free(lp);
  }

  printf("done\n");
  return 0;
}