Opis algorytmów





6.6.2.1 Opis algorytmow dzialania
 

Struktury danych:


struct hash_list


struct dir_cashe_entry

Funkcje obsługujące tablicę:


remove_hash


add_hash


find_entry

Funkcje operujące na kolejkach:


remove_lru


add_lru


update_lru


move_to_level2

Funkcje do odwoływania się do pamięci:


dcache_lookup


dcache_add

Inne:


inicjuje kolejki lru1 i lru2 oraz tablicę haszującą name_cash_init



Bibliografia:


zrodla Linuxa:  fs/dcache.c



void remove_hash(struct
dr_cache_etry * de)
 {
usuwa element de z tablicy haszującej poprzez przesunięcie wskaźników
w poprzedzającym i następującym po de elementach
}    Powrót.
 


void add_hash(struct
dir_cache_entry * de, struct hash_list * hash)
{
dodaje element wskazywany przez de na początek listy(w tablicy haszującej)
wskazywanej przez hash
}    Powrót.
 


struct dir_cache_entry * find_entry(struct
inode * dir, const char * name, int len, struct hash_list * hash)
{
dla każdej pozycji z listy hash sprawdź
{
czy zgadza się numer urządzenia;
czy zgadza się i-węzeł katalogu macierzystego
czy zgadza się wersja ???
czy zgadza się nazwa
czy zgadza się długoć nazwy
}
jeżeli wszystko się zgadza zwróć wskaźnik na aktualny element;
}    Powrót.
 


void remove_lru(struct
dir_cache_entry * de)
{
usuwamy element wskazywany przez de z kolejki lru w której się znajduje,
poprzez przesunięcie wskaźników u sąsiadów;
}    Powrót.
 


void add_lru(struct
dir_cache_entry * de, struct dir_cache_entry *head)
{
wstawiamy element wskazywany przez de na koniec kolejki wskazywanej
przez head;
}    Powrót.
 


void update_lru(struct
dir_cache_entry * de)
{
jesli(element wskazywany przez de jest na początku kolejki)
{
przesuwamy wskażnik na głowę kolejki o jedną pozycję do przodu;
}
else
{
usuń element wskazywany przez de;
wstaw element wskazywany przez de, do kolejki wskazywanej przez de->lru_head;
}
}    Powrót.
 


void move_to_level2(struct
dir_cache_entry * old_de, struct hash_list * hash)
{
jesli( old_de jest w level2)
{
wywołaj update(old_de);
koniec;
}
przesuń wskaźnik na głowę kolejki o jeden do przodu;
usuń dotychczasowy pierwszy element z tablicy haszującej;  
(remove_hash(de))
skopiuj dane z old_de na miejsce poprzedniego pierwszego elementu (de);
wstaw de do hasz listy (hash) na jej poczatek (add_hash);

// w ten sposób otrzymalimy sytuację, w której element jest na końcu
kolejki level2, zas na początku odpowiedniej listy haszującej(co zapewne
przyspieszy dostęp do tego elementu)
}    Powrót.
 


int dcache_lookup(struct
inode * dir, const char * name, int len, unsigned long * ino)
//Daje w wyniku : 0 - porażka, czyli nie znaleziono
//                         
1 - znaleziono, i-węzeł na zmiennej ino
{
jeżeli(nazwa za długa, czyli większa od EXT2_NAME_LEN) to koniec i
zwróć zero;
znajdź odpowiednią listę haszujaca;
jeżeli(nie ma w niej naszego elementu - szukamy przy pomocy find_entry)
{
koniec i zwróć zero;
}
//a jednak jest
na ino wpisujemy numer i-węzła znalezionej pozycji;
przesuwamy na koniec drugiej kolejki (move_to_level2);
i zwracamy jedynkę
}    Powrót.
 


void dcache_add(struct
inode * dir, const char * name, int len, unsigned long ino)
{
jeżeli(za długa nazwa) to niestety koniec;
//wpp. sprawdzamy czy jest w pamięci
sprawdzamy w której liscie haszującej powinien być (algorytm hashfn);
jeżeli(jest tam -sprawdzamy czy tam jest (find_entry))
{
uaktualniamy i-węzeł;
przesuwamy go na koniec jego kolejki (update_lru);
i koniec;
}
//nie było go więc:
przesuwamy wskaźnik na głowę kolejki level1;
usuwamy pierwszego z level1;
i wstawiamy nasz element na koniec level1;
}    Powrót.
 


Sporzadzil: Tomasz Chudzik