src/hd/sm_list.c

#ifndef lint
static const char       RCSid[] = "$Id$";
#endif
/*
 *  sm_list.c
 *   Routines for handling linked generic linked lists, stack, and
 *   circular lists. Data element is an int (can be cast to hold
 *   pointer to more general data element)
 */

#include "standard.h"
#include "sm_list.h" 

/* List of available edges */
static LIST *free_lists = NULL;
#ifdef DEBUG
extern int Malloc_cnt;   
#endif
LIST
/* NOTE: Memory is not initialized */
*new_list()
{
    LIST *l;

    /* check free list for available edges */
    if( free_lists )
    {
        l = free_lists;
        free_lists = LIST_NEXT(free_lists);
    }
    /* if no free edges- allocate the memory */
    else
    {
      if( !(l = (LIST *)malloc(sizeof(LIST))))
          error(SYSTEM,"new_list():Unable to allocate memory");
    }
    return(l);
}


/* attaches list a at the end of list b */
LIST
*append_list(a,b)
LIST *a,*b;
{
    LIST * l;

    if(!b)
       return(a);
    
    l = b;
    while(LIST_NEXT(l) && LIST_NEXT(l) != b)
       l = LIST_NEXT(l);

    SET_LIST_NEXT(l,a);
    
    return(b);
}

/* attaches list a at the end of list b */
LIST
*add_data(l,d,end)
LIST *l;
int d;
LIST **end;

{
    LIST *list,*lptr;

    list = new_list();
    SET_LIST_DATA(list,d);
    SET_LIST_NEXT(list,NULL);
    if(!l)
    {
      if(end)
        *end = list;
      return(list);
    }
    if(end)
      lptr = *end;
    else
    {
      lptr = l;
      while(LIST_NEXT(lptr))
        lptr = LIST_NEXT(lptr);
    }
    LIST_NEXT(lptr) = list;
    if(end)
      *end = list;

    return(l);
}

/* Adds data to the end of a circular list. If set, "end"
 * is a pointer to the last element in the list
 */
LIST
*add_data_to_circular_list(l,end,d)
LIST *l,**end;
int d;
{
    LIST *list;
    
    list = new_list();
    SET_LIST_DATA(list,d);

    if(!l)
       l = list;
    else
    {   
        if(*end)
          SET_LIST_NEXT(*end,list);
        else
           l = append_list(list,l);
    }

    *end = list;
    SET_LIST_NEXT(list,l);
    return(l);
}


/* frees the list */
LIST
*free_list(l)
LIST * l;
{
    if(!l)
       return(NULL);

    free_lists = append_list(free_lists,l);

    return(NULL);
}

/* Pushes data element d at the top of the list- returns pointer
   to new top of list
 */
LIST
*push_data(l,d)
LIST *l;
int d;
{
  LIST *list;

  list = new_list();
  SET_LIST_DATA(list,d);
  SET_LIST_NEXT(list,l);
  return(list);
}
/* Returns data element d at the top of the list- returns pointer
   to new top of list
 */
int
pop_list(l)
LIST **l;
{
    LIST *p;
    int d;
    
    if(!l)
       return(NULL);
    if(!(p = *l))
       return(NULL);

    d = LIST_DATA(p);
    
    *l = LIST_NEXT(p);

    LIST_NEXT(p) =NULL;
    free_list(p);
    
    return(d);
}    

/* Search through list for data element "d", and remove from
 *  list: Returns TRUE if found, false otherwise
 */
int
remove_from_list(d,list)
int d;
LIST **list;
{
    LIST *l,*prev;
    
    l = *list;
    prev = NULL;
    
    while(l)
    {
        if(LIST_DATA(l) == d)
        {
           if(l == *list)
              *list = LIST_NEXT(*list);
           else
              SET_LIST_NEXT(prev,LIST_NEXT(l));
        
           SET_LIST_NEXT(l,NULL);
           free_list(l);
           return(TRUE);
       }
        prev = l;
        l = LIST_NEXT(l);
    }
    return(FALSE);
}


Revision:	3.8
Committed:	Sat Feb 22 02:07:25 2003 UTC (21 years, 2 months ago) by greg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad3R6P1, rad3R5, rad3R6
Changes since 3.7:	+1 -4 lines
Log Message:	Changes and check-in for 3.5 release Includes new source files and modifications not recorded for many years See ray/doc/notes/ReleaseNotes for notes between 3.1 and 3.5 release
#	User	Rev	Content
1	gwlarson	3.1	#ifndef lint
2	greg	3.8	static const char RCSid[] = "$Id$";
3	gwlarson	3.1	#endif
4			/*
5			* sm_list.c
6			* Routines for handling linked generic linked lists, stack, and
7			* circular lists. Data element is an int (can be cast to hold
8			* pointer to more general data element)
9			*/
10
11			#include "standard.h"
12			#include "sm_list.h"
13
14			/* List of available edges */
15			static LIST *free_lists = NULL;
16			#ifdef DEBUG
17			extern int Malloc_cnt;
18			#endif
19			LIST
20	gwlarson	3.7	/* NOTE: Memory is not initialized */
21	gwlarson	3.1	*new_list()
22			{
23			LIST *l;
24
25			/* check free list for available edges */
26			if( free_lists )
27			{
28			l = free_lists;
29			free_lists = LIST_NEXT(free_lists);
30			}
31			/* if no free edges- allocate the memory */
32			else
33			{
34			if( !(l = (LIST *)malloc(sizeof(LIST))))
35			error(SYSTEM,"new_list():Unable to allocate memory");
36			}
37			return(l);
38			}
39
40
41			/* attaches list a at the end of list b */
42			LIST
43			*append_list(a,b)
44			LIST a,b;
45			{
46			LIST * l;
47
48			if(!b)
49			return(a);
50
51			l = b;
52			while(LIST_NEXT(l) && LIST_NEXT(l) != b)
53			l = LIST_NEXT(l);
54
55			SET_LIST_NEXT(l,a);
56
57			return(b);
58			}
59
60	gwlarson	3.4	/* attaches list a at the end of list b */
61			LIST
62			*add_data(l,d,end)
63			LIST *l;
64			int d;
65			LIST **end;
66
67			{
68			LIST list,lptr;
69
70			list = new_list();
71			SET_LIST_DATA(list,d);
72	gwlarson	3.7	SET_LIST_NEXT(list,NULL);
73	gwlarson	3.4	if(!l)
74			{
75			if(end)
76			*end = list;
77			return(list);
78			}
79			if(end)
80			lptr = *end;
81			else
82			{
83			lptr = l;
84			while(LIST_NEXT(lptr))
85			lptr = LIST_NEXT(lptr);
86			}
87			LIST_NEXT(lptr) = list;
88			if(end)
89			*end = list;
90
91			return(l);
92			}
93
94	gwlarson	3.1	/* Adds data to the end of a circular list. If set, "end"
95			* is a pointer to the last element in the list
96			*/
97			LIST
98			*add_data_to_circular_list(l,end,d)
99			LIST l,*end;
100			int d;
101			{
102			LIST *list;
103
104			list = new_list();
105			SET_LIST_DATA(list,d);
106
107			if(!l)
108			l = list;
109			else
110			{
111			if(*end)
112			SET_LIST_NEXT(*end,list);
113			else
114			l = append_list(list,l);
115			}
116
117			*end = list;
118			SET_LIST_NEXT(list,l);
119			return(l);
120			}
121
122
123	gwlarson	3.5
124	gwlarson	3.1	/* frees the list */
125			LIST
126			*free_list(l)
127			LIST * l;
128			{
129			if(!l)
130			return(NULL);
131	gwlarson	3.2
132	gwlarson	3.1	free_lists = append_list(free_lists,l);
133
134			return(NULL);
135			}
136
137	gwlarson	3.5	/* Pushes data element d at the top of the list- returns pointer
138			to new top of list
139			*/
140			LIST
141			*push_data(l,d)
142			LIST *l;
143			int d;
144			{
145			LIST *list;
146
147			list = new_list();
148			SET_LIST_DATA(list,d);
149			SET_LIST_NEXT(list,l);
150			return(list);
151			}
152	gwlarson	3.1	/* Returns data element d at the top of the list- returns pointer
153			to new top of list
154			*/
155			int
156			pop_list(l)
157			LIST **l;
158			{
159			LIST *p;
160	gwlarson	3.2	int d;
161	gwlarson	3.1
162			if(!l)
163			return(NULL);
164			if(!(p = *l))
165			return(NULL);
166
167			d = LIST_DATA(p);
168
169			*l = LIST_NEXT(p);
170
171			LIST_NEXT(p) =NULL;
172			free_list(p);
173
174			return(d);
175			}
176
177			/* Search through list for data element "d", and remove from
178			* list: Returns TRUE if found, false otherwise
179			*/
180			int
181			remove_from_list(d,list)
182			int d;
183			LIST **list;
184			{
185			LIST l,prev;
186
187			l = *list;
188			prev = NULL;
189
190			while(l)
191			{
192			if(LIST_DATA(l) == d)
193			{
194			if(l == *list)
195			list = LIST_NEXT(list);
196			else
197			SET_LIST_NEXT(prev,LIST_NEXT(l));
198
199			SET_LIST_NEXT(l,NULL);
200			free_list(l);
201			return(TRUE);
202			}
203			prev = l;
204			l = LIST_NEXT(l);
205			}
206			return(FALSE);
207			}
208	gwlarson	3.7
209
210
211
212	gwlarson	3.1
213
214
215
216
217
218
219
220
221