/*
 * The directory cache is a "two-level" cache, each level doing LRU on
 * its entries.  Adding new entries puts them at the end of the LRU
 * queue on the first-level cache, while the second-level cache is
 * fed by any cache hits.
 *
 * The idea is that new additions (from readdir(), for example) will not
 * flush the cache of entries that have really been used.
 *
 * There is a global hash-table over both caches that hashes the entries
 * based on the directory inode number and device as well as on a
 * string-hash computed over the name.
 */

#include <linux/fs.h>
#include <linux/string.h>
***************DEKLARACJE STAŁYCH I STRUKTUR DANYCH**************
/*
 * Don't bother caching long names.. They just take up space in the cache, and
 * for a name cache you just want to cache the "normal" names anyway which tend
 * to be short.
 */
// Do pamięci wprowadzae są tylko te pozycje katalogowe, których długosć nazwy nie przekracza DCACHE_NAME_LEN, ograniczenie to wprowadzono, aby nadmiernie nie obciazac pamieci

#define DCACHE_NAME_LEN 15       //stała ogranicza długoć nazwy pozycji katalogowej
#define DCACHE_SIZE 128                  //okresla iloć pozycji w kazdej kolejce lru

//Poniższa struktura sluży do implementacji list haszujących, ktorych elementami sa dir_cache_entry

/*struct hash_list {
        struct dir_cache_entry * next;
        struct dir_cache_entry * prev;
};
 

 * The dir_cache_entry must be in this order: we do ugly things with the pointers
 */
struct dir_cache_entry {
        struct hash_list h;                                               //wskaźnik do kolejki
        kdev_t dc_dev;                                                 //numer urządzenia
        unsigned long dir;                                              //numer i-węzła katalogu
        unsigned long version;                                       //wersja ???
        unsigned long ino;                                             //numer i-węzła pozycji
        unsigned char name_len;                                   //długosć nazwy
        char name[DCACHE_NAME_LEN];              //nazwa
        struct dir_cache_entry ** lru_head;                  //wskaźnik na kolejke(głowę) lru, w której
                                                                                  znajduje się dana pozycja katalogowa
        struct dir_cache_entry * next_lru,  * prev_lru;   //wskaźnik na poprzedni i następny w
                                                                                  kolejce lru
};

#define dcache_offset(x) ((unsigned long)&((struct dir_cache_entry*)0)->x)
#define dcache_datalen (dcache_offset(lru_head) - dcache_offset(dc_dev))

#define COPYDATA(de, newde) \
memcpy((void *) &newde->dc_dev, (void *) &de->dc_dev, dcache_datalen)

//deklaracje kolejek lru (tablice ograniczone stałą)
static struct dir_cache_entry level1_cache[DCACHE_SIZE];
static struct dir_cache_entry level2_cache[DCACHE_SIZE];

/*
 * The LRU-lists are doubly-linked circular lists, and do not change in size
 * so these pointers always have something to point to (after _init)
 */
//deklaracje głów kolejek lru
static struct dir_cache_entry * level1_head;
static struct dir_cache_entry * level2_head;

/*
 * The hash-queues are also doubly-linked circular lists, but the head is
 * itself on the doubly-linked list, not just a pointer to the first entry.
 */
//kolejki haszujące są dwukierunkowymi cyklicznymi listami z wyróżnioną głową

#define DCACHE_HASH_QUEUES 32  //ilosć list haszujących

//definicja funkcji haszującej - zwraca wartosć z przedziału (0 - DCACHE_HASH_QUEUES)
zależy od i-węzła katalogu, nazwy i jej długosci, oraznumeru urządzenia
#define hash_fn(dev,dir,namehash) ((HASHDEV(dev) ^ (dir) ^ (namehash)) % DCACHE_HASH_QUEUES)

//tablica haszująca w polu[i-tym] zawiera wskaźniki do początku i końca i-tej listy hashującej
static struct hash_list hash_table[DCACHE_HASH_QUEUES];
 

***************************OPIS FUNKCJI**********************************

//funkcja usuwa element wskazywany przez de(pozycje) z kolejki lru
każdy element jest zawsze tylko w jednej kolejce
static inline void remove_lru(struct dir_cache_entry * de)
{
        struct dir_cache_entry * next = de->next_lru;
        struct dir_cache_entry * prev = de->prev_lru;

        next->prev_lru = prev;
        prev->next_lru = next;
}

//funkcja wstawia element wskazywany przez de na koniec kolejki wskazywanej przez head
static inline void add_lru(struct dir_cache_entry * de, struct dir_cache_entry *head)
{
        struct dir_cache_entry * prev = head->prev_lru;

        de->next_lru = head;
        de->prev_lru = prev;
        prev->next_lru = de;
        head->prev_lru = de;
}

//funkcja przesuwa element wskazywany przez de na koniec kolejki w której się znajduje
static inline void update_lru(struct dir_cache_entry * de)
{
        if (de == *de->lru_head)
                *de->lru_head = de->next_lru;     //jesli był na początku to tylko przesuwamy głowę
        else {
                remove_lru(de);                            //wpp. usuwa i wstawia
                add_lru(de,*de->lru_head);
        }
}

/*
 * Stupid name"hash" algorithm. Write something better if you want to,
 * but I doubt it matters that much
 */
//głupi algorytm mieszania(haszowania)- przyp. autora
static inline unsigned long namehash(const char * name, int len)
{
        return len +
                ((const unsigned char *) name)[0]+
                ((const unsigned char *) name)[len-1];
}

//Funkcje do obsługi tablicy mieszającej
/*
 * Hash queue manipulation. Look out for the casts..
 */

//funkcja usuwa element wskazywany przez de z tablicy mieszającej
static inline void remove_hash(struct dir_cache_entry * de)
{
        struct dir_cache_entry * next = de->h.next;

        if (next) {
                struct dir_cache_entry * prev = de->h.prev;
                next->h.prev = prev;
                prev->h.next = next;
                de->h.next = NULL;
        }
}

//funkcja dodaje element wskazywany przez de na początek listy wskazywanej przez hash
static inline void add_hash(struct dir_cache_entry * de, struct hash_list * hash)
{
        struct dir_cache_entry * next = hash->next;
        de->h.next = next;
        de->h.prev = (struct dir_cache_entry *) hash;
        next->h.prev = de;
        hash->next = de;
}

/*
 * Find a directory cache entry given all the necessary info.
 */
//Funkcja stara się odnaleźć strukturę dir_cache_entry, w kolejce wskazywanej przez 'hash', odpowiadającą pozycji z katalogu 'dir' zadanej nazwie pliku, jej długosci, ponadto musi się zgadzać numer i-węzła katalogu, numer urządzenia i wersja.
static inline struct dir_cache_entry * find_entry(struct inode * dir, const char * name, int len, struct hash_list * hash)
{
        struct dir_cache_entry * de = hash->next;

        for (de = hash->next ; de != (struct dir_cache_entry *) hash ; de = de->h.next) {
                if (de->dc_dev != dir->i_dev)
                        continue;
                if (de->dir != dir->i_ino)
                        continue;
                if (de->version != dir->i_version)
                        continue;
                if (de->name_len != len)
                        continue;
                if (memcmp(de->name, name, len))
                        continue;
                return de;
        }
        return NULL;
}

/*
 * Move a successfully used entry to level2. If already at level2,
 * move it to the end of the LRU queue..
 */
//Funkcja przesuwa element wskazywany przez old_de na koniec kolejki level2
static inline void move_to_level2(struct dir_cache_entry * old_de, struct hash_list * hash)
{
        struct dir_cache_entry * de;

        if (old_de->lru_head == &level2_head) {     // sprawdzamy, czy kolejką do której należy
                                                                            // element, jest lvel2, jeli tak to przesuwamy
                                                                            // go na koniec (update_lru())
                update_lru(old_de);
                return;
        }
        de = level2_head;                                        // wpp. usuwamy pierwszy element z level2
        level2_head = de->next_lru;                        // i wstawiamy kopię old_de do level2
        remove_hash(de);
        COPYDATA(old_de, de);
        add_hash(de, hash);
}

// Funkcja sprawdza, czy szukany element wyspecyfikowany w nagłówku znajduje się w tablicy haszującej. 0 - porażka, 1 - sukces. ino wskazuje po wyjciu na znaleziony element
int dcache_lookup(struct inode * dir, const char * name, int len, unsigned long * ino)
{
        struct hash_list * hash;
        struct dir_cache_entry *de;

        if (len > DCACHE_NAME_LEN)   //nazwa za długa, czyli elementu na pewno nie ma
                return 0;
//liczymy w której tablicy haszującej szukać
        hash = hash_table + hash_fn(dir->i_dev, dir->i_ino, namehash(name,len));
        de = find_entry(dir, name, len, hash);  //sprawdzamy, czy jest tam ( w 'hash') nasz element
        if (!de)
                return 0;          //nie było, więc zero
        *ino = de->ino;       //a tutaj jednak się znalazł
        move_to_level2(de, hash);   //więc wrzucamy go na koniec level2
        return 1;                              //i dajemy w wyniku jedynkę (sukcess!!!)
}
 

//Funkcja dodaje do pamięci wyspecyfikowany w nagłówku element(pozycję katalogową)
void dcache_add(struct inode * dir, const char * name, int len, unsigned long ino)
{
        struct hash_list * hash;
        struct dir_cache_entry *de;

        if (len > DCACHE_NAME_LEN)
                return;    //tutaj nam się nie udało bo: "nazwa była za długa"
//a jednak poszukajmy, która to lista w tablicy haszującej???
        hash = hash_table + hash_fn(dir->i_dev, dir->i_ino, namehash(name,len));
//teraz już wiemy gdzie szukać, więc do dzieła!!!
        if ((de = find_entry(dir, name, len, hash)) != NULL) {
//już wiemy, że w tablicy haszującej jest nasz element, wskazuje go 'de'
                de->ino = ino;     //uaktualniamy i-węzeł
                update_lru(de);   //i przesuwamy się na koniec kolejki
                return;
        }
 //tutaj jestemy w sytuacji, gdzie nie było elementu w pamięci, więc go wstawiamy,
czyli: przesuwamy wskaźnikna głowę kolejki, usuwamy dotychczasowy pierwszy element,
kopiujemy dane i wstawiamy nowy element na ostatnią pozycję level1
        de = level1_head;
        level1_head = de->next_lru;
        remove_hash(de);
        de->dc_dev = dir->i_dev;
        de->dir = dir->i_ino;
        de->version = dir->i_version;
        de->ino = ino;
        de->name_len = len;
        memcpy(de->name, name, len);
        add_hash(de, hash);
}

//Funkcja inicjuje kolejki lru1 i lru2, oraz tablicę haszującą
unsigned long name_cache_init(unsigned long mem_start, unsigned long mem_end)
{
        int i;
        struct dir_cache_entry * p;

        /*
         * Init level1 LRU lists..
         */
        p = level1_cache;
        do {
                p[1].prev_lru = p;
                p[0].next_lru = p+1;
                p[0].lru_head = &level1_head;
        } while (++p < level1_cache + DCACHE_SIZE-1);
        level1_cache[0].prev_lru = p;
        p[0].next_lru = &level1_cache[0];
        p[0].lru_head = &level1_head;
        level1_head = level1_cache;

        /*
         * Init level2 LRU lists..
         */
        p = level2_cache;
        do {
                p[1].prev_lru = p;
                p[0].next_lru = p+1;
                p[0].lru_head = &level2_head;
        } while (++p < level2_cache + DCACHE_SIZE-1);
        level2_cache[0].prev_lru = p;
        p[0].next_lru = &level2_cache[0];
        p[0].lru_head = &level2_head;
        level2_head = level2_cache;

        /*
         * Empty hash queues..
         */
        for (i = 0 ; i < DCACHE_HASH_QUEUES ; i++)
                hash_table[i].next = hash_table[i].next =
                        (struct dir_cache_entry *) &hash_table[i];
        return mem_start;
}