Daftar tertaut adalah struktur data dinamis. Daftar tertaut dapat digunakan ketika jumlah total elemen tidak diketahui sebelumnya. Itu tumbuh dan menyusut dalam memori, relatif terhadap jumlah item yang dikandungnya.
Daftar tertaut paling mudah diimplementasikan menggunakan kelas dalam bahasa pemrograman berorientasi objek. VHDL memiliki beberapa fitur berorientasi objek yang dapat digunakan untuk mengabstraksikan kompleksitas implementasi dari pengguna.
Pada artikel ini kita akan menggunakan tipe akses, catatan, dan tipe yang dilindungi untuk mengimplementasikan daftar tertaut di VHDL. Kami akan membuat paket VHDL baru di mana kami akan menulis semua kode daftar tertaut kami.
Hal pertama yang akan kita lakukan adalah mendeklarasikan sebuah paket yang akan berisi kode kita. Paket VHDL adalah kumpulan tipe, objek, atau subprogram yang dapat diimpor ke file VHDL lain. Sebagian besar modul VHDL mengimpor paket std_logic_1164 dari perpustakaan IEEE. Kami membuat paket kami sendiri, sangat mirip.
Isi file DataStructures.vhd baru kami:
package DataStructures is -- Public declarations go here end package DataStructures; package body DataStructures is -- Private declarations and implementations go here end package body DataStructures;
Meskipun paket hanya akan berisi implementasi daftar tertaut, kami akan membuktikannya di masa mendatang dengan menamakannya DataStructures. Orang dapat dengan mudah membayangkan bahwa seseorang ingin menambahkan struktur data lain seperti pohon atau peta hash ke dalamnya nanti.
Paket terdiri dari dua bagian; wilayah deklaratif, dan badan. Wilayah deklaratif adalah tempat Anda meletakkan segala sesuatu yang seharusnya terlihat oleh pengguna paket. Tubuh dilindungi secara pribadi, dan tidak dapat diakses dari luar.
Jenis yang dilindungi adalah konstruksi seperti kelas di VHDL. Mereka dapat berisi subprogram, deklarasi tipe, dan variabel. Jenis yang dilindungi terdiri dari deklarasi publik dan badan pribadi. Kami akan menambahkan deklarasi ke deklarasi paket, dan badan ke badan paket.
File DataStructures.vhd kami setelah menambahkan jenis yang dilindungi:
package DataStructures is
type LinkedList is protected
-- Prototypes of subprograms
procedure Push(constant Data : in integer);
impure function Pop return integer;
impure function IsEmpty return boolean;
end protected;
end package DataStructures;
package body DataStructures is
type LinkedList is protected body
end protected body;
end package body DataStructures;
Kami menamai tipe yang dilindungi LinkedList karena akan berisi semua yang terkait dengan daftar tertaut. Jika kita menambahkan jenis struktur data lain ke paket, itu berarti jenis lain yang dilindungi.
Dalam wilayah deklaratif dari tipe yang dilindungi, kami telah mendeklarasikan tiga subprogram. Belum ada implementasinya, nanti kita bahas. Agar subprogram terlihat di luar tipe yang dilindungi, mereka harus dideklarasikan di sini.
Tiga subprogram adalah metode daftar tertaut standar:Push, Pop, dan IsEmpty. Push menambahkan elemen baru ke awal daftar. Pop menghapus elemen dari akhir daftar. IsEmpty adalah fungsi utilitas yang mengembalikan true jika daftarnya kosong.
Catatan adalah tipe komposit yang mungkin berisi beberapa tipe anggota. Ini bekerja seperti struct dalam bahasa pemrograman C. Ketika sinyal atau variabel dibuat dari tipe record, anggota data dapat direferensikan dengan menggunakan "." notasi. Misalnya MyItem.Data .
Deklarasi rekaman kami di dalam badan tipe yang dilindungi:
type LinkedList is protected body
type Item is record
Data : integer;
NextItem : Ptr;
end record;
end protected body;
Kami telah mendeklarasikan tipe record di badan tipe yang dilindungi. Wilayah deklaratif dari tipe yang dilindungi tidak dapat berisi deklarasi tipe atau sinyal lain, jadi kita harus mendeklarasikannya di badan tipe yang dilindungi.
Itu bukan masalah bagi kami karena Item adalah tipe yang digunakan secara internal. Tidak perlu terlihat dari luar. Pengguna daftar tertaut harus mengaksesnya hanya melalui tiga subprogram yang dideklarasikan secara publik.
Catatan kami berisi dua anggota data; Data dan Item Berikutnya. Sedangkan Data bertipe integer , NextItem adalah, untuk saat ini, tipe Ptr misterius.
Jenis akses adalah pointer VHDL. Dengan menggunakannya, kita dapat membuat objek secara dinamis selama run-time. Kami akan mendeklarasikan tipe akses baru bernama Ptr yang akan menunjuk ke objek yang dibuat secara dinamis dari tipe Item.
Badan paket dengan jenis akses baru ditambahkan:
package body DataStructures is
type LinkedList is protected body
-- Declaration of incomplete Item type
type Item;
-- Declaration of pointer type to the Item type
type Ptr is access Item;
-- Full declaration of the Item type
type Item is record
Data : integer;
NextItem : Ptr; -- Pointer to the next Item
end record;
-- Root of the linked list
variable Root : Ptr;
end package body DataStructures;
Sebuah node daftar tertaut harus berisi referensi ke node berikutnya dalam daftar. Kami telah menerapkan ini dalam catatan Item dengan anggota NextItem. Ini adalah tipe Ptr, yang pada gilirannya merupakan penunjuk kembali ke tipe Item. Untuk menghindari masalah ayam/telur ini, pertama-tama kami mendeklarasikan Item sebagai tipe yang tidak lengkap. Kemudian, kami mendeklarasikan tipe Ptr sebagai penunjuk ke tipe yang tidak lengkap. Terakhir, kita tentukan deklarasi lengkap dari tipe Item.
Hal terakhir yang kami lakukan adalah mendeklarasikan variabel baru bernama Root dengan tipe Ptr. Ini akan menjadi akar dari daftar tertaut. Jika daftar kosong, nilai Root akan menjadi null . Jika tidak, itu akan menunjuk ke item pertama dalam daftar.
Sekarang saatnya untuk mengimplementasikan subprogram yang kami deklarasikan di wilayah deklaratif dari tipe yang dilindungi. Itu adalah prosedur Push, dan dua fungsi tidak murni:Pop dan IsEmpty.
Kami akan menempatkan implementasi subprogram di dalam tubuh tipe yang dilindungi.
Push adalah satu-satunya subprogram yang merupakan prosedur. Fungsi dalam VHDL memerlukan nilai kembalian yang tidak dapat dihilangkan. Untuk menghindari penggunaan nilai pengembalian dummy, prosedur lebih disukai.
Prosedur Push:
procedure Push(Data : in integer) is
variable NewItem : Ptr;
variable Node : Ptr;
begin
-- Dynamically allocate a new item
NewItem := new Item;
NewItem.Data := Data;
-- If the list is empty, this becomes the root node
if Root = null then
Root := NewItem;
else
-- Start searching from the root node
Node := Root;
-- Find the last node
while Node.NextItem /= null loop
Node := Node.NextItem;
end loop;
-- Append the new item at the end of the list
Node.NextItem := NewItem;
end if;
end;
Hal pertama yang terjadi adalah objek baru bertipe Item dialokasikan secara dinamis. Ini dilakukan dengan menggunakan new kata kunci. Setiap kali new kata kunci digunakan, memori dinamis digunakan oleh simulator.
Sisa kode hanyalah algoritma daftar tertaut standar. Item baru ditambahkan ke akhir daftar, atau menjadi item Root jika daftar kosong. Baca daftar tertaut di Wikipedia jika Anda membutuhkan lebih banyak latar belakang.
Pop menghapus elemen tertua dari daftar dan mengembalikannya ke pemanggil. Jika kita hanya menghapus referensi ke elemen yang muncul dan mengembalikannya, akan ada kehilangan memori di simulator. Setelah panggilan fungsi selesai, referensi ke objek yang dibuat secara dinamis akan hilang selamanya.
Tidak ada pengumpulan sampah di VHDL sebelum VHDL-2017 (juga disebut sebagai VHDL-2018 atau VHDL-2019). Dan VHDL-2017 tidak didukung oleh sebagian besar simulator. Oleh karena itu, kita harus memanggil deallocate sebelum kembali dari fungsinya.
deallocate operator membebaskan memori yang digunakan oleh objek yang dialokasikan secara dinamis. Untuk setiap panggilan ke new , harus ada panggilan ke deallocate sebelum referensi ke objek dihapus.
Fungsi Pop:
impure function Pop return integer is variable Node : Ptr; variable RetVal : integer; begin Node := Root; Root := Root.NextItem; -- Copy and free the dynamic object before returning RetVal := Node.Data; deallocate(Node); return RetVal; end;
Setelah kita memanggil deallocate , kita tidak dapat mereferensikan data yang ditunjuk oleh variabel Node. Ini telah digratiskan oleh simulator. Solusinya adalah menyalin data ke variabel lokal sebelum membebaskan, lalu mengembalikan nilai variabel.
Memeriksa apakah daftar kosong atau tidak dapat dilakukan dengan memeriksa apakah simpul akar menunjuk ke sesuatu selain nol:
impure function IsEmpty return boolean is begin return Root = null; end;
Untuk menjalankan kode kita, kita perlu membuat testbench. Sebenarnya, linked list hanya bisa digunakan di testbenches. Jenis akses tidak dapat disintesis, tetapi sangat berguna untuk tujuan verifikasi.
Di testbench, pertama-tama kita mengimpor work Perpustakaan. Ini adalah pustaka default di VHDL, dan di sinilah paket DataStructures kami berada. Setelah itu, kita bisa mengimport tipe protected LinkedList seperti ini:
library work; use work.DataStructures.LinkedList;
Variabel bersama adalah variabel yang dapat diakses oleh beberapa proses. Tidak seperti variabel reguler yang hanya dapat dideklarasikan dalam satu proses, variabel bersama dapat dideklarasikan di wilayah deklaratif arsitektur. Dengan demikian, mereka memiliki cakupan yang sama dengan sinyal.
Kita harus menggunakan variabel bersama karena tidak mungkin untuk mendeklarasikan sinyal tipe yang dilindungi. Jika kami mencoba, ModelSim akan mengeluh:(vcom-1464) Deklarasi ilegal dari sinyal “List” dari tipe work.DataStructures.LinkedList (tipe adalah tipe yang dilindungi).
Kami mendeklarasikan variabel bersama dari tipe LinkedList di wilayah deklaratif dari testbench:
architecture sim of LinkedListTb is shared variable List : LinkedList; begin
Untuk menguji tiga fungsi utilitas kami, kami membuat proses baru. Dalam prosesnya, kami menambahkan For-loop yang mendorong lima bilangan bulat ke daftar tertaut. Terakhir, kami mengosongkan daftar tertaut dalam loop Sementara yang berjalan hingga fungsi IsEmpty kami mengembalikan true :
library work;
use work.DataStructures.LinkedList;
entity LinkedListTb is
end entity;
architecture sim of LinkedListTb is
shared variable List : LinkedList;
begin
process is
begin
for i in 1 to 5 loop
report "Pushing " & integer'image(i);
List.Push(i);
end loop;
while not List.IsEmpty loop
report "Popping " & integer'image(List.Pop);
end loop;
wait;
end process;
end architecture;
Setelah menulis semua kode yang sebelumnya kita bicarakan di artikel ini, paket DataStructures akan terlihat seperti ini:
package DataStructures is
type LinkedList is protected
procedure Push(constant Data : in integer);
impure function Pop return integer;
impure function IsEmpty return boolean;
end protected;
end package DataStructures;
package body DataStructures is
type LinkedList is protected body
type Item;
type Ptr is access Item;
type Item is record
Data : integer;
NextItem : Ptr;
end record;
variable Root : Ptr;
procedure Push(Data : in integer) is
variable NewItem : Ptr;
variable Node : Ptr;
begin
NewItem := new Item;
NewItem.Data := Data;
if Root = null then
Root := NewItem;
else
Node := Root;
while Node.NextItem /= null loop
Node := Node.NextItem;
end loop;
Node.NextItem := NewItem;
end if;
end;
impure function Pop return integer is
variable Node : Ptr;
variable RetVal : integer;
begin
Node := Root;
Root := Root.NextItem;
RetVal := Node.Data;
deallocate(Node);
return RetVal;
end;
impure function IsEmpty return boolean is
begin
return Root = null;
end;
end protected body;
end package body DataStructures;
Output ke konsol simulator saat kita menekan tombol run di ModelSim:
VSIM 10> run # ** Note: Pushing 1 # Time: 0 ns Iteration: 0 Instance: /linkedlisttb # ** Note: Pushing 2 # Time: 0 ns Iteration: 0 Instance: /linkedlisttb # ** Note: Pushing 3 # Time: 0 ns Iteration: 0 Instance: /linkedlisttb # ** Note: Pushing 4 # Time: 0 ns Iteration: 0 Instance: /linkedlisttb # ** Note: Pushing 5 # Time: 0 ns Iteration: 0 Instance: /linkedlisttb # ** Note: Popping 1 # Time: 0 ns Iteration: 0 Instance: /linkedlisttb # ** Note: Popping 2 # Time: 0 ns Iteration: 0 Instance: /linkedlisttb # ** Note: Popping 3 # Time: 0 ns Iteration: 0 Instance: /linkedlisttb # ** Note: Popping 4 # Time: 0 ns Iteration: 0 Instance: /linkedlisttb # ** Note: Popping 5 # Time: 0 ns Iteration: 0 Instance: /linkedlisttb
Seperti yang dapat kita lihat dari hasil cetak, lima bilangan bulat didorong ke daftar tertaut. Kemudian, while-loop di testbench mengeluarkannya dari daftar sesuai urutan penyisipannya.
VHDL
Dalam tutorial sebelumnya, kita belajar bagaimana menggunakan For-Loop untuk melakukan iterasi pada rentang integer. Tetapi bagaimana jika kita menginginkan kontrol loop yang lebih rinci daripada sekadar rentang bilangan bulat tetap? Kita bisa menggunakan While-Loop untuk ini. While-Loop akan terus
Saat mempelajari bahasa pemrograman baru, saya selalu suka memulai dengan belajar cara mencetak. Saat Anda menguasai keluaran Hello World!, Anda tahu bahwa Anda telah membuat lingkungan bekerja. Ini juga menunjukkan kerangka dasar bahasa, kode minimum yang diperlukan untuk menghasilkan keluaran apa
Apa itu Paket di Java? PAKET di Jawa adalah kumpulan kelas, sub-paket, dan antarmuka. Ini membantu mengatur kelas Anda ke dalam struktur folder dan membuatnya mudah untuk menemukan dan menggunakannya. Lebih penting lagi, ini membantu meningkatkan penggunaan kembali kode. Setiap paket di Java memil
Dalam pencetakan 3D selalu ada serangkaian faktor yang bergantung pada pengguna , yang sering menyebabkan hasil cetak memuaskan atau gagal. Semua faktor dikumpulkan dalam profil cetak yang digunakan setiap pengguna di setiap cetakan 3D. Dalam profil pencetakan FDM 3D, parameter dalam jumlah tak ter