LibRCG  3.1.1
list.c
Go to the documentation of this file.
1 
9 #include <stdlib.h>
10 #include "list.h"
11 
12 
14 {
15  List list=malloc(sizeof(SList));
16  if(list)
17  {
18  list->size=0;
19  list->first=NULL;
20  list->last=NULL;
21  }
22  return list;
23 }
24 
25 //==============================================================================
26 
27 void listDelete(List list)
28 {
29  ListNode this,next;
30  if(!list->size) free(list);
31  else
32  {
33  for(this=list->first,next=this->next;next;this=next,next=next->next)
34  free(this);
35  free(this);
36  free(list);
37  }
38 }
39 
40 //==============================================================================
41 
42 int listInsertFst(List list,void* value)
43 {
44  int result=0;
45  ListNode new;
46  if(!list->size)
47  {
48  new=malloc(sizeof(SListNode));
49  if(new)
50  {
51  new->value=value;
52  new->next=NULL;
53  new->prev=NULL;
54  list->size++;
55  list->first=new;
56  list->last=new;
57  }
58  else result=1;
59  }
60  else
61  {
62  new=malloc(sizeof(SListNode));
63  if(new)
64  {
65  new->value=value;
66  new->next=list->first;
67  new->prev=NULL;
68  list->size++;
69  list->first->prev=new;
70  list->first=new;
71  }
72  else result=1;
73  }
74  return result;
75 }
76 
77 //==============================================================================
78 
79 int listInsertLst(List list,void* value)
80 {
81  int result=0;
82  ListNode new;
83  if(!list->size)
84  {
85  new=malloc(sizeof(SListNode));
86  if(new)
87  {
88  new->value=value;
89  new->next=NULL;
90  new->prev=NULL;
91  list->size++;
92  list->first=new;
93  list->last=new;
94  }
95  else result=1;
96  }
97  else
98  {
99  new=malloc(sizeof(SListNode));
100  if(new)
101  {
102  new->value=value;
103  new->next=NULL;
104  new->prev=list->last;
105  list->size++;
106  list->last->next=new;
107  list->last=new;
108  }
109  else result=1;
110  }
111  return result;
112 }
113 
114 //==============================================================================
115 
116 int listInsertAt(List list,int index,void* value)
117 {
118  int size=listSize(list),result=0;
119  ListNode aux,new;
120  if(index<0||index>size) result=1;
121  else if(!index) result=listInsertFst(list,value);
122  else if(index==size) result=listInsertLst(list,value);
123  else if(index>size/2)
124  {
125  for(index=size-index,aux=list->last;index>0;index--,aux=aux->prev);
126  new=malloc(sizeof(SListNode));
127  if(new)
128  {
129  new->value=value;
130  new->next=aux->next;
131  new->prev=aux;
132  list->size++;
133  aux->next->prev=new;
134  aux->next=new;
135  }
136  else result=1;
137  }
138  else
139  {
140  for(aux=list->first;index>0;index--,aux=aux->next);
141  new=malloc(sizeof(SListNode));
142  if(new)
143  {
144  new->value=value;
145  new->next=aux;
146  new->prev=aux->prev;
147  list->size++;
148  aux->prev->next=new;
149  aux->prev=new;
150  }
151  else result=0;
152  }
153  return result;
154 }
155 
156 //==============================================================================
157 
158 int listRemoveFst(List list,void** value)
159 {
160  int result=0;
161  ListNode aux;
162  if(!list->size)
163  {
164  if(value) *value=NULL;
165  result=1;
166  }
167  else if(list->size==1)
168  {
169  if(value) *value=list->first->value;
170  free(list->first);
171  list->first=NULL;
172  list->last=NULL;
173  list->size=0;
174  }
175  else
176  {
177  if(value) *value=list->first->value;
178  aux=list->first;
179  list->first->next->prev=NULL;
180  list->first=list->first->next;
181  free(aux);
182  list->size--;
183  }
184  return result;
185 }
186 
187 //==============================================================================
188 
189 int listRemoveLst(List list,void** value)
190 {
191  int result=0;
192  ListNode aux;
193  if(!list->size)
194  {
195  if(value) *value=NULL;
196  result=1;
197  }
198  else if(list->size==1)
199  {
200  if(value) *value=list->last->value;
201  free(list->last);
202  list->first=NULL;
203  list->last=NULL;
204  list->size=0;
205  }
206  else
207  {
208  if(value) *value=list->last->value;
209  aux=list->last;
210  list->last->prev->next=NULL;
211  list->last=list->last->prev;
212  free(aux);
213  list->size--;
214  }
215  return result;
216 }
217 
218 //==============================================================================
219 
220 int listRemoveAt(List list,int index,void** value)
221 {
222  int size=listSize(list),result=0;
223  ListNode aux;
224  if(index<0||index>size-1) result=1;
225  else if(index==0) result=listRemoveFst(list,value);
226  else if(index==size-1) result=listRemoveLst(list,value);
227  else if(index>size/2)
228  {
229  for(aux=list->last,index=size-index-1;index>0;index--,aux=aux->prev);
230  if(value) *value=aux->value;
231  aux->prev->next=aux->next;
232  aux->next->prev=aux->prev;
233  free(aux);
234  list->size--;
235  }
236  else
237  {
238  for(aux=list->first;index>0;index--,aux=aux->next);
239  if(value) *value=aux->value;
240  aux->prev->next=aux->next;
241  aux->next->prev=aux->prev;
242  free(aux);
243  list->size--;
244  }
245  return result;
246 }
247 
248 //==============================================================================
249 
250 int listFst(List list,void** value)
251 {
252  int result=0;
253  if(!list->size)
254  {
255  *value=NULL;
256  result=1;
257  }
258  else *value=list->first->value;
259  return result;
260 }
261 
262 //==============================================================================
263 
264 int listLst(List list,void** value)
265 {
266  int result=0;
267  if(!list->size)
268  {
269  *value=NULL;
270  result=1;
271  }
272  else *value=list->last->value;
273  return result;
274 }
275 
276 //==============================================================================
277 
278 int listAt(List list,int index,void** value)
279 {
280  int size=listSize(list),result=0;
281  ListNode aux;
282  if(index<0||index>size-1)
283  {
284  *value=NULL;
285  result=1;
286  }
287  else
288  {
289  if(index>size/2) for(index=size-index-1,aux=list->last;index>0;index--,aux=aux->prev);
290  else for(aux=list->first;index>0;index--,aux=aux->next);
291  *value=aux->value;
292  }
293  return result;
294 }
295 
296 //==============================================================================
297 
298 int listSize(List list)
299 {
300  return list->size;
301 }
302 
303 //==============================================================================
304 
305 int listMap(List list,void(*fun)(void*))
306 {
307  int result=0;
308  ListNode aux;
309  if(!list->size) result=1;
310  else
311  {
312  for(aux=list->first;aux;aux=aux->next)
313  fun(aux->value);
314  }
315  return result;
316 }
317 
318 //==============================================================================
319 
321 {
322  int ctrl;
323  ListNode aux;
324  Iterator it;
325  it=newIt(list->size);
326  for(aux=list->first,ctrl=0;aux&&!ctrl;aux=aux->next)
327  ctrl=itAdd(it,aux->value);
328  if(ctrl)
329  {
330  itDelete(it);
331  it=NULL;
332  }
333  return it;
334 }
ListNode last
Last node.
Definition: list.h:44
struct sListNode * next
Next node.
Definition: list.h:26
void listDelete(List list)
Deletes a list.
Definition: list.c:27
int listAt(List list, int index, void **value)
Provides the element at the specified position of a list.
Definition: list.c:278
int listRemoveAt(List list, int index, void **value)
Removes the element at the specified position of a list.
Definition: list.c:220
int listFst(List list, void **value)
Provides the value at the first position of a list.
Definition: list.c:250
int listInsertLst(List list, void *value)
Inserts an element at the end of a list.
Definition: list.c:79
int size
Number of elements of this linked list.
Definition: list.h:40
int listRemoveLst(List list, void **value)
Removes the last element of a list.
Definition: list.c:189
int listRemoveFst(List list, void **value)
Removes the first element of a list.
Definition: list.c:158
Iterator structure.
Definition: iterator.h:17
void itDelete(Iterator it)
Deletes an iterator.
Definition: iterator.c:36
Implementation of a linked list.
int listMap(List list, void(*fun)(void *))
Applies a function to the elements of a list.
Definition: list.c:305
int itAdd(Iterator it, void *val)
Adds an element to an iterator.
Definition: iterator.c:44
ListNode first
First node.
Definition: list.h:42
Linked list node structure.
Definition: list.h:19
struct sListNode * prev
Previous node.
Definition: list.h:24
int listInsertAt(List list, int index, void *value)
Inserts an new element at the specified position of a list.
Definition: list.c:116
Iterator listIterator(List list)
Creates an iterator from a list.
Definition: list.c:320
Linked list structure.
Definition: list.h:37
int listInsertFst(List list, void *value)
Inserts an element at the beginning of a list.
Definition: list.c:42
int listSize(List list)
Returns the size of a list.
Definition: list.c:298
void * value
Node's value.
Definition: list.h:22
int listLst(List list, void **value)
Provides the value at the last position of a list.
Definition: list.c:264
List newList(void)
Creates a list.
Definition: list.c:13
Iterator newIt(int size)
Creates an iterator.
Definition: iterator.c:12

LibRCG © 2004-2015   Rui Carlos Gonçalves