← Back to branch summary

~ubuntu-branches/ubuntu/edgy/lynx/edgy

« back to all changes in this revision

Viewing changes to WWW/Library/Implementation/HTList.c

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2004-09-16 12:14:10 UTC
  • Revision ID: james.westby@ubuntu.com-20040916121410-cz1gu92c4nqfeyrg
Tags: upstream-2.8.5
Import upstream version 2.8.5

Show diffs side-by-side

added added

removed removed

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