
/** @file lists.c
 *
 * Podpurne funkce pro praci se spojovymi Listy. Jedna se o obousmerne
 * cyklicke spojove Listy s hlavou. Kazdy List tez disponuje spinlockem,
 *  coz je synchronizacni primitivum, ktere umoznuje k danemu Listu synchronizovat
 * pristup tak, aby s nim v kazdem okamziku pracovalo nejvyse jedno vlakno.
 */

#include <ntddk.h>
#include "driver.h"
#include "lists.h"



/** Vytvori novy spojovy seznam.
 *
 *  @param PoolType Typ pametoveho fondu, do ktereho bude datova struktura
 *  noveho seznamu ulozena.
 *  @param DestroyItem Adresa zpetne volane funkce, ktera bude volana na
 *  kazdy prvek nachazejici se v danem seznamu pri jeho uvolnovani z pameti.
 *
 *  @returns Funkce vraci adresu noveho spojoveho seznamu. Tuto adresu je
 *  mozne pouzit v dalsich funkcich pro praci s touto datovou strukturou.
 */
PLIST lListCreate(POOL_TYPE PoolType, LIST_DESTROY_ITEM_ROUTINE DestroyItem)
{
  PLIST Ret = NULL;
  KdPrint(("lists.c: ListCreate(PoolType=%u; DestroyItem=0x%p)\n", PoolType, DestroyItem));

  Ret = ExAllocatePoolWithTag(PoolType, sizeof(LIST), POOL_TAG);
  if (Ret != NULL) {
    // Podarilo se. Inicializujeme hlavu, spinlock a nastavime rusici rutinu
    InitializeListHead(&Ret->Head);
    KeInitializeSpinLock(&Ret->Lock);
    Ret->DestroyItem = DestroyItem;
  }

  KdPrint(("lists.c: ListCreate(-):0x%p\n", Ret));
  return Ret;
}


/** Zrusi spojovy seznam.
 *
 * Pokud ruseny seznam obsahuje nejake prvky, na kazdy z nich pred jeho
 * zrusenim zavola rutinu DestroyItem definovanou pri vytvareni seznamu.
 *
 * @param List Spojovy seznam, ktery chce volajici zrusit.
 */
VOID lListDestroy(PLIST List)
{
  PLIST_ENTRY Item = NULL;
  PLIST_ENTRY Next = NULL;
  KdPrint(("lists.c: ListDestroy(List=0x%p)\n", List));

  Item = List->Head.Blink;
  while (Item != &List->Head) {
    Next = Item->Blink;
    if (List->DestroyItem != NULL)
      List->DestroyItem(Item);

    Item = Next; 
  }

  ExFreePoolWithTag(List, POOL_TAG);

  KdPrint(("lists.c: ListDestroy(-)\n"));
  return;
}


/** Zrusi spojovy seznam.
 *
 * Procedure se chova stejne jako lListDestroy, pouze pomoci spinlocku zamezuje
 * pristupu dalsich vlaken k seznamu.
 *
 * @param List Seznam, ktery si volajici preje zrusit.
 */
VOID lListDestroyLock(PLIST List)
{
  PLIST_ENTRY Item = NULL;
  PLIST_ENTRY Next = NULL;
  KLOCK_QUEUE_HANDLE QHandle;
  KdPrint(("lists.c: ListDestroyLock(List=0x%p)\n", List));

  lListLock(List, &QHandle);
  Item = List->Head.Blink;
  while (Item != &List->Head) {
    Next = Item->Blink;
    if (List->DestroyItem != NULL)
      List->DestroyItem(Item);

    Item = Next; 
  }
  
  lListUnlock(List, &QHandle);
  ExFreePoolWithTag(List, POOL_TAG);

  KdPrint(("lists.c: ListDestroyLock(-)\n"));
  return;
}


/** Otestuje seznam, zda neni prazdny.
 *
 * Pro prazdny seznam vrati TRUE, pro neprazdny FALSE.
 *
 * @param List. Seznam, ktery se ma testovat.
 */
BOOLEAN lListEmpty(PLIST List)
{
  BOOLEAN Ret = FALSE;
  KdPrint(("lists.c: ListEmpty(List=0x%p)\n", List));

  Ret = IsListEmpty(&List->Head);

  KdPrint(("lists.c: ListEmpty(-):%u\n", Ret));
  return Ret;
}


/** Varianta predchozi rutiny vylepsena o synchronizaci.
 *
 * @param List Seznam, ktery chce volajici otestovat.
 */
BOOLEAN lListEmptyLock(PLIST List)
{
  BOOLEAN Ret = FALSE;
  KLOCK_QUEUE_HANDLE QHandle;
  KdPrint(("lists.c: ListEmptyLock(List=0x%p)\n", List));

  lListLock(List, &QHandle);
  Ret = lListEmpty(List);
  lListUnlock(List, &QHandle);

  KdPrint(("lists.c: ListEmptyLock(-):%u\n", Ret));
  return Ret;
}


/** Vlozi na konec seznamu novy prvek.
 *
 * @param List Spojovy seznam, do ktereho chce voaljici vkladat.
 * @param Item Prvek, ktery se ma vlozit.
 */
VOID lListTailInsert(PLIST List, PLIST_ENTRY Item)
{
  KdPrint(("lists.c: ListTailInsert(List=0x%p; Item=0x%p)\n", List, Item));

  InsertTailList(&List->Head, Item);

  KdPrint(("lists.c: ListTailInsert(-)\n"));
  return;
}


/** Vkladani prvku na konec seznamu vylepsene o synchronizaci.
 *
 * @param List Spojovy seznam, do ktereho chce voaljici vkladat.
 * @param Item Prvek, ktery se ma vlozit.
 */ 
VOID lListTailInsertLock(PLIST List, PLIST_ENTRY Item)
{
  KLOCK_QUEUE_HANDLE QHandle;
  KdPrint(("lists.c: ListTailInsertLock(List=0x%p; Item=0x%p)\n", List, Item));

  lListLock(List, &QHandle);
  lListTailInsert(List, Item);
  lListUnlock(List, &QHandle);

  KdPrint(("lists.c: ListTailInsertLock(-)\n"));
  return;
}


/** Vlozi novy Item na zacatek seznamu.
 *
 * @param List Spojovy seznamu, do ktereho chce voaljici vkladat.
 * @param Item Prvek, ktery se ma vlozit.
 */
VOID lListHeadInsert(PLIST List, PLIST_ENTRY Item)
{
  KdPrint(("lists.c: ListHeadInsert(List=0x%p; Item=0x%p)\n", List, Item));

  InsertHeadList(&List->Head, Item);

  KdPrint(("lists.c: ListHeadInsert(-)\n"));
  return;
}


/** Vkladani prvku na zacatek seznamu vylepsene o synchronizaci.
 *
 * @param List Spojovy seznam, do ktereho chce voaljici vkladat.
 * @param Item Prvek, ktery se ma vlozit.
 */ 
VOID lListHeadInsertLock(PLIST List, PLIST_ENTRY Item)
{
  KLOCK_QUEUE_HANDLE QHandle;
  KdPrint(("lists.c: ListHeadInsertLock(List=0x%p; Item=0x%p)\n", List, Item));

  lListLock(List, &QHandle);
  lListHeadInsert(List, Item);
  lListUnlock(List, &QHandle);

  KdPrint(("lists.c: ListHeadInsertLock(-)\n"));
  return;
}


/** Odebere prvni prvek ze seznamu.
 *
 * Vrati adresu odebraneho prvku. V pripade prazdneho seznamu vrati NULL.
 *
 * @param List Seznam, ze ktereho chce volajici odebrat.
 */
PLIST_ENTRY lListHeadRemove(PLIST List)
{
  PLIST_ENTRY Ret = NULL;
  KdPrint(("lists.c: ListHeadRemove(List=0x%p)\n", List));

  if (!lListEmpty(List)) {
    Ret = RemoveHeadList(&List->Head);
    InitializeListHead(Ret);
  }

  KdPrint(("lists.c: ListHeadRemove(-):0x%p\n", Ret));
  return Ret;
}


/** Odebirani prvniho prvku ze seznamu vylepsene o synchronizaci.
 *
 * Vrati prvni prvek Seznamu. V pripade prazdneho seznamu vrati NULL.
 *
 * @param List Seznam, ze ktereho se ma odebirat.
 */
PLIST_ENTRY lListHeadRemoveLock(PLIST List)
{
  PLIST_ENTRY Ret = NULL;
  KLOCK_QUEUE_HANDLE QHandle;
  KdPrint(("lists.c: ListHeadRemoveLock(List=0x%p)\n", List));

  lListLock(List, &QHandle);
  Ret = lListHeadRemove(List);
  lListUnlock(List, &QHandle);

  KdPrint(("lists.c: ListHeadRemoveLock(-):0x%p\n", Ret));
  return Ret;
}


/** Odebere posledni prvek ze seznamu.
 *
 * Vrati adresu odebraneho prvku. V pripade prazdneho seznamu vrati NULL.
 *
 * @param List Seznam, ze ktereho chce volajici odebrat.
 */
PLIST_ENTRY lListTailRemove(PLIST List)
{
  PLIST_ENTRY Ret = NULL;
  KdPrint(("lists.c: ListTailRemove(List=0x%p)\n", List));

  if (!lListEmpty(List)) {
    Ret = RemoveTailList(&List->Head);
    InitializeListHead(Ret);
  }

  KdPrint(("lists.c: ListTailRemove(-):0x%p\n", Ret));
  return Ret;
}


/** Odebirani posledniho prvku ze seznamu vylepsene o synchronizaci.
 *
 * Vrati posledniho prvek seznamu. V pripade prazdneho seznamu vrati NULL.
 *
 * @param List Seznam, ze ktereho se ma odebirat.
 */
PLIST_ENTRY lListTailRemoveLock(PLIST List)
{
  PLIST_ENTRY Ret = NULL;
  KLOCK_QUEUE_HANDLE QHandle;
  KdPrint(("lists.c: ListTailRemoveLock(List=0x%p)\n", List));

  lListLock(List, &QHandle);
  Ret = lListTailRemove(List);
  lListUnlock(List, &QHandle);

  KdPrint(("lists.c: ListTailRemoveLock(-):0x%p\n", Ret));
  return Ret;
}


/** Zamkne seznam.
 *
 * Zamceny seznam garantuje vlaknu, ktere zamykani provedlo, exklizivni
 * pristup. Ostatni vlakna, ktera se pokousi se seznamem pracovat,
 * jsou pozastavena (aktivnim cekanim), dokud seznam neni odemcen.
 *
 * Pokus o zamceni zamceneho seznamu zablokuje volajici vlakno.
 *
 * @param List Seznam, který má byt zamcen.
 * @param QHandle Viz. napoveda ke KeAcquireInStackQueuedSpinLock ci text knihy.
 */
VOID lListLock(PLIST List, PKLOCK_QUEUE_HANDLE QHandle)
{
  KdPrint(("lists.c: ListLock(List=0x%p; QHandle=0x%p)\n", List, QHandle));

  KeAcquireInStackQueuedSpinLock(&List->Lock, QHandle);

  KdPrint(("lists.c: ListLock(-)\n"));
  return;
}

/** Odemkne spojovy seznam.
 *
 * @param List Seznam, ktery se ma odemknout.
 * @param QHandle Viz ListLock.
 */
VOID lListUnlock(PLIST List, PKLOCK_QUEUE_HANDLE QHandle)
{
  KdPrint(("lists.c: ListUnlock(List=0x%p; QHandle=0x%p)\n", List, QHandle));

  KeReleaseInStackQueuedSpinLock(QHandle);

  KdPrint(("lists.c: ListUnlock(-)\n"));
  return;
}
