Programmeringsmetodik: Lösningar till tentamen 2009-11-05

Observera att detta är ett förslag på lösning. Det finns andra lösningar som också är korrekta.

Här finns också ett program som slumpar fram filen avlyssnat.txt, så att man kan provköra sitt program: skapa-avlyssnat.c. (Programmet skapar en fil med 2 miljarder rader, som innehåller 2 miljoner unika IP-nummer, och som blir ungefär 50 gigabyte stor.)

Uppgiften (30 p)

Den här lösningen använder en hashtabell med fix storlek. På en modern dator med snabb processor (Intel Core i7 920) men förhållandevis långsam disk (Western Digital Caviar Green 1TB SATA/300), och med 2 miljarder rader i avlyssnat.txt och 2 miljoner unika IP-nummer, tar programmet 52 minuter att köra. Att bara läsa filen med 2 miljarder rader från disken, utan att behandla data på något sätt, tar på samma dator 11 minuter. Programmet använder ungefär 90 megabyte minne.

Programmet består av tre moduler:

Huvudmodulen, med bland annat main-funktionen. Denna modul består av filen hittamax.c.
Datatypen Dator, som används för att spara information om en dator. En dator har ett IP-nummer, ett antal skickade meddelanden och ett antal mottagna meddelanden. Denna modul består av filen Dator.h. (Filen Dator.c är tom och behövs inte.)
Datatypen Datorer, som används för att spara information om en hel mängd av datorer.
1. Man kan initiera en datormängd med hjälp av funktionen datorer_init.
2. Man kan lägga till en ny dator med hjälp av funktionen addera_dator.
3. Man kan söka efter en dator med ett visst IP-nummer med hjälp av funktionen hitta_dator.
4. Man kan söka efter datorerna med maximalt antal skickade respektive mottagna meddelanden med hjälp av funktionen datorer_max.
Denna modul består av filerna Datorer.h och Datorer.c.

Filen hittamax.c:

// hittamax.c

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

Datorer datorer;

unsigned int strang_till_ip(char* strang) {
    unsigned int byte1, byte2, byte3, byte4;
    sscanf(strang, "%u.%u.%u.%u", &byte1, &byte2, &byte3, &byte4);
    // Kan bli fel ordning, men det spelar ingen roll!
    unsigned int ip = (byte1 << 24) | (byte2 << 16) | (byte3 << 8) | byte4;
    return ip;
}

char* ip_till_strang(unsigned int ip) {
    static char farlig_statisk_buffer[100];
    unsigned int byte1, byte2, byte3, byte4;
    byte1 = (ip & 0xff000000) >> 24;
    byte2 = (ip & 0x00ff0000) >> 16;
    byte3 = (ip & 0x0000ff00) >> 8;
    byte4 = (ip & 0x000000ff);
    sprintf(farlig_statisk_buffer, "%u.%u.%u.%u", byte1, byte2, byte3, byte4);
    return farlig_statisk_buffer;
}

void las_filen(Datorer* datorer, char* filnamn) {
    FILE* avlyssnat = fopen(filnamn, "r");
    if (avlyssnat == NULL) {
        fprintf(stderr, "Gick inte att läsa filen '%s'.\n", filnamn);
        exit(EXIT_FAILURE);
    }
    char sandare[25 + 1]; // Max: nnn.nnn.nnn.nnn = 15 tecken
    char mottagare[15 + 1];
    while (fscanf(avlyssnat, "%15s %15s", sandare, mottagare) == 2) {
        unsigned int ip_sandare = strang_till_ip(sandare);
        unsigned int ip_mottagare = strang_till_ip(mottagare);
        Dator* sandande_dator = addera_dator(datorer, ip_sandare);
        sandande_dator->antal_skickade += 1;
        Dator* mottagande_dator = addera_dator(datorer, ip_mottagare);
        mottagande_dator->antal_mottagna += 1;
    }
    fclose(avlyssnat);
}

int main(void) {
    datorer_init(&datorer);
    las_filen(&datorer, "avlyssnat.txt");
    Dator* dator_max_skickade;
    Dator* dator_max_mottagna;
    datorer_max(&datorer, &dator_max_skickade, &dator_max_mottagna);

    printf("Flest skickade från IP %u (%s): %u\n",
           dator_max_skickade->ip,
           ip_till_strang(dator_max_skickade->ip),
           dator_max_skickade->antal_skickade);
    printf("Flest mottagna till IP %u (%s): %u\n",
           dator_max_mottagna->ip,
           ip_till_strang(dator_max_mottagna->ip),
           dator_max_mottagna->antal_mottagna);

    return 0;
} // main

Filen Dator.h:

// Dator.h

#ifndef DATOR_H
#define DATOR_H

struct Dator {
    unsigned int ip;
    unsigned int antal_skickade;    
    unsigned int antal_mottagna;
};

typedef struct Dator Dator;

#endif

Filen Dator.c är tom och behövs inte.

Filen Datorer.h:

// Datorer.h

#ifndef DATORER_H
#define DATORER_H

#include "Dator.h"

#define HASHTABELLENS_STORLEK 3000017

struct Datorhashpost {
    Dator dator;
    struct Datorhashpost* nasta_i_bucketen;
};

typedef struct Datorhashpost Datorhashpost;

struct Datorer {
    Datorhashpost* hashtabell[HASHTABELLENS_STORLEK];
};

typedef struct Datorer Datorer;

extern void datorer_init(Datorer* datorer);
extern void datorer_max(Datorer* datorer, Dator** max_skickade, Dator** max_mottagna);
extern Dator* hitta_dator(Datorer* datorer, unsigned int ip);
extern Dator* addera_dator(Datorer* datorer, unsigned int ip);

#endif

Filen Datorer.c:

// Datorer.c

#include <stdlib.h>
#include "Dator.h"
#include "Datorer.h"

void datorer_init(Datorer* datorer) {
    for (int bucket = 0; bucket < HASHTABELLENS_STORLEK; ++bucket)
        datorer->hashtabell[bucket] = NULL;
} // datorer_init

void datorer_max(Datorer* datorer, Dator** max_skickade, Dator** max_mottagna) {
    Dator* max_skickade_hittills = NULL;
    Dator* max_mottagna_hittills = NULL;
    
    for (int bucket = 0; bucket < HASHTABELLENS_STORLEK; ++bucket) {
        Datorhashpost* aktuell = datorer->hashtabell[bucket];
        while (aktuell != NULL) {
            if (max_skickade_hittills == NULL || aktuell->dator.antal_skickade > max_skickade_hittills->antal_skickade)
                max_skickade_hittills = &aktuell->dator;
            if (max_mottagna_hittills == NULL || aktuell->dator.antal_mottagna > max_mottagna_hittills->antal_mottagna)
                max_mottagna_hittills = &aktuell->dator;
            aktuell = aktuell->nasta_i_bucketen;
        }
    }
    *max_skickade = max_skickade_hittills;
    *max_mottagna = max_mottagna_hittills;
} // datorer_max

static unsigned int hashfunktion(unsigned int ip) {
    return ip % HASHTABELLENS_STORLEK;
} // hashfunktion

Dator* hitta_dator(Datorer* datorer, unsigned int ip) {
    unsigned int bucket = hashfunktion(ip);
    Datorhashpost* aktuell = datorer->hashtabell[bucket];
    while (aktuell != NULL) {
        if (aktuell->dator.ip == ip)
            return &aktuell->dator;
        aktuell = aktuell->nasta_i_bucketen;
    }
    return NULL;
} // hitta_dator

Dator* addera_dator(Datorer* datorer, unsigned int ip) {
    unsigned int bucket = hashfunktion(ip);
    Datorhashpost* aktuell = datorer->hashtabell[bucket];
    while (aktuell != NULL) {
        if (aktuell->dator.ip == ip)
            return &aktuell->dator; // Den fanns redan!
        aktuell = aktuell->nasta_i_bucketen;
    }
    Datorhashpost* ny_dator = malloc(sizeof(Datorhashpost));
    ny_dator->dator.ip = ip;
    ny_dator->dator.antal_skickade = 0;
    ny_dator->dator.antal_mottagna = 0;
    ny_dator->nasta_i_bucketen = datorer->hashtabell[bucket];
    datorer->hashtabell[bucket] = ny_dator;
    return &ny_dator->dator;
} // addera_dator

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 22 november 2009