list.c

3D游戏场景编辑器

/****************************************************************************************/
/*  List.c                                                                              */
/*                                                                                      */
/*  Author:       Jim Mischel                                                           */
/*  Description:  This module implements a fairly simple linked-list API that provides  */
/*                the most common list operations.  See list.h for a function listing.  */
/*                                                                                      */
/*  The contents of this file are subject to the Genesis3D Public License               */
/*  Version 1.01 (the "License"); you may not use this file except in                   */
/*  compliance with the License. You may obtain a copy of the License at                */
/*  http://www.genesis3d.com                                                            */
/*                                                                                      */
/*  Software distributed under the License is distributed on an "AS IS"                 */
/*  basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See                */
/*  the License for the specific language governing rights and limitations              */
/*  under the License.                                                                  */
/*                                                                                      */
/*  The Original Code is Genesis3D, released March 25, 1999.                            */
/*Genesis3D Version 1.1 released November 15, 1999                            */
/*  Copyright (C) 1999 WildTangent, Inc. All Rights Reserved           */
/*                                                                                      */
/*  Prepared for GenEdit-Classic ver. 0.5, Dec. 15, 2000								*/
/****************************************************************************************/
#include "list.h"
#include <malloc.h>
#include <assert.h>
#include <string.h>


typedef struct tag_ListIterator ListNode;
struct tag_ListIterator
{
	ListNode *Next;		// next node in list
	ListNode *Prev;		// previous node in list
	void *Data;			// data being held by the node
};

struct tag_List
{
	ListNode *Head;		// pointer to first node in list
	ListNode *Tail;		// pointer to last node in list (makes appending much faster)
	int nItems;			// number of items in the list
};


List *List_Create
	(
	  void
	)
{
	List *pList;

	pList = (List *)malloc (sizeof (List));
	if (pList != NULL)
	{
		pList->nItems = 0;
		pList->Head = NULL;
		pList->Tail = NULL;
	}
	return pList;
}


// Destroy a list object.
// Deallocates all memory allocated to the list, and sets *ppList to NULL.
// If DestroyFcn is not NULL, the function is called for each item in the list.
void List_Destroy
	(
	  List **ppList,
	  List_DestroyCallback DestroyFcn
	)
{
	List *pList;
	ListNode *p;

	assert (ppList != NULL);
	assert (*ppList != NULL);

	pList = *ppList;
	p = pList->Head;
	while (p != NULL)
	{
		ListNode *pNext;

		pNext = p->Next;
		if (DestroyFcn != NULL)
		{
			DestroyFcn (p->Data);
		}
		free (p);
		--(pList->nItems);
		p = pNext;
	}
	assert (pList->nItems == 0);

	free (*ppList);
	*ppList = NULL;
}


void *List_GetData
	(
	  ListIterator pli
	)
{
	assert (pli != LIST_INVALID_NODE);

	return pli->Data;
}

// List_Insert is a local function that inserts a node between two
// existing nodes.  It handles the head and tail cases specially.
// All insertion functions call this one to do the actual insertion.
// On success, returns an iterator that references the new node.
// Returns NULL on failure
static ListIterator List_Insert
	(
	  List *pList,
	  ListNode *Prev,
	  ListNode *Next,
	  void *pData
	)
{
	ListNode *NewNode;

	#ifndef NDEBUG
	{
		// Verify the links so we know we're not cross-linking the list.
		if (Prev == LIST_INVALID_NODE)
		{
			assert (Next == pList->Head);
		}
		else
		{
			assert (Next == Prev->Next);
		}
		if (Next == LIST_INVALID_NODE)
		{
			assert (Prev == pList->Tail);
		}
		else
		{
			assert (Prev == Next->Prev);
		}
	}
	#endif


	// set up the new node...
	NewNode = malloc (sizeof (ListNode));
	if (NewNode != LIST_INVALID_NODE)
	{
		NewNode->Data = pData;
		NewNode->Prev = Prev;
		NewNode->Next = Next;

		// and connect everything else accordingly

		if (Next == LIST_INVALID_NODE)
		{
			// appending
			assert (Prev == pList->Tail);
			pList->Tail = NewNode;
		}

		if (Prev == LIST_INVALID_NODE)
		{
			// prepending
			assert (Next == pList->Head);
			pList->Head = NewNode;
		}


		if (Prev != LIST_INVALID_NODE)
		{
			Prev->Next = NewNode;
		}
		if (Next != LIST_INVALID_NODE)
		{
			Next->Prev = NewNode;
		}

		// maintain list node count
		++(pList->nItems);
	}
	return NewNode;
}


// Append an item to the list (add to the end)
ListIterator List_Append
	(
	  List *pList,
	  void *pData
	)
{
	assert (pList != NULL);

	return List_Insert (pList, pList->Tail, LIST_INVALID_NODE, pData);
}

// Prepend (add to the front) an item to the list
ListIterator List_Prepend
	(
	  List *pList,
	  void *pData
	)
{
	assert (pList != NULL);

	return List_Insert (pList, LIST_INVALID_NODE, pList->Head, pData);
}


// Insert an item after an existing item.
// *pli references the node after which the data should be inserted,
// and must have been returned by one of the Get functions,
ListIterator List_InsertAfter
	(
	  List *pList,
	  ListIterator pli,
	  void *pData
	)
{
	assert (pList != NULL);
	assert (pli != LIST_INVALID_NODE);

	return List_Insert (pList, pli, pli->Next, pData);
}


// Insert an item before an existing item.
// *pli references the node before which the data should be inserted,
// and must have been returned by one of the Get functions,
ListIterator List_InsertBefore
	(
	  List *pList,
	  ListIterator pli,
	  void *pData
	)
{
	// make sure that *pli is referencing a valid node
	assert (pList != NULL);
	assert (pli != LIST_INVALID_NODE);

	return List_Insert (pList, pli->Prev, pli, pData);
}

// Remove the item referenced by pli.
// If DestroyFcn is not NULL, it will be called with the address of the
// item's data.
geBoolean List_Remove
	(
	  List *pList,
	  ListIterator pli,
	  List_DestroyCallback DestroyFcn
	)
{
	// make sure we're referencing a valid node
	assert (pList != NULL);
	assert (pli != LIST_INVALID_NODE);

	// get rid of the data
	if (DestroyFcn != NULL)
	{
		DestroyFcn (pli->Data);
	}

	// Now unlink it

	if (pList->Head == pli)
	{
		// then this better be the first node
		assert (pli->Prev == LIST_INVALID_NODE);
		pList->Head = pli->Next;
	}
	else
	{
		assert (pli->Prev != LIST_INVALID_NODE);
		pli->Prev->Next = pli->Next;
	}

	if (pList->Tail == pli)
	{
		// then this better be the last node
		assert (pli->Next == LIST_INVALID_NODE);
		pList->Tail = pli->Prev;
	}
	else
	{
		assert (pli->Next != LIST_INVALID_NODE);

		pli->Next->Prev = pli->Prev;
	}

	// and deallocate the node
	free (pli);

	--(pList->nItems);

	return GE_TRUE;
}

// Return a pointer to the first node's data.
// *pli is initialized here to reference the first node.
void *List_GetFirst
	(
	  List *pList,
	  ListIterator *pli
	)
{
    assert (pList != NULL);
    assert (pli != NULL);

    *pli = pList->Head;
    if (*pli != LIST_INVALID_NODE)
    {
        return (*pli)->Data;
    }
    else
    {
        return NULL;
    }
}

// Return a pointer to the item following the node referenced by pli.
// *pli is updated to reference the new node.
#pragma warning (disable: 4100)
void *List_GetNext
	(
	  List *pList,
	  ListIterator *pli
	)
{
    assert (pList != NULL);
	// make sure that pli is referencing a valid node.
    assert (pli != NULL);
    assert (*pli != LIST_INVALID_NODE);

	*pli = (*pli)->Next;
    if (*pli == LIST_INVALID_NODE)
    {
        return LIST_INVALID_NODE;
    }
    else
    {
        return (*pli)->Data;
    }
}
#pragma warning (default: 4100)

// Return a pointer to the last node's data.
// *pli is initialized here to reference the last node.
void *List_GetLast
	(
	  List *pList,
	  ListIterator *pli
	)
{
    *pli = pList->Tail;
    if (*pli != LIST_INVALID_NODE)
    {
        return (*pli)->Data;
    }
    else
    {
        return NULL;
    }
}

// Return a pointer to the item preceding the node referenced by pli.
// *pli is updated to reference the new node.
#pragma warning (disable: 4100)
void *List_GetPrev
	(
	  List *pList,
	  ListIterator *pli
	)
{
    assert (pList != NULL);

	// make sure that pli is referencing a valid node
    assert (pli != NULL);
    assert (*pli != LIST_INVALID_NODE);

    *pli = (*pli)->Prev;
    if (*pli == LIST_INVALID_NODE)
    {
        return LIST_INVALID_NODE;
    }
    else
    {
        return (*pli)->Data;
    }
}
#pragma warning (default: 4100)

// return number of items in list.
int List_GetNumItems
	(
	  const List *pList
	)
{
    assert (pList != NULL);
	assert (pList->nItems >= 0);	// if it's < 0, then something really bad happened
    
	#ifndef NDEBUG
    {
		ListNode *pNode;
		int Count;

		Count = 0;
		pNode = pList->Head;
		while (pNode != LIST_INVALID_NODE)
		{
			++Count;
			pNode = pNode->Next;
		}
        assert (Count == pList->nItems);
    }
    #endif

    return pList->nItems;
}


// Call the CallbackFcn for each item in the list.
// CallbackFcn will be called with each list item's data, and lParam.
// lParam is a pointer to a user-defined data block.
int List_ForEach
	(
	  List *pList,
	  List_ForEachCallback CallbackFcn,
	  void *lParam
	)
{
    ListIterator li;
    void *pData;

    assert (pList != NULL);
    assert (CallbackFcn != NULL);

    pData = List_GetFirst (pList, &li);
    while (pData != NULL)
    {
        CallbackFcn (pData, lParam);
        pData = List_GetNext (pList, &li);
    }
    return 0;
}