Daftar Tertaut Singly dan Doubly
Daftar Yang Ditautkan Senyap
Sistem operasi menyediakan dukungan bawaan untuk daftar yang ditautkan secara sesat yang menggunakan struktur SINGLE_LIST_ENTRY . Daftar yang ditautkan secara senyap terdiri dari kepala daftar ditambah beberapa jumlah entri daftar. (Jumlah entri daftar adalah nol jika daftar kosong.) Setiap entri daftar direpresentasikan sebagai struktur SINGLE_LIST_ENTRY . Kepala daftar juga direpresentasikan sebagai struktur SINGLE_LIST_ENTRY .
Setiap struktur SINGLE_LIST_ENTRY berisi anggota Berikutnya yang menunjuk ke struktur SINGLE_LIST_ENTRY lain. Dalam struktur SINGLE_LIST_ENTRY yang mewakili kepala daftar, anggota Berikutnya menunjuk ke entri pertama dalam daftar, atau null jika daftar kosong. Dalam struktur SINGLE_LIST_ENTRY yang mewakili entri dalam daftar, anggota Berikutnya menunjuk ke entri daftar berikutnya, atau adalah NULL jika entri ini adalah yang terakhir dalam daftar.
Rutinitas yang memanipulasi daftar yang ditautkan secara senyap membawa pointer ke SINGLE_LIST_ENTRY yang mewakili kepala daftar. Mereka memperbarui penunjuk Berikutnya sehingga menunjuk ke entri pertama daftar setelah operasi.
Misalkan variabel ListHead adalah penunjuk ke struktur SINGLE_LIST_ENTRY yang mewakili kepala daftar. Driver memanipulasi ListHead sebagai berikut:
Untuk menginisialisasi daftar sebagai kosong, atur ListHead-Next> menjadi NULL.
Untuk menambahkan entri baru ke daftar, alokasikan SINGLE_LIST_ENTRY untuk mewakili entri baru, lalu panggil PushEntryList untuk menambahkan entri ke awal daftar.
Munculkan entri pertama dari daftar dengan menggunakan PopEntryList.
Seorang SINGLE_LIST_ENTRY, dengan sendirinya, hanya memiliki anggota Berikutnya. Untuk menyimpan data Anda sendiri dalam daftar, sematkan SINGLE_LIST_ENTRY sebagai anggota struktur yang menjelaskan entri daftar, sebagai berikut.
typedef struct {
// driver-defined members
.
.
.
SINGLE_LIST_ENTRY SingleListEntry;
// other driver-defined members
.
.
.
} XXX_ENTRY;
Untuk menambahkan entri baru ke daftar, alokasikan struktur XXX_ENTRY , lalu teruskan penunjuk ke anggota SingleListEntry ke PushEntryList. Untuk mengonversi penunjuk ke SINGLE_LIST_ENTRY kembali ke XXX_ENTRY, gunakan CONTAINING_RECORD. Berikut adalah contoh rutinitas yang menyisipkan dan menghapus entri yang ditentukan driver dari daftar yang ditautkan.
typedef struct {
PVOID DriverData1;
SINGLE_LIST_ENTRY SingleListEntry;
ULONG DriverData2;
} XXX_ENTRY, *PXXX_ENTRY;
void
PushXxxEntry(PSINGLE_LIST_ENTRY ListHead, PXXX_ENTRY Entry)
{
PushEntryList(ListHead, &(Entry->SingleListEntry));
}
PXXX_ENTRY
PopXxxEntry(PSINGLE_LIST_ENTRY ListHead)
{
PSINGLE_LIST_ENTRY SingleListEntry;
SingleListEntry = PopEntryList(ListHead);
return CONTAINING_RECORD(SingleListEntry, XXX_ENTRY, SingleListEntry);
}
Sistem ini juga menyediakan versi atom dari operasi daftar, ExInterlockedPopEntryList dan ExInterlockedPushEntryList. Masing-masing mengambil parameter kunci putaran tambahan. Rutinitas memperoleh kunci putar sebelum memperbarui daftar, dan kemudian rutin melepaskan kunci putar setelah operasi selesai. Saat kunci ditahan, gangguan dinonaktifkan. Setiap operasi dalam daftar harus menggunakan kunci putar yang sama untuk memastikan bahwa setiap operasi tersebut dalam daftar disinkronkan dengan setiap operasi lainnya. Anda harus menggunakan kunci putar hanya dengan rutinitas DaftarXxxExInterlocked ini. Jangan gunakan kunci putar untuk tujuan lain. Driver dapat menggunakan kunci yang sama untuk beberapa daftar, tetapi perilaku ini meningkatkan ketidakcocokan kunci sehingga driver harus menghindarinya.
Misalnya, rutinitas ExInterlockedPopEntryList dan ExInterlockedPushEntryList dapat mendukung berbagi daftar yang ditautkan secara sesat oleh utas driver yang berjalan di IRQL = PASSIVE_LEVEL dan ISR yang berjalan di DIRQL. Rutinitas ini menonaktifkan gangguan ketika kunci putaran ditahan. Dengan demikian, ISR dan utas driver dapat dengan aman menggunakan kunci spin yang sama dalam panggilan mereka ke rutinitas DaftarXxxExInterlocked ini tanpa mempertaruhkan kebuntuan.
Jangan mencampur panggilan ke versi atomik dan non-atomik dari operasi daftar pada daftar yang sama. Jika versi atomik dan non-atom dijalankan secara bersamaan pada daftar yang sama, struktur data mungkin menjadi rusak dan komputer mungkin berhenti merespons atau pemeriksaan bug (yaitu, crash). (Anda tidak dapat memperoleh kunci putar saat memanggil rutinitas non-atomik sebagai alternatif untuk mencampur panggilan ke versi atomik dan non-atomik dari operasi daftar. Menggunakan kunci putaran dalam mode ini tidak didukung dan mungkin masih menyebabkan kerusakan daftar.)
Sistem ini juga menyediakan implementasi alternatif dari daftar atom yang ditautkan secara sesuka hati yang lebih efisien. Untuk informasi selengkapnya, lihat Daftar Tertaut Senyap Berurutan.
Daftar Tertaut Doubly
Sistem operasi menyediakan dukungan bawaan untuk daftar tertaut doubly yang menggunakan struktur LIST_ENTRY . Daftar tertaut doubly terdiri dari kepala daftar ditambah beberapa jumlah entri daftar. (Jumlah entri daftar adalah nol jika daftar kosong.) Setiap entri daftar direpresentasikan sebagai struktur LIST_ENTRY . Kepala daftar juga direpresentasikan sebagai struktur LIST_ENTRY .
Setiap struktur LIST_ENTRY berisi anggota Flink dan anggota Blink . Kedua anggota adalah penunjuk ke struktur LIST_ENTRY .
Dalam struktur LIST_ENTRY yang mewakili kepala daftar, anggota Flink menunjuk ke entri pertama dalam daftar dan anggota Blink menunjuk ke entri terakhir dalam daftar. Jika daftar kosong, maka Flink dan Blink dari daftar head point ke kepala daftar itu sendiri.
Dalam struktur LIST_ENTRY yang mewakili entri dalam daftar, anggota Flink menunjuk ke entri berikutnya dalam daftar, dan anggota Blink menunjuk ke entri sebelumnya dalam daftar. (Jika entri adalah yang terakhir dalam daftar, Flink menunjuk ke kepala daftar. Demikian pula, jika entri adalah yang pertama dalam daftar, Blink menunjuk ke kepala daftar.)
(Meskipun aturan ini mungkin tampak mengejutkan pada pandangan pertama, aturan ini memungkinkan penyisipan daftar dan operasi penghapusan diimplementasikan tanpa cabang kode bersyarat.)
Rutinitas yang memanipulasi daftar yang ditautkan berlipat-lipat mengambil penunjuk ke LIST_ENTRY yang mewakili kepala daftar. Rutinitas ini memperbarui anggota Flink dan Blink di kepala daftar sehingga anggota ini menunjuk ke entri pertama dan terakhir dalam daftar yang dihasilkan.
Misalkan variabel ListHead adalah penunjuk ke struktur LIST_ENTRY yang mewakili kepala daftar. Driver memanipulasi ListHead sebagai berikut:
Untuk menginisialisasi daftar sebagai kosong, gunakan InitializeListHead, yang menginisialisasi ListHead-Flink> dan ListHead-Blink> untuk menunjuk ke ListHead.
Untuk menyisipkan entri baru di kepala daftar, alokasikan LIST_ENTRY untuk mewakili entri baru, lalu panggil InsertHeadList untuk menyisipkan entri di awal daftar.
Untuk menambahkan entri baru ke ekor daftar, alokasikan LIST_ENTRY untuk mewakili entri baru, lalu panggil InsertTailList untuk menyisipkan entri di akhir daftar.
Untuk menghapus entri pertama dari daftar, gunakan RemoveHeadList. Ini mengembalikan penunjuk ke entri yang dihapus dari daftar, atau ke ListHead jika daftar kosong.
Untuk menghapus entri terakhir dari daftar, gunakan RemoveTailList. Ini mengembalikan penunjuk ke entri yang dihapus dari daftar, atau ke ListHead jika daftar kosong.
Untuk menghapus entri tertentu dari daftar, gunakan RemoveEntryList.
Untuk memeriksa apakah daftar kosong, gunakan IsListEmpty.
Untuk menambahkan daftar ke ekor daftar lain, gunakan AppendTailList.
Seorang LIST_ENTRY, dengan sendirinya, hanya memiliki anggota Blink dan Flink. Untuk menyimpan data Anda sendiri dalam daftar, sematkan LIST_ENTRY sebagai anggota struktur yang menjelaskan entri daftar, sebagai berikut.
typedef struct {
// driver-defined members
.
.
.
LIST_ENTRY ListEntry;
// other driver-defined members.
.
.
.
} XXX_ENTRY;
Untuk menambahkan entri baru ke daftar, alokasikan struktur XXX_ENTRY , lalu teruskan penunjuk ke anggota ListEntry ke InsertHeadList atau InsertTailList. Untuk mengonversi pointer ke LIST_ENTRY kembali ke XXX_ENTRY, gunakan CONTAINING_RECORD. Untuk contoh teknik ini, menggunakan daftar yang ditautkan secara senyap, lihat Daftar Tertaut Senyap di atas.
Sistem ini juga menyediakan versi atom dari operasi daftar, ExInterlockedInsertHeadList, ExInterlockedInsertTailList, dan ExInterlockedRemoveHeadList. (Perhatikan bahwa tidak ada versi atom RemoveTailList atau RemoveEntryList.) Setiap rutinitas mengambil parameter kunci putaran tambahan. Rutinitas memperoleh kunci putaran sebelum memperbarui daftar dan kemudian melepaskan kunci putar setelah operasi selesai. Saat kunci ditahan, gangguan dinonaktifkan. Setiap operasi pada daftar harus menggunakan kunci putar yang sama untuk memastikan bahwa setiap operasi tersebut dalam daftar disinkronkan satu sama lain. Anda harus menggunakan kunci putar hanya dengan rutinitas DaftarXxxExInterlocked ini. Jangan gunakan kunci putar untuk tujuan lain. Driver dapat menggunakan kunci yang sama untuk beberapa daftar, tetapi perilaku ini meningkatkan ketidakcocokan kunci sehingga driver harus menghindarinya.
Misalnya, rutinitas ExInterlockedInsertHeadList, ExInterlockedInsertTailList, dan ExInterlockedRemoveHeadList dapat mendukung berbagi daftar yang ditautkan dua kali lipat oleh utas driver yang berjalan di IRQL = PASSIVE_LEVEL dan ISR yang berjalan di DIRQL. Rutinitas ini menonaktifkan gangguan ketika kunci putaran ditahan. Dengan demikian, ISR dan utas driver dapat dengan aman menggunakan kunci spin yang sama dalam panggilan mereka ke rutinitas DaftarXxxExInterlocked ini tanpa mempertaruhkan kebuntuan.
Jangan mencampur panggilan ke versi atomik dan non-atomik dari operasi daftar pada daftar yang sama. Jika versi atomik dan non-atom dijalankan secara bersamaan pada daftar yang sama, struktur data mungkin menjadi rusak dan komputer mungkin berhenti merespons atau pemeriksaan bug (yaitu, crash). (Anda tidak dapat bekerja memperoleh kunci spin saat memanggil rutinitas non-atomik untuk menghindari pencampuran panggilan ke versi atomik dan non-atomik dari operasi daftar. Menggunakan kunci putaran dalam mode ini tidak didukung dan mungkin masih menyebabkan kerusakan daftar.)
Daftar Tertaut Berurutan
Daftar yang ditautkan secara berurutan adalah implementasi dari daftar yang ditautkan secara sesat yang mendukung operasi atomik. Ini lebih efisien untuk operasi atom daripada implementasi daftar yang ditautkan secara sesat yang dijelaskan dalam Singly Linked Lists.
Struktur SLIST_HEADER digunakan untuk menjelaskan kepala daftar yang ditautkan secara berurutan, sementara SLIST_ENTRY digunakan untuk menggambarkan entri dalam daftar.
Driver memanipulasi daftar sebagai berikut:
Untuk menginisialisasi struktur SLIST_HEADER , gunakan ExInitializeSListHead.
Untuk menambahkan entri baru ke daftar, alokasikan SLIST_ENTRY untuk mewakili entri baru, lalu panggil ExInterlockedPushEntrySList untuk menambahkan entri ke awal daftar.
Munculkan entri pertama dari daftar dengan menggunakan ExInterlockedPopEntrySList.
Untuk menghapus daftar sepenuhnya, gunakan ExInterlockedFlushSList.
Untuk menentukan jumlah entri dalam daftar, gunakan ExQueryDepthSList.
Seorang SLIST_ENTRY, dengan sendirinya, hanya memiliki anggota Berikutnya. Untuk menyimpan data Anda sendiri dalam daftar, sematkan SLIST_ENTRY sebagai anggota struktur yang menjelaskan entri daftar, sebagai berikut.
typedef struct
{
// driver-defined members
.
.
.
SLIST_ENTRY SListEntry;
// other driver-defined members
.
.
.
} XXX_ENTRY;
Untuk menambahkan entri baru ke daftar, alokasikan struktur XXX_ENTRY , lalu teruskan penunjuk ke anggota SListEntry ke ExInterlockedPushEntrySList. Untuk mengonversi penunjuk ke SLIST_ENTRY kembali ke XXX_ENTRY, gunakan CONTAINING_RECORD. Untuk contoh teknik ini, menggunakan daftar tertaut yang tidak berurutan, lihat Daftar Tertaut Senyap.
Peringatan Untuk sistem operasi Microsoft Windows 64-bit, struktur SLIST_ENTRY harus selaras 16 byte.
Windows XP dan versi Windows yang lebih baru menyediakan versi yang dioptimalkan dari fungsi daftar tertaut berurutan yang tidak tersedia di Windows 2000. Jika driver Anda menggunakan fungsi-fungsi ini dan juga harus berjalan dengan Windows 2000, driver harus menentukan bendera _WIN2K_COMPAT_SLIST_USAGE, sebagai berikut:
#define _WIN2K_COMPAT_SLIST_USAGE
Untuk prosesor berbasis x86, bendera ini menyebabkan pengkompilasi menggunakan versi fungsi daftar tertaut berurutan yang kompatibel dengan Windows 2000.