Aracılığıyla paylaş

Tekli ve Çift Bağlantılı Listeler

Tek Bağlantılı Listeler

İşletim sistemi, SINGLE_LIST_ENTRY yapıları kullanan tek tek bağlantılı listeler için yerleşik destek sağlar. Tek bağlantılı liste, bir liste başlığı ve bir dizi liste girdisi içerir. (Liste boşsa, liste girdilerinin sayısı sıfırdır.) Her liste girdisi bir SINGLE_LIST_ENTRY yapısı olarak temsil edilir. Liste başı da SINGLE_LIST_ENTRY bir yapı olarak temsil edilir.

Her SINGLE_LIST_ENTRY yapısı, başka bir SINGLE_LIST_ENTRY yapısına işaret eden bir Sonraki üye içerir. Liste başlığını temsil eden SINGLE_LIST_ENTRY yapısında , Sonraki üye listedeki ilk girdiye işaret eder veya liste boşsa NULL olur. Listedeki bir girdiyi temsil eden SINGLE_LIST_ENTRY yapısında , Sonraki üye listenin bir sonraki girdisine işaret eder veya bu girdi listenin son girdisiyse NULL olur.

Tek bağlantılı listeyi işleyen yordamlar, liste başlığını temsil eden bir SINGLE_LIST_ENTRY işaretçisini alır. İşlemden sonra listenin ilk girişine işaret edebilmesi için Sonraki işaretçisini güncellerler.

ListHead değişkeninin, liste başlığını temsil eden SINGLE_LIST_ENTRY yapısına yönelik bir işaretçi olduğunu varsayalım. Bir sürücü ListHead'i aşağıdaki gibi işler:

  • Listeyi boş olarak başlatmak için ListHead-Next> değerini NULL olarak ayarlayın.

  • Listeye yeni bir girdi eklemek için, yeni girdiyi temsil etmek için bir SINGLE_LIST_ENTRY ayırın ve sonra girişi listenin başına eklemek için PushEntryList öğesini çağırın.

  • PopEntryList kullanarak ilk girdiyi listeden çıkar.

Bir SINGLE_LIST_ENTRY tek başına yalnızca Bir Sonraki üyesi vardır. Listelerde kendi verilerinizi depolamak için , SINGLE_LIST_ENTRY liste girdisini açıklayan yapının bir üyesi olarak aşağıdaki gibi ekleyin.

typedef struct {
  // driver-defined members
  .
  .
  .
  SINGLE_LIST_ENTRY SingleListEntry;
 
  // other driver-defined members
  .
  .
  .
} XXX_ENTRY;

Listeye yeni bir girdi eklemek için bir XXX_ENTRY yapısı tahsis edin ve ardından SingleListEntry üyesine bir işaretçi geçirerek PushEntryList fonksiyonuna gönderin. İşaretçiyi SINGLE_LIST_ENTRYden XXX_ENTRY'ye geri dönüştürmek için CONTAINING_RECORD'i kullanın. Aşağıda, tek tek bağlı bir listeden sürücü tanımlı girdiler ekleyip kaldıran yordamlara bir örnek verilmiştir.

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, exInterlockedPopEntryList ve ExInterlockedPushEntryList liste işlemlerinin atomik sürümlerini de sağlar. Her biri fazladan bir spin lock parametresi alır. Rutin, listeyi güncellemeden önce dönüş kilidini alır ve ardından işlem tamamlandıktan sonra dönüş kilidini serbest bırakır. Kilit tutulurken kesmeler devre dışı bırakılır. Listedeki her işlem, listedeki bu tür her işlemin diğer tüm işlemlerle eşitlendiğinden emin olmak için aynı döndürme kilidini kullanmalıdır. Döndürme kilidini yalnızca bu ExInterlockedXxxList yordamlarıyla kullanmanız gerekir. Döndürme kilidini başka bir amaç için kullanmayın. Sürücüler birden çok liste için aynı kilidi kullanabilir, ancak bu davranış kilit çekişmelerini artırır, bu nedenle sürücülerin bundan kaçınması gerekir.

Örneğin, ExInterlockedPopEntryList ve ExInterlockedPushEntryList yordamları, IRQL = PASSIVE_LEVEL'de çalışan bir sürücü iş parçacığı ve DIRQL'de çalışan bir ISR tarafından tek bağlantılı bir listenin paylaşımını destekleyebilir. Bu rutinler, döndürme kilidi tutulduğunda kesmeleri devre dışı bırakır. Bu nedenle ISR ve sürücü iş parçacığı, kilitlenme riski olmadan bu ExInterlockedXxxList yordamlarına yapılan çağrılarda aynı döndürme kilidini güvenle kullanabilir.

Aynı listedeki liste işlemlerinin atomik ve atomik olmayan sürümlerine çağrıları karıştırmayın. Atomik ve atomik olmayan sürümler aynı listede aynı anda çalıştırılırsa, veri yapısı bozulabilir ve bilgisayar yanıt vermeyi veya hata denetimini ( kilitlenme) durdurabilir. (Liste işlemlerinin atomik ve atomik olmayan sürümlerine yönelik çağrıları karıştırmaya alternatif olarak atomik olmayan yordamı çağırırken döndürme kilidini alamazsınız. Spin lock'un bu şekilde kullanılması desteklenmez ve yine de liste bozulmasına neden olabilir.)

Sistem ayrıca daha verimli atomik tek bağlantılı listelerin alternatif bir uygulamasını sağlar. Daha fazla bilgi için bkz. Sıralı Tek Bağlantılı Listeler.

Çift Yönlü Bağlantılı Listeler

İşletim sistemi, LIST_ENTRY yapıları kullanan iki kez bağlantılı listeler için yerleşik destek sağlar. Çift bağlantılı liste, bir liste başlığının yanı sıra bazı liste girdilerinden oluşur. (Liste boşsa, liste girdilerinin sayısı sıfırdır.) Her liste girdisi bir LIST_ENTRY yapısı olarak temsil edilir. Liste başı da LIST_ENTRY bir yapı olarak temsil edilir.

Her LIST_ENTRY yapısı bir Flink üyesi ve bir Blink üyesi içerir. Her iki üye de LIST_ENTRY yapıların işaretçileridir.

Liste başlığını temsil eden LIST_ENTRY yapısında Flink üyesi listedeki ilk girdiyi, Blink üyesi ise listedeki son girdiyi gösterir. Liste boşsa, liste başlığının Flink ve Blink özellikleri liste başlığının kendisine işaret eder.

Listedeki bir girdiyi temsil eden LIST_ENTRY yapısında , Flink üyesi listedeki bir sonraki girdiyi, Blink üyesi ise listedeki önceki girdiyi gösterir. (Girdi listedeki son girdiyse, Flink liste başlığını gösterir. Benzer şekilde, girdi listedeki ilk girdiyse , Blink liste başlığını gösterir.)

Bu kurallar ilk bakışta şaşırtıcı görünse de, liste ekleme ve kaldırma işlemlerinin koşullu kod dalları olmadan uygulanmasına izin verir.

İki yönlü bağlı listeyi işleyen rutinler, liste başlığını temsil eden bir LIST_ENTRY işaretçisini alır. Bu rutinler, Flink ve Blink üyelerini güncelleyerek liste başlığında bu üyelerin sonuçta elde edilen listedeki ilk ve son girdilere işaret etmesini sağlar.

ListHead değişkeninin, liste başlığını temsil eden LIST_ENTRY yapısına yönelik bir işaretçi olduğunu varsayalım. Bir sürücü ListHead'i aşağıdaki gibi işler:

  • Listeyi boş olarak başlatmak için InitializeListHead fonksiyonunu kullanın; bu, ListHead->Flink ve ListHead->Blink işaretçilerini ListHead üzerine ayarlar.

  • Listenin başına yeni bir girdi eklemek için, yeni girdiyi temsil etmek için bir LIST_ENTRY ayırın ve sonra girişi listenin başına eklemek için InsertHeadList öğesini çağırın.

  • Listenin kuyruğuna yeni bir girdi eklemek için, yeni girdiyi temsil etmek için bir LIST_ENTRY ayırın ve ardından InsertTailList'i çağırarak girdiyi listenin sonuna ekleyin.

  • Listeden ilk girdiyi kaldırmak için RemoveHeadList kullanın. Bu, listeden kaldırılan girdiye veya liste boşsa ListHead'e bir işaretçi döndürür.

  • Listeden son girdiyi kaldırmak için RemoveTailList kullanın. Bu, listeden kaldırılan girdiye veya liste boşsa ListHead'e bir işaretçi döndürür.

  • Belirtilen bir girdiyi listeden kaldırmak için RemoveEntryList kullanın.

  • Bir listenin boş olup olmadığını denetlemek için IsListEmpty kullanın.

  • Listeyi başka bir listenin kuyruğuna eklemek için AppendTailList kullanın.

Bir LIST_ENTRY, tek başına yalnızca Blink ve Flink üyelerine sahiptir. Listelerde kendi verilerinizi depolamak için , LIST_ENTRY aşağıda gösterildiği gibi liste girdisini açıklayan yapının bir üyesi olarak ekleyin.

typedef struct {
  // driver-defined members
  .
  .
  .
  LIST_ENTRY ListEntry;
 
  // other driver-defined members.
  .
  .
  .
} XXX_ENTRY;

Listeye yeni bir girdi eklemek için, XXX_ENTRY bir yapı ayırın ve ardından ListEntry üyesine bir işaretçiyi InsertHeadList veya InsertTailList'e geçirin. Bir işaretçiyi LIST_ENTRY türünden tekrar XXX_ENTRY türüne çevirmek için CONTAINING_RECORD'i kullanın. Tek bağlantılı listeleri kullanarak bu tekniğin bir örneği için yukarıdaki Tek Tek Bağlantılı Listeler'e bakın.

Sistem ayrıca liste işlemlerinin atomik sürümlerini de sağlar: ExInterlockedInsertHeadList, ExInterlockedInsertTailList ve ExInterlockedRemoveHeadList. RemoveTailList veya RemoveEntryList'in atomik sürümü yoktur. Her bir rutin fazladan bir spin lock parametresi alır. Yordam, listeyi güncellemeden önce spin kilidini alır ve işlem tamamlandıktan sonra spin kilidini serbest bırakır. Kilit tutulurken kesmeler devre dışı bırakılır. Listedeki her işlem, listedeki her işlemin birbiriyle eşitlendiğinden emin olmak için aynı döndürme kilidini kullanmalıdır. Döndürme kilidini yalnızca bu ExInterlockedXxxList yordamlarıyla kullanmanız gerekir. Döndürme kilidini başka bir amaç için kullanmayın. Sürücüler birden çok liste için aynı kilidi kullanabilir, ancak bu davranış kilit çekişmelerini artırır, bu nedenle sürücülerin bundan kaçınması gerekir.

Örneğin, ExInterlockedInsertHeadList, ExInterlockedInsertTailList ve ExInterlockedRemoveHeadList rutinleri, IRQL = PASSIVE_LEVEL'de çalışan bir sürücü iş parçacığı ve DIRQL'de çalışan bir ISR tarafından çifte bağlı bir listenin paylaşımını destekleyebilir. Bu rutinler, döndürme kilidi tutulduğunda kesmeleri devre dışı bırakır. Bu nedenle ISR ve sürücü iş parçacığı, kilitlenme riski olmadan bu ExInterlockedXxxList yordamlarına yapılan çağrılarda aynı döndürme kilidini güvenle kullanabilir.

Aynı listedeki liste işlemlerinin atomik ve atomik olmayan sürümlerine çağrıları karıştırmayın. Atomik ve atomik olmayan sürümler aynı listede aynı anda çalıştırılırsa, veri yapısı bozulabilir ve bilgisayar yanıt vermeyi veya hata denetimini ( kilitlenme) durdurabilir. (Liste işlemlerinin atomik ve atom dışı sürümlerine yönelik çağrıların karıştırılmasını önlemek için atomik olmayan yordamı çağırırken döndürme kilidini alamazsınız. Spin lock'un bu şekilde kullanılması desteklenmez ve yine de liste bozulmasına neden olabilir.)

Sıralı Tek Bağlantılı Listeler

Sıralı tek bağlantılı liste, atomik işlemleri destekleyen tek bağlantılı listelerin uygulanmasıdır. Atomik işlemler için Tek Bağlantılı Listeler'de açıklanan tek bağlantılı listelerin uygulanmasından daha verimlidir.

SLIST_HEADER yapısı tek tek bağlantılı sıralı listenin başını tanımlamak için kullanılırken, listedeki bir girişi açıklamak için SLIST_ENTRY kullanılır.

Bir sürücü listeyi aşağıdaki gibi işler:

Bir SLIST_ENTRY tek başına yalnızca Bir Sonraki üyesi vardır. Listelerde kendi verilerinizi depolamak için , SLIST_ENTRY liste girdisini açıklayan yapının bir üyesi olarak aşağıdaki gibi ekleyin.

typedef struct 
{
  // driver-defined members
  .
  .
  .
  SLIST_ENTRY SListEntry;
  // other driver-defined members
  .
  .
  .

} XXX_ENTRY;

Listeye yeni bir girdi eklemek için bir XXX_ENTRY yapısı ayırın ve ardından SListEntry üyesine ExInterlockedPushEntrySList'e bir işaretçi geçirin.

Bir işaretçiyi SLIST_ENTRY olarak XXX_ENTRY'ye dönüştürmek için CONTAINING_RECORD kullanın. Bu tekniğin bir örneği için, sıralanmamış tek tek bağlantılı listeleri kullanarak, bkz. Tek Tek Bağlantılı Listeler.

Uyarı 64 bit Microsoft Windows işletim sistemlerinde SLIST_ENTRY yapıların 16 bayt hizalanmış olması gerekir.

  • Last updated on