1 /* -*- c -*- */
2
3 /*
4 * list.c
5 *
6 * chpp
7 *
8 * Copyright (C) 1998 Mark Probst
9 *
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU General Public License
12 * as published by the Free Software Foundation; either version 2
13 * of the License, or (at your option) any later version.
14 *
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, write to the Free Software
22 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
23 */
24
25 #include <string.h>
26
27 #include "memory.h"
28
29 #include "list.h"
30
31 static listElement*
allocListElement(list * lst)32 allocListElement (list *lst)
33 {
34 return (listElement*)memXAlloc(lst->elementAllocSize);
35 }
36
37 list*
listNewList(list * lst,int elementSize)38 listNewList (list *lst, int elementSize)
39 {
40 lst->first = lst->last = 0;
41 lst->elementSize = elementSize;
42 if (elementSize <= sizeof(int))
43 lst->elementAllocSize = sizeof(listElement);
44 else
45 lst->elementAllocSize = sizeof(listElement) + elementSize - sizeof(int);
46 lst->length = 0;
47 lst->pointerType = 0;
48
49 return lst;
50 }
51
52 list*
listNewPointerList(list * lst)53 listNewPointerList (list *lst)
54 {
55 lst->first = lst->last = 0;
56 lst->elementSize = sizeof(void*);
57 if (lst->elementSize <= sizeof(int))
58 lst->elementAllocSize = sizeof(listElement);
59 else
60 lst->elementAllocSize = sizeof(listElement) + lst->elementSize - sizeof(int);
61 lst->length = 0;
62 lst->pointerType = 1;
63
64 return lst;
65 }
66
67 int
listLength(list * lst)68 listLength (list *lst)
69 {
70 return lst->length;
71 }
72
73 listElement*
listAppend(list * lst,void * data)74 listAppend (list *lst, void *data)
75 {
76 listElement *elem = allocListElement(lst);
77
78 listSetElementData(lst, elem, data);
79
80 elem->prev = lst->last;
81 elem->next = 0;
82
83 if (lst->last == 0)
84 lst->first = lst->last = elem;
85 else
86 lst->last = lst->last->next = elem;
87
88 ++lst->length;
89
90 return elem;
91 }
92
93 listElement*
listPrepend(list * lst,void * data)94 listPrepend (list *lst, void *data)
95 {
96 listElement *elem = allocListElement(lst);
97
98 listSetElementData(lst, elem, data);
99
100 elem->prev = 0;
101 elem->next = lst->first;
102
103 if (lst->first == 0)
104 lst->first = lst->last = elem;
105 else
106 lst->first = lst->first->prev = elem;
107
108 ++lst->length;
109
110 return elem;
111 }
112
113 listElement*
listFirstElement(list * lst)114 listFirstElement (list *lst)
115 {
116 return lst->first;
117 }
118
119 listElement*
listLastElement(list * lst)120 listLastElement (list *lst)
121 {
122 return lst->last;
123 }
124
125 listElement*
listNThElement(list * lst,int n)126 listNThElement (list *lst, int n)
127 {
128 listElement *elem;
129 int i;
130
131 if (n < 0 || n >= lst->length)
132 return 0;
133
134 elem = lst->first;
135 for (i = 0; i < n; ++i)
136 elem = elem->next;
137
138 return elem;
139 }
140
141 listElement*
listNextElement(listElement * elem)142 listNextElement (listElement *elem)
143 {
144 return elem->next;
145 }
146
147 listElement*
listPreviousElement(listElement * elem)148 listPreviousElement (listElement *elem)
149 {
150 return elem->prev;
151 }
152
153 listElement*
listInsertBeforeElement(list * lst,listElement * elem,void * data)154 listInsertBeforeElement (list *lst, listElement *elem, void *data)
155 {
156 listElement *newElem = allocListElement(lst);
157
158 listSetElementData(lst, newElem, data);
159
160 newElem->prev = elem->prev;
161 newElem->next = elem;
162
163 if (elem->prev != 0)
164 elem->prev->next = newElem;
165 else
166 lst->first = newElem;
167
168 elem->prev = newElem;
169
170 ++lst->length;
171
172 return newElem;
173 }
174
175 listElement*
listInsertAfterElement(list * lst,listElement * elem,void * data)176 listInsertAfterElement (list *lst, listElement *elem, void *data)
177 {
178 listElement *newElem = allocListElement(lst);
179
180 listSetElementData(lst, newElem, data);
181
182 newElem->prev = elem;
183 newElem->next = elem->next;
184
185 if (elem->next != 0)
186 elem->next->prev = newElem;
187 else
188 lst->last = newElem;
189
190 elem->next = newElem;
191
192 ++lst->length;
193
194 return newElem;
195 }
196
197 void
listRemoveElement(list * lst,listElement * elem)198 listRemoveElement (list *lst, listElement *elem)
199 {
200 if (elem->prev != 0)
201 elem->prev->next = elem->next;
202 else
203 lst->first = elem->next;
204
205 if (elem->next != 0)
206 elem->next->prev = elem->prev;
207 else
208 lst->last = elem->prev;
209
210 --lst->length;
211 }
212
213 void*
listElementData(list * lst,listElement * elem)214 listElementData (list *lst, listElement *elem)
215 {
216 if (lst->pointerType)
217 return *(void**)&elem->data;
218 else
219 return (void*)&elem->data;
220 }
221
222 void*
listNThElementData(list * lst,int n)223 listNThElementData (list *lst, int n)
224 {
225 return listElementData(lst, listNThElement(lst, n));
226 }
227
228 void
listSetElementData(list * lst,listElement * elem,void * data)229 listSetElementData (list *lst, listElement *elem, void *data)
230 {
231 if (lst->pointerType)
232 memcpy(&elem->data, &data, lst->elementSize);
233 else
234 memcpy(&elem->data, data, lst->elementSize);
235 }
236