#include <stdio.h>
#include <stdlib.h>
#include "list.h"

//
// Define a data structure that contains a list_head
//

typedef struct queue_s {
  struct list_head next;
  int data;
} queue_t;

//
// Define a list of structures
//

struct list_head request_q;

//
// Add an element to the end of the list, so it will be the last one popped
//

queue_t * queue_add_fifo(int data) 
{
  queue_t * next;

  next = (queue_t *) malloc(sizeof(queue_t));
  next->data = data;
  
  //
  //  Add to the tail for FIFO queueing
  //

  list_add_tail(&next->next, &request_q );

  return(next);
}

//
// Add an element to the head of the list, so it will be the next one popped
//

queue_t * queue_add_lifo(int data) 
{
  queue_t * next;

  next = (queue_t *) malloc(sizeof(queue_t));
  next->data = data;
  
  //
  //  Add to the head for LIFO (stack) queueing
  //

  list_add(&next->next, &request_q );

  return(next);
}

//
// Pop an element off the head of the queue
//

queue_t * queue_pop(void)
{
  //
  // Check if the queue is empty
  //
  if (!list_empty(&request_q)) {
    queue_t * next;
    
    // 
    // Get the first entry on the list. This is the one that request_q.next points to.
    // 
    next = list_entry(request_q.next,queue_t,next);
    list_del(&next->next);
    return(next);
  } else {
    return(NULL);
  }
}

//
// Pop an element off the tail of the queue
//

queue_t * queue_pop_tail(void)
{
  //
  // Check if the queue is empty
  //
  if (!list_empty(&request_q)) {
    queue_t * next;
    
    // 
    // Get the last entry on the list. This is the one that request_q.prev points to.
    // 
    next = list_entry(request_q.prev,queue_t,next);
    list_del(&next->next);
    return(next);
  } else {
    return(NULL);
  }
}

//
// Find the first entry in the list with a matching data value
//

queue_t * find_queue_entry(int data) 
{
  struct list_head * next;

  //
  // Iterate over the list
  //

  list_for_each(next, &request_q) {
    queue_t * elem;

    //
    // Get a pointer to the element on the list
    //
    elem = list_entry(next, queue_t, next);
    if (elem->data == data) {
      return(elem);
    }
  }
  return(NULL);
    
}

//
// Delete all entries from the queue that match the data value
//
void del_queue_entry(int data) 
{
  struct list_head * next;
  struct list_head * temp;

  //
  // Iterate over the list. We need to use the safe iterator because we may want to 
  // remove things.
  //

  list_for_each_safe(next, temp, &request_q) {
    queue_t * elem;

    //
    // Get a pointer to the element on the list
    //
    elem = list_entry(next, queue_t, next);
    
    //
    // Delete the element if the data field matches
    //

    if (elem->data == data) {
      list_del(&elem->next);
    }
  }
    
}

void print_queue(void) 
{
  struct list_head * next;

  //
  // Iterate over the list
  //

  printf("Queue:\n");
  list_for_each(next, &request_q) {
    queue_t * elem;

    //
    // Get a pointer to the element on the list
    //

    elem = list_entry(next, queue_t, next);

    printf("\t%d\n",elem->data);
  }

}

int main(int argc, char * argv[])
{
    INIT_LIST_HEAD(&request_q);
    queue_t * elem;

    queue_add_fifo(1);
    queue_add_fifo(2);
    queue_add_fifo(3);
    queue_add_fifo(4);
    queue_add_fifo(5);

    printf("Should be 1,2,3,4,5\n");
    print_queue(); 
    
    elem =queue_pop(); // should be 1

    printf("Should be 1: %d\n",elem->data);
    
    elem = queue_pop_tail();

    printf("Should be 5: %d\n",elem->data);
    
    printf("Should be 2,3,4\n");
    print_queue(); 

    queue_pop();
    queue_pop();
    queue_pop();

    printf("Should be empty\n");
    print_queue();

    queue_add_lifo(10);
    queue_add_lifo(20);
    queue_add_lifo(30);
    queue_add_lifo(40);

    printf("Should be 40,30,20,10\n");
    print_queue();

    elem = find_queue_entry(20);
    printf("Should be non-NULL: %p\n",elem);

    elem = find_queue_entry(50);
    printf("Should be NULL: %p\n",elem);

    del_queue_entry(20);
    
    printf("Should be 40,30,10\n");
    print_queue();

    del_queue_entry(40);
    del_queue_entry(10);
    del_queue_entry(30);
    
    printf("Should be empty\n");
    print_queue();


}