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
*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");
    }
    /* clear the memory */
    bzero(l, sizeof(LIST));

    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);

    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);
}

/* 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);
}

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

    free_lists = append_list(free_lists,l);

    return(NULL);
}

/* 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.4
Committed:	Mon Dec 28 18:07:35 1998 UTC (25 years, 3 months ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Changes since 3.3:	+34 -0 lines
Log Message:	New insertion routine New Culling routine based on insertion algorithm Adapted old insertion code: now used by picking Point location code returns on-vertex,on-edge, or in-triangle Added on_edge case for subdivision Implemented unordered sets Removed deletion from quadtree- added set compression to replace functionality
#	Content
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	*new_list()
24	{
25	LIST *l;
26
27	/* check free list for available edges */
28	if( free_lists )
29	{
30	l = free_lists;
31	free_lists = LIST_NEXT(free_lists);
32	}
33	/* if no free edges- allocate the memory */
34	else
35	{
36	if( !(l = (LIST *)malloc(sizeof(LIST))))
37	error(SYSTEM,"new_list():Unable to allocate memory");
38	}
39	/* clear the memory */
40	bzero(l, sizeof(LIST));
41
42	return(l);
43	}
44
45
46	/* attaches list a at the end of list b */
47	LIST
48	*append_list(a,b)
49	LIST a,b;
50	{
51	LIST * l;
52
53	if(!b)
54	return(a);
55
56	l = b;
57	while(LIST_NEXT(l) && LIST_NEXT(l) != b)
58	l = LIST_NEXT(l);
59
60	SET_LIST_NEXT(l,a);
61
62	return(b);
63	}
64
65	/* attaches list a at the end of list b */
66	LIST
67	*add_data(l,d,end)
68	LIST *l;
69	int d;
70	LIST **end;
71
72	{
73	LIST list,lptr;
74
75	list = new_list();
76	SET_LIST_DATA(list,d);
77
78	if(!l)
79	{
80	if(end)
81	*end = list;
82	return(list);
83	}
84	if(end)
85	lptr = *end;
86	else
87	{
88	lptr = l;
89	while(LIST_NEXT(lptr))
90	lptr = LIST_NEXT(lptr);
91	}
92	LIST_NEXT(lptr) = list;
93	if(end)
94	*end = list;
95
96	return(l);
97	}
98
99	/* Adds data to the end of a circular list. If set, "end"
100	* is a pointer to the last element in the list
101	*/
102	LIST
103	*add_data_to_circular_list(l,end,d)
104	LIST l,*end;
105	int d;
106	{
107	LIST *list;
108
109	list = new_list();
110	SET_LIST_DATA(list,d);
111
112	if(!l)
113	l = list;
114	else
115	{
116	if(*end)
117	SET_LIST_NEXT(*end,list);
118	else
119	l = append_list(list,l);
120	}
121
122	*end = list;
123	SET_LIST_NEXT(list,l);
124	return(l);
125	}
126
127	/* Pushes data element d at the top of the list- returns pointer
128	to new top of list
129	*/
130	LIST
131	*push_data(l,d)
132	LIST *l;
133	int d;
134	{
135	LIST * list;
136
137	list = new_list();
138	SET_LIST_DATA(list,d);
139	SET_LIST_NEXT(list,l);
140	return(list);
141	}
142
143	/* frees the list */
144	LIST
145	*free_list(l)
146	LIST * l;
147	{
148	if(!l)
149	return(NULL);
150
151	free_lists = append_list(free_lists,l);
152
153	return(NULL);
154	}
155
156	/* Returns data element d at the top of the list- returns pointer
157	to new top of list
158	*/
159	int
160	pop_list(l)
161	LIST **l;
162	{
163	LIST *p;
164	int d;
165
166	if(!l)
167	return(NULL);
168	if(!(p = *l))
169	return(NULL);
170
171	d = LIST_DATA(p);
172
173	*l = LIST_NEXT(p);
174
175	LIST_NEXT(p) =NULL;
176	free_list(p);
177
178	return(d);
179	}
180
181	/* Search through list for data element "d", and remove from
182	* list: Returns TRUE if found, false otherwise
183	*/
184	int
185	remove_from_list(d,list)
186	int d;
187	LIST **list;
188	{
189	LIST l,prev;
190
191	l = *list;
192	prev = NULL;
193
194	while(l)
195	{
196	if(LIST_DATA(l) == d)
197	{
198	if(l == *list)
199	list = LIST_NEXT(list);
200	else
201	SET_LIST_NEXT(prev,LIST_NEXT(l));
202
203	SET_LIST_NEXT(l,NULL);
204	free_list(l);
205	return(TRUE);
206	}
207	prev = l;
208	l = LIST_NEXT(l);
209	}
210	return(FALSE);
211	}
212
213
214
215
216
217
218
219
220
221