#include <string.h>
#include "filesys/file.h"
#include "userprog/process.h"
#include "threads/thread.h"
#include "threads/vaddr.h"
#include "threads/malloc.h"
#include "threads/palloc.h"
#include "vm/page.h"

static unsigned page_table_hash (const struct hash_elem *e, void *aux UNUSED);
static bool page_table_cmp_less (const struct hash_elem *a, const struct hash_elem *b,
    void *aux UNUSED);
static void page_table_entry_free (struct hash_elem *e, void *aux UNUSED);
static bool page_table_insert (struct hash *ht, struct page_table_entry *pte);

/* initialize page table structure */
void
page_table_init (struct hash *ht)
{
  hash_init (ht, page_table_hash, page_table_cmp_less, NULL);
}

/* calulcates and returns the hash used as key of the hash/page table */
static unsigned
page_table_hash (const struct hash_elem *e, void *aux UNUSED)
{
  const struct page_table_entry *pte = hash_entry (e, struct page_table_entry, elem);
  return hash_bytes (&pte->upage, sizeof pte->upage);
}

/* page table comperator needed by the hash table implementation.
   returns true if A is less than B, or false if A is greater than
   or equal to B */
static bool
page_table_cmp_less (const struct hash_elem *a, const struct hash_elem *b,
    void *aux UNUSED)
{
  const struct page_table_entry *pte1 = hash_entry (a, struct page_table_entry, elem);
  const struct page_table_entry *pte2 = hash_entry (b, struct page_table_entry, elem);
  return (pte1->upage < pte2->upage);
}

/* frees the content of page table */
void
page_table_free (struct hash *ht)
{
  hash_destroy (ht, page_table_entry_free);
}

/* frees a single page table entry */
static void
page_table_entry_free (struct hash_elem *e, void *aux UNUSED)
{
  struct page_table_entry *pte = hash_entry (e, struct page_table_entry, elem);
  free (pte);
}

/* inserts a new entry into the page table.
   returns false if entry is invalid or already in the table */
static bool
page_table_insert (struct hash *ht, struct page_table_entry *pte)
{
  if (pte == NULL)
    return false;
  return (hash_insert (ht, &pte->elem) == NULL);
}

/* inserts a new entry of type segment into the page table.
   returns false if entry is invalid or already in the table */
bool
page_table_insert_segment (struct hash *ht, struct file *file, off_t ofs,
    void *upage, uint32_t read_bytes, bool writable)
{
  struct page_table_entry *pte = malloc (sizeof *pte);
  if (pte == NULL)
    return false;

  pte->upage  = upage;
  pte->loaded = false;
  pte->segment.file       = file;
  pte->segment.ofs        = ofs;
  pte->segment.read_bytes = read_bytes;
  pte->segment.writable   = writable;
  return page_table_insert (ht, pte);
}

/* fetch an entry from the page table. returns NULL if not found */
struct page_table_entry *
page_table_fetch (struct hash *ht, void *upage)
{
  struct page_table_entry pte;
  struct hash_elem *e;

  pte.upage = upage;
  e = hash_find (ht, &pte.elem);
  return ((e != NULL) ? hash_entry (e, struct page_table_entry, elem) : NULL);
}

/* remove an entry from the page table. returns the element or NULL if not found.
   the caller is responsible for freeing the element! */
struct page_table_entry *
page_table_remove (struct hash *ht, void *upage)
{
  struct page_table_entry pte;
  struct hash_elem *e;

  pte.upage = upage;
  e = hash_delete (ht, &pte.elem);
  return ((e != NULL) ? hash_entry (e, struct page_table_entry, elem) : NULL);
}

/* load the page referenced by the page table entry.
   returns true on success or already loaded, false otherwise */
bool
page_load (struct page_table_entry *pte)
{
  struct segment *data;
  if (pte->loaded)
    return true;

  data = &pte->segment;
  file_seek (data->file, data->ofs);

  /* Get a page of memory. */
  uint8_t *kpage = palloc_get_page (PAL_USER);
  if (kpage == NULL)
    return false;

  /* Load this page. */
  if (file_read (data->file, kpage, data->read_bytes)
      != (int) data->read_bytes)
    {
      palloc_free_page (kpage);
      return false;
    }
  memset (kpage + data->read_bytes, 0, PGSIZE - data->read_bytes);

  /* Add the page to the process's address space. */
  if (!process_install_page (pte->upage, kpage, data->writable))
    {
      palloc_free_page (kpage);
      return false;
    }

  pte->loaded = true;
  return true;
}