~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

Linux Cross Reference
Tina4/src/file/dicom.old/CTN/lst.c

Version: ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /*
  2           Copyright (C) 1993, RSNA and Washington University
  3 
  4           The software and supporting documentation for the Radiological
  5           Society of North America (RSNA) 1993 Digital Imaging and
  6           Communications in Medicine (DICOM) Demonstration were developed
  7           at the
  8                   Electronic Radiology Laboratory
  9                   Mallinckrodt Institute of Radiology
 10                   Washington University School of Medicine
 11                   510 S. Kingshighway Blvd.
 12                   St. Louis, MO 63110
 13           as part of the 1993 DICOM Central Test Node project for, and
 14           under contract with, the Radiological Society of North America.
 15 
 16           THIS SOFTWARE IS MADE AVAILABLE, AS IS, AND NEITHER RSNA NOR
 17           WASHINGTON UNIVERSITY MAKE ANY WARRANTY ABOUT THE SOFTWARE, ITS
 18           PERFORMANCE, ITS MERCHANTABILITY OR FITNESS FOR ANY PARTICULAR
 19           USE, FREEDOM FROM ANY COMPUTER DISEASES OR ITS CONFORMITY TO ANY
 20           SPECIFICATION. THE ENTIRE RISK AS TO QUALITY AND PERFORMANCE OF
 21           THE SOFTWARE IS WITH THE USER.
 22 
 23           Copyright of the software and supporting documentation is
 24           jointly owned by RSNA and Washington University, and free access
 25           is hereby granted as a license to use this software, copy this
 26           software and prepare derivative works based upon this software.
 27           However, any distribution of this software source code or
 28           supporting documentation or derivative works (source code and
 29           supporting documentation) must include the three paragraphs of
 30           the copyright notice.
 31 */
 32 /*
 33 ** @$=@$=@$=
 34 */
 35 /*
 36 **                              DICOM 93
 37 **                   Electronic Radiology Laboratory
 38 **                 Mallinckrodt Institute of Radiology
 39 **              Washington University School of Medicine
 40 **
 41 ** Module Name(s):
 42 ** Author, Date:        Thomas R. Leith, 15-Apr-93
 43 ** Intent:              This package implements atomic functions on
 44 **                      linked lists.
 45 ** Last Update:         $Author: smm $, $Date: 1998/07/31 19:31:52 $
 46 ** Source File:         $RCSfile: lst.c,v $
 47 ** Revision:            $Revision: 1.11 $
 48 ** Status:              $State: Exp $
 49 */
 50 
 51 static char rcsid[] = "$Revision: 1.11 $ $RCSfile: lst.c,v $";
 52 
 53 #include <stdlib.h>
 54 #include <string.h>
 55 #include <stddef.h>
 56 #ifdef MALLOC_DEBUG
 57 #include "malloc.h"
 58 #endif
 59 
 60 #include "dicom.h"
 61 #include "lstprivate.h"         /* Private definitions */
 62 #include "lst.h"                /* Public definitions */
 63 
 64 #define CURRENT  (*list)->current
 65 #define OLD_NEXT (*list)->current->next
 66 #define OLD_PREV (*list)->current->previous
 67 
 68 
 69 
 70 LST_HEAD *
 71 LST_Create(void)
 72 /*
 73 **  This module creates a new list head and returns your handle to it.
 74 **
 75 */
 76 {
 77     LST_HEAD
 78     * ptr;
 79 
 80     ptr = CTN_MALLOC(sizeof(LST_HEAD));
 81     if (ptr == NULL)
 82         return NULL;
 83 
 84     ptr->head = NULL;
 85     ptr->tail = NULL;
 86     ptr->current = NULL;
 87     ptr->count = 0;
 88     return ptr;
 89 }
 90 
 91 
 92 
 93 CONDITION
 94 LST_Destroy(LST_HEAD ** list)
 95 /*
 96  *  This routine will destroy a list.  The list must be empty.
 97  *  The list handle is set to NULL as a side-effect.
 98  *
 99  */
100 {
101 
102     if ((*list)->count != 0)
103         return LST_LISTNOTEMPTY;
104 
105     CTN_FREE(*list);
106     *list = NULL;
107     return LST_NORMAL;
108 }
109 
110 
111 
112 CONDITION
113 LST_Enqueue(LST_HEAD ** list, LST_NODE * node)
114 /*
115  *  Adds a new node to the tail of the list and returns
116  *  status.
117  *
118  */
119 {
120     node->next = NULL;          /* no next node              */
121     node->previous = (*list)->tail;     /* previous is old tail      */
122     if ((*list)->head == NULL)  /* if list was empty...      */
123         (*list)->head = node;   /* it has a head now!        */
124     else
125         (*list)->tail->next = node;     /* old tail now has a next   */
126 
127     (*list)->tail = node;       /* list now has a new tail    */
128     (*list)->count++;           /* bump the counter           */
129     return LST_NORMAL;
130 }
131 
132 CONDITION
133 LST_Push(LST_HEAD ** list, LST_NODE * node)
134 /*
135  *  Adds a new node to the head of the list and returns
136  *  status.
137  *
138  */
139 
140 {
141     node->next = (*list)->head; /* set the forward link      */
142     node->previous = NULL;      /* set rearward link         */
143     if ((*list)->tail == NULL)  /* if the list was empty     */
144         (*list)->tail = node;   /* set the tail pointer      */
145     else                        /* otherwise,                */
146         (*list)->head->previous = node; /* old head now has a previous                  */
147 
148     (*list)->head = node;       /* set new first node        */
149     (*list)->count++;           /* bump the counter          */
150     return LST_NORMAL;
151 
152 }
153 
154 LST_NODE *
155 LST_Dequeue(LST_HEAD ** list)
156 /*
157  *  Removes a node from the head of the list and returns
158  *  a pointer to it.
159  *
160  */
161 {
162     LST_NODE
163     * ptr;
164 
165     if ((*list)->head == NULL) {/* list is empty             */
166         (*list)->count = 0;
167         return NULL;
168     }
169     ptr = (*list)->head;        /* save the head             */
170     (*list)->head = ptr->next;  /* set new head of list      */
171     if ((*list)->head == NULL)  /* if the list is now empty  */
172         (*list)->tail = NULL;   /* there is no tail anymore  */
173     else
174         (*list)->head->previous = NULL; /* new head has no previous  */
175     ptr->next = NULL;           /* hide data from user       */
176     (*list)->count--;           /* list has one fewer node   */
177     /* now                       */
178     return ptr;
179 }
180 
181 
182 
183 LST_NODE *
184 LST_Pop(LST_HEAD ** list)
185 /*
186  *  Removes a node from the head of the list and returns
187  *  a pointer to it.
188  *
189  */
190 {
191     LST_NODE
192     * ptr;
193 
194     if ((*list)->head == NULL) {/* list is empty             */
195         (*list)->count = 0;
196         return NULL;
197     }
198     ptr = (*list)->head;        /* save the head             */
199     (*list)->head = ptr->next;  /* set new head of list      */
200     if ((*list)->head == NULL)  /* if the list is now empty  */
201         (*list)->tail = NULL;   /* there is no tail anymore  */
202     else
203         (*list)->head->previous = NULL; /* new head has no previous  */
204     ptr->next = NULL;           /* hide data from user       */
205     (*list)->count--;           /* list has one fewer node   */
206     /* now                       */
207     return ptr;
208 }
209 
210 
211 
212 unsigned long
213 LST_Count(LST_HEAD ** list)
214 /*
215  *  Returns the number of nodes in the list.
216  *
217  */
218 {
219     return (*list)->count;
220 }
221 
222 
223 
224 LST_NODE *
225 LST_Head(LST_HEAD ** list)
226 /*
227  *  Returns a pointer to the node at the head of the list.
228  *  It does NOT remove the node from the list.
229  *
230  */
231 {
232     return (*list)->head;
233 }
234 
235 
236 LST_NODE *
237 LST_Current(LST_HEAD ** list)
238 /*
239  *  Returns a pointer to the current node.
240  *  It does NOT remove the node from the list.
241  *
242  */
243 {
244     return (*list)->current;
245 }
246 
247 
248 
249 LST_NODE *
250 LST_Tail(LST_HEAD ** list)
251 /*
252  *  Returns a pointer to the node at the tail of the list.
253  *  It does NOT remove the node from the list.
254  *
255  */
256 {
257     return (*list)->tail;
258 }
259 
260 
261 CONDITION
262 LST_Insert(LST_HEAD ** list, LST_NODE * node, LST_END where)
263 /*
264 **  Inserts a new node in the list.  User selects whether to insert closer
265 **  the HEAD end, or the TAIL end.  If the list is empty, the distinction is
266 **  moot.  In any case, CURRENT is set to the newly-inserted node.  In the
267 **  case of an error, the list is unchanged.
268 **/
269 
270 {
271     if ((where != LST_K_BEFORE) && (where != LST_K_AFTER))
272         goto badend;
273 
274     if ((*list)->head == NULL) {/* if the list was empty     */
275         (*list)->tail = node;   /* set the tail pointer      */
276         (*list)->head = node;   /* set the head pointer      */
277         (*list)->count = 0;     /* will get bumped later...  */
278         (node)->next = NULL;    /* there is no next          */
279         (node)->previous = NULL;/* and no previous           */
280 
281     } else if (CURRENT == NULL) /* is he mixing semantics?       */
282         goto nocurrent;
283 
284     else if ((CURRENT == (*list)->head) &&      /* if at the head           */
285              (where == LST_K_BEFORE)) { /* and inserting BEFORE   */
286         node->next = CURRENT;   /* splice new node in       */
287         CURRENT->previous = node;       /* before the current     */
288         node->previous = NULL;  /* new one has no previous  */
289         (*list)->head = node;   /* new one is first now     */
290 
291     } else if ((CURRENT == (*list)->tail) &&    /* if at the tail           */
292                (where == LST_K_AFTER)) {        /* and inserting AFTER    */
293         node->next = NULL;      /* new node has no next     */
294         node->previous = (*list)->tail; /* previous is old tail     */
295         CURRENT->next = node;   /* splice new node in       */
296         (*list)->tail = node;   /* new node is now the tail */
297 
298     } else if (where == LST_K_AFTER) {  /* not a special case       */
299         OLD_NEXT->previous = node;      /* we preceed a node        */
300         node->next = OLD_NEXT;  /* the old next follows us  */
301         node->previous = CURRENT;       /* the current preceeds us  */
302         CURRENT->next = node;   /* we follow current        */
303 
304     } else {                    /* not a special case       */
305         OLD_PREV->next = node;  /* we follow the previous   */
306         node->previous = OLD_PREV;      /* of current            */
307         node->next = CURRENT;   /* current follows us and   */
308         CURRENT->previous = node;       /* we preceed current     */
309     };
310 
311     (*list)->count++;           /* bump the counter          */
312     (*list)->current = node;    /* and set current        */
313     return LST_NORMAL;
314 
315 badend:
316     return LST_BADEND;
317 
318 nocurrent:
319     return LST_NOCURRENT;
320 }
321 
322 
323 
324 LST_NODE *
325 LST_Remove(LST_HEAD ** list, LST_END dir)
326 /*
327 **  Removes the current node from the list and returns a pointer to it.
328 **  How CURRENT gets set depends on which way the DIR argument points.  If
329 **  DIR is LST_K_BEFORE, CURRENT will move towards the tail-end of the
330 **  list.  If DIR is LST_K_AFTER, CURRENT will move towards the head-end of
331 **  the list.  If there is no node in the direction of DIR, CURRENT becomes
332 **  undefined.
333 **
334 **/
335 {
336     LST_NODE
337     * ptr;
338 
339     if ((dir != LST_K_BEFORE) && (dir != LST_K_AFTER))
340         goto baddir;
341     if (CURRENT == NULL)
342         goto nocurrent;
343     if ((*list)->head == NULL)
344         goto listempty;
345 
346     ptr = CURRENT;              /* save node                 */
347 
348     if (CURRENT == (*list)->head) {     /* removing the head         */
349         (*list)->head = OLD_NEXT;       /* set new head of list      */
350         if ((*list)->head == NULL)      /* if the list is now empty  */
351             (*list)->tail = NULL;       /* no tail anymore either    */
352         else
353             (*list)->head->previous = NULL;     /* new head has no previous  */
354         if (dir == LST_K_BEFORE)/* there is nothing before   */
355             (*list)->current = NULL;    /* the head of the list      */
356         else                    /* otherwise, remain         */
357             (*list)->current = (*list)->head;   /* at the head...         */
358 
359     } else if (CURRENT == (*list)->tail) {      /* removing the tail         */
360         (*list)->tail = OLD_PREV;       /* set new tail of list      */
361         (*list)->tail->next = NULL;     /* new tail has no next      */
362         if (dir == LST_K_AFTER) /* there is nothing after    */
363             (*list)->current = NULL;    /* the tail of a list        */
364         else                    /* otherwise, remain         */
365             (*list)->current = (*list)->tail;   /* at the tail...            */
366 
367     } else {                    /* not a special case        */
368         OLD_PREV->next = CURRENT->next; /* set forward pointer       */
369         OLD_NEXT->previous = CURRENT->previous; /* set backward pointer      */
370         if (dir == LST_K_BEFORE)/* depending on direction,   */
371             (*list)->current = CURRENT->previous;       /* set current             */
372         else                    /* in the                    */
373             (*list)->current = CURRENT->next;   /* list head                 */
374     }
375 
376     (*list)->count--;           /* one fewer nodes now       */
377     ptr->previous = NULL;       /* hide data from user       */
378     ptr->next = NULL;           /* hide data from user       */
379     return ptr;
380 
381 baddir:
382     return NULL;
383 
384 nocurrent:
385     return NULL;
386 
387 listempty:
388     (*list)->count = 0;
389     (*list)->current = NULL;
390     (*list)->head = (*list)->tail = NULL;
391     return NULL;
392 }
393 
394 
395 
396 LST_NODE *
397 LST_Next(LST_HEAD ** list)
398 /*
399  *  Returns a pointer to the next node in the list and
400  *  makes it current.
401  *
402  */
403 {
404     if ((*list)->head == NULL) {/* list is empty            */
405         (*list)->count = 0;
406         return NULL;
407     }
408     if (CURRENT == NULL) {      /* there is no CURRENT      */
409         return NULL;
410     }
411     CURRENT = CURRENT->next;    /* Set current to next and return it */
412     return CURRENT;
413 }
414 
415 
416 
417 LST_NODE *
418 LST_Previous(LST_HEAD ** list)
419 /*
420  *  Returns a pointer to the previous node in the list and
421  *  makes it current.
422  *
423  */
424 {
425     if ((*list)->head == NULL) {/* list is empty     */
426         (*list)->count = 0;
427         return NULL;
428     }
429     if (CURRENT == NULL) {      /* there is no CURRENT       */
430         return NULL;
431     }
432     if (CURRENT->previous == NULL) {    /* no PREVIOUS               */
433         return NULL;
434     }
435     CURRENT = CURRENT->previous;/* found it                  */
436     return CURRENT;
437 }
438 
439 
440 
441 LST_NODE *
442 LST_Position(LST_HEAD ** list, LST_NODE * node)
443 /*
444  *  Make a node current and return the argument.
445  *
446  *
447  *  Notes:  node = lst_position(list, lst_head(list));
448  *          makes the node at the head of the list current
449  *          and returns a pointer to it.
450  *
451  *      The routine tries to verify that "node" is in the list
452  *      by doing a few consistency checks.  It assumes that if
453  *      any of three "known" pointers are what they should be
454  *      that all is well.  Its not damnfoolproof, but...
455  */
456 {
457     if ((*list)->head == NULL) {/* list is empty     */
458         return NULL;
459     }
460     if (node == NULL)
461         return NULL;
462     if (((node->previous == NULL) && ((*list)->head == node)) ||
463         ((node->next == NULL) && ((*list)->tail == node)) ||
464         (node->previous->next == node)) {       /* its probably OK       */
465 
466         CURRENT = node;
467         return CURRENT;
468     };
469 
470     return NULL;
471 }
472 
473 /*
474  *  Sort a list in order according to a comparison algorithm provided
475  *  by the caller.
476  *
477  */
478 CONDITION
479 LST_Sort(LST_HEAD ** list, size_t nodeSize, int (*compare) ())
480 {
481     LST_NODE
482         * n1,
483         *n2;
484     LST_HEAD
485         temp,
486         *head;
487     CTNBOOLEAN
488         inserted;
489 
490     if ((*list)->head == NULL) {/* list is empty     */
491         return LST_NORMAL;
492     }
493     head = &temp;
494     head->head = NULL;
495     head->tail = NULL;
496     head->current = NULL;
497     head->count = 0;
498 
499     while ((n1 = LST_Dequeue(list)) != NULL) {
500         n2 = LST_Head(&head);
501         if (n2 != NULL)
502             (void) LST_Position(&head, n2);
503         inserted = FALSE;
504         while (n2 != NULL && !inserted) {
505             if (compare(n1, n2) < 0) {
506                 (void) LST_Insert(&head, n1, LST_K_BEFORE);
507                 inserted = TRUE;
508             } else
509                 n2 = LST_Next(&head);
510         }
511         if (n2 == NULL)
512             (void) LST_Enqueue(&head, n1);
513     }
514     **list = *head;
515     return LST_NORMAL;
516 }
517 
518 /*
519  *  Return the item at position index.  Can be NULL if list is
520  *  empty or we go off the end of the list.
521  *
522  */
523 LST_NODE *
524 LST_Index(LST_HEAD ** l, int index)
525 {
526     LST_NODE
527     * n;
528 
529     n = LST_Head(l);
530     if (n == NULL)
531         return NULL;
532 
533     index--;
534     LST_Position(l, n);
535     while (index-- > 0 && n != NULL)
536         n = LST_Next(l);
537 
538     return n;
539 }
540 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

This page was automatically generated by the LXR engine.
Visit the LXR main site for more information.