xref: /aoo42x/main/vcl/source/fontsubset/list.cxx (revision 3935342b)
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