2 /********************************************************************/
3 /* STRIPE: converting a polygonal model to triangle strips
6 Advisors: Steven Skiena and Amitabh Varshney
8 /********************************************************************/
10 /*---------------------------------------------------------------------*/
12 -----------------------------------------------------------------------*/
14 #ifndef QUEUE_INCLUDED
15 #define QUEUE_INCLUDED
18 /*****************************************************************
19 This structure is used to store the List linkage information of a
20 ListInfo structure. It contains all the necessary information for the
21 List functions to function properly. This structure must be the first
22 one defined in any block of memory to be linked with the List functions.
23 for an example of the used of The Node structure look in the files
24 ipd2dms.c and ipd2man.h
25 ******************************************************************/
36 /*****************************************************************
37 Next : is a pointer to the next structure in this List.
38 Previous : is a pointer to the previous structure in this List.
39 priority : this is the priority of this structure in the List. The
40 highest priority is 0. This field is only used by the
41 functions EnQue and DeQue.
42 ******************************************************************/
48 /*****************************************************************
49 This is the general means of linking application defined information into
50 Lists and queues. All structures must begin with the Node Structure. All
51 other data in the structure is user definable.
52 ******************************************************************/
56 Node ListNode; /* link to the next Listinfo Structure */
57 /* user definable data */
58 } ListInfo, *PLISTINFO;
60 /*****************************************************************
61 ListNode : this is the required node structure for the List
62 mainpulation functions. This must be the first
63 element of a user definable structure.
65 In order for an application to use the List routines, it must define
66 a structure with all the needed information. The first element in the
67 user definable structure must be a Node structure. The Node structure
68 contains all the necessary information for the List routines to do their
69 magic. For an example of a user defined List structure see the file
70 ipd2i.h. The User definable structure can be passed to any List function
71 that excepts a pointer to a ListInfo structure.
82 the user definable portion of the above structure is represented by
83 the integers a,b,c,d,e,f,g. When passing this structure to a List
84 function a cast of (ListInfo *) must be made to satisify the "C" complier.
85 ******************************************************************/
90 /*****************************************************************
91 ListHead is used as a header to a List. LHeaders[0] points to the
92 head of the List. LHeaders[1] points the tail of the list. When
93 accessing these variables use the defines LISTHEAD, LISTTAIL.
94 ******************************************************************/
98 PLISTINFO LHeaders[2];
101 ListHead, *PLISTHEAD;
103 /*****************************************************************
104 LHeaders : this is an array of two pointers to ListInfo structures.
105 This information is used to point to the head and tail of
107 NumList : this integer hold the number of structures linked into this
112 LISTHEAD : when Peeking down a list this specifies you should
113 start at the Head of the list and search downward.
115 LISTTAIL : when Peeking down a list this specifies you should
116 start at the tail of the list and search foward.
117 ******************************************************************/
125 typedef void * PVOID;
127 #define PEEKFROMHEAD( lh, ind ) ( PeekList( (lh), LISTHEAD, (ind) ) )
128 #define PEEKFROMTAIL( lh, ind ) ( PeekList( (lh), LISTTAIL, (ind) ) )
129 #define EMPTYLIST( lh ) ( ( (lh)->LHeaders[LISTHEAD] == NULL ) )
131 /* General utility routines */
132 /* %%s QueRoutines */
133 BOOL InitList ( PLISTHEAD );
135 /*****************************************************************
136 InitList : Initialize a new list structure for use with the List
139 INPUTS : LHead : a pointer to a ListHead structure.
140 OUTPUT : a boolean value TRUE if no errors occured FALSE
142 ******************************************************************/
145 PLISTINFO PeekList ( PLISTHEAD, int, int );
147 /*****************************************************************
148 PeekList : This funciton peeks down a list for the N'th element
149 from the HEAD or TAIL of the list
151 INPUTS : LHead : a pointer to a List head structure.
152 from : can either search from the HEAD or TAIL
154 where : how many nodes from the begining should the
156 OUTPUT : a pointer to a ListInfo structure identified by
157 from/where or NULL if an error occurred.
158 ******************************************************************/
161 PLISTINFO RemoveList( PLISTHEAD LHead, PLISTINFO LInfo );
164 /*****************************************************************
165 RemoveList: Remove a ListInfo structure from a List.
167 INPUTS : LHead : a pointer to a ListHead structure.
168 LInfo : a pointer to the ListInfo structure to remove
170 OUTPUT : a pointer to the ListInfo structure that was removed or
171 NULL if an error occurred.
172 ******************************************************************/
174 BOOL InsertNode( PLISTHEAD LHead, int nPos, PLISTINFO LInfo );
176 /*****************************************************************
177 InsertNode: add a node to a list after a given node
179 INPUTS : LHead : a pointer to a ListHead structure.
180 nPos : the position to insert the node into
181 LInfo : a pointer to the new node to add to the list.
182 OUTPUT: a boolean value TRUE if all goes well false otherwise
183 *****************************************************************/
185 BOOL AddHead ( PLISTHEAD, PLISTINFO );
187 /*****************************************************************
188 AddHead : add a ListInfo structure to the HEAD of a list.
190 INPUTS : LHead : a pointer to a ListHead structure of the list
192 LInfo : a pointer to the ListInfo structure to add to
194 OUTPUT : A boolean value TRUE if no errors occurred FALSE
196 ******************************************************************/
199 BOOL AddTail ( PLISTHEAD, PLISTINFO );
201 /*****************************************************************
202 AddTail : Add a ListInfo structure to the TAIL of a list.
204 INPUTS : LHead : a pointer to a ListHead structure of the List
206 LInfo : a pointer to the ListInfo structure to add to
208 OUTPUT : a boolean value TRUE if no errors occurred FALSE
210 ******************************************************************/
213 PLISTINFO RemTail ( PLISTHEAD );
215 /*****************************************************************
216 RemTail : Remove a ListInfo structure from the TAIL of a List.
218 INPUTS : LHead : a pointer to a ListHead structure of the List
220 OUTPUT : a pointer to the ListInfo structure that was removed
221 or NULL if an error occurred.
222 ******************************************************************/
225 PLISTINFO RemHead ( PLISTHEAD );
227 /*****************************************************************
228 RemHead : Remove a ListInfo structure from the Head of a List.
230 INPUTS : LHead : a pointer to a ListHead structure of the List
232 OUTPUT : a pointer to the ListInfo structure that was removed or
233 NULL if an error occurred.
234 ******************************************************************/
236 PLISTINFO SearchList(
237 PLISTHEAD lpListHead,
239 int ( * CompareCallBack) ( PVOID, PVOID ) );
241 /*****************************************************************
243 Try to find a specific node in the queue whose key matches with
244 searching key. Return the pointer to that node if found, return NULL
248 lpHashTbl => a far pointer to the hash table
249 lpKey => a far poniter to searching key
250 CompareCallBack => comparision function
252 Output: a far pointer to the node to be found
254 ******************************************************************/
256 #define NumOnList(lh) ( ((lh)->NumList) )
258 /*****************************************************************
259 NumOnList: Returns the number of Nodes linked to a ListHead
260 structure. This number is maintained by the List
262 ******************************************************************/
264 #define GetNextNode(pli) ( ((pli)->ListNode.Next) )
266 /********************************************************
267 GetNextNode: This macro returns the Next Structure in this list.
268 This macro will return NULL if no more structures are
270 *********************************************************/
272 #define GetPrevNode(pli) ( ((pli)->ListNode.Previous) )
274 /********************************************************
275 GetPrevNode: This macro returns the Previous Structure in this list.
276 This macro will reutrn NULL if no more structures are
278 ********************************************************/