/* 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;
}