Line data Source code
1 : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : /*
3 : * This file is part of the LibreOffice project.
4 : *
5 : * This Source Code Form is subject to the terms of the Mozilla Public
6 : * License, v. 2.0. If a copy of the MPL was not distributed with this
7 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 : *
9 : * This file incorporates work covered by the following license notice:
10 : *
11 : * Licensed to the Apache Software Foundation (ASF) under one or more
12 : * contributor license agreements. See the NOTICE file distributed
13 : * with this work for additional information regarding copyright
14 : * ownership. The ASF licenses this file to you under the Apache
15 : * License, Version 2.0 (the "License"); you may not use this file
16 : * except in compliance with the License. You may obtain a copy of
17 : * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 : */
19 :
20 : /*[]---------------------------------------------------[]*/
21 : /*| |*/
22 : /*| list.c - bidirectional list class |*/
23 : /*| |*/
24 : /*| |*/
25 : /*| Author: Alexander Gelfenbain |*/
26 : /*[]---------------------------------------------------[]*/
27 :
28 : #include <rtl/alloc.h>
29 : #include <assert.h>
30 :
31 : #include "list.h"
32 :
33 : /*- private data types */
34 : typedef struct _lnode {
35 : struct _lnode *next;
36 : struct _lnode *prev;
37 :
38 : void *value;
39 :
40 : } lnode;
41 :
42 : struct _list {
43 : lnode *head, *tail, *cptr;
44 : size_t aCount;
45 : list_destructor eDtor;
46 : };
47 :
48 : /*- private methods */
49 :
50 0 : static lnode *newNode(void *el)
51 : {
52 0 : lnode *ptr = (lnode *)rtl_allocateMemory(sizeof(lnode));
53 : assert(ptr != 0);
54 :
55 0 : ptr->value = el;
56 :
57 0 : return ptr;
58 : }
59 :
60 0 : static lnode *appendPrim(list pThis, void *el)
61 : {
62 0 : lnode *ptr = newNode(el);
63 : lnode **flink, *blink;
64 :
65 0 : if (pThis->tail != 0) {
66 0 : flink = &(pThis->tail->next);
67 0 : blink = pThis->tail;
68 : } else {
69 0 : flink = &pThis->head;
70 0 : blink = 0;
71 0 : pThis->cptr = ptr; /*- list was empty - set current to this element */
72 : }
73 :
74 0 : *flink = ptr;
75 0 : pThis->tail = ptr;
76 :
77 0 : ptr->prev = blink;
78 0 : ptr->next = 0;
79 :
80 0 : pThis->aCount++;
81 0 : return ptr;
82 : }
83 :
84 : /*- public methods */
85 0 : list listNewEmpty(void) /*- default ctor */
86 : {
87 0 : list pThis = (list)rtl_allocateMemory(sizeof(struct _list));
88 : assert(pThis != 0);
89 :
90 0 : pThis->aCount = 0;
91 0 : pThis->eDtor = 0;
92 0 : pThis->head = pThis->tail = pThis->cptr = 0;
93 :
94 0 : return pThis;
95 : }
96 :
97 0 : void listDispose(list pThis) /*- dtor */
98 : {
99 : assert(pThis != 0);
100 0 : listClear(pThis);
101 0 : rtl_freeMemory(pThis);
102 0 : }
103 :
104 0 : void listSetElementDtor(list pThis, list_destructor f)
105 : {
106 : assert(pThis != 0);
107 0 : pThis->eDtor = f;
108 0 : }
109 :
110 : /* calling this function on an empty list is a run-time error */
111 0 : void *listCurrent(list pThis)
112 : {
113 : assert(pThis != 0);
114 : assert(pThis->cptr != 0);
115 0 : return pThis->cptr->value;
116 : }
117 :
118 0 : int listCount(list pThis)
119 : {
120 : assert(pThis != 0);
121 0 : return pThis->aCount;
122 : }
123 :
124 0 : int listIsEmpty(list pThis)
125 : {
126 : assert(pThis != 0);
127 0 : return pThis->aCount == 0;
128 : }
129 :
130 0 : int listNext(list pThis)
131 : {
132 0 : return listSkipForward(pThis, 1);
133 : }
134 :
135 0 : int listSkipForward(list pThis, int n)
136 : {
137 0 : int m = 0;
138 : assert(pThis != 0);
139 :
140 0 : if (pThis->cptr == 0) return 0;
141 :
142 0 : while (n != 0) {
143 0 : if (pThis->cptr->next == 0) break;
144 0 : pThis->cptr = pThis->cptr->next;
145 0 : n--;
146 0 : m++;
147 : }
148 0 : return m;
149 : }
150 :
151 0 : int listToFirst(list pThis)
152 : {
153 : assert(pThis != 0);
154 :
155 0 : if (pThis->cptr != pThis->head) {
156 0 : pThis->cptr = pThis->head;
157 0 : return 1;
158 : }
159 0 : return 0;
160 : }
161 :
162 0 : int listToLast(list pThis)
163 : {
164 : assert(pThis != 0);
165 :
166 0 : if (pThis->cptr != pThis->tail) {
167 0 : pThis->cptr = pThis->tail;
168 0 : return 1;
169 : }
170 0 : return 0;
171 : }
172 :
173 0 : list listAppend(list pThis, void *el)
174 : {
175 : assert(pThis != 0);
176 :
177 0 : appendPrim(pThis, el);
178 0 : return pThis;
179 : }
180 :
181 0 : list listRemove(list pThis)
182 : {
183 0 : lnode *ptr = 0;
184 0 : if (pThis->cptr == 0) return pThis;
185 :
186 0 : if (pThis->cptr->next != 0) {
187 0 : ptr = pThis->cptr->next;
188 0 : pThis->cptr->next->prev = pThis->cptr->prev;
189 : } else {
190 0 : pThis->tail = pThis->cptr->prev;
191 : }
192 :
193 0 : if (pThis->cptr->prev != 0) {
194 0 : if (ptr == 0) ptr = pThis->cptr->prev;
195 0 : pThis->cptr->prev->next = pThis->cptr->next;
196 : } else {
197 0 : pThis->head = pThis->cptr->next;
198 : }
199 :
200 0 : if (pThis->eDtor) pThis->eDtor(pThis->cptr->value); /* call the dtor callback */
201 :
202 0 : rtl_freeMemory(pThis->cptr);
203 0 : pThis->aCount--;
204 0 : pThis->cptr = ptr;
205 0 : return pThis;
206 : }
207 :
208 0 : list listClear(list pThis)
209 : {
210 0 : lnode *node = pThis->head, *ptr;
211 :
212 0 : while (node) {
213 0 : ptr = node->next;
214 0 : if (pThis->eDtor) pThis->eDtor(node->value); /* call the dtor callback */
215 0 : rtl_freeMemory(node);
216 0 : pThis->aCount--;
217 0 : node = ptr;
218 : }
219 :
220 0 : pThis->head = pThis->tail = pThis->cptr = 0;
221 : assert(pThis->aCount == 0);
222 0 : return pThis;
223 : }
224 :
225 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
