1 //Copyright Paul Reiche, Fred Ford. 1992-2002
2
3 /*
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17 */
18
19 #include "displist.h"
20 #include "libs/log.h"
21
22 #ifdef QUEUE_TABLE
23 #define NULL_HANDLE NULL
24 #endif
25
26 /*
27 * This file contains code for generic doubly linked lists.
28 * If QUEUE_TABLE is defined, each lists has its own preallocated
29 * pool of link structures. The size is specific on InitQueue(),
30 * and poses a hard limit on the number of elements in the list.
31 */
32
33 BOOLEAN
InitQueue(QUEUE * pq,COUNT num_elements,OBJ_SIZE size)34 InitQueue (QUEUE *pq, COUNT num_elements, OBJ_SIZE size)
35 {
36 SetHeadLink (pq, NULL_HANDLE);
37 SetTailLink (pq, NULL_HANDLE);
38 SetLinkSize (pq, size);
39 #ifndef QUEUE_TABLE
40 return (TRUE);
41 #else /* QUEUE_TABLE */
42 SetFreeList (pq, NULL_HANDLE);
43 #if 0
44 log_add (log_Debug, "InitQueue(): num_elements = %d (%d)",
45 num_elements, (BYTE)num_elements);
46 #endif
47 if (AllocQueueTab (pq, num_elements) != NULL)
48 {
49 do
50 FreeLink (pq, GetLinkAddr (pq, num_elements));
51 while (--num_elements);
52
53 return (TRUE);
54 }
55
56 return (FALSE);
57 #endif /* QUEUE_TABLE */
58 }
59
60 BOOLEAN
UninitQueue(QUEUE * pq)61 UninitQueue (QUEUE *pq)
62 {
63 #ifdef QUEUE_TABLE
64 SetHeadLink (pq, NULL_HANDLE);
65 SetTailLink (pq, NULL_HANDLE);
66 SetFreeList (pq, NULL_HANDLE);
67 FreeQueueTab (pq);
68
69 return (TRUE);
70 #else /* !QUEUE_TABLE */
71 HLINK hLink;
72
73 while ((hLink = GetHeadLink (pq)) != NULL_HANDLE)
74 {
75 RemoveQueue (pq, hLink);
76 if (!FreeLink (pq, hLink))
77 return (FALSE);
78 }
79
80 return (TRUE);
81 #endif /* QUEUE_TABLE */
82 }
83
84 // Empty the queue. The elements linked to in the queue are unchanged.
85 void
ReinitQueue(QUEUE * pq)86 ReinitQueue (QUEUE *pq)
87 {
88 SetHeadLink (pq, NULL_HANDLE);
89 SetTailLink (pq, NULL_HANDLE);
90 #ifdef QUEUE_TABLE
91 {
92 COUNT num_elements;
93
94 SetFreeList (pq, NULL_HANDLE);
95
96 num_elements = SizeQueueTab (pq);
97 if (num_elements)
98 {
99 do
100 FreeLink (pq, GetLinkAddr (pq, num_elements));
101 while (--num_elements);
102 }
103 }
104 #endif /* QUEUE_TABLE */
105 }
106
107 #ifdef QUEUE_TABLE
108 HLINK
AllocLink(QUEUE * pq)109 AllocLink (QUEUE *pq)
110 {
111 HLINK hLink;
112
113 hLink = GetFreeList (pq);
114 if (hLink)
115 {
116 LINK *LinkPtr;
117
118 LinkPtr = LockLink (pq, hLink);
119 SetFreeList (pq, _GetSuccLink (LinkPtr));
120 UnlockLink (pq, hLink);
121 }
122 else
123 log_add (log_Debug, "AllocLink(): No more elements");
124
125 return (hLink);
126 }
127
128 void
FreeLink(QUEUE * pq,HLINK hLink)129 FreeLink (QUEUE *pq, HLINK hLink)
130 {
131 LINK *LinkPtr;
132
133 LinkPtr = LockLink (pq, hLink);
134 _SetSuccLink (LinkPtr, GetFreeList (pq));
135 UnlockLink (pq, hLink);
136
137 SetFreeList (pq, hLink);
138 }
139 #endif /* QUEUE_TABLE */
140
141 void
PutQueue(QUEUE * pq,HLINK hLink)142 PutQueue (QUEUE *pq, HLINK hLink)
143 {
144 LINK *LinkPtr;
145
146 if (GetHeadLink (pq) == 0)
147 SetHeadLink (pq, hLink);
148 else
149 {
150 HLINK hTail;
151 LINK *lpTail;
152
153 hTail = GetTailLink (pq);
154 lpTail = LockLink (pq, hTail);
155 _SetSuccLink (lpTail, hLink);
156 UnlockLink (pq, hTail);
157 }
158
159 LinkPtr = LockLink (pq, hLink);
160 _SetPredLink (LinkPtr, GetTailLink (pq));
161 _SetSuccLink (LinkPtr, NULL_HANDLE);
162 UnlockLink (pq, hLink);
163
164 SetTailLink (pq, hLink);
165 }
166
167 void
InsertQueue(QUEUE * pq,HLINK hLink,HLINK hRefLink)168 InsertQueue (QUEUE *pq, HLINK hLink, HLINK hRefLink)
169 {
170 if (hRefLink == 0)
171 PutQueue (pq, hLink);
172 else
173 {
174 LINK *LinkPtr;
175 LINK *RefLinkPtr;
176
177 LinkPtr = LockLink (pq, hLink);
178 RefLinkPtr = LockLink (pq, hRefLink);
179 _SetPredLink (LinkPtr, _GetPredLink (RefLinkPtr));
180 _SetPredLink (RefLinkPtr, hLink);
181 _SetSuccLink (LinkPtr, hRefLink);
182
183 if (GetHeadLink (pq) == hRefLink)
184 SetHeadLink (pq, hLink);
185 else
186 {
187 HLINK hPredLink;
188 LINK *PredLinkPtr;
189
190 hPredLink = _GetPredLink (LinkPtr);
191 PredLinkPtr = LockLink (pq, hPredLink);
192 _SetSuccLink (PredLinkPtr, hLink);
193 UnlockLink (pq, hPredLink);
194 }
195 UnlockLink (pq, hRefLink);
196 UnlockLink (pq, hLink);
197 }
198 }
199
200 void
RemoveQueue(QUEUE * pq,HLINK hLink)201 RemoveQueue (QUEUE *pq, HLINK hLink)
202 {
203 LINK *LinkPtr;
204
205 LinkPtr = LockLink (pq, hLink);
206 if (GetHeadLink (pq) == hLink)
207 {
208 SetHeadLink (pq, _GetSuccLink (LinkPtr));
209 }
210 else
211 {
212 HLINK hPredLink;
213 LINK *PredLinkPtr;
214
215 hPredLink = _GetPredLink (LinkPtr);
216 PredLinkPtr = LockLink (pq, hPredLink);
217 _SetSuccLink (PredLinkPtr, _GetSuccLink (LinkPtr));
218 UnlockLink (pq, hPredLink);
219 }
220 if (GetTailLink (pq) == hLink)
221 {
222 SetTailLink (pq, _GetPredLink (LinkPtr));
223 }
224 else
225 {
226 HLINK hSuccLink, hPredLink;
227 LINK *SuccLinkPtr;
228
229 hSuccLink = _GetSuccLink (LinkPtr);
230 SuccLinkPtr = LockLink (pq, hSuccLink);
231 hPredLink = _GetPredLink (LinkPtr);
232 _SetPredLink (SuccLinkPtr, hPredLink);
233 UnlockLink (pq, hSuccLink);
234 }
235 UnlockLink (pq, hLink);
236 }
237
238 COUNT
CountLinks(QUEUE * pq)239 CountLinks (QUEUE *pq)
240 {
241 COUNT LinkCount;
242 HLINK hLink, hNextLink;
243
244 LinkCount = 0;
245 for (hLink = GetHeadLink (pq); hLink; hLink = hNextLink)
246 {
247 LINK *LinkPtr;
248
249 ++LinkCount;
250
251 LinkPtr = LockLink (pq, hLink);
252 hNextLink = _GetSuccLink (LinkPtr);
253 UnlockLink (pq, hLink);
254 }
255
256 return (LinkCount);
257 }
258
259 void
ForAllLinks(QUEUE * pq,void (* callback)(LINK *,void *),void * arg)260 ForAllLinks (QUEUE *pq, void (*callback)(LINK *, void *), void *arg)
261 {
262 HLINK hLink, hNextLink;
263
264 for (hLink = GetHeadLink (pq); hLink; hLink = hNextLink)
265 {
266 LINK *LinkPtr;
267 LinkPtr = LockLink (pq, hLink);
268 hNextLink = _GetSuccLink (LinkPtr);
269 (*callback) (LinkPtr, arg);
270 UnlockLink (pq, hLink);
271 }
272 }
273
274
275