
/**
 * @file: hash_table.c
 *
 * Tento soubor implementuje hashovaci tabulku pro obecne pouziti. Tato
 * datova struktura resi kolize metodou retezeni prvku.
 */

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


/** Zamkne zadany slot tabulky pro sdileny pristup.
 *
 * @param Table Hashovaci tabulka, kterou chce volajici zamknout.
 * @param Index Index ciloveho slotu.
 */
static VOID HashTableLockShared(PHASH_TABLE Table, ULONG32 Index)
{
  ASSERT(Index < Table->Size);
  KeEnterCriticalRegion();
  ExAcquireResourceSharedLite(&Table->Locks[Index], TRUE);

  return;
}


/** Zamkne zadany slot tabulky pro exkluzivni pristup.
 *
 * @param Table Hashovaci tabulka, kterou chce volajici zamknout.
 * @param Index Index ciloveho slotu.
 */
static VOID HashTableLockExclusive(PHASH_TABLE Table, ULONG32 Index)
{
  ASSERT(Index < Table->Size);
  KeEnterCriticalRegion();
  ExAcquireResourceExclusiveLite(&(Table->Locks[Index]), TRUE);

  return;
}

/** Odemkne slot hashovaci tabulky.
 *
 * @param Table Adresa cilove hashovaci tabulky.
 * @param Index Cislo slotu, ktery chce volajici odemknout.
 */
static VOID HashTableUnlock(PHASH_TABLE Table, ULONG32 Index)
{
  ASSERT(Index < Table->Size);
  ExReleaseResourceLite(&Table->Locks[Index]);
  KeLeaveCriticalRegion();

  return;
}



/** Vytvori novou instanci hashovaci tabulky.
 *
 * Funkce vytvori hashovaci tabulku se zadanym poctem slotu a se zadanou
 * hashovaci, porovnavaci a uklidovou funkci.
 *
 * @param Size Udava pocet slotu hashovaci tabulky.
 * @param HashFunction Adresa hashovaci funkce. Tato hodnota musi nest
 * platna data.
 * @param CompareFunction Adresa porovnavaci funkce. Tato hodnota musi
 * nest platna data.
 * @param FreeFunction Adresa uklidove funkce. Pokud volajici specifikuje
 * NULL, hashovaci tabulka nebude pri svem mazani volat zadnou uklidovou
 * funkci.
 * @param Table. Adresa promenne, do ktere rutina v pripade uspechu zapise adresu
 * struktury nove hashovaci tabulky.
 *
 * @return Rutina vraci hodnotu NTSTATUS indikujici uspech ci neuspech operace.
 */
NTSTATUS HashTableCreate(IN ULONG32 Size, IN HASH_FUNCTION HashFunction, IN COMPARE_FUNCTION CompareFunction, IN FREE_ITEM_FUNCTION FreeFunction, OUT PHASH_TABLE *Table)
{
  LONG i = 0;
  LONG j = 0;
  NTSTATUS Status = STATUS_UNSUCCESSFUL;
  KdPrint(("hash_table.c: HashTableCreate(Size=%u; HashFunction=0x%p; CompareFunction=0x%p; FreeFunction=0x%p; Table=0x%p)\n", Size, HashFunction, CompareFunction, FreeFunction, Table));

  *Table = ExAllocatePoolWithTag(NonPagedPool, sizeof(HASH_TABLE) + Size * sizeof(PHASH_ITEM), POOL_TAG);
  if (*Table != NULL) {
    (*Table)->Size = Size;
    (*Table)->HashFunction = HashFunction;
    (*Table)->CompareFunction = CompareFunction;
    (*Table)->FreeFunction = FreeFunction;
    (*Table)->Locks = ExAllocatePoolWithTag(NonPagedPool, Size * sizeof(ERESOURCE), POOL_TAG);
    if ((*Table)->Locks != NULL) {
      for (i = 0; i < (LONG)Size; i++) {
        (*Table)->Buckets[i] = NULL;
        Status = ExInitializeResourceLite(&((*Table)->Locks[i]));
        if (!NT_SUCCESS(Status)) {
          for (j = 0; j < i; j++)
            ExDeleteResourceLite(&((*Table)->Locks[j]));
		
          ExFreePoolWithTag((*Table)->Locks, POOL_TAG);
          ExFreePoolWithTag(*Table, POOL_TAG);
          break;
        }
      }
    } else {
      ExFreePoolWithTag(*Table, POOL_TAG);
      Status = STATUS_INSUFFICIENT_RESOURCES;
    }
  } else Status = STATUS_INSUFFICIENT_RESOURCES;
  
  KdPrint(("hash_table.c: HashTableCreate(-):0x%x, *Table=0x%p\n", Status, *Table));
  return Status;
}


/** Odstrani celou hashovaci tabulku z pameti.
 *
 * Na kazdy objekt, ktery se v tabulce nachazi, je zavolana uklidova funkce
 * (prvek FreeFunction ve strukture hashovaci tabulky), ktera by mela zajistit
 * jeho uvolneni z pameti.
 *
 * @param Table Hashovaci tabulka, kterou si volajici preje odstranit.
 */
VOID HashTableDestroy(IN PHASH_TABLE Table)
{
  LONG i = 0;
  PHASH_ITEM Tmp = NULL;
  PHASH_ITEM Bucket = NULL;
  KdPrint(("hash_table.c: HashTableDestroy(Table=%p)\n", Table));

  for (i = 0; i < (LONG)Table->Size; i++) {
    ExDeleteResourceLite(&Table->Locks[i]);
    Bucket = Table->Buckets[i];
    if (Bucket != NULL) {
      do {
        Tmp = Bucket;
        Bucket = Bucket->Next;
        if (Table->FreeFunction != NULL)
          Table->FreeFunction(Tmp->Object);
		
        ExFreePoolWithTag(Tmp, POOL_TAG);
      } while (Bucket != NULL);
    }
  }
    
  ExFreePoolWithTag(Table->Locks, POOL_TAG);
  ExFreePoolWithTag(Table, POOL_TAG);
  
  KdPrint(("hash_table.c: HashTableDestroy(-)\n"));
  return;
}


/** Prida novy prvek do hashovaci tabulky.
 *
 * @param Table Cilova hashovaci tabulka.
 * @param Object Prvek, ktery si volajici preje pridat.
 * @param Key Hodnota klice, pod kterym ma byt prvek pridan.
 *
 * @return Funkce vraci hodnotu NTSTATUS indikujici uspech ci neuspech
 * operace.
 */
NTSTATUS HashTableInsert(IN PHASH_TABLE Table, IN PVOID Object, IN PVOID Key)
{
  ULONG32 Index = 0;
  PHASH_ITEM Tmp = NULL;
  NTSTATUS Status = STATUS_UNSUCCESSFUL;
  KdPrint(("hash_table.c: HashTableInsert(Tabulka=0x%p; Object=0x%p; Key=0x%p)\n", Table, Object, Key));

  Index = Table->HashFunction(Key) % Table->Size;
  Tmp = (PHASH_ITEM)ExAllocatePoolWithTag(NonPagedPool, sizeof(HASH_ITEM), POOL_TAG);
  if (Tmp != NULL) {
    Tmp->Object = Object;
	HashTableLockExclusive(Table, Index);
	Tmp->Next = Table->Buckets[Index];
    Table->Buckets[Index] = Tmp;
    HashTableUnlock(Table, Index);
	Status = STATUS_SUCCESS;
  } else Status = STATUS_INSUFFICIENT_RESOURCES;
  
  KdPrint(("hash_table.c: HashTableInsert(-):0x%x\n", Status));
  return Status;
}


/** Odstrani prvek pod zadanym klicem z hashovaci tabulky.
 *
 * Na cilovy objekt neni volana uklidova funkce.
 *
 * @param Table Cilova hashovaci tabulka.
 * @param Key Klic identifikujici hledany objekt.
 * 
 * @return Pokud se cilovy objekt podari z tabulky vyjmout, funkce
 * vrati jeho adresu. V pripade neuspechu vraci NULL.
 */
PVOID HashTableDelete(IN PHASH_TABLE Table, IN PVOID Key)
{
  ULONG32 Index = 0;
  PHASH_ITEM Akt = NULL;
  PHASH_ITEM Prev = NULL;
  PVOID Object = NULL;
  BOOLEAN Ret = FALSE;
  KdPrint(("hash_table.c: HashTableDelete(Table=0x%p; Key=0x%p)\n", Table, Key));

  Index = Table->HashFunction(Key) % Table->Size;
  HashTableLockExclusive(Table, Index);
  Akt = Table->Buckets[Index];
  Prev = NULL;
  while (Akt != NULL) {
    Ret = Table->CompareFunction(Akt->Object, Key);
    if (Ret) {
      Object = Akt->Object;
      if (Prev != NULL)
        Prev->Next = Akt->Next;
      else Table->Buckets[Index] = Akt->Next;
	  
      ExFreePoolWithTag(Akt, POOL_TAG);
      Akt = NULL;
    } else {
      Prev = Akt;
      Akt = Akt->Next;
    }
  }
  
  HashTableUnlock(Table, Index);

  KdPrint(("hash_tabulka.c: HashTableDelete(-):0x%p\n", Object));
  return Object;
}


/** Vrati adresu objektu, ktery se v hashovaci tabulce nachazi pod
 *  zadanym klicem.
 *
 *  @param Table Cilova hashovaci tabulka.
 *  @param Key Klic identifikujici hledany objekt.
 *
 *  @return Funkce vrati adresu objektu, ktery byl do tabulky vlozen pod
 *  zadanym klicem. V pripade, ze objekt se v tabulce nenachazi, rutina
 *  vrati NULL.
 */
PVOID HashTableGet(IN PHASH_TABLE Table, IN PVOID Key)
{
  BOOLEAN Ret = FALSE;
  ULONG32 Index = 0;
  PHASH_ITEM Akt = NULL;
  PVOID Object = NULL;
  KdPrint(("hash_table.c: HashTableGet(Table=0x%p; Key=0x%p)\n", Table, Key));

  Index = Table->HashFunction(Key) % Table->Size;
  HashTableLockShared(Table, Index);
  Akt = Table->Buckets[Index];
  while (Akt != NULL) {
    Ret = Table->CompareFunction(Akt->Object, Key);
    if (Ret) {
      Object = Akt->Object;
      Akt = NULL;
    } else Akt = Akt->Next;
  }
  
  HashTableUnlock(Table, Index);

  KdPrint(("hash_table.c: HashTableGet(-):0x%p\n", Object));
  return Object;
}
