Kesatuan Berpisah di C

Tidak jelas bagaimana untuk menyatakan jenis Haskell ini dalam C:

data Tree = Leaf Int | Inner Tree Tree

Tidak seperti bahasa seperti Haskell dan Rust, C tidak mempunyai sokongan terbina dalam untuk
kesatuan berpecah. Walau bagaimanapun, ia menyediakan semua bahan yang kami perlukan untuk mewakili mereka, jika kami bersedia melakukan sedikit penaipan tambahan.

Perkara pertama yang perlu disedari ialah kesatuan terputus terdiri daripada:

• Beberapa varian yang berbeza
• Setiap satunya mempunyai beberapa data yang dikaitkan dengannya.

Dalam contoh pokok binari kami, kami mempunyai dua varian: "daun" dan "dalam". Varian daun menyimpan satu integer (datanya), dan varian dalam menyimpan dua Pokok (mewakili anak kiri dan kanannya).

Kita boleh mewakili haiwan sedemikian dalam C menggunakan struct dengan dua medan:

1. "teg jenis", biasanya integer, menunjukkan varian yang diwakili.
2. Medan data yang menyimpan data yang dikaitkan dengan varian.

Adalah mudah untuk menentukan teg jenis varian yang berbeza menggunakan enum:

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

Bagaimana pula dengan menyimpan data? Ini adalah jenis masalah yang kesatuan wujud untuk diselesaikan.

Kesatuan

Kesatuan hanyalah sebahagian daripada memori yang mampu menyimpan beberapa jenis data yang berbeza. Sebagai contoh, berikut ialah kesatuan yang boleh menyimpan sama ada int 32-bit atau tatasusunan 5 aksara.

union int_or_chars {
        int num;
        char letters[5];
};

Pembolehubah yang jenisnya ialah union int_or_chars boleh menyimpan sama ada int atau tatasusunan 5 aksara pada bila-bila masa tertentu (hanya bukan kedua-duanya pada masa yang sama):

union int_or_chars quux;

// We can store an int:
quux.num = 42;
printf("quux.num = %d\n", quux.num);
// => quux.num = 42

// Or 5 chars:
quux.letters[0] = 'a';
quux.letters[1] = 'b';
quux.letters[2] = 'c';
quux.letters[3] = 'd';
quux.letters[4] = 0;
printf("quux.letters = %s\n", quux.letters);
// => quux.letters = abcd

// But not both. The memory is "shared", so the chars saved above are
// now being interpreted as an int:
printf("quux.num = %x\n", quux.num);
// quux.num = 64636261

return 0;

Kesatuan seperti union int_or_chars mempunyai sebahagian besar memori yang cukup besar untuk menampung ahli terbesarnya. Berikut ialah skema yang menunjukkan cara ini berfungsi:

+ ---- + ---- + ---- + ---- + ---- +
| byte |      |      |      |      |
+ ---- + ---- + ---- + ---- + ---- +
|<--   int uses these 4  -->|
|<--  array of chars uses all 5 -->|

Yang membantu menjelaskan sebab mencetak quux.num mengakibatkan "sampah" selepas kami menyimpan tatasusunan aksara dalam quux: ia bukan sampah, ia adalah rentetan "abcd" yang ditafsirkan sebagai integer. (Pada mesin saya, quux.num dicetak dalam hex sebagai 64636261. Aksara 'a' mempunyai nilai ASCII 0x61, 'b' mempunyai nilai 0x62, 'c' ialah 0x63 dan 'd' ialah 0x64. pesanan diterbalikkan kerana pemproses saya adalah little-endian.)

Sebagai nota akhir tentang kesatuan, anda mungkin terkejut dengan saiz yang dilaporkan mengikut saiz:

printf("%ld\n", sizeof(union int_or_chars));
// => 8

Pada mesin saya, jenis kesatuan int_or_chars mempunyai saiz 8 bait, bukan 5 seperti yang kami jangkakan. Beberapa padding telah ditambahkan kerana keperluan penjajaran yang ditetapkan oleh seni bina pemproses saya.

Kembali ke Pokok Binari

Kami kini bersedia untuk meneruskan menterjemah jenis pokok binari daripada Haskell kepada C. Kami telah pun menentukan enum untuk mewakili jenis varian. Kini kami memerlukan kesatuan untuk menyimpan datanya:

union tree_data {
        int leaf;
        struct inner_data inner;
};

di mana struct inner_data ialah struct yang mengandungi anak kiri dan kanan varian "dalam":

struct inner_data {
        struct tree *left;
        struct tree *right;
};

Perhatikan bahawa varian "dalaman" mengekalkan penunjuk pada anak kiri dan kanannya. Arahan adalah perlu kerana jika tidak, pokok struct tidak akan mempunyai saiz tetap.

Dengan adanya kepingan ini, kami bersedia untuk menentukan jenis pokok kami:

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

struct tree;
struct inner_data {
        struct tree *left;
        struct tree *right;
};

union tree_data {
        int leaf;
        struct inner_data inner;
};

// A representation of a binary tree.
struct tree {
        enum tree_type type;
        union tree_data data;
};

Bermain dengan Pokok

Mari kita tulis beberapa fungsi untuk membina pokok:

// Construct a leaf node.
struct tree *leaf(int value) {
        struct tree *t = malloc(sizeof(*t));
        t->type = TREE_LEAF;
        t->data.leaf = value;
        return t;
}

// Construct an inner node.
struct tree *inner(struct tree *left, struct tree *right) {
        struct tree *t = malloc(sizeof(*t));
        t->type = TREE_INNER;
        t->data.inner.left = left;
        t->data.inner.right = right;
        return t;
}

dan cetaknya:

void print_tree(struct tree *t) {
        switch (t->type) {
        case TREE_LEAF:
                printf("%d", t->data.leaf);
                return;
        case TREE_INNER:
                printf("(");
                print_tree(t->data.inner.left);
                printf(" ");
                print_tree(t->data.inner.right);
                printf(")");
                return;
        }
}

Ini membolehkan kami menterjemah ungkapan Haskell:

Inner (Inner (Leaf 1) (Leaf 2)) (Leaf 3)

ke dalam C sebagai:

inner(inner(leaf(1), leaf(2)), leaf(3));

Contohnya:

struct tree *t = inner(inner(leaf(1), leaf(2)), leaf(3));
print_tree(t);
// => ((1 2) 3)

Sebagai contoh yang lebih menarik, mari menterjemah fungsi carian mendalam-pertama ini:

-- Check if a value is in a tree.
search :: Int -> Tree -> Bool
search v (Leaf w) = v == w
search v (Inner l r) = search v l || search v r

Menggunakan jenis pokok kami:

// Check if a value is in a tree.
int search(int value, struct tree *t) {
        switch (t->type) {
        case TREE_LEAF:
                return t->data.leaf == value;
        case TREE_INNER:
                return (
                        search(value, t->data.inner.left) ||
                        search(value, t->data.inner.right)
                );
        }
}

Sudah tentu lebih bertele-tele, tetapi proses terjemahannya mudah (sehingga pengkompil mungkin boleh melakukan perkara seperti ini untuk kita...).

Tukar ganti

Kami mengakhiri dengan sedikit penyelewengan tentang pertukaran yang terlibat dalam perwakilan alternatif. Secara khususnya, anggap bukan:

union tree_data {
        int leaf;
        struct inner_data inner;
};

kami menggunakan:

union tree_data {
        int leaf;
        struct inner_data *inner;
        //                ^ The difference.
};

Dalam kes pertama, kesatuan mengandungi struct inner_data, manakala dalam kes kedua ia menyimpan penunjuk kepada struct ini. Akibatnya, kesatuan pertama adalah lebih besar sedikit pada 16 bait, berbanding 8 untuk versi penunjuk pada mesin saya. Malangnya bukan hanya nod dalam yang terjejas: nod daun menggunakan gabungan 16-bait yang sama tetapi hanya menyimpan satu int (4-bait). Ini terasa agak membazir.

Walau bagaimanapun, itu bukan keseluruhan cerita. Kami akan membayar untuk arahan tambahan setiap kali kami mengakses anak kiri dan kanan nod dalam: bacaan tidak semestinya murah, terutamanya jika memori yang ditunjukkan tidak dicache.

Saya mengesyaki pendekatan utama yang dibentangkan di sini ialah titik permulaan yang lebih baik dalam kebanyakan kes, dan cubaan mencukur beberapa bait (putih menyebabkan bacaan tambahan) tidak berbaloi sehingga ianya menjadi.

Atas ialah kandungan terperinci Kesatuan Berpisah di C. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!