Zugriff auf Nullzeiger fuehrt zu Segfault

thpetrus

Hallo, ich schreibe gerade an eine Hashtabler und um Kollisionen zu vermeiden, werden Eintraege mit dem selben Hash in einer Liste gespeichert. Leider reichen meine C Kenntnisse nicht dazu aus, um diese Listen jeweils zu durchlaufen.

dict.h:

#ifndef __DICT
#define __DICT

#define DICT_EMPTY_PLACEHOLDER ""

typedef struct dictEntry {
    void *key;
    void *value;
    struct dictEntry *next;
} dictEntry;

typedef struct dict {
    dictEntry **table;
    unsigned long size;
    unsigned long items;
} dict;

unsigned long hash(unsigned char *string);

dict *dictCreate(unsigned long size);
void dictAdd(dict *d, void *key, void *value);
void *dictFetch(dict *d, void *key);
void dictRemove(dict *d, void *key);

void _dictAddRaw(dict *d, dictEntry *entry);
dict *_dictRehash(dict *d);

#endif

dict.c

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

/* TODO
 * integer hash function
 * rehashing
 */

/* courtesy of Daniel J Bernstein */
unsigned long hash(unsigned char *string) {
    unsigned long hash = 5381;
    int c;

    while (c = *string++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

dict *dictCreate(unsigned long size) {
    dict *d;

    d = malloc(sizeof(dict));
    d->size  = size;
    d->items  = 0;
    d->table = malloc(size * sizeof(dictEntry*));

    return d;
}

void dictAdd(dict *d, void *key, void *value) {
    dictEntry *entry;

    entry = malloc(sizeof *entry);

    entry->key   = key;
    entry->value = value;
    entry->next  = NULL;

    if ((d->items / d->size) >= 0.5) d = _dictRehash(d);

    _dictAddRaw(d, entry);
}

void _dictAddRaw(dict *d, dictEntry *entry) {
    int index = hash(entry->key) & d->size;

    if (d->table[index]) {
        dictEntry *next, *prev;

        next = d->table[index];

        while (next) {
            prev = next;
            /* this line seg faults */
            next = next->next;
        }

        prev->next = entry;
    } else {
        d->table[index] = entry;
    }
    d->items++;
}

dict *_dictRehash(dict *d) {
    int i;
    dict *_d;
    dictEntry *dit, *entry;

    _d = dictCreate(d->size * 2);

    for (i = 0; i < d->size; i++) {
        dit = d->table[ i];

        while (dit) {
            entry = dit;
            entry->next = 0;

            _dictAddRaw(_d, entry);
            dit = dit->next;
        }
    }

    free(d->table);
    free(d);

    return _d;
}

void *dictFetch(dict *d, void *key) {
    int index = hash(key) & d->size;

    if (d->table[index]->key == key) {
        return d->table[index]->value;
    } else {
        dictEntry *next;
        next = d->table[index];

        while (next) {
            if (next->key == key) {
                return next->value;
            }

            next = next->next;
        }

        return DICT_EMPTY_PLACEHOLDER;
    }
}

void dictRemove(dict *d, void *key) {
    int index = hash(key) & d->size;
    dictEntry *dit, *next, *prev;
    dit = d->table[index];

    while (dit) {
        if (dit->key == key) {
            prev = dit;
            next = dit->next;

            prev->next = next;
            free(dit);
        }

        dit = dit->next;
    }
}

void dictFree(dict *d) {
    int i;
    dictEntry *dit, *next;

    for (i = 0; i < d->size; i++) {
        dit = d->table[ i];

        while (dit) {
            next = dit->next;
            free(dit);

            dit = next;
        }
    }
}

Dem ubrigen Code muss eigentlich erstmal keine Beachtung geschenkt werden, die Fehlerquelle ist _dictAddRaw(). Beim iterieren von d->table[index] (dieser Arrayeintrag enthaelt jeweils die Listen), versuche ich per dictEntry.next->next->next (usw.) auf die jeweils folgenden Elemente zuzugreifen:

Eintrag1->Eintrag2->Eintrag3->???

Beim letzten Element, welches in next keinen validen Zeiger enthaelt, kommt es zum Segmentation Fault. Wie kann ich diesen Fehler vermeiden? Falls moeglich bitte mit Erklaerung, die Hashtable ist mein Erstlingswerk.

Ich finde deine Berechnung vom Index etwas merkmürdig. (Zeile 47)
Was passiert, wenn size = 32 ist und hash() aber 16 ergibt?

Zudem sind Bezeichner die mit einem _ beginnen, dem Compiler vorbehalten.

thpetrus

Hallo, danke fuer den Beitrag, aber beides hat nichts mit dem Fehler zu tun.

Ich habe den problematischen Code nochmal isoliert, vielleicht kann man es dann besser betrachten:

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

typedef struct entry {
    void *value;
    struct entry *next;
} entry;

typedef struct list {
    entry *items;
} list;

list *create(void) {
    list *l;

    l = malloc (sizeof(list));
    l->items = malloc(sizeof(entry*));
    l->items->next = NULL;

    return l;
}

void add(list *l, void *value) {
    entry *temp, *last, *new;

    for (temp = l->items; temp != NULL; temp = temp->next) {
        last = temp;
    }

    new = malloc(sizeof(*new));

    new->value = value;
    new->next = NULL;

    last->next = new;
}

void display(list *l) {
    entry *temp;

    for (temp = l->items; temp != NULL; temp = temp->next) {
        printf("%s\n", temp->value);
    }
}

int main(void) {
    list *l = create();

    add(l, "item1");
    add(l, "item2");
    add(l, "item3");
    add(l, "item4");

    display(l);

    return 0;
}

Zeile 17:
Welchen Wert hat sizeof(entry*) ? (Das ist ein Zeiger.)

thpetrus

Stimmt, das ist ein Fehler. Es muss direkt sizeof(entry) sein.

Der Fehler in der Liste ist, dass l->items nicht initliaisiert wird, deshalb Segfault, wenn man die Schleife iteriert. Aendert man Zeile 18 in:

l->items = NULL;

funktioniert die Liste.

Bei der Hashtable ist der Fehler auch eine Variaibleninitialisierung, naemlich in dict.table (jedes Arrayelement muss initialisiert werden), sowie ein Fehler in der Hashberechnung: index muss jeweils um eins verringert werden, weil dict.size der tatsaechlichen Groesse entspricht und nicht dem hoechsten Arrayindex.
Es sind noch ein paar kleinere Fehler im Code, die ich mittlerweile ausgemaerzt habe.

Danke!

Vorsicht mit den Begriffen.

thpetrus schrieb:

Der Fehler in der Liste ist, dass l->items nicht initliaisiert wird, deshalb Segfault, wenn man die Schleife iteriert. Aendert man Zeile 18 in:
l->items = NULL;
funktioniert die Liste.

Nicht ganz.
Bisher stand da: l ->items = malloc(sizeof(entry*));
Das ist eine erstmalige Wertzuweisung und demnach eine Initialisierung.

Das nachfolgende l->items->next = NULL; lief allerdings schon in Speicher, der dir nicht mehr gehörte, da du durch das entry* zuwenig Speicher gefordert hast.
Also konnt das ->next jederzeit überschrieben werden.

Wutz

Wer für das simple Aufsammeln von einfachsten Daten in einer Collection verkettete Listen verwendet, ist selbst schuld.