C言語メモリ管理(初級)----チェーンテーブル

前の文章では2次元動的配列の作成と破棄を実現しましたが、チェーンテーブル、読者はチェーンテーブルの基本的な知識を持っていなければなりません.本稿のチェーンテーブルの実現は読者がよく知っている実現といくつかの違いがあります.
文字列形式の式を受け入れ、その結果を計算して出力する計算機プログラムを書くと仮定します.まず、入力した文字列をいくつかの基本的な式要素に分割するパスです.これらの式要素には、演算子、演算数、カッコが含まれ、それぞれ異なる属性があります.たとえば、演算子には優先度プロパティがあります.これらの式要素をチェーンテーブルに保存する必要があります.計算中に再帰的に計算するだけでいいです.私たちはこのチェーン時計を実現します.
式要素の構造は次のとおりです.

struct exp_elem
{
    char *body;                /*      */
    int type;                /*    */
    struct exp_elem *parent;
    struct exp_elem *next;
};

チェーンテーブルは、最初のノードを指すポインタにすぎません.ここでは、式と呼びます.

typedef struct exp_elem* express_t;

同時に、構文解析の結果を格納するためにチェーンテーブルオブジェクトを定義します.

express_t the_express;

メモリ管理の習慣を身につけるために、メモリの割り当てが成功したらすぐに初期化したほうがいいです.解放後、すぐにポインタをNULLにして、いわゆる野ポインタの問題を防ぐために、包装されたメモリの割り当てと解放の関数を2つ書きます.

void *malloc_space(unsigned int n)
{
    void *dest = NULL;
    
    dest = malloc(n);
    if (dest != NULL) memset(dest, 0, n);

    return dest;
}

int free_space(void **p)
{
    if (p == NULL) return -1;
 
    if (*p != NULL)
    {
        free(*p);
        *p = NULL;
    }

    return 0;
}

読者はこのfreeを疑うかもしれない.spaceでは、ポインタ自体の値(NULLに設定)を変更する必要があるため、ポインタ自体のアドレスを渡さなければなりません.そうしないと、変更はパラメータポインタですが、実パラメータは変更されていません.これは「C言語メモリ管理-動的配列」で説明されています.
本題に戻り、文法分析では、演算子や数を識別するなど、式要素を識別するたびに、対応するチェーンテーブルにノードを追加して、純粋なテキスト型式から構造的な式への変換を実現する必要があります.ノードポインタを初期化する関数を実現します.

int exp_elem_init(struct exp_elem **dest)
{
    if (dest == NULL) return -1;

    *dest = (struct exp_elem *)malloc_space(sizeof(struct exp_elem));
    if (dest == NULL) return -2;

    (*dest)->body = NULL;
    (*dest)->type = -1;
    (*dest)->parent = NULL;
    (*dest)->next = NULL;

    return 0;
}

これにより、ノードを作成するために使用できます.

struct exp_elem *pnode = NULL;
i = exp_elem_init(&pnode);
if (i != 0) return -1;
/* TODO .... */

作成して初期化すると、各メンバーに値を割り当てる必要があります.そこで、関数を書いて完成します.

int exp_elem_fill(struct exp_elem *dest, const char *v_body, int v_type)
{
    if (dest == NULL) return -2;
 
    dest->body = strdup(v_body);
    dest->type = v_type;

    return 0;
}

この関数を使用すると、ノードの各メンバーの要件を満たすことができますが、strdup関数にはメモリ割り当てがあり、ノードを解放するときにbodyメンバーが占有する空間を解放することを覚えておく必要があります.
チェーンテーブルにノードを追加する必要があります.関数のプロトタイプは次のとおりです.

int express_add_elem(express_t **exp, struct exp_elem *v_elem);

ここではなぜ二次ポインタを使用するのか、チェーンテーブルに要素を挿入する過程でヘッドポインタを修正する可能性があるため、チェーンテーブルの末尾に要素を挿入する場合、最初の要素を挿入するときだけヘッドポインタを修正する必要があり、チェーンテーブルの頭に要素を挿入する場合、挿入する要素ごとにヘッドポインタを修正する必要があり、性能の考慮から、本物の計算機は尾に挿入すべきだが、チェーンテーブルの頭に要素を挿入することを選択した.インタフェースの定義ができました.この関数の内部でポインタv_を直接Elemはチェーンテーブルに挿入しますか、それともその指すノードをコピーしてチェーンテーブルに挿入しますか.前者を採用すると、主関数では絶対にポインタを解放することはできませんが、後者を採用すると解放する必要があります.これはあなた自身が好きになったように見えますが、私は新しいポインタをコピーする傾向があります.もし複数のポインタが同じメモリ空間を指している場合、解放時に野ポインタの問題が発生します.私はいつもプログラムの中で申請したメモリが1つのポインタしかないようにするのが好きです.具体的には、次のようになります.

int express_add_elem(express_t **exp, struct exp_elem *v_elem)
{
    struct exp_elem *p_elem = NULL;
    int i = 0;

    if (exp == NULL || v_elem == NULL) return -1;

    if (v_elem->parent != NULL || v_elem->next != NULL) return -2;  /*        ，           */

    i = exp_elem_init(&p_elem);
    if (i != 0) return -3;

    i = exp_elem_fill(p_elem, v_elem->body, v_elem->type);
    if (i != 0) return -4;

    p_elem->parent = NULL;
    p_elem->next = *exp;

    if (*exp != NULL) (*exp)->parent = p_elem;

    *exp = p_elem;

    return 0;
}

これにより、新しいノードが作成されると、チェーンテーブルに挿入されます.

i = express_add_elem(&the_express, p_elem);

そのうちp_Elemは新しく作成されたノードポインタです.
作成があればリリースする必要があります.次の関数は、ノードのリリースを完了します.

int exp_elem_free(struct exp_elem **v_elem)
{
    if (v_elem == NULL) return -1;

    if (*v_elem == NULL) return 0;

    free_space(&((*v_elem)->body));

    if ((*v_elem)->parent != NULL)
    {
        exp_elem_free(&((*v_elem)->parent));
    }

    if ((*v_elem)->next != NULL)
    {
        exp_elem_free(&((*v_elem)->next));
    }

    *v_elem = NULL;

    return 0;
} 

関数の内部で、再帰的な方法で1つのノードの前のノードと後のノードを解放します.ここでは、構造自体にポインタが含まれており、スタック上のメモリが割り当てられている場合は、構造を解放する前に、これらのポインタが指すメモリを解放しなければなりません.そうしないと、アドレスが二度と見つからないメモリで、メモリが漏れてしまいます.この解放ノードの関数があれば、チェーンテーブルを破棄する作業は非常に楽になります.チェーンテーブルの最初のノードを解放すればいいです.他の後続ノードを再帰的に解放するからです.

int express_destroy(express_t *exp)
{
    int i = 0;

    if (exp == NULL) return -1;

    i = exp_elem_free((struct exp_elem **)exp);
    if (i != 0) return -2;

    return 0;
}

ただし、チェーンテーブルの要素を削除する必要がある場合は、ノードアドレスをexp_に直接伝えることはできません.elem_free関数は、チェーンテーブル全体が削除されるため、このノードをチェーンテーブルから中断してから、この関数に渡さなければなりません.
----