/* aide, Advanced Intrusion Detection Environment

 *

 * Copyright (C) 1999-2002,2005,2006,2010 Rami Lehti,Pablo Virolainen,

 * Richard van den Berg, Hannes von Haugwitz

 * $Header$

 *

 * This program is free software; you can redistribute it and/or

 * modify it under the terms of the GNU General Public License as

 * published by the Free Software Foundation; either version 2 of the

 * License, or (at your option) any later version.

 *

 * This program is distributed in the hope that it will be useful, but

 * WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU

 * General Public License for more details.

 *

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 */

#include "aide.h"

#include <stdlib.h>

#include "list.h"

#include "report.h"

/*for locale support*/

#include "locale-aide.h"

/*for locale support*/

/* list

 * limitations:

 * Only the head knows where the tail is

 * Every item knows where the head is

 * And that is not true anymore. 

 * Now list has header which knows head and tail.

 * Every item knows header.

 */

/* list_sorted_insert()

 * Adds an item in a sorted list:

 *   - The first argument is the head of the list

 *   - The second argument is the data to be added

 *   - The third argument is the function pointer to the compare function to use

 *   - Returns the head of the list

 */

list* list_sorted_insert(list* listp, void* data, int (*compare) (const void*, const void*)) {

    list* newitem=NULL;

    list* curitem=NULL;

    newitem=(list*)malloc(sizeof(list));

    if (newitem==NULL) {

        error(0,"Not enough memory to add a new item to list.\n");

        exit(EXIT_FAILURE);

    }

    if (listp==NULL){

        list_header* header=(list_header*)malloc(sizeof(list_header));

        if (header==NULL){

            error(0,"Not enough memory for list header allocation\n");

            exit(EXIT_FAILURE);

        }

        newitem->data=data;

        newitem->header=header;

        newitem->next=NULL;

        newitem->prev=NULL;

        header->head=newitem;

        header->tail=newitem;

        return newitem;

    } else {

        /* add element in sorted, non-empty list (use insertion sort) */

        curitem = listp->header->head;

        newitem->header=listp->header;

        newitem->data=data;

        if (compare(newitem->data,curitem->data) <= 0) {

            /* new element is the new head */

            listp->header->head=newitem;

            curitem->prev=newitem;

            newitem->next=curitem;

            newitem->prev=NULL;

            return newitem;

        } else {

            /* find position for new element */

            while(compare(newitem->data, curitem->data) > 0 && curitem->next != NULL) {

               curitem=curitem->next;

            }

            if (curitem->next == NULL && compare(newitem->data, curitem->data) > 0) {

                /* new element is the new tail */

                listp->header->tail=newitem;

                curitem->next=newitem;

                newitem->prev=curitem;

                newitem->next=NULL;

            } else {

                /* new element is an inner element */

                curitem->prev->next=newitem;

                newitem->prev=curitem->prev;

                curitem->prev=newitem;

                newitem->next=curitem;

            }

        }

        return listp;

    }

}

/* list_append()

 * append an item to list

 * returns the head

 * The first argument is the head of the list

 * The second argument is the data to be added

 * Returns list head

 */

/* 

 * Some way to handle mallocs failure would be nice.

 */

list* list_append(list* listp,void*data)

{

  list* newitem=NULL;

  newitem=(list*)malloc(sizeof(list));

  if (newitem==NULL) {

    error(0,"Not enough memory to add a new item to list.\n");

    exit(EXIT_FAILURE);

  }

  if(listp==NULL){

    list_header* header=(list_header*)malloc(sizeof(list_header));

    if (header==NULL){

      error(0,"Not enough memory for list header allocation\n");

      exit(EXIT_FAILURE);

    }

    newitem->data=data;

    newitem->header=header;

    newitem->next=NULL;

    newitem->prev=NULL;

    header->head=newitem;

    header->tail=newitem;

    return newitem;

  }else {

    /* We have nonempthy list.

     * add to last

     */

    newitem->prev=listp->header->tail;

    newitem->next=NULL;

    newitem->data=data;

    newitem->header=listp->header;

    listp->header->tail->next=newitem;

    listp->header->tail=newitem;

    return listp;

  }

  /* Not reached */

  return NULL;

}

/*

 * delete_list_item()

 * delete a item from list

 * returns head of a list.

 */

list* list_delete_item(list* item){

  list* r;

  if (item==NULL) {

    error(200,"Tried to remove from empthy list\n");

    return item;

  }

  if (item->header->head==item->header->tail) {

    /*

     * Ollaan poistamassa listan ainoaa alkiota.

     * Tällöin palautetaan NULL

     */

    free(item->header);

    free(item);

    return NULL;

  }

  /* 

   * Nyt meillä on listassa ainakin kaksi alkiota 

   *  

   */

  /* poistetaan listan viimeistä alkiota */

  if (item==item->header->tail){

    r=item->prev;

    item->header->tail=r;

    r->next=NULL;

    r=r->header->head;

    free(item);

    return r;

  }

  /*

   * Poistetaan listan ensimmäinen alkio.

   */  

  if (item==item->header->head) {

    r=item->next;

    item->header->head=r;

    r->prev=NULL;

    r=r->header->head;

    free(item);

    return r;

  }

  r=item->prev;

  item->prev->next=item->next;

  item->next->prev=item->prev;

  free(item);

  r=r->header->head;

  return r;

}