馬氏清潔功能故障

Question

我試圖寫一個函數來清理被此代碼

/* 
* Markov chain random text generator. 
*/ 

#include <string.h> 
#include <stdlib.h> 
#include <stdio.h> 
#include <string.h> 
#include <time.h> 
#include "eprintf.h" 

enum { 
NPREF = 2, /* number of prefix words */ 
NHASH = 4093, /* size of state hash table array */ 
MAXGEN = 10000 /* maximum words generated */ 
}; 

typedef struct State State; 
typedef struct Suffix Suffix; 

struct State { /* prefix + suffix list */ 
char* pref[NPREF]; /* prefix words */ 
Suffix* suf;   /* list of suffixes */ 
State* next;   /* next in hash table */ 
}; 

struct Suffix { /* list of suffixes */ 
char* word;   /* suffix */ 
Suffix* next;   /* next in list of suffixes */ 
}; 

State* lookup(char *prefix[], int create); 
void build(char *prefix[], FILE*); 
void generate(int nwords); 
void add(char *prefix[], char *word); 

State* statetab[NHASH]; /* hash table of states */ 

char NONWORD[] = "\n"; /* cannot appear as real word */ 

/* markov main: markov-chain random text generation */ 
int main(void) 
{ 
int i, nwords = MAXGEN; 
char *prefix[NPREF];  /* current input prefix */ 

int c; 
long seed; 

setProgName("markov"); 
seed = time(NULL); 

srand(seed); 
for (i = 0; i < NPREF; i++) /* set up initial prefix */ 
    prefix[i] = NONWORD; 
build(prefix, stdin); 
add(prefix, NONWORD); 
generate(nwords); 
return 0; 
} 

const int MULTIPLIER = 31; /* for hash() */ 

/* hash: compute hash value for array of NPREF strings */ 
unsigned int hash(char* s[NPREF]) 
{ 
unsigned int h; 
unsigned char *p; 
int i; 

h = 0; 
for (i = 0; i < NPREF; i++) 
    for (p = (unsigned char *) s[i]; *p != '\0'; p++) 
     h = MULTIPLIER * h + *p; 
return h % NHASH; 
} 


/* lookup: search for prefix; create if requested. */ 
/* returns pointer if present or created; NULL if not. */ 
/* creation doesn't strdup so strings mustn't change later. */ 
State* lookup(char *prefix[NPREF], int create) 
{ 
int i, h; 
State *sp; 

h = hash(prefix); 
for (sp = statetab[h]; sp != NULL; sp = sp->next) { 
    for (i = 0; i < NPREF; i++) 
     if (strcmp(prefix[i], sp->pref[i]) != 0) 
      break; 
    if (i == NPREF)  /* found it */ 
     return sp; 
} 
if (create) { 
    sp = (State *) emalloc(sizeof(State)); 
    for (i = 0; i < NPREF; i++) 
     sp->pref[i] = prefix[i]; 
    sp->suf = NULL; 
    sp->next = statetab[h]; 
    statetab[h] = sp; 
} 
return sp; 
} 

/* addsuffix: add to state. suffix must not change later */ 
void addsuffix(State *sp, char *suffix) 
{ 
Suffix *suf; 

suf = (Suffix *) emalloc(sizeof(Suffix)); 
suf->word = suffix; 
suf->next = sp->suf; 
sp->suf = suf; 
} 

/* add: add word to suffix list, update prefix */ 
void add(char *prefix[NPREF], char *suffix) 
{ 
State *sp; 

sp = lookup(prefix, 1); /* create if not found */ 
addsuffix(sp, suffix); 
/* move the words down the prefix */ 
memmove(prefix, prefix+1, (NPREF-1)*sizeof(prefix[0])); 
prefix[NPREF-1] = suffix; 
} 

/* build: read input, build prefix table */ 
void build(char *prefix[NPREF], FILE *f) 
{ 
char buf[100], fmt[10]; 

/* create a format string; %s could overflow buf */ 
sprintf(fmt, "%%%ds", sizeof(buf)-1); 
while (fscanf(f, fmt, buf) != EOF) 
    add(prefix, estrdup(buf)); 
} 

/* generate: produce output, one word per line */ 
void generate(int nwords) 
{ 
State *sp; 
Suffix *suf; 
char *prefix[NPREF], *w; 
int i, nmatch; 

for (i = 0; i < NPREF; i++) /* reset initial prefix */ 
    prefix[i] = NONWORD; 

for (i = 0; i < nwords; i++) { 
    sp = lookup(prefix, 0); 
    if (sp == NULL) 
     eprintf("internal error: lookup failed"); 
    nmatch = 0; 
    for (suf = sp->suf; suf != NULL; suf = suf->next) 
     if (rand() % ++nmatch == 0) /* prob = 1/nmatch */ 
      w = suf->word; 
    if (nmatch == 0) 
     eprintf("internal error: no suffix %d %s", i, prefix[0]); 
    if (strcmp(w, NONWORD) == 0) 
     break; 
    printf("%s\n", w); 
    memmove(prefix, prefix+1, (NPREF-1)*sizeof(prefix[0])); 
    prefix[NPREF-1] = w; 
} 
} 

這裏產生的哈希表是我迄今爲止對我清潔功能

/*Clean Function*/ 
void clean_up(State *sp) 
{ 
State *temp; 
Suffix *temp2, temp3; 

for(int h = 0; h < NHASH; h++) 
{ 
    for (sp = statetab[h]; sp != NULL; sp = sp->next) 
    { 
     while(sp->suf != NULL) 
     { 
      temp2= sp->suf; 
      temp3= *temp2->next; 
      free(temp2); 
      sp->suf= &temp3; 
     } 

    } 
} 
} 

我認爲我在正確的軌道上，我正在經歷哈希表中的每個索引，然後從狀態到狀態並釋放後綴。我不知道該怎麼做前綴，因爲在我釋放每個狀態之前我必須釋放它們。任何幫助將不勝感激。

Answer 1

在代碼中，您要複製到TEMP3節點，住在自動記憶（「在棧上」）指向SP->薩夫本內存將（在循環的下一次迭代）導致自由地調用此對象的地址（其具有不被的malloc獲得的，並且因此不能由被釋放遊離（））

void clean_up(State *sp) 
{ 
State *temp; 
Suffix *temp2, **pp; 

for(int h = 0; h < NHASH; h++) 
{ 
    for (sp = statetab[h]; sp != NULL; sp = sp->next) 
    { 
     for (pp = &sp->suf; *pp; *pp = temp2) 
     { 
      temp2 = (*pp)->next;  
      free(*pp); 
     } 

    } 
} 
} 

Answer 2

示例代碼從馬爾可夫程序在The Practice of Programming由Kernighan和派克衍生，一本最優秀的書。

既然你正試圖清理statetab，主要清理功能，不需要任何理由。您必須小心，不要直接在statetab中釋放狀態，但您需要釋放鏈接關閉的輔助狀態statetab[i].next。

typedef struct State State; 
typedef struct Suffix Suffix; 

struct State { /* prefix + suffix list */ 
char* pref[NPREF]; /* prefix words */ 
Suffix* suf;   /* list of suffixes */ 
State* next;   /* next in hash table */ 
}; 

struct Suffix { /* list of suffixes */ 
char* word;   /* suffix */ 
Suffix* next;   /* next in list of suffixes */ 
}; 

State* statetab[NHASH]; /* hash table of states */ 

static void free_state(State *state); 
static void free_suffix(Suffix *suffix); 

static void cleanup(void) 
{ 
    for (int i = 0; i < NHASH; i++) 
     free_state(statetab[i]); 
} 

static void free_state(State *state) 
{ 
    if (state != 0) 
    { 
     for (int i = 0; i < NPREF; i++) 
      free(state->pref[i]); 
     free_suffix(state->suf); 
     if (state->next != 0) 
     { 
      free_state(state->next); 
      free(state->next); 
     } 
    } 
} 

static void free_suffix(Suffix *suffix) 
{ 
    if (suffix != 0) 
    { 
     free(suffix->word); 
     free_suffix(suffix->next); 
     free(suffix); 
    } 
} 

你看到我是如何設計的基礎上，xxxx結構的設計free_xxxx()代碼？

警告講師：未編譯的代碼，更少的測試代碼。

---

我挖掘了TPOP網站的代碼，並嘗試應用它。我提出了一些修正到的釋放碼上述（語法錯誤固定，在free_state()和free_suffix()空檢查），但是代碼作爲一個整體不被設計爲允許數據被釋放。

有幾個問題。首先，一些前綴未分配（NONWORD）。通過測試一個前綴是否爲NONWORD，可能避免釋放這些字符串，但這很糟糕。也可以分配這些前綴（將NONWORD替換爲estrdup(NONWORD)）。我認爲還有另一個地方，在某個地方，一個未分配的指針被隱藏在狀態表的前綴中;我越來越崩潰的malloc()「釋放未分配存儲器」（這是從「雙釋放分配的內存」不同，我相信）的抱怨，但我沒有設法解決這個問題。

然而，再換個問題;前綴被重用。也就是說，系統中幾乎每個前綴都被用作一個前綴的第二個單詞，然後作爲下一個前綴的第一個單詞。因此，你不能隨意釋放前綴。

如果你設計這個以便內存可以被釋放，那麼你可能會設計它，以便有一個'原子'系統（不可變的字符串），以便每個單詞被分配一次並且經常重用如果需要的話（D Hanson的C Interfaces and Implementations: Techniques for Creating Reusable Code作爲術語的來源）。釋放狀態表的代碼將只集中在非字數據上。會有代碼釋放整套原子。

我跑了馬爾科夫程序valgrind沒有清理;沒有內存訪問問題，也沒有泄露的數據;在節目出口處仍然可以訪問。我使用的約15000字（約2900字不同）中的數據文件，以及統計信息：

==9610== HEAP SUMMARY: 
==9610==  in use at exit: 695,269 bytes in 39,567 blocks 
==9610== total heap usage: 39,567 allocs, 0 frees, 695,269 bytes allocated 
==9610== 
==9610== LEAK SUMMARY: 
==9610== definitely lost: 0 bytes in 0 blocks 
==9610== indirectly lost: 0 bytes in 0 blocks 
==9610==  possibly lost: 0 bytes in 0 blocks 
==9610== still reachable: 695,269 bytes in 39,567 blocks 

所以，你爲自己設定一個有趣的練習。但是，我認爲如果不修改一些內存分配機制，這樣數據就可以乾淨地釋放，這是不可能實現的。

（在BSD，因此Mac OS X上也有一對叫setprogname()和getprogname()在<stdlib.h>功能。在BSD，setprogname()是main()之前自動調用大幹快（與argv[0]，我相信）。該聲明中eprintf.h衝突與<stdlib.h>的聲明，這可能是爲什麼在這個問題的代碼使用setProgName()而不是原來的setprogname()。我選擇在eprintf.h修復setprogname()，使花了const char *參數，因此在<stdlib.h>匹配的聲明。）

---

^{TPOP之前在 http://plan9.bell-labs.com/cm/cs/tpop和 http://cm.bell-labs.com/cm/cs/tpop但都是現在（2015年8月10日）打破。 另請參見TPOP上的維基百科。}