src/hd/sm_list.c

/* Copyright (c) 1998 Silicon Graphics, Inc. */

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