/** 
 * @file linked_list.h
 *
 * Persistent linked lists using mmapped files.
 *
 * Goals:
 * 1. We want to store a linked data structure (a linked list, a tree, etc.) in
 *    a file (preferably using mmap) as binary data.
 * 2. We don't want to make assumptions about the order of the different parts 
 *    of the data structure. E.g., the structure and ordering of a linked list
 *    should be determined by its links, not the order in which nodes are 
 *    stored.
 *
 * Idea: Create an array of nodes and link them using their indices as node 
 * references, instead of pointers (memory addresses).
 *
 * Rationale: Memory addresses stop being valid as soon as the memory is 
 * released, e.g., after the program terminates. Indices mean the same thing 
 * regardless of where the data is stored since they represent _relative 
 * offsets_.
 */

#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/mman.h>

#include <assert.h>

typedef struct node {
  int data;
  // instead of a pointer (i.e., struct node *next) we use an index into the 
  // "storage" as the _node reference_. An empty list will be represented as
  // `(unsigned long) -1`
  unsigned long next;
} node_t;


// Use an array of nodes as the "storage" and keep a pointer to the next 
// available space
unsigned long current_node = 0; // the last node that has been allocated
node_t *storage = NULL;         // pointer to the "node storage"


/** 
 * Allocate a new node and return its storage index.
 *
 * @return The index of the newly allocated node in the storage.
 */
long alloc_node() {
  return current_node++;
}

/**
 * Prepend a new node to the the list.
 *
 * @param data Node payload.
 * @param next The reference ("storage index") of the old head of the list.
 *
 * @return The reference to the new list head.
 */
unsigned long cons(int data, unsigned long next) {
  unsigned long new_idx = alloc_node();
  node_t *tmp = &storage[new_idx];
  tmp->data = data;
  tmp->next = next;
  return new_idx;
}


/**
 * Print the list.
 *
 * @param head Reference ("storage index") to the head of the list.
 */
void print_list(unsigned long head) {
  unsigned long current = head;
  while (current != -1) {
    printf("%d ", storage[current].data);
    current = storage[current].next;
  }

  putchar('\n');
}

/**
 * Insert a new item as the second element of the list.
 *
 * @param data Payload of the second node.
 * @param head Reference to the head of the list.
 */
void insert_as_second(int data, unsigned long head) {
  unsigned long tmp = storage[head].next;
  unsigned long new = alloc_node();

  storage[new].data = data;
  storage[head].next = new;
  storage[new].next = tmp;
}

int main(int argc, char **argv) {

  unsigned long head = -1;

  /* For this exercise, we will just assume that we won't need more than
   * 4096 bytes of storage for our linked list. We could simply keep the 
   * maximum number of nodes we can store (4096 / sizeof(node_t)) and fail to
   * allocate a new node when we run out of space */
  int fd = open("linked_list.bin", O_RDWR | O_CREAT | O_TRUNC, 0644);

  ftruncate(fd, 4096);

  /* Map the file as the node storage in memory */
  storage = mmap(NULL, 4096, PROT_READ | PROT_WRITE, 
      MAP_SHARED | MAP_FILE, fd, 0);

  for (int i = 20; i >= 0; --i) {
    head = cons(i, head);
  }

  insert_as_second(head, 42);
  print_list(head);

  // You can check how the list is represented in the file by using, e.g.,
  // hexdump:
  // $ hexdump linked_list.bin | less
  // Can you recognize the payload and the next references?

  munmap(storage, 4096);
  close(fd);

  return 0;
}