1 /*
2 * bltChain.c --
3 *
4 * The module implements a generic linked list package.
5 *
6 * Copyright 1991-1998 Lucent Technologies, Inc.
7 *
8 * Permission to use, copy, modify, and distribute this software and
9 * its documentation for any purpose and without fee is hereby
10 * granted, provided that the above copyright notice appear in all
11 * copies and that both that the copyright notice and warranty
12 * disclaimer appear in supporting documentation, and that the names
13 * of Lucent Technologies any of their entities not be used in
14 * advertising or publicity pertaining to distribution of the software
15 * without specific, written prior permission.
16 *
17 * Lucent Technologies disclaims all warranties with regard to this
18 * software, including all implied warranties of merchantability and
19 * fitness. In no event shall Lucent Technologies be liable for any
20 * special, indirect or consequential damages or any damages
21 * whatsoever resulting from loss of use, data or profits, whether in
22 * an action of contract, negligence or other tortuous action, arising
23 * out of or in connection with the use or performance of this
24 * software.
25 */
26
27 #include "bltInt.h"
28 #include "bltChain.h"
29
30 #ifndef ALIGN
31 #define ALIGN(a) \
32 (((size_t)a + (sizeof(double) - 1)) & (~(sizeof(double) - 1)))
33 #endif /* ALIGN */
34
35 /*
36 *----------------------------------------------------------------------
37 *
38 * Blt_ChainCreate --
39 *
40 * Creates a new linked list (chain) structure and initializes
41 * its pointers;
42 *
43 * Results:
44 * Returns a pointer to the newly created chain structure.
45 *
46 *----------------------------------------------------------------------
47 */
48 Blt_Chain *
Blt_ChainCreate()49 Blt_ChainCreate()
50 {
51 Blt_Chain *chainPtr;
52
53 chainPtr = Blt_Malloc(sizeof(Blt_Chain));
54 if (chainPtr != NULL) {
55 Blt_ChainInit(chainPtr);
56 }
57 return chainPtr;
58 }
59
60 /*
61 *----------------------------------------------------------------------
62 *
63 * Blt_ChainAllocLink --
64 *
65 * Creates a new chain link. Unlink Blt_ChainNewLink, this
66 * routine also allocates extra memory in the node for data.
67 *
68 * Results:
69 * The return value is the pointer to the newly created entry.
70 *
71 *----------------------------------------------------------------------
72 */
73 Blt_ChainLink *
Blt_ChainAllocLink(extraSize)74 Blt_ChainAllocLink(extraSize)
75 unsigned int extraSize;
76 {
77 Blt_ChainLink *linkPtr;
78 unsigned int linkSize;
79
80 linkSize = ALIGN(sizeof(Blt_ChainLink));
81 linkPtr = Blt_Calloc(1, linkSize + extraSize);
82 assert(linkPtr);
83 if (extraSize > 0) {
84 /* Point clientData at the memory beyond the normal structure. */
85 linkPtr->clientData = (ClientData)((char *)linkPtr + linkSize);
86 }
87 return linkPtr;
88 }
89
90 /*
91 *----------------------------------------------------------------------
92 *
93 * Blt_ChainNewLink --
94 *
95 * Creates a new link.
96 *
97 * Results:
98 * The return value is the pointer to the newly created link.
99 *
100 *----------------------------------------------------------------------
101 */
102 Blt_ChainLink *
Blt_ChainNewLink()103 Blt_ChainNewLink()
104 {
105 Blt_ChainLink *linkPtr;
106
107 linkPtr = Blt_Malloc(sizeof(Blt_ChainLink));
108 assert(linkPtr);
109 linkPtr->clientData = NULL;
110 linkPtr->nextPtr = linkPtr->prevPtr = NULL;
111 return linkPtr;
112 }
113
114 /*
115 *----------------------------------------------------------------------
116 *
117 * Blt_ChainReset --
118 *
119 * Removes all the links from the chain, freeing the memory for
120 * each link. Memory pointed to by the link (clientData) is not
121 * freed. It's the caller's responsibility to deallocate it.
122 *
123 * Results:
124 * None.
125 *
126 *----------------------------------------------------------------------
127 */
128 void
Blt_ChainReset(chainPtr)129 Blt_ChainReset(chainPtr)
130 Blt_Chain *chainPtr; /* Chain to clear */
131 {
132 if (chainPtr != NULL) {
133 Blt_ChainLink *oldPtr;
134 Blt_ChainLink *linkPtr = chainPtr->headPtr;
135
136 while (linkPtr != NULL) {
137 oldPtr = linkPtr;
138 linkPtr = linkPtr->nextPtr;
139 Blt_Free(oldPtr);
140 }
141 Blt_ChainInit(chainPtr);
142 }
143 }
144
145 /*
146 *----------------------------------------------------------------------
147 *
148 * Blt_ChainDestroy
149 *
150 * Frees all the nodes from the chain and deallocates the memory
151 * allocated for the chain structure itself. It's assumed that
152 * the chain was previous allocated by Blt_ChainCreate.
153 *
154 * Results:
155 * None.
156 *
157 *----------------------------------------------------------------------
158 */
159 void
Blt_ChainDestroy(chainPtr)160 Blt_ChainDestroy(chainPtr)
161 Blt_Chain *chainPtr;
162 {
163 if (chainPtr != NULL) {
164 Blt_ChainReset(chainPtr);
165 Blt_Free(chainPtr);
166 }
167 }
168
169 /*
170 *----------------------------------------------------------------------
171 *
172 * Blt_ChainInit --
173 *
174 * Initializes a linked list.
175 *
176 * Results:
177 * None.
178 *
179 *----------------------------------------------------------------------
180 */
181 void
Blt_ChainInit(chainPtr)182 Blt_ChainInit(chainPtr)
183 Blt_Chain *chainPtr;
184 {
185 chainPtr->nLinks = 0;
186 chainPtr->headPtr = chainPtr->tailPtr = NULL;
187 }
188
189 /*
190 *----------------------------------------------------------------------
191 *
192 * Blt_ChainLinkAfter --
193 *
194 * Inserts an entry following a given entry.
195 *
196 * Results:
197 * None.
198 *
199 *----------------------------------------------------------------------
200 */
201 void
Blt_ChainLinkAfter(chainPtr,linkPtr,afterPtr)202 Blt_ChainLinkAfter(chainPtr, linkPtr, afterPtr)
203 Blt_Chain *chainPtr;
204 Blt_ChainLink *linkPtr, *afterPtr;
205 {
206 if (chainPtr->headPtr == NULL) {
207 chainPtr->tailPtr = chainPtr->headPtr = linkPtr;
208 } else {
209 if (afterPtr == NULL) {
210 /* Prepend to the front of the chain */
211 linkPtr->nextPtr = chainPtr->headPtr;
212 linkPtr->prevPtr = NULL;
213 chainPtr->headPtr->prevPtr = linkPtr;
214 chainPtr->headPtr = linkPtr;
215 } else {
216 linkPtr->nextPtr = afterPtr->nextPtr;
217 linkPtr->prevPtr = afterPtr;
218 if (afterPtr == chainPtr->tailPtr) {
219 chainPtr->tailPtr = linkPtr;
220 } else {
221 afterPtr->nextPtr->prevPtr = linkPtr;
222 }
223 afterPtr->nextPtr = linkPtr;
224 }
225 }
226 chainPtr->nLinks++;
227 }
228
229 /*
230 *----------------------------------------------------------------------
231 *
232 * Blt_ChainLinkBefore --
233 *
234 * Inserts a link preceding a given link.
235 *
236 * Results:
237 * None.
238 *
239 *----------------------------------------------------------------------
240 */
241 void
Blt_ChainLinkBefore(chainPtr,linkPtr,beforePtr)242 Blt_ChainLinkBefore(chainPtr, linkPtr, beforePtr)
243 Blt_Chain *chainPtr; /* Chain to contain new entry */
244 Blt_ChainLink *linkPtr; /* New entry to be inserted */
245 Blt_ChainLink *beforePtr; /* Entry to link before */
246 {
247 if (chainPtr->headPtr == NULL) {
248 chainPtr->tailPtr = chainPtr->headPtr = linkPtr;
249 } else {
250 if (beforePtr == NULL) {
251 /* Append to the end of the chain. */
252 linkPtr->nextPtr = NULL;
253 linkPtr->prevPtr = chainPtr->tailPtr;
254 chainPtr->tailPtr->nextPtr = linkPtr;
255 chainPtr->tailPtr = linkPtr;
256 } else {
257 linkPtr->prevPtr = beforePtr->prevPtr;
258 linkPtr->nextPtr = beforePtr;
259 if (beforePtr == chainPtr->headPtr) {
260 chainPtr->headPtr = linkPtr;
261 } else {
262 beforePtr->prevPtr->nextPtr = linkPtr;
263 }
264 beforePtr->prevPtr = linkPtr;
265 }
266 }
267 chainPtr->nLinks++;
268 }
269
270 /*
271 *----------------------------------------------------------------------
272 *
273 * Blt_ChainUnlinkLink --
274 *
275 * Unlinks a link from the chain. The link is not deallocated,
276 * but only removed from the chain.
277 *
278 * Results:
279 * None.
280 *
281 *----------------------------------------------------------------------
282 */
283 void
Blt_ChainUnlinkLink(chainPtr,linkPtr)284 Blt_ChainUnlinkLink(chainPtr, linkPtr)
285 Blt_Chain *chainPtr;
286 Blt_ChainLink *linkPtr;
287 {
288 int unlinked; /* Indicates if the link is actually
289 * removed from the chain. */
290
291 unlinked = FALSE;
292 if (chainPtr->headPtr == linkPtr) {
293 chainPtr->headPtr = linkPtr->nextPtr;
294 unlinked = TRUE;
295 }
296 if (chainPtr->tailPtr == linkPtr) {
297 chainPtr->tailPtr = linkPtr->prevPtr;
298 unlinked = TRUE;
299 }
300 if (linkPtr->nextPtr != NULL) {
301 linkPtr->nextPtr->prevPtr = linkPtr->prevPtr;
302 unlinked = TRUE;
303 }
304 if (linkPtr->prevPtr != NULL) {
305 linkPtr->prevPtr->nextPtr = linkPtr->nextPtr;
306 unlinked = TRUE;
307 }
308 if (unlinked) {
309 chainPtr->nLinks--;
310 }
311 linkPtr->prevPtr = linkPtr->nextPtr = NULL;
312 }
313
314 /*
315 *----------------------------------------------------------------------
316 *
317 * Blt_ChainDeleteLink --
318 *
319 * Unlinks and also frees the given link.
320 *
321 * Results:
322 * None.
323 *
324 *----------------------------------------------------------------------
325 */
326 void
Blt_ChainDeleteLink(chainPtr,linkPtr)327 Blt_ChainDeleteLink(chainPtr, linkPtr)
328 Blt_Chain *chainPtr;
329 Blt_ChainLink *linkPtr;
330 {
331 Blt_ChainUnlinkLink(chainPtr, linkPtr);
332 Blt_Free(linkPtr);
333 }
334
335 Blt_ChainLink *
Blt_ChainAppend(chainPtr,clientData)336 Blt_ChainAppend(chainPtr, clientData)
337 Blt_Chain *chainPtr;
338 ClientData clientData;
339 {
340 Blt_ChainLink *linkPtr;
341
342 linkPtr = Blt_ChainNewLink();
343 Blt_ChainLinkBefore(chainPtr, linkPtr, (Blt_ChainLink *)NULL);
344 Blt_ChainSetValue(linkPtr, clientData);
345 return linkPtr;
346 }
347
348 Blt_ChainLink *
Blt_ChainPrepend(chainPtr,clientData)349 Blt_ChainPrepend(chainPtr, clientData)
350 Blt_Chain *chainPtr;
351 ClientData clientData;
352 {
353 Blt_ChainLink *linkPtr;
354
355 linkPtr = Blt_ChainNewLink();
356 Blt_ChainLinkAfter(chainPtr, linkPtr, (Blt_ChainLink *)NULL);
357 Blt_ChainSetValue(linkPtr, clientData);
358 return linkPtr;
359 }
360
361 /*
362 *----------------------------------------------------------------------
363 *
364 * Blt_ChainGetNthLink --
365 *
366 * Find the link at the given position in the chain.
367 *
368 * Results:
369 * Returns the pointer to the link, if that numbered link
370 * exists. Otherwise NULL.
371 *
372 *----------------------------------------------------------------------
373 */
374 Blt_ChainLink *
Blt_ChainGetNthLink(chainPtr,position)375 Blt_ChainGetNthLink(chainPtr, position)
376 Blt_Chain *chainPtr; /* Chain to traverse */
377 int position; /* Index of link to select from front
378 * or back of the chain. */
379 {
380 Blt_ChainLink *linkPtr;
381
382 if (chainPtr != NULL) {
383 for (linkPtr = chainPtr->headPtr; linkPtr != NULL;
384 linkPtr = linkPtr->nextPtr) {
385 if (position == 0) {
386 return linkPtr;
387 }
388 position--;
389 }
390 }
391 return NULL;
392 }
393
394 /*
395 *----------------------------------------------------------------------
396 *
397 * Blt_ChainSort --
398 *
399 * Sorts the chain according to the given comparison routine.
400 *
401 * Results:
402 * None.
403 *
404 * Side Effects:
405 * The chain is reordered.
406 *
407 *----------------------------------------------------------------------
408 */
409 void
Blt_ChainSort(chainPtr,proc)410 Blt_ChainSort(chainPtr, proc)
411 Blt_Chain *chainPtr; /* Chain to traverse */
412 Blt_ChainCompareProc *proc;
413 {
414 Blt_ChainLink **linkArr;
415 register Blt_ChainLink *linkPtr;
416 register int i;
417
418 if (chainPtr->nLinks < 2) {
419 return;
420 }
421 linkArr = Blt_Malloc(sizeof(Blt_ChainLink *) * (chainPtr->nLinks + 1));
422 if (linkArr == NULL) {
423 return; /* Out of memory. */
424 }
425 i = 0;
426 for (linkPtr = chainPtr->headPtr; linkPtr != NULL;
427 linkPtr = linkPtr->nextPtr) {
428 linkArr[i++] = linkPtr;
429 }
430 qsort((char *)linkArr, chainPtr->nLinks, sizeof(Blt_ChainLink *),
431 (QSortCompareProc *)proc);
432
433 /* Rethread the chain. */
434 linkPtr = linkArr[0];
435 chainPtr->headPtr = linkPtr;
436 linkPtr->prevPtr = NULL;
437 for (i = 1; i < chainPtr->nLinks; i++) {
438 linkPtr->nextPtr = linkArr[i];
439 linkPtr->nextPtr->prevPtr = linkPtr;
440 linkPtr = linkPtr->nextPtr;
441 }
442 chainPtr->tailPtr = linkPtr;
443 linkPtr->nextPtr = NULL;
444 Blt_Free(linkArr);
445 }
446