Programexempel från Progmet-föreläsning 13, måndag 27 oktober 2008
==================================================================



1. Forts: Den abstrakta datatypen "mängd av heltal"
---------------------------------------------------


Repetition
----------

1. Fast array av tal, ett tal per position
2. Dynamisk allokerad array av tal, ett tal per position
3. Fast array av flaggor, en per möjligt tal



Variant 4 - fast array av flaggor, en per möjligt tal, men packad
-----------------------------------------------------------------

/* IntSet.h */

#ifndef INTSET_H
#define INTSET_H

#include <limits.h>

#define INTSET_MAX_NUMBER 1000
#define INTSET_NR_BYTES ((INTSET_MAX_NUMBER + 1) / CHAR_BIT + 1)

struct IntSet {
    char members[INTSET_NR_BYTES];
};

typedef struct IntSet IntSet;

extern void IntSet_init(IntSet* isp);
extern void IntSet_add(IntSet* isp, int n);
extern int IntSet_is_member(IntSet* isp, int n);
extern void IntSet_remove(IntSet* isp, int n);
extern void IntSet_cleanup(IntSet* isp);

#endif

/* IntSet.c */

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

void IntSet_init(IntSet* isp) {
    for (int i = 0; i < INTSET_NR_BYTES; ++i)
        isp->members[i] = 0;
}

void IntSet_add(IntSet* isp, int new_number) {
    if (IntSet_is_member(isp, new_number)) {
        // Already a member, so do nothing
    }
    else if (new_number < 0 || new_number > INTSET_MAX_NUMBER) {
        fprintf(stderr, "IntSet: Number outside allowed range. Sorry.\n");
        exit(EXIT_FAILURE);
    }
    else {
        isp->members[new_number / CHAR_BIT] |= (1 << new_number % CHAR_BIT);
    }
}

int IntSet_is_member(IntSet* isp, int wanted) {
    if (wanted < 0 || wanted > INTSET_MAX_NUMBER)
        return 0;
    else
        return (isp->members[wanted / CHAR_BIT] & (1 << wanted % CHAR_BIT)) != 0;
        // return isp->members[wanted / CHAR_BIT] & (1 << wanted % CHAR_BIT); -- Doesn't work:
}

void IntSet_remove(IntSet* isp, int doomed) {
    if (doomed < 0 || doomed > INTSET_MAX_NUMBER) {
        // Outside range, so can't be in the set. Do nothing.
        exit(EXIT_FAILURE);
    }
    else {
        isp->members[doomed / CHAR_BIT] &= ~(1 << doomed % CHAR_BIT);
    }
}

void IntSet_cleanup(IntSet* isp) {
    for (int i = 0; i <= INTSET_NR_BYTES; ++i)
        isp->members[i] = 0;
}



Variant 5 - binärt träd
-----------------------

/* IntSet.h */

#ifndef INTSET_H
#define INTSET_H

struct IntSetNode {
    int member;
    struct IntSetNode* left;
    struct IntSetNode* right;
};

struct IntSet {
    struct IntSetNode* root;
};

typedef struct IntSet IntSet;

extern void IntSet_init(IntSet* isp);
extern void IntSet_add(IntSet* isp, int n);
extern int IntSet_is_member(IntSet* isp, int n);
extern void IntSet_remove(IntSet* isp, int n);
extern void IntSet_cleanup(IntSet* isp);

#endif

/* IntSet.c */

....



Variant 6 - hashtabell
----------------------

/* IntSet.h */

#ifndef INTSET_H
#define INTSET_H

#define INTSET_HASH_TABLE_SIZE 4703

struct IntSetHashNode {
    int member;
    struct IntSetHashNode* next_in_bucket;
};

struct IntSet {
    struct IntSetHashNode* hash_table[INTSET_HASH_TABLE_SIZE];
};

typedef struct IntSet IntSet;

extern void IntSet_init(IntSet* isp);
extern void IntSet_add(IntSet* isp, int new_number);
extern int IntSet_is_member(IntSet* isp, int wanted);
extern void IntSet_remove(IntSet* isp, int wanted);
extern void IntSet_cleanup(IntSet* isp);

#endif

/* IntSet.c */

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

void IntSet_init(IntSet* isp) {
    for (int i = 0; i < INTSET_HASH_TABLE_SIZE; ++i)
        isp->hash_table[i] = NULL;
}

static unsigned int hash_function(int n) {
    if (n < 0)
        n = -n;
    return n % INTSET_HASH_TABLE_SIZE;
}

void IntSet_add(IntSet* isp, int new_number) {
    if (IntSet_is_member(isp, new_number)) {
        // Already a member, so do nothing
    }
    else {
        struct IntSetHashNode* newnode = malloc(sizeof(struct IntSetHashNode));
        if (newnode == NULL) {
            fprintf(stderr, "IntSet: Minnet är fullt. Vi beklagar. Adjö.\n");
            exit(EXIT_FAILURE);
        }
        newnode->member = new_number;
        unsigned int position = hash_function(new_number);
        newnode->next_in_bucket = isp->hash_table[position];
        isp->hash_table[position] = newnode;
    }
}

int IntSet_is_member(IntSet* isp, int wanted) {
    unsigned int position = hash_function(wanted);
    struct IntSetHashNode* p = isp->hash_table[position];
    while (p != NULL) {
        if (p->member == wanted)
            return 1;
        else
            p = p->next_in_bucket;
    }
    return 0;
}

void IntSet_remove(IntSet* isp, int wanted) {
    unsigned int position = hash_function(wanted);
    struct IntSetHashNode* p = isp->hash_table[position];
    struct IntSetHashNode* previous = NULL;
    while (p != NULL) {
        if (p->member == wanted) {
            struct IntSetHashNode* doomed = p;
            if (previous == NULL)
                isp->hash_table[position] = p->next_in_bucket;
            else
                previous->next_in_bucket = p->next_in_bucket;
            free(doomed);
            return;
        }
        previous = p;
        p = p->next_in_bucket;
    }
}

void IntSet_cleanup(IntSet* isp) {
    for (int i = 0; i < INTSET_HASH_TABLE_SIZE; ++i) {
        struct IntSetHashNode* p = isp->hash_table[i];
        while (p != NULL) {
            struct IntSetHashNode* doomed = p;
            p = p->next_in_bucket;
            free(doomed);
        }
    }
}



2. Hårdvarunära programmering
-----------------------------

minesmappning
volatile