list.h

Go to the documentation of this file.

#ifndef LIST_H
#define LIST_H

/****************************************************************************************/
/*  List                                                                                */
/*                                                                                      */
/*  Author: Charles Bloom                                                               */
/*  Description: List/Link/Node Primitives                                              */
/*                                                                                      */
/*  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           */
/*                                                                                      */
/****************************************************************************************/

#include "basetype.h"

#ifdef __cplusplus
extern "C" {
#endif

#define LISTCALL        __fastcall

/*******************************************/
geBoolean List_Start(void);
geBoolean List_Stop(void);

/*******************************************/
typedef struct List List;

extern List *   LISTCALL List_Create(void);
extern void             LISTCALL List_Destroy(List * pList);
extern List *   LISTCALL List_AddTail(List *pList,void * Data);
extern List *   LISTCALL List_AddHead(List *pList,void * Data);
        // returns a pointer to the node created
extern void *   LISTCALL List_CutHead(List *pList);
extern void *   LISTCALL List_CutTail(List *pList);
extern void *   LISTCALL List_PeekHead(List *pList);
extern void *   LISTCALL List_PeekTail(List *pList);

extern List *   LISTCALL List_Next(List *pNode);
extern List *   LISTCALL List_Prev(List *pNode);

extern void             LISTCALL List_CutNode(List *pNode);
extern void             LISTCALL List_DeleteNode(List *pNode);
extern void             LISTCALL List_FreeNode(List *pNode);
extern void *   LISTCALL List_NodeData(List *pNode);

extern List *   List_Find(List *pList,void *Data);

/****

        Iterate on a list via :

        List *pNode,*pList;
        for( pNode = List_Next(pList); pNode != pList; pNode = List_Next(pNode) )
        {
                //do stuff to pNode
        }

****/

typedef struct Stack Stack;

extern Stack *  LISTCALL Stack_Create(void);
extern void     LISTCALL Stack_Destroy(Stack * pStack);
extern void     LISTCALL Stack_Push_Func(Stack *pStack,void * Data);
extern void *   LISTCALL Stack_Pop_Func(Stack *pStack);
extern int              LISTCALL Stack_Extend(Stack *pStack);   // returns new length

#ifdef _DEBUG

#define Stack_Push      Stack_Push_Func
#define Stack_Pop       Stack_Pop_Func

#else

// this struct is exposed only in release mode!
// don't look into it!

struct Stack
{
        void ** Buffer, **End;
        void ** Head;
        int members;
};

//#define Stack_Push(pStack,Data)       do { *((pStack)->Head)++ = (void *)(Data); if ( (pStack)->Head == (pStack)->End ) Stack_Extend(pStack); } while(0)
#define Stack_Push(pStack,Data) *((pStack)->Head)++ = (void *)(Data), ( (pStack)->Head != (pStack)->End ) || Stack_Extend(pStack)
#define Stack_Pop(pStack)               ( ((pStack)->Head == (pStack)->Buffer) ? NULL : *( -- ((pStack)->Head) ) )

#endif

typedef struct Link Link;

extern Link *   LISTCALL Link_Create(void);
extern void             LISTCALL Link_Destroy(Link * pLink);
extern void             LISTCALL Link_Push(Link *pLink,void * Data);
extern void *   LISTCALL Link_Pop(Link *pLink);
extern void *   LISTCALL Link_Peek(Link *pLink);

typedef struct LinkNode LinkNode;

/************************************/
/*** a radix of each type ****/

typedef struct RadixList RadixList;

extern RadixList * RadixList_Create(int RadixListMax);
extern void RadixList_Destroy(RadixList * pRadixList);
extern List * RadixList_Add(RadixList *pRadixList,void * Data,int Key);
        // returns a pointer to the node created
extern void * RadixList_CutMax(RadixList *pRadixList,int * pMaxKey);
extern void * RadixList_CutMin(RadixList *pRadixList,int * pMinKey);
extern void * RadixList_CutKey(RadixList *pRadixList,int Key);

typedef struct RadixLN RadixLN;

extern RadixLN * RadixLN_Create(int RadixLNMax);
extern void RadixLN_Destroy(RadixLN * pRadixLN);
extern void RadixLN_AddTail(RadixLN *pRadixLN,LinkNode * LN,int Key);
extern void RadixLN_AddHead(RadixLN *pRadixLN,LinkNode * LN,int Key);
extern LinkNode * RadixLN_CutMax(RadixLN *pRadixLN,int * pMaxKey);
extern LinkNode * RadixLN_CutMin(RadixLN *pRadixLN,int * pMinKey);
extern LinkNode * RadixLN_CutKey(RadixLN *pRadixLN,int Key);
extern LinkNode * RadixLN_PeekMax(RadixLN *pRadixLN,int * pMaxKey);
extern LinkNode * RadixLN_PeekMin(RadixLN *pRadixLN,int * pMinKey);

typedef struct RadixLink RadixLink;

extern                  RadixLink * RadixLink_Create(int RadixLinkMax);
extern void             RadixLink_Destroy(RadixLink * pRadixLink);
extern void             RadixLink_Add(RadixLink *pRadixLink,void * Data,int Key);
extern void *   RadixLink_CutMax(RadixLink *pRadixLink,int * pMaxKey);
extern void *   RadixLink_CutMin(RadixLink *pRadixLink,int * pMinKey);
extern void *   RadixLink_CutKey(RadixLink *pRadixLink,int Key);
extern void             RadixLink_Grow(RadixLink *pRadixLink,int NewMax);

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

typedef struct Hash Hash;
typedef struct HashNode HashNode;

extern Hash *   Hash_Create(void);
extern void             Hash_Destroy(Hash *pHash);
HashNode *      LISTCALL Hash_Add(Hash *pHash,uint32 Key,uint32 Data);
void            LISTCALL Hash_DeleteNode(Hash *pHash,HashNode *pNode);
HashNode *      LISTCALL Hash_Get(Hash *pHash,uint32 Key,uint32 *pData);
                                                        // pdata is optional
HashNode *      LISTCALL Hash_WalkNext(Hash *pHash,HashNode *pCur);
                                                        //use pCur == NULL to start walking

uint32          LISTCALL Hash_NumMembers(Hash *pHash);

void    HashNode_SetData(HashNode *pNode,uint32 Data);
void    HashNode_GetData(HashNode *pNode,uint32 *pKey,uint32 *pData);
uint32  HashNode_Key(HashNode *pNode);
uint32  HashNode_Data(HashNode *pNode);

uint32  Hash_StringToKey(const char * String);

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

struct LinkNode 
{
        LinkNode *Next,*Prev;
}; 

#define zLN_InitList(List)                      do { (List)->Next = List; (List)->Prev = List; } while(0)
#define zLN_Cut(Node)                           do { (Node)->Prev->Next = (Node)->Next; (Node)->Next->Prev = (Node)->Prev; zLN_InitList(Node); } while(0)
#define zLN_Fix(Node)                           do { (Node)->Prev->Next = Node; (Node)->Next->Prev = Node; } while(0)
#define zLN_AddAfter(Node,List)         do { (Node)->Prev = List; (Node)->Next = (List)->Next; LN_Fix(Node); } while(0)
#define zLN_AddBefore(Node,List)        do { (Node)->Next = List; (Node)->Prev = (List)->Prev; LN_Fix(Node); } while(0)
#define zLN_Walk_Editting(Node,List,Holder)     for( Node = (List)->Next; (Node) != (List) && ((Holder) = (Node)->Next) != NULL ; Node = Holder )
#define zLN_Walk(Node,List)                     for( Node = (List)->Next; (Node) != (List) ; Node = (Node)->Next )
#define zLN_EmptyList(List)                     ( (List)->Next == (List) )

#define LN_InitList(List)                       zLN_InitList((LinkNode *)List)
#define LN_Cut(Node)                            zLN_Cut((LinkNode *)Node)
#define LN_Fix(Node)                            zLN_Fix((LinkNode *)Node)
#define LN_AddAfter(Node,List)          zLN_AddAfter((LinkNode *)Node,(LinkNode *)List)
#define LN_AddBefore(Node,List)         zLN_AddBefore((LinkNode *)Node,(LinkNode *)List)
#define LN_Walk(Node,List)                      zLN_Walk((LinkNode *)Node,(LinkNode *)List)
#define LN_Walk_Editting(Node,List,Holder)                      zLN_Walk_Editting((LinkNode *)Node,(LinkNode *)List,((LinkNode *)Holder))
#define LN_EmptyList(List)                      zLN_EmptyList((LinkNode *)List)
#define LN_Prev(Node)                           (void *)(((LinkNode *)Node)->Prev)
#define LN_Next(Node)                           (void *)(((LinkNode *)Node)->Next)

#define LN_Null(node)   LN_InitList(node)

LinkNode *      LISTCALL LN_CutHead(LinkNode *pList);
LinkNode *      LISTCALL LN_CutTail(LinkNode *pList);

int LN_ListLen(LinkNode *pList);

#define LN_AddHead(list,node)   LN_AddAfter(node,list)
#define LN_AddTail(list,node)   LN_AddBefore(node,list)
#define LN_IsEmpty      LN_EmptyList


        /* use LN_Walk as :
        *

                void doStuffOnAllNodes(LinkNode *pList)
                {
                        LinkNode *pNode;
                        LN_Walk(pNode,pList) {
                                doStuff(pNode);
                        }
                }

        *
        */

#ifdef __cplusplus
}
#endif

#endif  // LIST_H

---