Struktur data generik

Membangun kontainer generik tanpa sistem template.

Daftar isi

Struktur data generik adalah kontainer yang menampung elemen bertipe apa pun tanpa menduplikasi definisi strukturnya untuk setiap tipe. Topik ini membangun tumpukan (stack) generik dari struct berparameter tipe, melengkapinya dengan proc push, pop, peek, dan panjang, lalu memakainya untuk tipe int dan string dalam satu program utuh. Pembahasan juga menyentuh aliran alokasi memori kontainer melalui context.allocator, perbandingan pendekatan Odin dengan template C++ dan macro C, serta kontainer generik yang sudah tersedia di core:container. Semua contoh dijalankan melalui odin run, dan keluaran aslinya ditempel setelah kodenya.

Struct dengan parameter tipe#

Struct dapat mendeklarasikan parameter tipe sehingga bentuk datanya ditulis sekali dan digunakan untuk banyak tipe elemen. Fitur ini adalah polimorfisme parametrik yang diterapkan pada tipe data, bukan pada proc. Parameter ditulis di dalam kurung setelah kata kunci struct, dengan tanda dolar $ di depan nama polimorfiknya dan anotasi typeid yang menyatakan bahwa parameter itu menerima tipe, bukan nilai. Deklarasi berikut mendefinisikan kontainer tumpukan yang tipe elemennya tidak tetap.

odin Deklarasi kontainer tumpukan generik

// tidak-dijalankan

// T adalah parameter tipe, dan items menyimpan elemen bertipe T
Stack :: struct($T: typeid) {
        items: [dynamic]T,
}

Nama T berlaku sebagai nama tipe di dalam tubuh struct, sehingga field items dapat ditulis bertipe [dynamic]T, yaitu dynamic array yang tipe elemennya mengikuti parameter. Setiap pemakaian struct dengan tipe konkret menghasilkan satu instansi tersendiri pada saat kompilasi, sebagaimana proc generik pada bentuk eksplisit $T: typeid. Instansi dibentuk dengan menulis nama tipe di dalam kurung, misalnya Stack(int) untuk tumpukan bertipe int dan Stack(string) untuk tumpukan bertipe string.

Nilai nol dari instansi tersebut sudah sah untuk dipakai. Deklarasi angka: Stack(int) menghasilkan struct yang field items-nya nil dan belum menyimpan memori apa pun, sedangkan penulisan angka := Stack(int){} memberikan hasil yang sama. Alokasi memori pertama baru terjadi ketika append menambahkan elemen, dan alokasi itu mengalir melalui context.allocator pada saat pemanggilan. Mekanisme ini diuji secara langsung pada bagian alokasi memori di bawah.

Proc push, pop, dan peek#

Odin tidak memiliki method yang terikat pada struct, sehingga operasi kontainer ditulis sebagai proc biasa yang menerima pointer ke kontainernya. Parameter s: ^Stack($T) pada proc berikut mengenalkan nama polimorfik T melalui tipe pointer yang dikirim pemanggil, dan bentuk ini disebut implisit karena tipe tidak diserahkan sebagai argumen terpisah. Nama T kemudian dipakai pada tipe parameter nilai, sehingga tipe nilai yang boleh ditambahkan mengikuti tipe instansi kontainernya. Pemanggilan push(&angka, 10) pada variabel bertipe Stack(int) menetapkan instansi push yang parameternya bertipe int, tanpa penulisan tipe apa pun di tempat pemanggilan.

odin Prosedur push, pop, dan peek untuk kontainer generik

// tidak-dijalankan

// push menaruh nilai baru di puncak tumpukan
push :: proc(s: ^Stack($T), nilai: T) {
        append(&s.items, nilai)
}

// pop mengambil nilai di puncak tumpukan sekaligus menghapusnya
pop :: proc(s: ^Stack($T)) -> (nilai: T, ok: bool) {
        if len(s.items) == 0 {
                return
        }
        nilai = s.items[len(s.items)-1]
        resize(&s.items, len(s.items)-1)
        return nilai, true
}

// peek membaca nilai di puncak tumpukan tanpa menghapusnya
peek :: proc(s: ^Stack($T)) -> (nilai: T, ok: bool) {
        if len(s.items) == 0 {
                return
        }
        return s.items[len(s.items)-1], true
}

Proc pop mengembalikan pasangan (nilai: T, ok: bool) untuk membedakan pemanggilan yang berhasil dari pemanggilan pada tumpukan kosong. Hasil bernama (named result) dinolkan secara bawaan, sehingga pernyataan return tanpa nilai pada cabang tumpukan kosong mengembalikan nilai nol tipe instansi beserta false.

Penghapusan elemen puncak memakai resize, yaitu proc bawaan bahasa yang mengubah panjang dynamic array. Pemanggilan resize(&s.items, len(s.items)-1) hanya menurunkan panjangnya sebanyak satu elemen tanpa menyalin ulang isi dan tanpa mengalokasikan memori baru, sedangkan kapasitas buffernya dipertahankan untuk pemanggilan push berikutnya. Proc panjang :: proc(s: ^Stack($T)) -> int melengkapi operasi ini dengan mengembalikan len(s.items), dan program utuh pada bagian berikut memuat keempat proc tersebut beserta pemanggilannya.

Program utuh dengan dua tipe#

Program berikut menyatukan seluruh bagian sebelumnya dalam satu berkas main.odin. Proc main memakai kontainer yang sama untuk dua instansi yang berbeda, yaitu angka: Stack(int) dan nama: Stack(string). Tumpukan angka diuji dengan peek, satu kali pop, dan pencetakan field items yang memperlihatkan isinya, sedangkan tumpukan nama dikosongkan seluruhnya melalui perulangan for len(nama.items) > 0. Satu pemanggilan pop terakhir pada tumpukan yang sudah kosong memperlihatkan perilaku penanda ok.

odin main.odin

package main

import "core:fmt"
import "core:mem"

// Tumpukan generik: T adalah parameter tipe yang diganti saat kompilasi.
Stack :: struct($T: typeid) {
        items: [dynamic]T,
}

// push menaruh nilai baru di puncak tumpukan.
push :: proc(s: ^Stack($T), nilai: T) {
        append(&s.items, nilai)
}

// pop mengambil nilai di puncak tumpukan sekaligus menghapusnya.
// Hasilnya berupa pasangan nilai dan penanda keberhasilan.
pop :: proc(s: ^Stack($T)) -> (nilai: T, ok: bool) {
        if len(s.items) == 0 {
                return
        }
        nilai = s.items[len(s.items)-1]
        resize(&s.items, len(s.items)-1)
        return nilai, true
}

// peek membaca nilai di puncak tumpukan tanpa menghapusnya.
peek :: proc(s: ^Stack($T)) -> (nilai: T, ok: bool) {
        if len(s.items) == 0 {
                return
        }
        return s.items[len(s.items)-1], true
}

// panjang menyatakan banyaknya nilai yang tersimpan.
panjang :: proc(s: ^Stack($T)) -> int {
        return len(s.items)
}

main :: proc() {
        // Tumpukan bertipe int
        angka: Stack(int)
        push(&angka, 10)
        push(&angka, 24)
        push(&angka, 100)

        fmt.printfln("panjang angka: %v", panjang(&angka))
        puncak, ok_puncak := peek(&angka)
        fmt.printfln("puncak angka: %v (ok: %v)", puncak, ok_puncak)

        atas, ok := pop(&angka)
        fmt.printfln("pop angka: %v (ok: %v)", atas, ok)
        fmt.printfln("sisa isi angka: %v", angka.items)

        // Tumpukan bertipe string
        nama: Stack(string)
        push(&nama, "Ali")
        push(&nama, "Budi")
        push(&nama, "Citra")

        for len(nama.items) > 0 {
                keluar, ok_keluar := pop(&nama)
                fmt.printfln("pop nama: %v (ok: %v)", keluar, ok_keluar)
        }

        _, ok_kosong := pop(&nama)
        fmt.printfln("pop tumpukan kosong -> ok: %v", ok_kosong)

        // Alokasi kontainer mengikuti context.allocator
        ctx_awal := context
        ta: mem.Tracking_Allocator
        mem.tracking_allocator_init(&ta, context.allocator)
        defer mem.tracking_allocator_destroy(&ta)
        context.allocator = mem.tracking_allocator(&ta)

        log_sensor: Stack(f32)
        push(&log_sensor, 21.5)
        push(&log_sensor, 22.0)
        fmt.printfln("byte dialokasikan lewat context: %v", ta.current_memory_allocated)

        delete(log_sensor.items)
        fmt.printfln("byte setelah delete: %v", ta.current_memory_allocated)

        context = ctx_awal
}

bash

# sumberkan lingkungan sandbox jalur odin bila belum tersedia
[ -f /home/kal/my-project/tools/env.sh ] && source /home/kal/my-project/tools/env.sh
# jalankan program dari dalam folder topik
odin run main.odin -file

text Keluaran

panjang angka: 3
puncak angka: 100 (ok: true)
pop angka: 100 (ok: true)
sisa isi angka: [10, 24]
pop nama: Citra (ok: true)
pop nama: Budi (ok: true)
pop nama: Ali (ok: true)
pop tumpukan kosong -> ok: false
byte dialokasikan lewat context: 32
byte setelah delete: 0

Keluaran memperlihatkan perilaku tumpukan secara utuh. Nilai 100 yang terakhir ditambahkan adalah nilai pertama yang keluar, sedangkan field items tersisa [10, 24] setelah pemanggilan pop itu. Pada tumpukan nama, urutan keluar terbalik dari urutan masuk, yaitu Citra, Budi, kemudian Ali, sebagaimana konvensi LIFO (last in, first out) tumpukan. Pemanggilan pop pada tumpukan kosong hanya menetapkan ok bernilai false, sehingga pemanggil yang memeriksa penanda itu tidak pernah membaca nilai yang tidak ada.

Alokasi memori mengikuti context#

Dynamic array di dalam kontainer tidak menyimpan alokator sendiri, karena setiap pemanggilan append menggunakan context.allocator pada saat alokasi terjadi. Konsekuensinya, kontainer generik yang sama bekerja dengan alokator apa pun yang dipasangkan ke context, tanpa perubahan tipe maupun proc-nya. Pola ini berbeda dari kontainer yang membawa field alokator sendiri, karena tiap instansi terikat pada satu alokator sejak pembuatannya. Pada program di atas, bagian akhir main menukar context.allocator dengan alokator pelacak dari core:mem untuk membuktikan aliran itu.

Alokator pelacak dipasangkan melalui mem.tracking_allocator_init(&ta, context.allocator), kemudian context.allocator = mem.tracking_allocator(&ta) membuat semua permintaan alokasi berikutnya tercatat. Dua pemanggilan push pada log_sensor: Stack(f32) menyisakan 32 byte yang sedang dialokasikan menurut ta.current_memory_allocated, dan pemanggilan delete(log_sensor.items) mengembalikannya menjadi nol. Angka 32 byte adalah ukuran buffer dynamic array yang sedang dipakai, bukan ukuran dua nilai f32 saja, karena append mengalokasikan kapasitas dan bukan hanya ukuran datanya.

Pemulihan context dilakukan dengan menyimpan nilai context sebelum penukaran, yaitu ctx_awal := context, dan mengembalikannya melalui context = ctx_awal setelah pengukuran. Pernyataan defer mem.tracking_allocator_destroy(&ta) melepas sumber daya pelacak ketika main berakhir. Pola simpan-pulihkan ini menjaga bagian lain program tetap menggunakan alokator semula, dan kontainer generik tidak perlu mengetahui bahwa perpindahan itu terjadi.

Perbandingan dengan template dan macro#

Tujuan yang sama dapat dicapai dengan template pada C++ atau macro pada C, tetapi ketiga pendekatan ini bekerja pada lapisan yang berbeda. Macro C digantikan oleh preprocessor melalui substitusi teks sebelum compiler membaca programnya, sehingga tidak ada pemeriksaan tipe pada definisinya dan error baru terlihat pada hasil ekspansinya. Instansi template C++ dibuat oleh compiler dengan pemeriksaan tipe per instansi, dan fiturnya yang luas mencakup spesialisasi khusus per tipe beserta metaprogramming pada waktu kompilasi. Odin memilih fitur tunggal, yaitu substitusi parameter tipe saat kompilasi tanpa spesialisasi khusus, sehingga perilaku per tipe dibatasi melalui klausul where dan dukungan operator pada tipe instansinya.

Aspek	Macro C	Template C++	Odin
Waktu substitusi	Sebelum kompilasi, oleh preprocessor	Saat kompilasi, oleh compiler	Saat kompilasi, oleh compiler
Pemeriksaan tipe	Tidak ada pada definisinya	Per instansi pada saat kompilasi	Deklarasi diperiksa sekali, lalu per instansi
Perilaku khusus per tipe	Dengan trik teks	Didukung melalui spesialisasi	Tidak ada, diatur melalui `where`

Perbedaan yang paling terasa bagi pengguna adalah ukuran fiturnya. Substitusi Odin berhenti pada parameter tipe dan nilai konstanta, sehingga deklarasi kontainer tetap berbentuk struct biasa dengan satu parameter di depannya. Untuk kontainer sederhana seperti tumpukan, fitur yang lebih kecil ini sudah mencakup kebutuhannya, sedangkan kebutuhan yang lebih kompleks dapat menunggu sampai benar-benar muncul.

Kontainer generik yang tersedia#

Pustaka inti Odin sudah menyediakan kontainer generik pada paket core:container, sehingga kontainer buatan sendiri paling tepat dipandang sebagai cara memahami mekanismenya. Paket tersebut tidak memuat tipe bernama Stack pada build ini, tetapi kontainer inti yang tersedia antara lain Queue generik pada core:container/queue, Small_Array pada core:container/small_array yang menyimpan elemen pertamanya dalam array tetap berukuran N, priority_queue, serta pohon pencarian seperti avl dan rbtree. Queue dideklarasikan sebagai Queue :: struct($T: typeid) dengan proc push_back, push_front, pop_back, dan pop_front, dan dokumentasinya menyatakan bahwa struct itu menyediakan perilaku tumpukan sekaligus antrean dalam satu struktur. Nama Stack memang muncul di core:mem, tetapi di sana nama itu menunjuk alokator memori berstruktur tumpukan, bukan kontainer elemen.

Tumpukan sederhana tetap layak ditulis sendiri karena operasinya pendek. Kontainer pada topik ini hanya berupa struct berisi satu dynamic array ditambah beberapa proc kecil, dan seluruhnya muat dalam satu berkas. Apabila kebutuhan bertambah, misalnya pengosongan seluruh isi atau iterasi dari puncak, pola struct berparameter tipe yang sama terus dapat dikembangkan tanpa mengubah proc yang sudah ada.

Kesalahan umum#

Kesalahan pertama adalah menulis parameter tipe struct tanpa anotasi typeid. Deklarasi Stack :: struct($T) { ... } ditolak compiler dengan pesan Syntax Error: Expected at least 1 polymorphic parameter yang menunjuk baris deklarasinya, karena bentuk singkat $T tanpa anotasi tidak diterima pada daftar parameter struct. Perbaikannya berupa penulisan anotasi lengkap, yaitu Stack :: struct($T: typeid) { ... }, sehingga parameter itu dinyatakan menerima tipe.

Kesalahan kedua adalah menampung hasil pop dengan := dua kali pada lingkup yang sama. Pemanggilan atas, ok := pop(&angka) yang ditulis lagi pada baris berikutnya ditolak dengan pesan Redeclaration of 'atas' in this scope, karena := mendeklarasikan variabel baru dan nama atas sudah ada. Perbaikannya berupa pemberian nama berbeda untuk setiap hasil, misalnya puncak, ok_puncak sebagaimana pada program utuh, atau penugasan ulang dengan = apabila variabelnya sudah dideklarasikan.

Kesalahan ketiga adalah mengabaikan penanda ok sebelum nilai kembalian pop digunakan. Nilai kembalian pada tumpukan kosong adalah nilai nol tipe instansi, misalnya string kosong untuk Stack(string), yang tampak sah padahal tidak ada elemen yang diambil. Periksa ok sebelum nilai digunakan, sebagaimana perulangan pengosongan pada program utuh yang berhenti ketika ok bernilai false.

Ringkasan#

Struct dengan parameter tipe ditulis Stack :: struct($T: typeid), field boleh bertipe [dynamic]T, dan setiap pemakaian seperti Stack(int) atau Stack(string) menghasilkan instansi tersendiri pada saat kompilasi.
Operasi kontainer berupa proc biasa dengan parameter ^Stack($T), sehingga tipe elemennya disimpulkan secara implisit dari argumen tanpa method yang terikat pada struct.
Proc pop dan peek mengembalikan pasangan nilai dan penanda ok. Hasil bernama yang dikembalikan dengan return polos berisi nilai nol tipe instansi, dan penghapusan elemen puncak memakai resize tanpa alokasi baru.
Alokasi elemen mengalir melalui context.allocator, kontainer generik siap pakai seperti Queue tersedia di core:container, dan nama Stack di core:mem adalah alokator memori, bukan kontainer.

Referensi#

Overview — Odin Documentation — Bagian parametric polymorphism menjelaskan parameter tipe dengan $ dan anotasi typeid pada proc serta struct generik.
Paket core:container/queue — Referensi paket Odin — Dokumentasi Queue generik beserta proc push_back, push_front, pop_back, dan pop_front.
Paket core:mem — Referensi paket Odin — Dokumentasi Tracking_Allocator dan tracking_allocator_init yang dipakai untuk mengukur alokasi kontainer.