/*---------------------------------------------------------------------------*
  Project:     MEM library
  File:        mem_list.c
  Programmers: Makoto Takano

  Copyright 2005 Nintendo.  All rights reserved.

  These coded instructions, statements, and computer programs contain
  proprietary information of Nintendo of America Inc. and/or Nintendo
  Company Ltd., and are protected by Federal copyright law.  They may
  not be disclosed to third parties or copied or duplicated in any form,
  in whole or in part, without the prior written consent of Nintendo.
 *---------------------------------------------------------------------------*/

#include <revolution.h>
#include <revolution/mem/list.h>

#define OBJ_TO_LINK(list,obj)   ((MEMLink*)(((u32)(obj))+(list)->offset))


/*---------------------------------------------------------------------------*
  Name:         MEMInitList

  Description:  Initializes list structure.

  Arguments:    list :   pointer to list structure.
                offset : Designates the offset internal to the structure of the Link-type
                        member variable that is in the structure you want to connect to the list.
                        This is convenient when using the offsetof macro defined in stddef.h.
                        

  Returns:      None.
 *---------------------------------------------------------------------------*/
void
MEMInitList( MEMList* list, u16 offset )
{
    ASSERT( list != NULL );

    list->headObject = NULL;
    list->tailObject = NULL;
    list->numObjects = 0;
    list->offset     = offset;
}

/*---------------------------------------------------------------------------*
  Name:         SetFirstObject_                                      [static]

  Description:  Adds the first object to the list.

  Arguments:    list :   pointer to list structure.
                object: pointer to the object you want to add to the list.

  Returns:      None.
 *---------------------------------------------------------------------------*/
static void
SetFirstObject_( MEMList* list, void* object )
{
    MEMLink* link;

    ASSERT( list   != NULL );
    ASSERT( object != NULL );

    link = OBJ_TO_LINK(list, object);

    link->nextObject = NULL;
    link->prevObject = NULL;
    list->headObject = object;
    list->tailObject = object;
    list->numObjects++;
}

/*---------------------------------------------------------------------------*
  Name:         MEMAppendListObject

  Description:  Adds object to the end of the list.

  Arguments:    list :   pointer to list structure.
                object: pointer to the object you want to add to the list.

  Returns:      None.
 *---------------------------------------------------------------------------*/
void
MEMAppendListObject( MEMList* list, void* object )
{
    ASSERT( list   != NULL );
    ASSERT( object != NULL );

    if (list->headObject == NULL)
    {
        // When the list is empty.
        SetFirstObject_(list, object);
    }
    else
    {
        MEMLink* link = OBJ_TO_LINK(list, object);

        link->prevObject = list->tailObject;
        link->nextObject = NULL;

        OBJ_TO_LINK(list, list->tailObject)->nextObject = object;
        list->tailObject = object;
        list->numObjects++;
    }
}

/*---------------------------------------------------------------------------*
  Name:         MEMPrependListObject

  Description:  Inserts object at the head of the list.

  Arguments:    list :   pointer to list structure.
                object: pointer to the object you want to add to the list.

  Returns:      None.
 *---------------------------------------------------------------------------*/
void
MEMPrependListObject( MEMList* list, void* object )
{
    ASSERT( list   != NULL );
    ASSERT( object != NULL );

    if (list->headObject == NULL)
    {
        // When the list is empty.
        SetFirstObject_(list, object);
    }
    else
    {
        MEMLink* link = OBJ_TO_LINK(list, object);

        link->prevObject = NULL;
        link->nextObject = list->headObject;

        OBJ_TO_LINK(list, list->headObject)->prevObject = object;
        list->headObject = object;
        list->numObjects++;
    }
}

/*---------------------------------------------------------------------------*
  Name:         MEMInsertListObject

  Description:  Inserts object in the specified location. The object is inserted in front of
                the object specified in target. When the insertion point is not specified
                (when the target is NULL), the object is added to the end of the list.
                

  Arguments:    list :   pointer to list structure.
                target: pointer to object in the position you want to insert.
                object: pointer to the object you want to add to the list.

  Returns:      None.
 *---------------------------------------------------------------------------*/
void
MEMInsertListObject( MEMList* list, void* target, void* object )
{
    ASSERT( list   != NULL );
    ASSERT( object != NULL );

    if (target == NULL)
    {
        // when the target is not specified, same as AppendListObject()
        MEMAppendListObject(list, object);
    }
    else if (target == list->headObject)
    {
        // when target is the head of the list, same as PrependListObject()
        MEMPrependListObject(list, object);
    }
    else
    {
        MEMLink* link    = OBJ_TO_LINK(list, object);
        void* prevObj = OBJ_TO_LINK(list, target)->prevObject;
        MEMLink* prevLnk = OBJ_TO_LINK(list, prevObj);

        link->prevObject    = prevObj;
        link->nextObject    = target;
        prevLnk->nextObject = object;
        OBJ_TO_LINK(list, target)->prevObject = object;
        list->numObjects++;
    }
}

/*---------------------------------------------------------------------------*
  Name:         MEMRemoveListObject

  Description:  Deletes object from the list.

  Arguments:    list :   pointer to list structure.
                object: Pointer to the object you want to delete from the list.

  Returns:      None.
 *---------------------------------------------------------------------------*/
void
MEMRemoveListObject( MEMList* list, void* object )
{
    MEMLink* link;

    ASSERT( list   != NULL );
    ASSERT( object != NULL );

    link = OBJ_TO_LINK(list, object);

    if (link->prevObject == NULL)
    {
        list->headObject = link->nextObject;
    }
    else
    {
        OBJ_TO_LINK(list, link->prevObject)->nextObject = link->nextObject;
    }
    if (link->nextObject == NULL)
    {
        list->tailObject = link->prevObject;
    }
    else
    {
        OBJ_TO_LINK(list, link->nextObject)->prevObject = link->prevObject;
    }
    link->prevObject = NULL;
    link->nextObject = NULL;
    list->numObjects--;
}

/*---------------------------------------------------------------------------*
  Name:         MEMGetNextListObject

  Description:  Returns the object to be linked next after the object specified by 'object.'
                If NULL has been specified for the object, the function returns the object linked to the top of the list.
                

  Arguments:    list :   pointer to list structure.
                object: Pointer to object in list.

  Returns:      Returns a pointer to the next object after the specified object.
                If there is no next object, returns NULL.
 *---------------------------------------------------------------------------*/
void*
MEMGetNextListObject( MEMList* list, void* object )
{
    ASSERT( list != NULL );

    if (object == NULL)
    {
        return list->headObject;
    }
    return OBJ_TO_LINK(list, object)->nextObject;
}

/*---------------------------------------------------------------------------*
  Name:         MEMGetPrevListObject

  Description:  Returns the object linked in front of the object specified by 'object.'
                If NULL has been specified for the object, the function returns the object linked to the bottom of the list.
                

  Arguments:    list :   pointer to list structure.
                object: Pointer to object in list.

  Returns:      Returns a pointer to the previous object before the specified object.
                If there is no object in front, returns NULL.
 *---------------------------------------------------------------------------*/
void*
MEMGetPrevListObject( MEMList* list, void* object )
{
    ASSERT( list != NULL );

    if (object == NULL)
    {
        return list->tailObject;
    }
    return OBJ_TO_LINK(list, object)->prevObject;
}

/*---------------------------------------------------------------------------*
  Name:         MEMGetNthListObject

  Description:  Returns a pointer to the object linked Nth on the list.
                Note that the processing time required is longer the deeper in the list the object being linked appears due to the fact that the list is traversed in order beginning from the top.
                

  Arguments:    index  :  Object index.

  Returns:      Returns pointer to object. NULL is returned if there is no object corresponding to the specified index.
                
 *---------------------------------------------------------------------------*/
void*
MEMGetNthListObject( MEMList* list, u16 index )
{
    int      count  = 0;
    MEMLink* object = NULL;

    ASSERT( list != NULL );

    while ((object = (MEMLink*)MEMGetNextListObject(list, object)) != NULL)
    {
        if (index == count)
        {
            return object;
        }
        count++;
    }
    return NULL;
}

/*---------------------------------------------------------------------------*
  Name:         MEMCountListNode

  Description:  Counts the number of objects on the list. Because it counts the list in order from the beginning,
                it will take time if the list is long.
                

  Arguments:    list :   pointer to list structure.
 
  Returns:      Number of objects on the list.
 *---------------------------------------------------------------------------*/
#if 0
int
MEMCountListNode(MEMList* list)
{
    int   count  = 0;
    Node* object = NULL;

    ASSERT( list != NULL );

    while ((object = GetNextListObject(list, object)) != NULL)
    {
        count++;
    }
    return count;
}
#endif