1 /*
2 * $LynxId: HTList.c,v 1.20 2016/11/24 15:29:50 tom Exp $
3 *
4 * A small List class HTList.c
5 * ==================
6 *
7 * A list is represented as a sequence of linked nodes of type HTList.
8 * The first node is a header which contains no object.
9 * New nodes are inserted between the header and the rest of the list.
10 */
11
12 #include <HTUtils.h>
13 #include <HTList.h>
14
15 #include <LYLeaks.h>
16
17 /* Create list.
18 */
HTList_new(void)19 HTList *HTList_new(void)
20 {
21 HTList *newList;
22
23 if ((newList = typeMalloc(HTList)) == NULL)
24 outofmem(__FILE__, "HTList_new");
25
26 newList->object = NULL;
27 newList->next = NULL;
28
29 return newList;
30 }
31
32 /* Delete list.
33 */
HTList_delete(HTList * me)34 void HTList_delete(HTList *me)
35 {
36 HTList *current;
37
38 while ((current = me)) {
39 me = me->next;
40 FREE(current);
41 }
42
43 return;
44 }
45
46 /* Reverse order of elements in list.
47 */
HTList_reverse(HTList * start)48 HTList *HTList_reverse(HTList *start)
49 {
50 HTList *cur, *succ;
51
52 if (!(start && start->next && (cur = start->next->next)))
53 return start;
54 start->next->next = NULL;
55 while (cur) {
56 succ = cur->next;
57 cur->next = start->next;
58 start->next = cur;
59 cur = succ;
60 }
61 return start;
62 }
63
64 /* Append a list to another.
65 *
66 * If successful, the second list will become empty but not freed.
67 */
HTList_appendList(HTList * start,HTList * tail)68 HTList *HTList_appendList(HTList *start,
69 HTList *tail)
70 {
71 HTList *temp = start;
72
73 if (!start) {
74 CTRACE((tfp,
75 "HTList: Trying to append list %p to a nonexisting list\n",
76 (void *) tail));
77 return NULL;
78 }
79 if (!(tail && tail->next))
80 return start;
81
82 while (temp->next)
83 temp = temp->next;
84
85 temp->next = tail->next;
86 tail->next = NULL; /* tail is now an empty list */
87 return start;
88 }
89
90 /* Link object to START of list (so it is pointed to by the head).
91 *
92 * Unlike HTList_addObject(), it does not malloc memory for HTList entry,
93 * it use already allocated memory which should not be free'd by any
94 * list operations (optimization).
95 */
HTList_linkObject(HTList * me,void * newObject,HTList * newNode)96 void HTList_linkObject(HTList *me, void *newObject,
97 HTList *newNode)
98 {
99 if (me) {
100 if (newNode->object == NULL && newNode->next == NULL) {
101 /* It is safe: */
102 newNode->object = newObject;
103 newNode->next = me->next;
104 me->next = newNode;
105
106 } else {
107 /*
108 * This node is already linked to some list (probably this one), so
109 * refuse changing node pointers to keep the list valid!!!
110 */
111 CTRACE((tfp, "*** HTList: Refuse linking already linked obj "));
112 CTRACE((tfp, "%p, node %p, list %p\n",
113 (void *) newObject, (void *) newNode, (void *) me));
114 }
115
116 } else {
117 CTRACE((tfp,
118 "HTList: Trying to link object %p to a nonexisting list\n",
119 newObject));
120 }
121
122 return;
123 }
124
125 /* Add object to START of list (so it is pointed to by the head).
126 */
HTList_addObject(HTList * me,void * newObject)127 void HTList_addObject(HTList *me, void *newObject)
128 {
129 HTList *newNode;
130
131 if (me) {
132 if ((newNode = typeMalloc(HTList)) == NULL)
133 outofmem(__FILE__, "HTList_addObject");
134
135 newNode->object = newObject;
136 newNode->next = me->next;
137 me->next = newNode;
138
139 } else {
140 CTRACE((tfp, "HTList: Trying to add object %p to a nonexisting list\n",
141 newObject));
142 }
143
144 return;
145 }
146
147 /* Append object to END of list (furthest from the head).
148 */
HTList_appendObject(HTList * me,void * newObject)149 void HTList_appendObject(HTList *me, void *newObject)
150 {
151 HTList *temp = me;
152
153 if (temp && newObject) {
154 while (temp->next)
155 temp = temp->next;
156 HTList_addObject(temp, newObject);
157 }
158
159 return;
160 }
161
162 /* Insert an object into the list at a specified position.
163 * If position is 0, this places the object at the head of the list
164 * and is equivalent to HTList_addObject().
165 */
HTList_insertObjectAt(HTList * me,void * newObject,int pos)166 void HTList_insertObjectAt(HTList *me, void *newObject,
167 int pos)
168 {
169 HTList *newNode;
170 HTList *temp = me;
171 HTList *prevNode;
172 int Pos = pos;
173
174 if (!temp) {
175 CTRACE((tfp, "HTList: Trying to add object %p to a nonexisting list\n",
176 newObject));
177 return;
178 }
179 if (Pos < 0) {
180 Pos = 0;
181 CTRACE((tfp, "HTList: Treating negative object position %d as %d.\n",
182 pos, Pos));
183 }
184
185 prevNode = temp;
186 while ((temp = temp->next)) {
187 if (Pos == 0) {
188 if ((newNode = typeMalloc(HTList)) == NULL)
189 outofmem(__FILE__, "HTList_addObjectAt");
190
191 newNode->object = newObject;
192 newNode->next = temp;
193 if (prevNode)
194 prevNode->next = newNode;
195 return;
196 }
197 prevNode = temp;
198 Pos--;
199 }
200 if (Pos >= 0)
201 HTList_addObject(prevNode, newObject);
202
203 return;
204 }
205
206 /* Unlink specified object from list.
207 * It does not free memory.
208 */
HTList_unlinkObject(HTList * me,void * oldObject)209 BOOL HTList_unlinkObject(HTList *me, void *oldObject)
210 {
211 HTList *temp = me;
212 HTList *prevNode;
213
214 if (temp && oldObject) {
215 while (temp->next) {
216 prevNode = temp;
217 temp = temp->next;
218 if (temp->object == oldObject) {
219 prevNode->next = temp->next;
220 temp->next = NULL;
221 temp->object = NULL;
222 return YES; /* Success */
223 }
224 }
225 }
226 return NO; /* object not found or NULL list */
227 }
228
229 /* Remove specified object from list.
230 */
HTList_removeObject(HTList * me,void * oldObject)231 BOOL HTList_removeObject(HTList *me, void *oldObject)
232 {
233 HTList *temp = me;
234 HTList *prevNode;
235
236 if (temp && oldObject) {
237 while (temp->next) {
238 prevNode = temp;
239 temp = temp->next;
240 if (temp->object == oldObject) {
241 prevNode->next = temp->next;
242 FREE(temp);
243 return YES; /* Success */
244 }
245 }
246 }
247 return NO; /* object not found or NULL list */
248 }
249
250 /* Remove object at a given position in the list, where 0 is the
251 * object pointed to by the head (returns a pointer to the element
252 * (->object) for the object, and NULL if the list is empty, or
253 * if it doesn't exist - Yuk!).
254 */
HTList_removeObjectAt(HTList * me,int position)255 void *HTList_removeObjectAt(HTList *me, int position)
256 {
257 HTList *temp = me;
258 HTList *prevNode;
259 int pos = position;
260 void *result = NULL;
261
262 if (temp != NULL && pos >= 0) {
263 prevNode = temp;
264 while ((temp = temp->next) != NULL) {
265 if (pos == 0) {
266 prevNode->next = temp->next;
267 result = temp->object;
268 FREE(temp);
269 break;
270 }
271 prevNode = temp;
272 pos--;
273 }
274 }
275
276 return result;
277 }
278
279 /* Unlink object from START of list (the Last one inserted
280 * via HTList_linkObject(), and pointed to by the head).
281 * It does not free memory.
282 */
HTList_unlinkLastObject(HTList * me)283 void *HTList_unlinkLastObject(HTList *me)
284 {
285 HTList *lastNode;
286 void *lastObject;
287
288 if (me && me->next) {
289 lastNode = me->next;
290 lastObject = lastNode->object;
291 me->next = lastNode->next;
292 lastNode->next = NULL;
293 lastNode->object = NULL;
294 return lastObject;
295
296 } else { /* Empty list */
297 return NULL;
298 }
299 }
300
301 /* Remove object from START of list (the Last one inserted
302 * via HTList_addObject(), and pointed to by the head).
303 */
HTList_removeLastObject(HTList * me)304 void *HTList_removeLastObject(HTList *me)
305 {
306 HTList *lastNode;
307 void *lastObject;
308
309 if (me && me->next) {
310 lastNode = me->next;
311 lastObject = lastNode->object;
312 me->next = lastNode->next;
313 FREE(lastNode);
314 return lastObject;
315
316 } else { /* Empty list */
317 return NULL;
318 }
319 }
320
321 /* Remove object from END of list (the First one inserted
322 * via HTList_addObject(), and furthest from the head).
323 */
HTList_removeFirstObject(HTList * me)324 void *HTList_removeFirstObject(HTList *me)
325 {
326 HTList *temp = me;
327 HTList *prevNode;
328 void *firstObject;
329
330 if (!temp)
331 return NULL;
332
333 prevNode = temp;
334 if (temp->next) {
335 while (temp->next) {
336 prevNode = temp;
337 temp = temp->next;
338 }
339 firstObject = temp->object;
340 prevNode->next = NULL;
341 FREE(temp);
342 return firstObject;
343
344 } else { /* Empty list */
345 return NULL;
346 }
347 }
348
349 /* Determine total number of objects in the list,
350 * not counting the head.
351 */
HTList_count(HTList * me)352 int HTList_count(HTList *me)
353 {
354 HTList *temp = me;
355 int count = 0;
356
357 if (temp)
358 while ((temp = temp->next))
359 count++;
360
361 return count;
362 }
363
364 /* Determine position of an object in the list (a value of 0
365 * means it is pointed to by the head; returns -1 if not found).
366 */
HTList_indexOf(HTList * me,void * object)367 int HTList_indexOf(HTList *me, void *object)
368 {
369 HTList *temp = me;
370 int position = 0;
371
372 if (temp) {
373 while ((temp = temp->next)) {
374 if (temp->object == object)
375 return position;
376 position++;
377 }
378 }
379
380 return -1; /* Object not in the list */
381 }
382
383 /* Return pointer to the object at a specified position in the list,
384 * where 0 is the object pointed to by the head (returns NULL if
385 * the list is empty, or if it doesn't exist - Yuk!).
386 */
HTList_objectAt(HTList * me,int position)387 void *HTList_objectAt(HTList *me, int position)
388 {
389 HTList *temp = me;
390 int pos = position;
391
392 if (!temp || pos < 0)
393 return NULL;
394
395 while ((temp = temp->next)) {
396 if (pos == 0)
397 return temp->object;
398 pos--;
399 }
400
401 return NULL; /* Reached the end of the list */
402 }
403