1 /**************************************************************
2 *
3 * Licensed to the Apache Software Foundation (ASF) under one
4 * or more contributor license agreements. See the NOTICE file
5 * distributed with this work for additional information
6 * regarding copyright ownership. The ASF licenses this file
7 * to you under the Apache License, Version 2.0 (the
8 * "License"); you may not use this file except in compliance
9 * with the License. You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing,
14 * software distributed under the License is distributed on an
15 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16 * KIND, either express or implied. See the License for the
17 * specific language governing permissions and limitations
18 * under the License.
19 *
20 *************************************************************/
21
22
23
24 /*[]---------------------------------------------------[]*/
25 /*| |*/
26 /*| list.c - bidirectional list class |*/
27 /*| |*/
28 /*| |*/
29 /*| Author: Alexander Gelfenbain |*/
30 /*[]---------------------------------------------------[]*/
31
32 #include <rtl/alloc.h>
33
34 #if OSL_DEBUG_LEVEL == 0
35 # ifndef NDEBUG
36 # define NDEBUG
37 # endif
38 #endif
39
40 #include <assert.h>
41
42 /* #define TEST */
43 #include "list.h"
44
45 /*- private data types */
46 typedef struct _lnode {
47 struct _lnode *next;
48 struct _lnode *prev;
49
50 void *value;
51
52 } lnode;
53
54 struct _list {
55 lnode *head, *tail, *cptr;
56 size_t aCount;
57 list_destructor eDtor;
58 };
59
60 /*- private methods */
61
newNode(void * el)62 static lnode *newNode(void *el)
63 {
64 lnode *ptr = (lnode*)rtl_allocateMemory(sizeof(lnode));
65 assert(ptr != 0);
66
67 ptr->value = el;
68
69 return ptr;
70 }
71
appendPrim(list pThis,void * el)72 static lnode *appendPrim(list pThis, void *el)
73 {
74 lnode *ptr = newNode(el);
75 lnode **flink, *blink;
76
77 if (pThis->tail != 0) {
78 flink = &(pThis->tail->next);
79 blink = pThis->tail;
80 } else {
81 flink = &pThis->head;
82 blink = 0;
83 pThis->cptr = ptr; /*- list was empty - set current to pThis element */
84 }
85
86 *flink = ptr;
87 pThis->tail = ptr;
88
89 ptr->prev = blink;
90 ptr->next = 0;
91
92 pThis->aCount++;
93 return ptr;
94 }
95 #ifdef TEST
prependPrim(list pThis,void * el)96 static lnode *prependPrim(list pThis, void *el)
97 {
98 lnode *ptr = newNode(el);
99 lnode *flink, **blink;
100
101 if (pThis->head != 0) {
102 blink = &(pThis->head->prev);
103 flink = pThis->head;
104 } else {
105 blink = &pThis->tail;
106 flink = 0;
107 pThis->cptr = ptr; /*- list was empty - set current to pThis element */
108 }
109
110 *blink = ptr;
111 pThis->head = ptr;
112
113 ptr->next = flink;
114 ptr->prev = 0;
115
116 pThis->aCount++;
117 return ptr;
118 }
119 #endif
120
121 /*- public methods */
listNewEmpty(void)122 list listNewEmpty(void) /*- default ctor */
123 {
124 list pThis = (list)rtl_allocateMemory(sizeof(struct _list));
125 assert(pThis != 0);
126
127 pThis->aCount = 0;
128 pThis->eDtor = 0;
129 pThis->head = pThis->tail = pThis->cptr = 0;
130
131 return pThis;
132 }
133
134 #ifdef TEST
listNewCopy(list l)135 list listNewCopy(list l) /*- copy ctor */
136 {
137 lnode *ptr, *c;
138 list pThis;
139 assert(l != 0);
140
141 pThis = rtl_allocateMemory(sizeof(struct _list));
142 assert(pThis != 0);
143
144 ptr = l->head;
145
146 pThis->aCount = 0;
147 pThis->eDtor = 0;
148 pThis->head = pThis->tail = pThis->cptr = 0;
149
150 while (ptr) {
151 c = appendPrim(pThis, ptr->value);
152 if (ptr == l->cptr) pThis->cptr = c;
153 ptr = ptr->next;
154 }
155
156 return pThis;
157 }
158 #endif
159
listDispose(list pThis)160 void listDispose(list pThis) /*- dtor */
161 {
162 assert(pThis != 0);
163 listClear(pThis);
164 rtl_freeMemory(pThis);
165 }
166
listSetElementDtor(list pThis,list_destructor f)167 void listSetElementDtor(list pThis, list_destructor f)
168 {
169 assert(pThis != 0);
170 pThis->eDtor = f;
171 }
172
173 /* calling this function on an empty list is a run-time error */
listCurrent(list pThis)174 void *listCurrent(list pThis)
175 {
176 assert(pThis != 0);
177 assert(pThis->cptr != 0);
178 return pThis->cptr->value;
179 }
180
listCount(list pThis)181 int listCount(list pThis)
182 {
183 assert(pThis != 0);
184 return pThis->aCount;
185 }
186
listIsEmpty(list pThis)187 int listIsEmpty(list pThis)
188 {
189 assert(pThis != 0);
190 return pThis->aCount == 0;
191 }
192
193
194 #ifdef TEST
listAtFirst(list pThis)195 int listAtFirst(list pThis)
196 {
197 assert(pThis != 0);
198 return pThis->cptr == pThis->head;
199 }
200
listAtLast(list pThis)201 int listAtLast(list pThis)
202 {
203 assert(pThis != 0);
204 return pThis->cptr == pThis->tail;
205 }
206
listPosition(list pThis)207 int listPosition(list pThis)
208 {
209 int res = 0;
210 lnode *ptr;
211 assert(pThis != 0);
212
213 ptr = pThis->head;
214
215 while (ptr != pThis->cptr) {
216 ptr = ptr->next;
217 res++;
218 }
219
220 return res;
221 }
222 #endif
listFind(list pThis,void * el)223 int listFind(list pThis, void *el)
224 {
225 lnode *ptr;
226 assert(pThis != 0);
227
228 ptr = pThis->head;
229
230 while (ptr) {
231 if (ptr->value == el) {
232 pThis->cptr = ptr;
233 return 1;
234 }
235 ptr = ptr->next;
236 }
237
238 return 0;
239 }
240
listNext(list pThis)241 int listNext(list pThis)
242 {
243 return listSkipForward(pThis, 1);
244 }
245
listSkipForward(list pThis,int n)246 int listSkipForward(list pThis, int n)
247 {
248 int m = 0;
249 assert(pThis != 0);
250
251 if (pThis->cptr == 0) return 0;
252
253 while (n != 0) {
254 if (pThis->cptr->next == 0) break;
255 pThis->cptr = pThis->cptr->next;
256 n--;
257 m++;
258 }
259 return m;
260 }
261
listToFirst(list pThis)262 int listToFirst(list pThis)
263 {
264 assert(pThis != 0);
265
266 if (pThis->cptr != pThis->head) {
267 pThis->cptr = pThis->head;
268 return 1;
269 }
270 return 0;
271 }
272
listToLast(list pThis)273 int listToLast(list pThis)
274 {
275 assert(pThis != 0);
276
277 if (pThis->cptr != pThis->tail) {
278 pThis->cptr = pThis->tail;
279 return 1;
280 }
281 return 0;
282 }
283
listPositionAt(list pThis,int n)284 int listPositionAt(list pThis, int n) /*- returns the actual position number */
285 {
286 int m = 0;
287 assert(pThis != 0);
288
289 pThis->cptr = pThis->head;
290 while (n != 0) {
291 if (pThis->cptr->next == 0) break;
292 pThis->cptr = pThis->cptr->next;
293 n--;
294 m++;
295 }
296 return m;
297 }
298
listAppend(list pThis,void * el)299 list listAppend(list pThis, void *el)
300 {
301 assert(pThis != 0);
302
303 appendPrim(pThis, el);
304 return pThis;
305 }
306 #ifdef TEST
listPrepend(list pThis,void * el)307 list listPrepend(list pThis, void *el)
308 {
309 assert(pThis != 0);
310
311 prependPrim(pThis, el);
312 return pThis;
313 }
314
listInsertAfter(list pThis,void * el)315 list listInsertAfter(list pThis, void *el)
316 {
317 lnode *ptr;
318 assert(pThis != 0);
319
320 if (pThis->cptr == 0) return listAppend(pThis, el);
321
322 ptr = newNode(el);
323
324 ptr->prev = pThis->cptr;
325 ptr->next = pThis->cptr->next;
326 pThis->cptr->next = ptr;
327
328 if (ptr->next != 0) {
329 ptr->next->prev = ptr;
330 } else {
331 pThis->tail = ptr;
332 }
333 pThis->aCount++;
334 return pThis;
335 }
336
listInsertBefore(list pThis,void * el)337 list listInsertBefore(list pThis, void *el)
338 {
339 lnode *ptr;
340 assert(pThis != 0);
341
342 if (pThis->cptr == 0) return listAppend(pThis, el);
343
344 ptr = newNode(el);
345
346 ptr->prev = pThis->cptr->prev;
347 ptr->next = pThis->cptr;
348 pThis->cptr->prev = ptr;
349
350 if (ptr->prev != 0) {
351 ptr->prev->next = ptr;
352 } else {
353 pThis->head = ptr;
354 }
355 pThis->aCount++;
356 return pThis;
357 }
358 #endif
listRemove(list pThis)359 list listRemove(list pThis)
360 {
361 lnode *ptr = 0;
362 if (pThis->cptr == 0) return pThis;
363
364 if (pThis->cptr->next != 0) {
365 ptr = pThis->cptr->next;
366 pThis->cptr->next->prev = pThis->cptr->prev;
367 } else {
368 pThis->tail = pThis->cptr->prev;
369 }
370
371 if (pThis->cptr->prev != 0) {
372 if (ptr == 0) ptr = pThis->cptr->prev;
373 pThis->cptr->prev->next = pThis->cptr->next;
374 } else {
375 pThis->head = pThis->cptr->next;
376 }
377
378 if (pThis->eDtor) pThis->eDtor(pThis->cptr->value); /* call the dtor callback */
379
380 rtl_freeMemory(pThis->cptr);
381 pThis->aCount--;
382 pThis->cptr = ptr;
383 return pThis;
384 }
385
listClear(list pThis)386 list listClear(list pThis)
387 {
388 lnode *node = pThis->head, *ptr;
389
390 while (node) {
391 ptr = node->next;
392 if (pThis->eDtor) pThis->eDtor(node->value); /* call the dtor callback */
393 rtl_freeMemory(node);
394 pThis->aCount--;
395 node = ptr;
396 }
397
398 pThis->head = pThis->tail = pThis->cptr = 0;
399 assert(pThis->aCount == 0);
400 return pThis;
401 }
402
403 #ifdef TEST
404
listForAll(list pThis,void (* f)(void *))405 void listForAll(list pThis, void (*f)(void *))
406 {
407 lnode *ptr = pThis->head;
408 while (ptr) {
409 f(ptr->value);
410 ptr = ptr->next;
411 }
412 }
413
414
415 #include <stdio.h>
416
printlist(list l)417 void printlist(list l)
418 {
419 int saved;
420 assert(l != 0);
421 saved = listPosition(l);
422
423 printf("[ ");
424
425 if (!listIsEmpty(l)) {
426 listToFirst(l);
427 do {
428 printf("%d ", (int) listCurrent(l));
429 } while (listNext(l));
430 }
431
432 printf("]\n");
433
434 listPositionAt(l, saved);
435 }
436
printstringlist(list l)437 void printstringlist(list l)
438 {
439 int saved;
440 assert(l != 0);
441 saved = listPosition(l);
442
443 printf("[ ");
444
445 if (!listIsEmpty(l)) {
446 listToFirst(l);
447 do {
448 printf("'%s' ", (char *) listCurrent(l));
449 } while (listNext(l));
450 }
451
452 printf("]\n");
453
454 listPositionAt(l, saved);
455 }
456
printstat(list l)457 void printstat(list l)
458 {
459 printf("count: %d, position: %d, isEmpty: %d, atFirst: %d, atLast: %d.\n",
460 listCount(l), listPosition(l), listIsEmpty(l), listAtFirst(l), listAtLast(l));
461 }
462
allfunc(void * e)463 void allfunc(void *e)
464 {
465 printf("%d ", e);
466 }
467
edtor(void * ptr)468 void edtor(void *ptr)
469 {
470 printf("element dtor: 0x%08x\n", ptr);
471 rtl_freeMemory(ptr);
472 }
473
main()474 int main()
475 {
476 list l1, l2;
477 char *ptr;
478 int i;
479
480 l1 = listNewEmpty();
481 printstat(l1);
482
483 listAppend(l1, 1);
484 printstat(l1);
485
486 listAppend(l1, 2);
487 printstat(l1);
488
489 listAppend(l1, 3);
490 printstat(l1);
491
492 printlist(l1);
493
494 listToFirst(l1);
495 listInsertBefore(l1, -5);
496 printlist(l1);
497
498 l2 = listNewCopy(l1);
499 printlist(l2);
500
501 listForAll(l2, allfunc);
502 printf("\n");
503
504 listClear(l1);
505 listSetElementDtor(l1, edtor);
506
507 for(i=0; i<10; i++) {
508 ptr = rtl_allocateMemory(20);
509 snprintf(ptr, 20, "element # %d", i);
510 listAppend(l1, ptr);
511 }
512
513 printstringlist(l1);
514
515
516 listDispose(l1);
517 listDispose(l2);
518
519
520 return 0;
521 }
522 #endif
523
524 /* vim: set noet sw=4 ts=4: */
525