]> git.mxchange.org Git - flightgear.git/blob - Stripe_u/queue.c
Initial revision.
[flightgear.git] / Stripe_u / queue.c
1 /********************************************************************/
2 /*   STRIPE: converting a polygonal model to triangle strips    
3      Francine Evans, 1996.
4      SUNY @ Stony Brook
5      Advisors: Steven Skiena and Amitabh Varshney
6 */
7 /********************************************************************/
8
9 /*---------------------------------------------------------------------*/
10 /*   STRIPE: queue.c
11      This file contains the routines used in the data structures lists, which
12      are queues.
13 */
14 /*---------------------------------------------------------------------*/
15
16  #include "queue.h"
17  
18
19
20 /*----------------------------------------------------------------------------
21  * InitList:
22  */
23 BOOL  InitList  (PLISTHEAD LHead)
24  
25 {
26      if (LHead == NULL) return(FALSE);
27
28      LHead->LHeaders[LISTHEAD] = LHead->LHeaders[LISTTAIL] = NULL;
29      LHead->NumList = 0;
30      return(TRUE);
31 }
32
33 /*----------------------------------------------------------------------------
34  * AddHead:
35  */
36 BOOL  AddHead(PLISTHEAD LHead, PLISTINFO LInfo)
37 {
38      if (LHead == NULL || LInfo == NULL)
39           return(FALSE);
40      if (EMPTYLIST(LHead))
41           LHead->LHeaders[LISTTAIL] = LInfo;
42      else LHead->LHeaders[LISTHEAD]->ListNode.Previous = (void  *) LInfo;
43
44      LInfo->ListNode.Next = (void  *) LHead->LHeaders[LISTHEAD];
45      LHead->LHeaders[LISTHEAD] = LInfo;
46      LInfo->ListNode.Previous = NULL;
47      LHead->NumList++;
48      return(TRUE);
49 }
50
51 /*----------------------------------------------------------------------------
52  * AddTail
53  */
54 BOOL  AddTail(PLISTHEAD LHead, PLISTINFO LInfo)
55 {
56      if (LHead == NULL || LInfo == NULL)
57           return(FALSE);
58      if (EMPTYLIST(LHead))
59           LHead->LHeaders[LISTHEAD] = LInfo;
60      else LHead->LHeaders[LISTTAIL]->ListNode.Next = (void *) LInfo;
61
62      LInfo->ListNode.Previous = (void  *) LHead->LHeaders[LISTTAIL];
63      LHead->LHeaders[LISTTAIL] = LInfo;
64      LInfo->ListNode.Next = NULL;
65      LHead->NumList++;
66      return(TRUE);
67 }
68
69
70 BOOL  InsertNode( PLISTHEAD LHead, int nPos, PLISTINFO LInfo )
71 {
72 PLISTINFO LAddNode;
73
74      if ( LHead == NULL || LInfo == NULL || nPos > NumOnList( LHead ) ) 
75           return( FALSE );
76
77      if ( nPos == 0 )
78           AddHead( LHead, LInfo );
79      else if ( nPos == NumOnList( LHead ) ) 
80           AddTail( LHead, LInfo );
81      else
82      {
83           if ( (LAddNode = PeekList( LHead, LISTHEAD, nPos - 1 )) == NULL )
84                return( FALSE );
85           
86           ((PLISTINFO)LAddNode->ListNode.Next)->ListNode.Previous = LInfo;
87           LInfo->ListNode.Next      = LAddNode->ListNode.Next;
88           LInfo->ListNode.Previous  = LAddNode;
89           LAddNode->ListNode.Next   = LInfo;
90           
91           LHead->NumList++;
92      }
93
94      return( TRUE );
95 }
96
97
98
99
100 /*----------------------------------------------------------------------------
101  *  RemHead:
102  */
103 PLISTINFO  RemHead(PLISTHEAD LHead)
104 {
105      PLISTINFO t, t1;
106
107      if ( LHead == NULL || EMPTYLIST(LHead) )
108           return(NULL);
109
110      t = LHead->LHeaders[LISTHEAD];
111      LHead->LHeaders[LISTHEAD] = (PLISTINFO) t->ListNode.Next;
112
113      if (LHead->LHeaders[LISTHEAD] != NULL)
114      {
115           t1 = (PLISTINFO) t->ListNode.Next;
116           t1->ListNode.Previous = NULL;
117      }
118      else
119           LHead->LHeaders[LISTTAIL] = NULL;
120
121      LHead->NumList--;
122
123      return(t);
124 }
125
126 /*----------------------------------------------------------------------------
127  *  RemTail:
128  */
129 PLISTINFO  RemTail(PLISTHEAD   LHead)
130 {
131      PLISTINFO   t, t1;
132
133      if ( LHead == NULL || EMPTYLIST(LHead) )
134           return(NULL);
135
136      t = LHead->LHeaders[LISTTAIL];
137      LHead->LHeaders[LISTTAIL] = (PLISTINFO) t->ListNode.Previous;
138      if (LHead->LHeaders[LISTTAIL] != NULL)
139      {
140           t1 = (PLISTINFO) t->ListNode.Previous;
141           t1->ListNode.Next = NULL;
142      }
143      else
144           LHead->LHeaders[LISTHEAD] = NULL;
145
146      LHead->NumList--;
147      return(t);
148 }
149
150 /*----------------------------------------------------------------------------
151  * PeekList:
152  */
153 PLISTINFO  PeekList(PLISTHEAD LHead, int wch, int index )
154 {
155      PLISTINFO  t;
156
157      if (LHead == NULL)
158           return(NULL);
159      if ( (t = LHead->LHeaders[wch]) == NULL )
160           return(NULL);
161
162      for (; t != NULL && index > 0; index-- )
163           t = (wch == LISTHEAD)  ? (PLISTINFO) t->ListNode.Next  :
164                                    (PLISTINFO) t->ListNode.Previous;
165      return(t);
166 }
167
168
169 /*----------------------------------------------------------------------------
170  * RemoveList:
171  */
172 PLISTINFO   RemoveList( PLISTHEAD LHead, PLISTINFO LInfo )
173 {
174      PLISTINFO     t, t1;
175
176      t = LInfo;
177      if (LHead == NULL)
178           return(NULL);
179      if (LHead->LHeaders[LISTHEAD] == t)
180           t = (PLISTINFO) RemHead(LHead);
181      else if (LHead->LHeaders[LISTTAIL] == t)
182           t = (PLISTINFO) RemTail(LHead);
183      else
184      {
185           t1                    = (PLISTINFO) t->ListNode.Previous;
186           t1->ListNode.Next     = t->ListNode.Next;
187           t1                    = (PLISTINFO) t->ListNode.Next;
188           t1->ListNode.Previous = t->ListNode.Previous;
189           LHead->NumList--;
190      }
191
192      return(t);
193 }
194
195 /*----------------------------------------------------------------------------
196  * SearchList:
197  *       Try to find a specific node in the queue whose key matches with
198  *  searching key. Return the pointer to that node if found, return NULL
199  *  otherwise
200  *
201  *  Input:
202  *    lpHashTbl       => a far pointer to the hash table
203  *    lpKey           => a far poniter to searching key
204  *    CompareCallBack => comparision function
205  *
206  *  Output: a far pointer to the node to be found
207  *
208  */
209 PLISTINFO  SearchList(
210                         PLISTHEAD lpListHead,
211                         PVOID lpSKey,
212                         int (* CompareCallBack) ( PVOID, PVOID ) )
213 {
214 PLISTINFO lpListInfo;
215
216      lpListInfo = PeekList( lpListHead, LISTHEAD, 0);
217      while ( lpListInfo != NULL )
218      {
219           if ( CompareCallBack( lpListInfo, lpSKey ) )
220                break;
221           lpListInfo = GetNextNode( lpListInfo );
222      }
223
224      return( lpListInfo );
225 }
226