Annotation of libwww/Library/src/HTList.c, revision 2.29
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.29 ! frystyk 6: ** @(#) $Id: HTList.c,v 2.28 1996/12/13 22:06:14 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.28 eric 175: }
176:
177: PUBLIC int HTList_indexOfElement (HTList * me, HTList * element)
178: {
179: if (me) {
180: int position = 0;
181: if (me == element)
182: return -1;
183: while ((me = me->next)) {
184: if (me == element)
185: return position;
186: position++;
187: }
188: }
189: return -2;
2.27 eric 190: }
191:
192: PUBLIC HTList * HTList_elementOf (HTList * cur, void * object, HTList ** pLast)
193: {
194: HTList * last = cur;
195: void * pres;
196:
197: while ((pres = HTList_nextObject(cur))) {
198: if (pres == object) {
199: if (pLast)
200: *pLast = last;
201: return cur;
202: }
203: last = cur;
204: }
205:
206: /*
207: ** didn't find object, but return end of list so it is easy to append
208: */
209: if (pLast)
210: *pLast = last;
211: return NULL;
1.1 timbl 212: }
213:
2.17 frystyk 214: PUBLIC void * HTList_objectAt (HTList * me, int position)
1.1 timbl 215: {
2.17 frystyk 216: if (position < 0)
217: return NULL;
218: if (me) {
219: while ((me = me->next)) {
220: if (position == 0)
221: return me->object;
222: position--;
223: }
1.1 timbl 224: }
2.17 frystyk 225: return NULL; /* Reached the end of the list */
1.1 timbl 226: }
2.10 frystyk 227:
2.17 frystyk 228: PUBLIC void * HTList_removeObjectAt (HTList * me, int position)
2.10 frystyk 229: {
2.17 frystyk 230: if (position < 0)
231: return NULL;
232: if (me) {
233: HTList * prevNode;
234: prevNode = me;
235: while ((me = me->next)) {
236: if (position == 0) {
237: prevNode->next = me->next;
238: return me->object;
239: }
240: prevNode = me;
241: position--;
242: }
2.10 frystyk 243: }
2.17 frystyk 244: return NULL; /* Reached the end of the list */
2.10 frystyk 245: }
2.25 frystyk 246:
247: /*
248: ** Do an insertion sort algorithm on the list. An empty list is already
249: ** sorted and so is a single element list.
250: */
251: PUBLIC BOOL HTList_insertionSort (HTList * head, HTComparer * comp)
252: {
253: HTList *tail, *q, *r, *p;
254: if (head && head->next && comp) {
255: tail = head->next;
256: while (tail->next) {
257: q = tail->next;
258:
259: /*
260: ** Depending on the return status of the comparer we either move
261: ** the sentinel down the list or search the sorted sublist to
262: ** insert it.
263: */
264: if (comp(q->object, head->next->object) >= 0) {
265: tail->next = q->next;
266: q->next = head->next;
267: head->next = q;
268: } else {
269: r = head->next;
270: p = r->next;
271: while (comp(q->object, p->object) < 0) {
272: r = p;
273: p = r->next;
274: }
275:
276: /*
277: ** If sentinel was found then q is already in right place.
278: ** Otherwise we'll have to move it
279: */
280: if (q == p)
281: tail = q;
282: else {
283: tail->next = q->next;
284: q->next = p;
285: r->next = q;
286: }
287: }
288: }
289: return YES;
290: } else {
2.29 ! frystyk 291: if (CORE_TRACE) HTTrace("List........ Empty list or no sort algorithm\n");
2.25 frystyk 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