1 /* HTList.c
2 ** MANAGEMENT OF LINKED LISTS
3 **
4 ** (c) COPYRIGHT MIT 1995.
5 ** Please first read the full copyright statement in the file COPYRIGH.
6 ** @(#) $Id$
7 **
8 ** A list is represented as a sequence of linked nodes of type HTList.
9 ** The first node is a header which contains no object.
10 ** New nodes are inserted between the header and the rest of the list.
11 */
12
13 /* Library include files */
14 #include "wwwsys.h"
15 #include "HTUtils.h"
16 #include "HTList.h"
17
HTList_new(void)18 PUBLIC HTList * HTList_new (void)
19 {
20 HTList *newList;
21 if ((newList = (HTList *) HT_CALLOC(1, sizeof (HTList))) == NULL)
22 HT_OUTOFMEM("HTList_new");
23 newList->object = NULL;
24 newList->next = NULL;
25 return newList;
26 }
27
HTList_delete(HTList * me)28 PUBLIC BOOL HTList_delete (HTList * me)
29 {
30 if (me) {
31 HTList *current;
32 while ((current = me)) {
33 me = me->next;
34 HT_FREE(current);
35 }
36 return YES;
37 }
38 return NO;
39 }
40
HTList_addObject(HTList * me,void * newObject)41 PUBLIC BOOL HTList_addObject (HTList * me, void * newObject)
42 {
43 if (me) {
44 HTList *newNode;
45 if ((newNode = (HTList *) HT_CALLOC(1, sizeof(HTList))) == NULL)
46 HT_OUTOFMEM("HTList_addObject");
47 newNode->object = newObject;
48 newNode->next = me->next;
49 me->next = newNode;
50 return YES;
51 } else {
52 HTTRACE(CORE_TRACE, "HTList...... Can not add object %p to nonexisting list\n" _
53 newObject);
54 }
55 return NO;
56 }
57
HTList_appendObject(HTList * me,void * newObject)58 PUBLIC BOOL HTList_appendObject (HTList * me, void * newObject)
59 {
60 if (me) {
61 while (me->next) me = me->next;
62 return HTList_addObject(me, newObject);
63 }
64 return NO;
65 }
66
HTList_removeObject(HTList * me,void * oldObject)67 PUBLIC BOOL HTList_removeObject (HTList * me, void * oldObject)
68 {
69 if (me) {
70 HTList *previous;
71 while (me->next) {
72 previous = me;
73 me = me->next;
74 if (me->object == oldObject) {
75 previous->next = me->next;
76 HT_FREE(me);
77 return YES; /* Success */
78 }
79 }
80 }
81 return NO; /* object not found or NULL list */
82 }
83
HTList_addList(HTList * me,void * newObject)84 PUBLIC HTList * HTList_addList (HTList * me, void * newObject)
85 {
86 if (me) {
87 HTList *newNode;
88 if ((newNode = (HTList *) HT_CALLOC(1, sizeof(HTList))) == NULL)
89 HT_OUTOFMEM("HTList_addObject");
90 newNode->object = newObject;
91 newNode->next = me->next;
92 me->next = newNode;
93 return newNode;
94 } else {
95 HTTRACE(CORE_TRACE, "HTList...... Can not add object %p to nonexisting List\n" _ newObject);
96 }
97 return (HTList *) NULL;
98 }
99
HTList_appendList(HTList * me,void * newObject)100 PUBLIC HTList * HTList_appendList (HTList * me, void *newObject)
101 {
102 if (me) {
103 while (me->next)
104 me = me->next;
105 return HTList_addList(me, newObject);
106 }
107 return (HTList *) NULL;
108 }
109
110
HTList_quickRemoveElement(HTList * me,HTList * last)111 PUBLIC BOOL HTList_quickRemoveElement (HTList * me, HTList * last)
112 {
113 if (me && last) {
114 last->next = me->next;
115 HT_FREE(me);
116 return YES; /* Success */
117 }
118 return NO; /* object not found or NULL list */
119 }
120
HTList_removeObjectAll(HTList * me,void * oldObject)121 PUBLIC BOOL HTList_removeObjectAll (HTList * me, void * oldObject)
122 {
123 BOOL found = NO;
124
125 if (me)
126 {
127 HTList* i;
128
129 while ((i = me->next))
130 {
131 if (i->object == oldObject)
132 {
133 me->next = i->next;
134 HT_FREE(i);
135 found = YES; /* At least one object found */
136 }
137 else
138 {
139 me = i;
140 }
141 }
142 }
143
144 return found;
145 }
146
HTList_removeLastObject(HTList * me)147 PUBLIC void * HTList_removeLastObject (HTList * me)
148 {
149 if (me && me->next) {
150 HTList *lastNode = me->next;
151 void * lastObject = lastNode->object;
152 me->next = lastNode->next;
153 HT_FREE(lastNode);
154 return lastObject;
155 } else /* Empty list */
156 return NULL;
157 }
158
HTList_removeFirstObject(HTList * me)159 PUBLIC void * HTList_removeFirstObject (HTList * me)
160 {
161 if (me && me->next) {
162 HTList * prevNode;
163 void *firstObject;
164 while (me->next) {
165 prevNode = me;
166 me = me->next;
167 }
168 firstObject = me->object;
169 prevNode->next = NULL;
170 HT_FREE(me);
171 return firstObject;
172 } else /* Empty list */
173 return NULL;
174 }
175
HTList_firstObject(HTList * me)176 PUBLIC void * HTList_firstObject (HTList * me)
177 {
178 if (me && me->next) {
179 HTList * prevNode;
180 while (me->next) {
181 prevNode = me;
182 me = me->next;
183 }
184 return me->object;
185 } else /* Empty list */
186 return NULL;
187 }
188
HTList_count(HTList * me)189 PUBLIC int HTList_count (HTList * me)
190 {
191 int count = 0;
192 if (me)
193 while ((me = me->next))
194 count++;
195 return count;
196 }
197
HTList_indexOf(HTList * me,void * object)198 PUBLIC int HTList_indexOf (HTList * me, void * object)
199 {
200 if (me) {
201 int position = 0;
202 while ((me = me->next)) {
203 if (me->object == object)
204 return position;
205 position++;
206 }
207 }
208 return -1;
209 }
210
HTList_indexOfElement(HTList * me,HTList * element)211 PUBLIC int HTList_indexOfElement (HTList * me, HTList * element)
212 {
213 if (me) {
214 int position = 0;
215 if (me == element)
216 return -1;
217 while ((me = me->next)) {
218 if (me == element)
219 return position;
220 position++;
221 }
222 }
223 return -2;
224 }
225
HTList_elementOf(HTList * cur,void * object,HTList ** pLast)226 PUBLIC HTList * HTList_elementOf (HTList * cur, void * object, HTList ** pLast)
227 {
228 HTList * last = cur;
229 void * pres;
230
231 while ((pres = HTList_nextObject(cur))) {
232 if (pres == object) {
233 if (pLast)
234 *pLast = last;
235 return cur;
236 }
237 last = cur;
238 }
239
240 /*
241 ** didn't find object, but return end of list so it is easy to append
242 */
243 if (pLast)
244 *pLast = last;
245 return NULL;
246 }
247
HTList_objectAt(HTList * me,int position)248 PUBLIC void * HTList_objectAt (HTList * me, int position)
249 {
250 if (position < 0)
251 return NULL;
252 if (me) {
253 while ((me = me->next)) {
254 if (position == 0)
255 return me->object;
256 position--;
257 }
258 }
259 return NULL; /* Reached the end of the list */
260 }
261
HTList_removeObjectAt(HTList * me,int position)262 PUBLIC void * HTList_removeObjectAt (HTList * me, int position)
263 {
264 if (position < 0)
265 return NULL;
266 if (me) {
267 HTList * prevNode;
268 prevNode = me;
269 while ((me = me->next)) {
270 if (position == 0) {
271 prevNode->next = me->next;
272 return me->object;
273 }
274 prevNode = me;
275 position--;
276 }
277 }
278 return NULL; /* Reached the end of the list */
279 }
280
281 /*
282 ** Do an insertion sort algorithm on the list. An empty list is already
283 ** sorted and so is a single element list.
284 */
HTList_insertionSort(HTList * head,HTComparer * comp)285 PUBLIC BOOL HTList_insertionSort (HTList * head, HTComparer * comp)
286 {
287 HTList *tail, *q, *r, *p;
288 if (head && head->next && comp) {
289 tail = head->next;
290 while (tail->next) {
291 q = tail->next;
292
293 /*
294 ** Depending on the return status of the comparer we either move
295 ** the sentinel down the list or search the sorted sublist to
296 ** insert it.
297 */
298 if (comp(q->object, head->next->object) >= 0) {
299 tail->next = q->next;
300 q->next = head->next;
301 head->next = q;
302 } else {
303 r = head->next;
304 p = r->next;
305 while (comp(q->object, p->object) < 0) {
306 r = p;
307 p = r->next;
308 }
309
310 /*
311 ** If sentinel was found then q is already in right place.
312 ** Otherwise we'll have to move it
313 */
314 if (q == p)
315 tail = q;
316 else {
317 tail->next = q->next;
318 q->next = p;
319 r->next = q;
320 }
321 }
322 }
323 return YES;
324 } else {
325 HTTRACE(CORE_TRACE, "List........ Empty list or no sort algorithm\n");
326 }
327 return NO;
328 }
329
330