TDIU16 Process- och operativsystemprogrammering

C-introduktion

Introduktion till C

Här finns det exempel vi gick igenom på föreläsningen. Exemplet börjar med ett C++-program som vi stegvis skriver om till C. Programmet innehåller klassen sorted_list, som representerar en sorterad sekvens av heltal i en std::vector. Med hjälp av exemplet kommer vi alltså se hur vi implementerar allt detta i ren C i en stil som matchar det som används i Pintos.

All kod finns här. Filerna är döpta main0-9 och live0-9 för vart och ett av stegen nedan. All kod kan kompileras på Unix med kommandot make.

Notera: Den här sidan visar den tänkta lösningsgången. Den kan därför avvika något från det som presenterades på föreläsningen. Det viktiga ska dock stämma överens.

Steg 0

Filerna live0.cpp, live0.h och main0.cpp innehåller originalprogrammet skrivet i C++. I live0.h finns klassen sorted_list, som representerar en sorterad sekvens av heltal. Det maximala antalet heltal som ryms anges som parameter till konstruktorn. Om listan blir överfull kastas ett undantag. Filen main0.cpp innehåller ett huvudprogram som sätter in talen 100-1 i listan och skriver ut de 40 första i en tabell med 10 kolumner. Då kommer talen 1-40 att skrivas ut eftersom listan automatiskt sorterar innehållet.

Steg 1

Första steget mot ett program som kompilerar i C. Eftersom cout är något som bara finns i C++ börjar vi med att byta ut cout mot motsvarigheten printf i filen main1.cpp. Se exempelvis cppreference.com för en mer detaljerad beskrivning av hur formatsträngar fungerar. De kan även användas till scanf.

Steg 2

Eftersom C inte har klasser som i C++ börjar vi nu att göra om klassen sorted_list i live2.h till en struct. Medlemsfunktioner är inte heller något som C har stöd för, så vi flyttar ut dem ur klassen och lägger dem globalt i stället. Skillnaden mellan en medlemsfunktion och en icke-medlemsfunktion i C++ är (förutom att den får tillgång till privata medlemmar) att medlemsfunktioner automatiskt får en extra första parameter this. Eftersom vi inte använder medlemsfunktioner måste vi lägga till den parametern själva. Vi kallar den här för me, eftersom this är reserverat i C++. Vi skulle kunna använda this som variabelnamn i C sedan.

Vi måste också göra något med konstruktorn och destruktorn i klassen. Det vanligaste är att hantera dem som om de vore vanliga medlemsfunktioner vid namn create och destroy. Vi flyttar alltså ut dem ur klassen och får två funktioner som heter list_create och list_destroy. Eftersom de funktionerna nu är vanliga funktioner måste användaren av klassen själv vara noggran med att anropa list_create när en lista skapas list_destroy när en lista ska förstöras. Eftersom de är vanliga funktioner kan kompilatorn inte hjälpa till med detta.

Notera att vi hanterar publika och privata medlemsfunktioner lite olika. Publika funktioner deklarerar vi i headerfilen och privata funktioner deklarerar vi bara som static i implementationsfilen. Att deklarera funktioner och variabler som static innebär att andra kompileringsenheter (dvs. andra C-filer) inte kommer att komma åt symbolen, vilket är motsvarigheten till private i C.

Den statiska variabeln num_moves har också flyttats ut ur vår struct. Den har deklarerats med nyckelordet extern för att indikera att det bara är en deklaration och ingen definition. Skulle extern utelämnas så skulle varje C-fil få sin egen instans av variabeln, vilket länkaren sannolikt klagar på. Variabeln definieras sedan i live2.cpp.

Steg 3

Referenser är inte heller något som finns i C. Vi måste använda pekare i stället. I detta steg byter vi därför ut alla referenser till pekare. I funktionsdeklarationen kan vi byta ut & mot *, och sedan måste vi uppdatera alla ställen där parametern eller variabeln används. Vi måste dereferera pekaren varje gång den används för att den ska bete sig som en referens. Vi måste också lägga till ett & när vi skickar in en varabel som en referens. Vi vill exempelvis ersätta me med (*me) i koden. Notera att me->foo är ett smidigare sätt att skriva (*me).foo.

Steg 4

std::vector är inte heller något som finns i C. Vi måste implementera den funktionaliteten själva med hjälp av dynamisk minnesallokering och arrayer i stället. En vector är mer eller mindre en pekare till ett array och en storlek, så vi kan ersätta vector variabeln i vår struct med en pekarvariabel och ett heltal (en vector håller också koll på sin kapacitet, men det utnyttjar vi inte i det här exemplet, så vi ignorerar det).

För att allokera minne skulle vi kunna använda new int[max], men eftersom vi vill skriva C-kod använder vi i stället malloc(max*sizeof(int)), eller bättre calloc(max, sizeof(int)), som ser till att vi inte får overflow i multiplikationen och initierar minnet till 0. Eftersom både malloc och calloc returnerar en void * måste vi i C++ explicit omvandla pekaren till rätt typ med en C-cast (int *)calloc(max, sizeof(int)). Detta behövs inte i C, så vi kan ta bort den koden senare. Notera att vi behöver inkludera cstdlib för att få tillgång till malloc och calloc. Minne frigörs med funktionen free().

En annan sak som vi måste tänka på här är hur vi itererar igenom vår data. I list_add användes iteratorer, vilket inte heller finns i C. Som tur är kan vi använda pekare på samma sätt, eftersom iteratorer är byggda för att efterlikna pekarmanipulation i C.

I C och C++ är det möjligt att modifiera vad en pekare pekar på med hjälp av vanliga aritmetiska operationer. Vi kan exempelvis ta en pekare och säga p + 1 för att få en pekare till det som ligger precis efter *p i minnet. Hur långt fram uttrycket p + 1 hoppar i minnet beror på vad p pekar på. Det enklaste är att tänka sig att p pekar på ett element i en array, och att p + 1 ger nästa element oavsett hur stort varje element. p + 1 kommer alltså peka på olika ställen om p har typen int * eller char * eftersom sizeof(int) != sizeof(char). Pekare av typen void * går alltså inte att manipulera på detta sättet, även om vissa kompilatorer tillåter det ändå.

Varför fungerar pekarmanipulation på detta sättet? Jo, idén är att det ska vara smidigt att arbeta med just arrayer. Det ser man ganska tydligt om man tittar närmare på hur arrayer fungerar i C. Om vi deklarerar en array, int p[10];, så kan vi utan problem tilldela p till en variabel av typen int *q = p;. Arrayer är alltså bara en pekare till första elementet (det finns små skillnader, exempelvis med sizeof och flerdimensionella arrayer, men vi hoppar över dem nu). Det gör att både variablerna p och q kan användas som arrayer. Det är till och med så att p[1] är ekvivalent med *(p + 1).

Allt detta gör att vi kan använda pekare som iteratorer i C. Detta är inte så förvånande egentligen eftersom iteratorer är byggda för att efterlikna pekare i C. En iterator till början av en vektor motsvaras av en pekare till första elementet, och en iterator till slutet motsvarar en pekare till elementet efter sista elementet i vårt array, det vill säga &data[max] eller ekvivalent data + max. Vi kan stega pekarna med hjälp av ++ och -- eller genom vanlig aritmetik. Vi kan därför se att ändringarna i list_add i live4.cpp är minimala.

Steg 5

Undantag finns inte heller i C, så vi kan inte kasta undantag i list_add och list_get. I list_add kan vi helt enkelt lägga till ett returvärde för att indikera om allt gick bra eller inte. Egentligen borde vi kontrollera returvärdet i main6.c, men eftersom vi vet att alla insättningar kommer att gå bra struntar vi i det.

I list_get kan vi inte göra på samma sätt eftersom funktionen redan returnerar något. I det här fallet är det ett heltal som kan vara precis vad som helst. Alltså kan vi inte ha ett speciellt returvärde som visar att list_get misslyckades. Skulle vi returnera en pekare i stället så skulle vi kanske kunna använda NULL för det. Ett annat alternativ skulle vara att returnera resultatet som en utparameter och låta funktionen returnera en bool i stället. Eftersom felen som kan uppstå i list_get tyder på programmerarfel låter vi programmet terminera genom att anropa abort. Man skulle också kunna använda assert, vilket fungerar på liknande sätt.

Steg 6

Nu har vi kommit så långt att vi nästan kan kompilera koden med C-kompilatorn. Det är bara några få detaljer kvar. Först och främst måste vi ändra vilka headerfiler vi inkluderar. Namnen cstdlib är för C++. I C heter filerna stdlib.h i stället. Vi måste också inkludera stdbool.h för att kunna använda bool.

Till slut kommer en språklig skillnad: vi kan inte längre använda sorted_list för att referera till vår struct. C har olika namnrymder för typer, structs och unions. Vår struct heter alltså struct sorted_list eftersom det skulle kunna finnas något annat som heter union sorted_list eller bara sorted_list. Om man verkligen inte vill skriva struct framför namnet varje gång kan man använda typedef struct sorted_list sorted_list för att skapa ett alias. Efter det kan vi använda C-kompilatorn för att kompilera vårt program!

Notera: Det går att använda struct foo även i C++ för att skilja på exempelvis en struct och en funktion. Det behövs exempelvis om man ska anropa systemanropet stat eftersom man då behöver en struct stat som parameter.

Utöver det behöver vi göra ett par omskrivningar i main.c för att få koden att kompilera utan varningar. Först och främst måste vi deklarera print_first som static eftersom det är en privat funktion. Utöver det måste vi explicit säga att main inte tar några parametrar. I C betyder main(): funktionen main finns, men jag orkar inte berätta vilka parametrar den tar. I stället måste vi skriva main(void).

Steg 7

Antag nu att vi vill bryta ut innehållet i while loopen inuti list_add till en funktion. Jag vill då kunna modifiera pekaren into inifrån funktionen. Om jag bara skickar den som en parameter så kommer jag få en kopia av pekaren, vilket inte räcker. Jag skulle vilja ha en referens till pekaren (int *&into), men det går inte eftersom referenser inte finns i C. Här kan jag använda samma teknik som i steg 3: jag kan skicka en pekare till pekaren som parameter, det vill säga int **into. Då kan jag komma åt originalpekaren med (*into) som tidigare, och talet vid pekaren med *(*into) (även om det inte behövs). Det finns ingen begränsning på hur många pekarindirektioner som kan användas, men använder man mer än två så är det ofta ett tecken på att man bör tänka om.

Steg 8

Ända fram till nu har variablerna i struct sorted_list varit publika. Här visar vi hur man kan göra för att skapa privata variabler i C. Mycket likt funktioner så vill vi flytta deklarationen av sorted_list till C-filen. Vi måste dock ha en framåtdeklaration (eng. forward declaration) i headerfilen så att kompilatorn vet att typen finns. Det här gör att det bara är funktioner i live8.c som vet hur sorted_list ser ut, och därmed bara den koden som kan komma åt medlemmarna.

Den här lösningen har en liten nackdel i main8.c. Eftersom vi inte längre kan allokera struct sorted_list på stacken (varför?) måste vi använda malloc i live8.c, vilket vi gärna undviker om vi kan eftersom vi nu måste komma ihåg att frigöra mer minne. Att göra datamedlemmar privata på detta viset är alltså en avvägning mellan hur viktigt det är att gömma data och hur smidig koden ska vara att använda.

Steg 9

Här har vi också lagt till möjligheten att ange ett predikat till sorteringen. Det visar på hur funktionspekare fungerar i C (och C++).

Sidansvarig: Filip Strömbäck
Senast uppdaterad: 2022-03-09