Annotation of libwww/Library/src/HTList.c, revision 2.27
2.8 frystyk 1: /* HTList.c
2: ** MANAGEMENT OF LINKED LISTS
3: **
2.12 frystyk 4: ** (c) COPYRIGHT MIT 1995.
2.8 frystyk 5: ** Please first read the full copyright statement in the file COPYRIGH.
2.27 ! eric 6: ** @(#) $Id: HTList.c,v 2.26 1996/12/03 05:46:20 eric Exp $
1.1 timbl 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:
2.10 frystyk 13: /* Library include files */
2.22 frystyk 14: #include "sysdep.h"
2.10 frystyk 15: #include "HTUtils.h"
1.1 timbl 16: #include "HTList.h"
17:
2.17 frystyk 18: PUBLIC HTList * HTList_new (void)
1.1 timbl 19: {
2.20 frystyk 20: HTList *newList;
21: if ((newList = (HTList *) HT_CALLOC(1, sizeof (HTList))) == NULL)
22: HT_OUTOFMEM("HTList_new");
2.17 frystyk 23: newList->object = NULL;
24: newList->next = NULL;
25: return newList;
1.1 timbl 26: }
27:
2.17 frystyk 28: PUBLIC BOOL HTList_delete (HTList * me)
1.1 timbl 29: {
2.15 frystyk 30: if (me) {
31: HTList *current;
32: while ((current = me)) {
33: me = me->next;
2.20 frystyk 34: HT_FREE(current);
2.15 frystyk 35: }
36: return YES;
37: }
38: return NO;
1.1 timbl 39: }
40:
2.17 frystyk 41: PUBLIC BOOL HTList_addObject (HTList * me, void * newObject)
1.1 timbl 42: {
2.11 frystyk 43: if (me) {
2.20 frystyk 44: HTList *newNode;
45: if ((newNode = (HTList *) HT_CALLOC(1, sizeof(HTList))) == NULL)
46: HT_OUTOFMEM("HTList_addObject");
2.11 frystyk 47: newNode->object = newObject;
48: newNode->next = me->next;
49: me->next = newNode;
50: return YES;
51: } else {
2.25 frystyk 52: if (CORE_TRACE)
53: HTTrace("HTList...... Can not add object %p to nonexisting list\n",
2.11 frystyk 54: newObject);
55: }
56: return NO;
1.1 timbl 57: }
58:
2.18 frystyk 59: PUBLIC BOOL HTList_appendObject (HTList * me, void * newObject)
60: {
61: if (me) {
62: while (me->next) me = me->next;
63: return HTList_addObject(me, newObject);
64: }
65: return NO;
66: }
67:
2.27 ! eric 68: PUBLIC BOOL HTList_removeObject (HTList * me, void * oldObject)
1.1 timbl 69: {
2.11 frystyk 70: if (me) {
71: HTList *previous;
72: while (me->next) {
73: previous = me;
74: me = me->next;
2.19 frystyk 75: if (me->object == oldObject) {
2.11 frystyk 76: previous->next = me->next;
2.20 frystyk 77: HT_FREE(me);
2.11 frystyk 78: return YES; /* Success */
79: }
80: }
2.26 eric 81: }
82: return NO; /* object not found or NULL list */
83: }
84:
2.27 ! eric 85: PUBLIC BOOL HTList_quickRemoveElement (HTList * me, HTList * last)
2.26 eric 86: {
87: if (me && last) {
88: last->next = me->next;
89: HT_FREE(me);
90: return YES; /* Success */
1.1 timbl 91: }
2.11 frystyk 92: return NO; /* object not found or NULL list */
1.1 timbl 93: }
94:
2.27 ! eric 95: PUBLIC BOOL HTList_removeObjectAll (HTList * me, void * oldObject)
2.25 frystyk 96: {
97: BOOL found = NO;
98: if (me) {
99: HTList *previous;
100: while (me->next) {
101: previous = me;
102: me = me->next;
103: if (me->object == oldObject) {
104: previous->next = me->next;
105: HT_FREE(me);
106: found = YES; /* At least one object found */
107: }
108: }
109: }
110: return found;
111: }
112:
2.17 frystyk 113: PUBLIC void * HTList_removeLastObject (HTList * me)
1.1 timbl 114: {
2.17 frystyk 115: if (me && me->next) {
116: HTList *lastNode = me->next;
117: void * lastObject = lastNode->object;
118: me->next = lastNode->next;
2.20 frystyk 119: HT_FREE(lastNode);
2.17 frystyk 120: return lastObject;
121: } else /* Empty list */
122: return NULL;
123: }
124:
125: PUBLIC void * HTList_removeFirstObject (HTList * me)
126: {
127: if (me && me->next) {
128: HTList * prevNode;
129: void *firstObject;
130: while (me->next) {
131: prevNode = me;
132: me = me->next;
133: }
134: firstObject = me->object;
135: prevNode->next = NULL;
2.20 frystyk 136: HT_FREE(me);
2.17 frystyk 137: return firstObject;
2.24 frystyk 138: } else /* Empty list */
139: return NULL;
140: }
141:
142: PUBLIC void * HTList_firstObject (HTList * me)
143: {
144: if (me && me->next) {
145: HTList * prevNode;
146: while (me->next) {
147: prevNode = me;
148: me = me->next;
149: }
150: return me->object;
2.17 frystyk 151: } else /* Empty list */
152: return NULL;
1.1 timbl 153: }
154:
2.17 frystyk 155: PUBLIC int HTList_count (HTList * me)
1.1 timbl 156: {
2.17 frystyk 157: int count = 0;
158: if (me)
159: while ((me = me->next))
160: count++;
161: return count;
1.1 timbl 162: }
163:
2.17 frystyk 164: PUBLIC int HTList_indexOf (HTList * me, void * object)
1.1 timbl 165: {
2.17 frystyk 166: if (me) {
167: int position = 0;
168: while ((me = me->next)) {
169: if (me->object == object)
170: return position;
171: position++;
172: }
1.1 timbl 173: }
2.17 frystyk 174: return -1;
2.27 ! eric 175: }
! 176:
! 177: PUBLIC HTList * HTList_elementOf (HTList * cur, void * object, HTList ** pLast)
! 178: {
! 179: HTList * last = cur;
! 180: void * pres;
! 181:
! 182: while ((pres = HTList_nextObject(cur))) {
! 183: if (pres == object) {
! 184: if (pLast)
! 185: *pLast = last;
! 186: return cur;
! 187: }
! 188: last = cur;
! 189: }
! 190:
! 191: /*
! 192: ** didn't find object, but return end of list so it is easy to append
! 193: */
! 194: if (pLast)
! 195: *pLast = last;
! 196: return NULL;
1.1 timbl 197: }
198:
2.17 frystyk 199: PUBLIC void * HTList_objectAt (HTList * me, int position)
1.1 timbl 200: {
2.17 frystyk 201: if (position < 0)
202: return NULL;
203: if (me) {
204: while ((me = me->next)) {
205: if (position == 0)
206: return me->object;
207: position--;
208: }
1.1 timbl 209: }
2.17 frystyk 210: return NULL; /* Reached the end of the list */
1.1 timbl 211: }
2.10 frystyk 212:
2.17 frystyk 213: PUBLIC void * HTList_removeObjectAt (HTList * me, int position)
2.10 frystyk 214: {
2.17 frystyk 215: if (position < 0)
216: return NULL;
217: if (me) {
218: HTList * prevNode;
219: prevNode = me;
220: while ((me = me->next)) {
221: if (position == 0) {
222: prevNode->next = me->next;
223: return me->object;
224: }
225: prevNode = me;
226: position--;
227: }
2.10 frystyk 228: }
2.17 frystyk 229: return NULL; /* Reached the end of the list */
2.10 frystyk 230: }
2.25 frystyk 231:
232: /*
233: ** Do an insertion sort algorithm on the list. An empty list is already
234: ** sorted and so is a single element list.
235: */
236: PUBLIC BOOL HTList_insertionSort (HTList * head, HTComparer * comp)
237: {
238: HTList *tail, *q, *r, *p;
239: if (head && head->next && comp) {
240: #if 0
241: HTList * tail = head->next; /* Tail of the sorted list */
242: #else
243: tail = head->next;
244: #endif
245:
246: while (tail->next) {
247: #if 0
248: HTList * q = tail->next; /* Head of unsorted list */
249: #else
250: q = tail->next;
251: #endif
252:
253: /*
254: ** Depending on the return status of the comparer we either move
255: ** the sentinel down the list or search the sorted sublist to
256: ** insert it.
257: */
258: if (comp(q->object, head->next->object) >= 0) {
259: tail->next = q->next;
260: q->next = head->next;
261: head->next = q;
262: } else {
263: #if 0
264: HTList * r = head->next;
265: HTList * p = r->next;
266: #else
267: r = head->next;
268: p = r->next;
269: #endif
270: while (comp(q->object, p->object) < 0) {
271: r = p;
272: p = r->next;
273: }
274:
275: /*
276: ** If sentinel was found then q is already in right place.
277: ** Otherwise we'll have to move it
278: */
279: if (q == p)
280: tail = q;
281: else {
282: tail->next = q->next;
283: q->next = p;
284: r->next = q;
285: }
286: }
287: }
288: return YES;
289: } else {
290: if (CORE_TRACE)
291: HTTrace("List........ Empty list or no sort algorithm\n");
292: }
293: return NO;
294: }
295:
Webmaster
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to HTList.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Public] / libwww / Library / src