2

ここに（私が思うに）問題に関連するコードのスニペットを投稿しますが、必要に応じてペーストビンすることができます。おそらくすでに十分な数のコードを投稿しています：P

私のプログラムには、特定のハッシュバケットが20エントリに達したときに2倍にする必要があるハッシュテーブルが含まれています。ロジックは優れていると思いますが、それは魅力のようにコンパイルされますが、 セグメンテーション違反が発生します。サイズを変更しない場合、コードは魅力のように実行されますが、サイズを変更すると混乱します。

助けてくれてありがとう:)

エラー

Program received signal SIGSEGV, Segmentation fault.
0x0000000000401012 in ml_add (ml=0x7fffffffe528, me=0x75a5a0) at mlist.c:74
74          while((cursorNode->next) != NULL){
Missing separate debuginfos, use: debuginfo-install glibc-2.12-1.80.el6_3.5.x86_64
(gdb) backtrace
#0  0x0000000000401012 in ml_add (ml=0x7fffffffe528, me=0x75a5a0) at mlist.c:74
#1  0x0000000000401554 in main (argc=1, argv=0x7fffffffe638) at finddupl.c:39

ハッシュテーブルの構造

typedef struct bN { //linked list node containing data and next
    MEntry *nestedEntry;
    struct bN *next;
} bucketNode;

typedef struct bL { // bucket as linked list
    struct bN *first;
    int bucketSize;
} bucket;

struct mlist {
    struct bL *currentTable; //bucket array
};

関数の追加

int ml_add(MList **ml, MEntry *me){

    MList *tempList;
    tempList = *ml;

    bucketNode *tempNode = (bucketNode *)malloc(sizeof(bucketNode));
    tempNode->nestedEntry = me;
    tempNode->next = NULL;

    unsigned long currentHash = me_hash(me, tableSize);

    if((tempList->currentTable[currentHash].bucketSize) == 0)   {
        tempList->currentTable[currentHash].first = tempNode;
        tempList->currentTable[currentHash].bucketSize = (tempList->currentTable[currentHash].bucketSize) + 1;
    }
    else if((tempList->currentTable[currentHash].bucketSize) == 20){
        printf("About to resize");
        printf("About to resize");
        tempList = ml_resize(&tempList, (tableSize * 2));
        tableSize = tableSize * 2;
        ml_add(&tempList,me);
    }
    else{
        bucketNode *cursorNode;
        cursorNode = tempList->currentTable[currentHash].first;
        while((cursorNode->next) != NULL){
            cursorNode = cursorNode->next;
        }
        cursorNode->next = tempNode;
        tempList->currentTable[currentHash].bucketSize = (tempList->currentTable[currentHash].bucketSize) + 1;
        return 1;
    }

    return 1;

}

サイズ変更機能

MList *ml_resize(MList **ml, int newSize){
    MList *oldList;
    oldList = *ml;

    MList *newList;

    if ((newList = (MList *)malloc(sizeof(MList))) != NULL){
        newList->currentTable = (bucket *)malloc(newSize * sizeof(bucket));
        int i;
        for(i = 0; i < newSize; i++){
            newList->currentTable[i].first = NULL;
            newList->currentTable[i].bucketSize = 0;
        }
    }

    int j;
    for(j = 0; j < tableSize; j++){
        bucketNode *cursorNode = oldList->currentTable[j].first;
        bucketNode *nextNode;
        while(cursorNode != NULL){
            nextNode = cursorNode->next;
            ml_transfer(&newList, cursorNode, newSize); 
            cursorNode = nextNode;  
        }
    }

    free(oldList);

    return newList;
}

新しいリスト機能に転送

void ml_transfer(MList **ml, bucketNode *insertNode, int newSize){

    MList *newList;
    newList = *ml;

    bucketNode *tempNode = insertNode;

    tempNode->next = NULL;

    unsigned long currentHash = me_hash((tempNode->nestedEntry), newSize);

    if((newList->currentTable[currentHash].bucketSize) == 0)    {
        newList->currentTable[currentHash].first = tempNode;
        newList->currentTable[currentHash].bucketSize = (newList->currentTable[currentHash].bucketSize) + 1;
    }
    else{
        bucketNode *cursorNode;
        cursorNode = newList->currentTable[currentHash].first;
        while((cursorNode->next) != NULL){
            cursorNode = cursorNode->next;
        }
        cursorNode->next = tempNode;
        newList->currentTable[currentHash].bucketSize = (newList->currentTable[currentHash].bucketSize) + 1;
    }

}
4

1 に答える 1

1

問題はおそらく、ハッシュテーブルのサイズが変更されるたびml_add()に関数がパラメーターノードの更新に失敗するという事実にあります。MList** ml

ハッシュテーブルのサイズが変更されると、古いハッシュテーブルは破棄されますが（ml_resize（）内）、サイズ変更された新しいハッシュテーブルへのポインターは、tempList変数で更新されます。これは*mlのローカルコピーです。関数の外部でhashTableの参照を保持している変数を変更するには、* mlも更新する必要があります。そうしないと、削除された無効なHashtableを指したままになります。次の変更を試してください。

...
else if((tempList->currentTable[currentHash].bucketSize) == 20){
        printf("About to resize");
        printf("About to resize");
        tempList = ml_resize(&tempList, (tableSize * 2));
        tableSize = tableSize * 2;
        ml_add(&tempList,me);
        *ml = tempList;   // this is necesary to fix the pointer outside the
                           // function, that still points to the hashtable 
                           // memory freed by the resize function
}
...

また、コードに存在する2つのメモリリークについて私が行ったコメントにも注意してください。また、@ hexistが指摘した、先頭のいいねリストの最後に挿入する必要がないことを考慮に入れて、コードを簡略化します。それをより速くします。

于 2012-10-25T01:11:29.327 に答える