/******************************************************************************
 * Example solution to lab00. Mattias Eriksson.                               *
 * See the pintos lib/kernel/list.[ch] for a much more general linked list    * 
 ******************************************************************************/


#include <stdio.h>

struct list_item {
  int value;
  struct list_item * next;
};

/* puts x at the end of the list */
void append(struct list_item *first, int x)
{
  struct list_item * nit = (struct list_item *)malloc(sizeof(struct list_item));
  nit->next = NULL;
  nit->value = x;

  /* Find the spot */
  while(first->next != NULL){
    first = first->next;
  }
  
  first->next = nit;
}

 /* puts x at the beginning of the list */
void prepend(struct list_item *first, int x)
{
  struct list_item * nit = (struct list_item *)malloc(sizeof(struct list_item));
  nit->next = first->next;
  nit->value = x;
  first->next = nit;
}

/* prints all elements in the list */
void print(struct list_item *first){
  first = first->next; /* Ignore first entry */
  while(first != NULL){
    printf("%d, ", first->value);
    first = first->next;
  }
  printf("\n");
}

/* input_sorted: find the first element in the list larger than x
   and input x right before that element */
void input_sorted(struct list_item *first, int x)
{
  struct list_item * nit = (struct list_item *)malloc(sizeof(struct list_item));
  nit->value = x;

  /* Find the spot */
  while(first->next != NULL){
    if(first->next->value > x){
      break; /* exit the loop and insert before first->next */
    }
    first = first->next;
  }
  
  nit->next = first->next;
  first->next = nit;
}

/* free everything dynamically allocated */
void destroy(struct list_item *first)
{
  struct list_item *tmp, *next_to_del; /* Temporary pointers */
  tmp = first->next; /* Ignore first */
  first->next = NULL; /* Make the list look empty */

  while(tmp != NULL){
    next_to_del = tmp->next; /* Store pointer before freeing! */
    free(tmp);
    tmp = next_to_del;
  }
}

int main( int argc, char ** argv)
{
  int i;
  struct list_item root;
  root.value = -1; /* This value is always ignored */
  root.next = NULL;
  
  /* Let's test it! */
  append(&root,5);
  append(&root,17);
  prepend(&root,1);
  input_sorted(&root, 6);
  print(&root);
  destroy(&root);

  for(i=100; i>=0; i-=15){
    input_sorted(&root, i);
  }
  for(i=100; i>=0; i-=10){
    input_sorted(&root, i);
  }

  print(&root);
  destroy(&root);
}