/*
 * Sorted doubly loop-linked list. Used to implement many cache designs.
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "common.h"


#define INIT_KEY   0


NODE_TYPE *create_a_new_node()
{
    NODE_TYPE *p;

    p = (NODE_TYPE *) malloc(sizeof(NODE_TYPE));
    IF_OUT_OF_MEM( p, "creating a new node" );

    p->primary_key   = INIT_KEY;
    p->secondary_key = INIT_KEY;
    p->previous      = NULL;
    p->next          = NULL;

    p->hash_index    = INVALID_TAG;
    p->object.server = INVALID_TAG;
    p->object.path   = INVALID_TAG;
    p->size          = INVALID_TAG;
    p->frequency     = INVALID_TAG;
    p->time          = INVALID_TAG;

    return (p);
}

void init_sorted_list(NODE_TYPE **head)
{
    if ( (*head) != NULL ) {
        ERROR_LOG("\ninit_sorted_list: Should not initialize sorted list for ");
        ERROR_LOG("a non-NULL head pointor! Exit!\n\n");
        exit(-1);
    }

    (*head) = create_a_new_node();
    (*head)->previous = (*head);
    (*head)->next     = (*head);
}

static INT compare(NODE_TYPE *node1, NODE_TYPE *node2)
{

#ifdef MAKE_SURE
    if ( (node1==NULL) || (node2==NULL) ) {
        ERROR_LOG("\ncompare: one or both of the nodes is NULL! Exit!\n\n");
        exit(-1);
    }
#endif

    if (node1->primary_key != node2->primary_key) {
        return (node1->primary_key - node2->primary_key);
    }
    else {
        return (node1->secondary_key - node2->secondary_key);
    }
}

void add_node_into_sorted_list(NODE_TYPE *head, NODE_TYPE *new_node)
{
    NODE_TYPE *p;

#ifdef MAKE_SURE

    if (head == NULL) {
        ERROR_LOG("\nadd_node_into_sorted_list: The head is NULL! Exit!\n\n");
        exit(-1);
    }
    if ((new_node==NULL)||(new_node->previous!=NULL)||(new_node->next!=NULL)) {
        ERROR_LOG("\nadd_node_into_sorted_list: The new node head is NULL, ");
        ERROR_LOG("or its previous/next pointer is NOT NULL! Exit!\n\n");
        exit(-1);
    }

    /* make sure the new_node is not already in the list */
    p = head->next;
    while (p != head) {
        if ( p == new_node ) {
            ERROR_LOG("\nadd_node_into_sorted_list: The node you want to add ");
            ERROR_LOG("to the list is already in the list! Exit!\n");
            fprintf(stderr, "The node's key is: ( %lld , %lld )\n\n",
                    new_node->primary_key, new_node->secondary_key);
            exit(-1);
        }
        else {
            p = p->next;
        }
    }

#endif

    /* find the position where the new_node shall be put */
    p = head;
    while (p->next != head) {
        if ( compare(p->next, new_node) > 0 ) {
            p = p->next;
        }
        else {
            break;
        }
    }
    
    /* insert the new_node into the list */
    new_node->previous = p;
    new_node->next     = p->next;
    p->next->previous  = new_node;
    p->next            = new_node; /* this assignment must be the last one! */
}

void remove_node_from_sorted_list(NODE_TYPE *head, NODE_TYPE *node)
{
    NODE_TYPE *p;

#ifdef MAKE_SURE

    if ( (head==NULL) || (node==NULL) ) {
        ERROR_LOG("\nremove_node_from_sorted_list: The head or the specified ");
        ERROR_LOG("node is NULL! Exit!\n\n");
        exit(-1);
    }

    /* make sure the "node" is in the sorted list */
    p = head;
    while ( (p->next!=head) && (p->next!=node) ) {
        p = p->next;
    }
    if (p->next == head) {
        ERROR_LOG("\nremove_node_from_sorted_list: The node you want to ");
        ERROR_LOG("remove is not in this sorted list! Exit!\n\n");
        exit(-1);
    }
    else {
        p->next = node->next;
        node->next->previous = p;

        node->previous = NULL;
        node->next     = NULL;
    }

#else

    p = node->previous;
    p->next = node->next;
    node->next->previous = p;
    node->previous = NULL;
    node->next     = NULL;

#endif

}

NODE_TYPE *remove_last_node_from_sorted_list(NODE_TYPE *head)
{
    NODE_TYPE *p;

#ifdef MAKE_SURE

    if (head == NULL) {
        ERROR_LOG("\nremove_last_node_from_sorted_list: The head of the list ");
        ERROR_LOG("is NULL! Exit!\n\n");
        exit(-1);
    }

#endif

    p = head->previous;
    if (p == head) {
        ERROR_LOG("\nremove_last_node_from_sorted_list: The sorted list is ");
        ERROR_LOG("empty, so no last node to remove! Exit!\n\n");
        exit(-1);
    }
    else {
        p->previous->next = p->next;
        p->next->previous = p->previous;

        p->previous = NULL;
        p->next     = NULL;

        return (p);
    }
}

INT release_sorted_list(NODE_TYPE **head)
{
    INT num;
    NODE_TYPE *p;

    if ( (*head)==NULL ) {
       return(0);
    }

    num = 0;
    p = (*head)->previous;
    while (p != (*head) ) {
        (*head)->previous = p->previous;
        free(p);
        num++;
        p = (*head)->previous;
    }
    free(*head);
    (*head) = NULL;

    return (num);
}

void print_sorted_list(NODE_TYPE *head)
{
    INT i;
    NODE_TYPE *p;

    if (head == NULL) {
        ERROR_LOG("\nprint_sorted_list: The head of the list is NULL! Exit!\n");
        exit(-1);
    }

    printf("\nNodes in this sorted list:\n");
    i = 1;
    p = head->next;
    while (p != head) {
        printf("%9lld: [%lld] (%lld, %lld, %lld) (%lld,%lld)\n",i,p->hash_index,
               p->object.server, p->object.path, p->size,
               p->primary_key,   p->secondary_key );
        p = p->next;
        i++;
    }
    printf("\n");
}


/* #define TEST */
#ifdef TEST

main()
{
    INT i;
    NODE_TYPE *head1, *p;
    
    head1 = NULL;
    init_sorted_list(&head1);
    
    for (i=0; i<10; i++) {
        p = create_a_new_node();
        p->primary_key   = 0;
        p->secondary_key = i;
        add_node_into_sorted_list(head1, p);
    }
    
    print_sorted_list(head1);
    
    remove_node_from_sorted_list(head1, p);
    print_sorted_list(head1);
    
    p = remove_last_node_from_sorted_list(head1);
    print_sorted_list(head1);
    
    add_node_into_sorted_list(head1, p);
    print_sorted_list(head1);
    
    release_sorted_list(&head1);
    print_sorted_list(head1);
}

#endif

