/*

 * list.c: lists handling implementation

 *

 * Copyright (C) 2000 Gary Pennington and Daniel Veillard.

 *

 * Permission to use, copy, modify, and distribute this software for any

 * purpose with or without fee is hereby granted, provided that the above

 * copyright notice and this permission notice appear in all copies.

 *

 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED

 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF

 * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND

 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.

 *

 * Author: Gary.Pennington@uk.sun.com

 */

#define IN_LIBXML

#include "XmlEnglibxml.h"

#include <stdlib.h>

#include <string.h>

//#include "Libxml2_xmlmemory.h"

//#include "Libxml2_list.h"

#include "Libxml2_globals.h"

/*

 * Type definition are kept internal

 */

struct _xmlLink

{

    struct _xmlLink *next;

    struct _xmlLink *prev;

    void *data;

};

struct _xmlList

{

    xmlLinkPtr sentinel;

    void (*linkDeallocator)(xmlLinkPtr );

    int (*linkCompare)(const void *, const void*);

};

/************************************************************************

 *                                    *

 *                Interfaces                *

 *                                    *

 ************************************************************************/

/**

 * xmlLinkDeallocator:

 * @l:  a list

 * @lk:  a link

 *

 * Unlink and deallocate @lk from list @l

 */

static void

xmlLinkDeallocator(xmlListPtr l, xmlLinkPtr lk)

{

    (lk->prev)->next = lk->next;

    (lk->next)->prev = lk->prev;

    if(l->linkDeallocator)

        l->linkDeallocator(lk);

    xmlFree(lk);

}

/**

 * xmlLinkCompare:

 * @data0:  first data

 * @data1:  second data

 *

 * Compares two arbitrary data

 *

 * Returns -1, 0 or 1 depending on whether data1 is greater equal or smaller

 *          than data0

 */

static int

xmlLinkCompare(const void *data0, const void *data1)

{

    if (data0 < data1)

        return (-1);

    else if (data0 == data1)

	return (0);

    return (1);

}

/**

 * xmlListLowerSearch:

 * @l:  a list

 * @data:  a data

 *

 * Search data in the ordered list walking from the beginning

 *

 * Returns the link containing the data or NULL

 */

static xmlLinkPtr 

xmlListLowerSearch(xmlListPtr l, void *data) 

{

    xmlLinkPtr lk;

    for(lk = l->sentinel->next;lk != l->sentinel && l->linkCompare(lk->data, data) <0 ;lk = lk->next)

    {

    	//empty

    }

    return lk;    

}

/**

 * xmlListHigherSearch:

 * @l:  a list

 * @data:  a data

 *

 * Search data in the ordered list walking backward from the end

 *

 * Returns the link containing the data or NULL

 */

static xmlLinkPtr 

xmlListHigherSearch(xmlListPtr l, void *data) 

{

    xmlLinkPtr lk;

    for(lk = l->sentinel->prev;lk != l->sentinel && l->linkCompare(lk->data, data) >0 ;lk = lk->prev)

    {

    	//empty

    }

    return lk;    

}

/**

 * xmlListSearch:

 * @l:  a list

 * @data:  a data

 *

 * Search data in the list

 *

 * Returns the link containing the data or NULL

 */

static xmlLinkPtr 

xmlListLinkSearch(xmlListPtr l, void *data) 

{

    xmlLinkPtr lk;

    lk = xmlListLowerSearch(l, data);

    if (lk == l->sentinel)

        return NULL;

    else {

        if (l->linkCompare(lk->data, data) ==0)

            return lk;

        return NULL;

    }

}

/**

 * xmlListLinkReverseSearch:

 * @l:  a list

 * @data:  a data

 *

 * Search data in the list processing backward

 *

 * Returns the link containing the data or NULL

 */

static xmlLinkPtr 

xmlListLinkReverseSearch(xmlListPtr l, void *data) 

{

    xmlLinkPtr lk;

    lk = xmlListHigherSearch(l, data);

    if (lk == l->sentinel)

        return NULL;

    else {

        if (l->linkCompare(lk->data, data) ==0)

            return lk;

        return NULL;

    }

}

/**

 * xmlListCreate:

 * @deallocator:  an optional deallocator function

 * @compare:  an optional comparison function

 *

 * Create a new list

 *

 * Returns the new list or NULL in case of error

 */

xmlListPtr

xmlListCreate(xmlListDeallocator deallocator, xmlListDataCompare compare)

{

    xmlListPtr l;

    if (NULL == (l = (xmlListPtr )xmlMalloc( sizeof(xmlList)))) {

        xmlGenericError(xmlGenericErrorContext, 

		        EMBED_ERRTXT("Cannot initialize memory for list"));

        return (NULL);

    }

    /* Initialize the list to NULL */

    memset(l, 0, sizeof(xmlList));

    /* Add the sentinel */

    if (NULL ==(l->sentinel = (xmlLinkPtr )xmlMalloc(sizeof(xmlLink)))) {

        xmlGenericError(xmlGenericErrorContext, 

		        EMBED_ERRTXT("Cannot initialize memory for sentinel"));

	xmlFree(l);

        return (NULL);

    }

    l->sentinel->next = l->sentinel;

    l->sentinel->prev = l->sentinel;

    l->sentinel->data = NULL;

    /* If there is a link deallocator, use it */

    if (deallocator != NULL)

        l->linkDeallocator = deallocator;

    /* If there is a link comparator, use it */

    if (compare != NULL)

        l->linkCompare = compare;

    else /* Use our own */

        l->linkCompare = xmlLinkCompare;

    return l;

}

/**

 * xmlListInsert:

 * @l:  a list

 * @data:  the data

 *

 * Insert data in the ordered list at the beginning for this value

 *

 * Returns 0 in case of success, 1 in case of failure

 */

int

xmlListInsert(xmlListPtr l, void *data) 

{

    xmlLinkPtr lkPlace, lkNew;

    lkPlace = xmlListLowerSearch(l, data);

    /* Add the new link */

    lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));

    if (lkNew == NULL) {

        xmlGenericError(xmlGenericErrorContext, 

		        EMBED_ERRTXT("Cannot initialize memory for new link"));

        return (1);

    }

    lkNew->data = data;

    lkPlace = lkPlace->prev;

    lkNew->next = lkPlace->next;

    (lkPlace->next)->prev = lkNew;

    lkPlace->next = lkNew;

    lkNew->prev = lkPlace;

    return 0;

}

/**

 * xmlListAppend:

 * @l:  a list

 * @data:  the data

 *

 * Insert data in the ordered list at the end for this value

 *

 * Returns 0 in case of success, 1 in case of failure

 */

int xmlListAppend(xmlListPtr l, void *data) 

{

    xmlLinkPtr lkPlace, lkNew;

    lkPlace = xmlListHigherSearch(l, data);

    /* Add the new link */

    lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));

    if (lkNew == NULL) {

        xmlGenericError(xmlGenericErrorContext, 

		        EMBED_ERRTXT("Cannot initialize memory for new link"));

        return (0);

    }

    lkNew->data = data;

    lkNew->next = lkPlace->next;

    (lkPlace->next)->prev = lkNew;

    lkPlace->next = lkNew;

    lkNew->prev = lkPlace;

    return 1;

}

/**

 * xmlListDelete:

 * @l:  a list

 *

 * Deletes the list and its associated data

 */

void xmlListDelete(xmlListPtr l)

{

    xmlListClear(l);

    xmlFree(l->sentinel);

    xmlFree(l);

}

/**

 * xmlListRemoveFirst:

 * @l:  a list

 * @data:  list data

 *

 * Remove the first instance associated to data in the list

 *

 * Returns 1 if a deallocation occured, or 0 if not found

 */

int

xmlListRemoveFirst(xmlListPtr l, void *data)

{

    xmlLinkPtr lk;

    /*Find the first instance of this data */

    lk = xmlListLinkSearch(l, data);

    if (lk != NULL) {

        xmlLinkDeallocator(l, lk);

        return 1;

    }

    return 0;

}

/**

 * xmlListClear:

 * @l:  a list

 *

 * Remove the all data in the list

 */

void

xmlListClear(xmlListPtr l)

{

    xmlLinkPtr  lk = l->sentinel->next;

    while(lk != l->sentinel) {

        xmlLinkPtr next = lk->next;

        xmlLinkDeallocator(l, lk);

        lk = next;

    }

}

/**

 * xmlListEmpty:

 * @l:  a list

 *

 * Is the list empty ?

 *

 * Returns 1 if the list is empty, 0 otherwise

 */

int

xmlListEmpty(xmlListPtr l)

{

    return (l->sentinel->next == l->sentinel);

}

/**

 * xmlListFront:

 * @l:  a list

 *

 * Get the first element in the list

 *

 * Returns the first element in the list, or NULL

 */

xmlLinkPtr 

xmlListFront(xmlListPtr l)

{

    return (l->sentinel->next);

}

/**

 * xmlListSearch:

 * @l:  a list

 * @data:  a search value

 *

 * Search the list for an existing value of @data

 *

 * Returns the value associated to @data or NULL in case of error

 */

void *

xmlListSearch(xmlListPtr l, void *data) 

{

    xmlLinkPtr lk;

    lk = xmlListLinkSearch(l, data);

    if (lk)

        return (lk->data);

    return NULL;

}

#ifndef XMLENGINE_EXCLUDE_UNUSED

/**

 * xmlListReverseSearch:

 * @l:  a list

 * @data:  a search value

 *

 * Search the list in reverse order for an existing value of @data

 *

 * Returns the value associated to @data or NULL in case of error

 */

void *

xmlListReverseSearch(xmlListPtr l, void *data) 

{

    xmlLinkPtr lk;

    lk = xmlListLinkReverseSearch(l, data);

    if (lk)

        return (lk->data);

    return NULL;

}

/**

 * xmlListRemoveLast:

 * @l:  a list

 * @data:  list data

 *

 * Remove the last instance associated to data in the list

 *

 * Returns 1 if a deallocation occured, or 0 if not found

 */

int

xmlListRemoveLast(xmlListPtr l, void *data)

{

    xmlLinkPtr lk;

    /*Find the last instance of this data */

    lk = xmlListLinkReverseSearch(l, data);

    if (lk != NULL) {

	xmlLinkDeallocator(l, lk);

        return 1;

    }

    return 0;

}

/**

 * xmlListRemoveAll:

 * @l:  a list

 * @data:  list data

 *

 * Remove the all instance associated to data in the list

 *

 * Returns the number of deallocation, or 0 if not found

 */

int

xmlListRemoveAll(xmlListPtr l, void *data)

{

    int count=0;

    while(xmlListRemoveFirst(l, data))

        count++;

    return count;

}

/**

 * xmlListEnd:

 * @l:  a list

 *

 * Get the last element in the list

 *

 * Returns the last element in the list, or NULL

 */

xmlLinkPtr 

xmlListEnd(xmlListPtr l)

{

    return (l->sentinel->prev);

}

/**

 * xmlListPopBack:

 * @l:  a list

 *

 * Removes the last element in the list

 */

void

xmlListPopBack(xmlListPtr l)

{

    if(!xmlListEmpty(l))

        xmlLinkDeallocator(l, l->sentinel->prev);

}

/**

 * xmlListPushBack:

 * @l:  a list

 * @data:  new data

 *

 * add the new data at the end of the list

 *

 * Returns 1 if successful, 0 otherwise

 */

int

xmlListPushBack(xmlListPtr l, void *data) 

{

    xmlLinkPtr lkPlace, lkNew;

    lkPlace = l->sentinel->prev;

    /* Add the new link */

    if (NULL ==(lkNew = (xmlLinkPtr )xmlMalloc(sizeof(xmlLink)))) {

        xmlGenericError(xmlGenericErrorContext, 

		        EMBED_ERRTXT("Cannot initialize memory for new link"));

        return (0);

    }

    lkNew->data = data;

    lkNew->next = lkPlace->next;

    (lkPlace->next)->prev = lkNew;

    lkPlace->next = lkNew;

    lkNew->prev = lkPlace;

    return 1;

}

/**

 * xmlListReverse:

 * @l:  a list

 *

 * Reverse the order of the elements in the list

 */

void

xmlListReverse(xmlListPtr l) {

  xmlLinkPtr lk;

  xmlLinkPtr lkPrev = l->sentinel;

  for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next) {

    lkPrev->next = lkPrev->prev;

    lkPrev->prev = lk;

    lkPrev = lk;

  }

  /* Fix up the last node */

  lkPrev->next = lkPrev->prev;

  lkPrev->prev = lk;

}

/**

 * xmlListSort:

 * @l:  a list