template<typename K, class D>
class PageManager {
  private:
  Node* first;
  Node* last;
  K nodecount = 0;
  K max_nodes = 0;
  std::hash_set<K, Node*> page_table;
  void* flusher = NULL;  // The flusher is a callback function which is called when pages
                         // fall off the tail of the LRU maintained by the PageManager.
                         // The callback has a fucntion signature of:
                         // bool flusher(PageManager::Node* n)
                         //
                         // You can set the default flusher with a member function. If,
                         // after being invoked, the default flusher function returns false,
                         // the PageManager will assert as the database is not in a
                         // consistent state.  You should probably retry at least once
                         // after IO errors etc, to verify an error condition before
                         // returning false.
                         //
                         // if data in node is a pointer and needs to be freed, free it
                         // here.  Note that nodes that require special handling can have
                         // custom flushers.  A custom flusher returns a boolean
                         // return true.  In this case, the default flusher (if any)
                         // associated with the PageManager will not be called.  If the
                         // custom flusher returns false, then the node will be sent
                         // to the default flusher (if any).

  D loader = NULL;       // The opposite of the flusher, the loader loads a page on a
                         // miss of the LRU and puts the new data at the head.
                         // Must return the same type as the second parameter to the
                         // class template (D) and take an argument of the first type K.
                         // For example if the nodes in the LRU store  pointers to pages,
                         // and the pages are identified by an __int128, then the loader
                         // function would be defined like:
                         // Page* load_page(__int128 page_no);
                         // You must throw an exception if there is an error loading
                         // the page.

  class Node {
    Node* next=NULL;
    Node* prev=NULL;
    void* callback;
    K key;

    public:
    D data=NULL;

    // node has data but is not connected to linked list
    Node(K k, D d, void* flush_func= NULL) {
      key = k;
      data = d;
      callback = flush_func;
      prev = NULL;
      next = NULL;
    }

    D get_data() {
      return data;
    }

    K get_key() {
      return key;
    }

    void set_callback(void *flush_func) {
      callback = flush_func;
    }

    void exec_callback() {
      (*callback)(this);
    }

  };

  public:
  PageManager PageManager(K sz=2000, void* default_flusher=NULL) {
    set_size(sz);
    nodecount  = 0;
    flusher = default_flusher;
  }

  /* if this shrinks, the next addition to the LRU will rapidly prune
   * the LRU, flusing each of the removed nodes if a flusher is
   * defined. Minimum size is 128 and any value less than that is
   * adjusted up.
   */
  void set_size(K sz) {
    if(sz <128) sz=128;
    max_nodes = sz;
  }



  /* when a page falls off the LRU it is flushed to disk */
  void flush_block(Node *n) {
    assert(n != NULL && n->data != NULL);
    if(flusher_func)
      return (*flusher_func)(n);
  }

  /* Iterate the linked list trying to find the specified page number.
   * Also populates min/max values for min_page and max_page
   * if necessary.  This scans the whole list, but this
   * single scan can save many successive scans so it is
   * worth it, besides we might be finding a page near
   * the tail anyway.
   */
  Node* find(K key) {
    Node *n;
    /* list is empty or invalid page requested */
    if(nodecount == 0) return NULL;
    assert(key > 0);
    if(!(tmp=page_table[key])) {
      if(loader) {
        D d;
        d = (*loader)(k);
        assert(n != NULL);
        add(k,d,false);
      }
      return NULL;
    }
    return tmp;
  }
  add(K k, D d) {
    return add(k,d, true);
  }

private:
  Node* add(K k, D d, bool search) {
    Node* tmp = NULL;

    /* if search is false, then the node will be unconditionally added to the head,
       otherwise search to see if it already exists.  This is dangerous, so only
       the find function uses this after loading a page on am miss.  This is because
       such a page is guaranteed to go to the head, and if it called the add member
       without setting search=false, it would enter a recursive loop.
    */
    if(!no_search) tmp = find(k);

    /* add the node at the head */
    if(tmp == NULL) {
      tmp = new Node(k, d);

      /* this is the first node being added*/
      if(!nodecount) {
        last = first = tmp;
      }
      page_table[n->key] = n;
      ++nodecount;
      return tmp;
    /* Else update the page with the new data and moves it to head,
       unless sequential mode is on, in which case the page stays in
       place (it must for the file window optimization to work properly) */
    } else {
      /* update the previous node and set the pointer to the
       * next node on that page to be the pointer to the next
       * node on this page.  This "unlinks" the page from the
       * middle of the LRU so that it can be repositioned as
       * the head */
      tmp->prev->next = tmp->next;

      /* connect the new head to the current head by setting
       * the next pointer on the old head */
      tmp->next = first;

      /* then update the old head prev pointer to point to
       * the new head */
      first->prev = tmp;

      /* Finally replace the head pointer  */
      first = tmp;

    }
    tmp->data = p;
    /* first node was added */
    if(nodecount == 1) {
      page_table[n->key] = n;
      return(first = last = n);
    }

    while(nodecount > max_blocks) {
      --nodecount;
      /*flush the buffer to disk,
       * then unlink the bottom page*/
      flush(last);
      last->prev->next = NULL;
      page_table->erase(last->key);
      delete last;
      if(nodecount == 0) {
            first = NULL;
            last = NULL;
            min_page = max_page = 0;
      }
    }

    return tmp;

  }

}