Bagikan melalui

Daftar Terhubung Satu Arah dan Dua Arah

Daftar Tertaut Sederhana

Sistem operasi menyediakan dukungan bawaan untuk daftar yang ditautkan secara senyap yang menggunakan struktur SINGLE_LIST_ENTRY . Daftar tertaut tunggal terdiri dari kepala daftar ditambah sejumlah entri daftar. (Jumlah entri daftar adalah nol jika daftar kosong.) Setiap entri daftar direpresentasikan sebagai struktur SINGLE_LIST_ENTRY . Kepala daftar juga diwakili 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 tertaut tunggal mengambil penunjuk ke SINGLE_LIST_ENTRY yang mewakili kepala daftar. Mereka memperbarui pointer 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.

  • Keluarkan entri pertama dari daftar dengan menggunakan PopEntryList.

SINGLE_LIST_ENTRY, sendiri, hanya memiliki anggota Next. 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 oleh driver dari daftar terkait tunggal.

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 menerima parameter spin lock 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 putaran yang sama untuk memastikan bahwa setiap operasi tersebut dalam daftar disinkronkan dengan setiap operasi lainnya. Anda harus menggunakan kunci putar hanya dengan rutinitas ExInterlockedXxxList ini. Jangan gunakan kunci putar untuk tujuan lain. Pengemudi dapat menggunakan kunci yang sama untuk beberapa daftar, tetapi perilaku ini meningkatkan perebutan kunci sehingga pengemudi harus menghindarinya.

Misalnya, rutinitas ExInterlockedPopEntryList dan ExInterlockedPushEntryList dapat mendukung berbagi daftar tertaut tunggal oleh utas driver yang berjalan pada IRQL = PASSIVE_LEVEL dan ISR yang berjalan pada DIRQL. Rutinitas ini menonaktifkan gangguan ketika kunci putar ditahan. Dengan demikian, ISR dan utas driver dapat dengan aman menggunakan kunci putar yang sama dalam panggilan mereka ke rutinitas ExInterlockedXxxList ini tanpa risiko kebuntuan.

Jangan mencampur panggilan ke versi atomik dan nonatomi dari operasi daftar pada daftar yang sama. Jika versi atomik dan nonatomis dijalankan secara bersamaan pada daftar yang sama, struktur data mungkin menjadi rusak dan komputer mungkin berhenti merespons atau terjadi kesalahan sistem (yaitu, crash). (Anda tidak dapat memperoleh "spin lock" ketika memanggil rutinitas nonatomis, sebagai alternatif dari mencampurkan panggilan ke versi atom dan nonatomis dari operasi daftar. Menggunakan "spin lock" dengan cara ini tidak didukung dan mungkin masih menyebabkan kerusakan daftar.)

Sistem ini juga menyediakan implementasi alternatif dari daftar tertaut tunggal atomik yang lebih efisien. Untuk informasi selengkapnya, lihat Daftar Tertaut Berurutan.

Daftar Tertaut Ganda

Sistem operasi menyediakan dukungan bawaan untuk daftar berantai ganda yang menggunakan struktur LIST_ENTRY. Daftar tertaut ganda terdiri dari kepala daftar ditambah beberapa 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 elemen 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 kepala daftar menunjuk 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 ganda 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.

Sebuah 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 penunjuk ke LIST_ENTRY kembali ke XXX_ENTRY, gunakan CONTAINING_RECORD. Untuk contoh teknik ini, menggunakan daftar tertaut tunggal, lihat Daftar Tertaut Tunggal di atas.

Sistem ini juga menyediakan versi atom dari operasi daftar, ExInterlockedInsertHeadList, ExInterlockedInsertTailList, dan ExInterlockedRemoveHeadList. Tidak ada versi atomik dari RemoveTailList atau RemoveEntryList. Setiap rutinitas menerima parameter 'spin lock' ekstra. Rutinitas memperoleh kunci putar sebelum memperbarui daftar dan kemudian 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 satu sama lain. Anda harus menggunakan kunci putar hanya dengan rutinitas ExInterlockedXxxList ini. Jangan gunakan kunci putar untuk tujuan lain. Pengemudi dapat menggunakan kunci yang sama untuk beberapa daftar, tetapi perilaku ini meningkatkan perebutan kunci sehingga pengemudi 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 putar ditahan. Dengan demikian, ISR dan utas driver dapat dengan aman menggunakan kunci putar yang sama dalam panggilan mereka ke rutinitas ExInterlockedXxxList ini tanpa risiko kebuntuan.

Jangan mencampur panggilan ke versi atomik dan nonatomi dari operasi daftar pada daftar yang sama. Jika versi atomik dan nonatomis dijalankan secara bersamaan pada daftar yang sama, struktur data mungkin menjadi rusak dan komputer mungkin berhenti merespons atau pemeriksaan gangguan (yaitu crash). (Anda tidak dapat memperoleh kunci putar saat memanggil rutinitas nonatomis untuk menghindari pencampuran panggilan ke versi atomik dan nonatomi dari operasi daftar. Menggunakan kunci putar dengan cara ini tidak didukung dan mungkin masih menyebabkan kerusakan daftar.)

Daftar Tertaut Tunggal Berurutan

Daftar tertaut tunggal berurutan adalah implementasi daftar tertaut tunggal yang mendukung operasi atomik. Ini lebih efisien untuk operasi atom dibandingkan implementasi daftar tertaut tunggal yang dijelaskan dalam Daftar Tertaut Tunggal.

Struktur SLIST_HEADER digunakan untuk menjelaskan kepala daftar yang ditautkan secara berurutan, sementara SLIST_ENTRY digunakan untuk menjelaskan entri dalam daftar.

Driver memanipulasi daftar sebagai berikut:

SLIST_ENTRY, sendirian, hanya memiliki elemen Next. 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, yang menggunakan daftar tertaut tunggal yang tidak berurutan, lihat Daftar Tertaut Tunggal.

Peringatan Untuk sistem operasi Microsoft Windows 64-bit, struktur SLIST_ENTRY harus selaras 16 byte.

  • Last updated on