Branch data Line data Source code
1 : : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : : /*************************************************************************
3 : : *
4 : : * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 : : *
6 : : * Copyright 2000, 2010 Oracle and/or its affiliates.
7 : : *
8 : : * OpenOffice.org - a multi-platform office productivity suite
9 : : *
10 : : * This file is part of OpenOffice.org.
11 : : *
12 : : * OpenOffice.org is free software: you can redistribute it and/or modify
13 : : * it under the terms of the GNU Lesser General Public License version 3
14 : : * only, as published by the Free Software Foundation.
15 : : *
16 : : * OpenOffice.org is distributed in the hope that it will be useful,
17 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 : : * GNU Lesser General Public License version 3 for more details
20 : : * (a copy is included in the LICENSE file that accompanied this code).
21 : : *
22 : : * You should have received a copy of the GNU Lesser General Public License
23 : : * version 3 along with OpenOffice.org. If not, see
24 : : * <http://www.openoffice.org/license.html>
25 : : * for a copy of the LGPLv3 License.
26 : : *
27 : : ************************************************************************/
28 : :
29 : : /*[]---------------------------------------------------[]*/
30 : : /*| |*/
31 : : /*| list.c - bidirectional list class |*/
32 : : /*| |*/
33 : : /*| |*/
34 : : /*| Author: Alexander Gelfenbain |*/
35 : : /*[]---------------------------------------------------[]*/
36 : :
37 : : #include <stdlib.h>
38 : : #include <assert.h>
39 : :
40 : : #ifdef MALLOC_TRACE
41 : : #include <stdio.h>
42 : : #include </usr/local/include/malloc.h>
43 : : #endif
44 : : #include "list.h"
45 : :
46 : : /*- private data types */
47 : : typedef struct _lnode {
48 : : struct _lnode *next;
49 : : struct _lnode *prev;
50 : :
51 : : void *value;
52 : :
53 : : } lnode;
54 : :
55 : : struct _list {
56 : : lnode *head, *tail, *cptr;
57 : : size_t aCount;
58 : : list_destructor eDtor;
59 : : };
60 : :
61 : : /*- private methods */
62 : :
63 : 0 : static lnode *newNode(void *el)
64 : : {
65 : 0 : lnode *ptr = malloc(sizeof(lnode));
66 : : assert(ptr != 0);
67 : :
68 : 0 : ptr->value = el;
69 : :
70 : 0 : return ptr;
71 : : }
72 : :
73 : 0 : static lnode *appendPrim(list this, void *el)
74 : : {
75 : 0 : lnode *ptr = newNode(el);
76 : : lnode **flink, *blink;
77 : :
78 [ # # ]: 0 : if (this->tail != 0) {
79 : 0 : flink = &(this->tail->next);
80 : 0 : blink = this->tail;
81 : : } else {
82 : 0 : flink = &this->head;
83 : 0 : blink = 0;
84 : 0 : this->cptr = ptr; /*- list was empty - set current to this element */
85 : : }
86 : :
87 : 0 : *flink = ptr;
88 : 0 : this->tail = ptr;
89 : :
90 : 0 : ptr->prev = blink;
91 : 0 : ptr->next = 0;
92 : :
93 : 0 : this->aCount++;
94 : 0 : return ptr;
95 : : }
96 : :
97 : : /*- public methods */
98 : 0 : list listNewEmpty(void) /*- default ctor */
99 : : {
100 : 0 : list this = malloc(sizeof(struct _list));
101 : : assert(this != 0);
102 : :
103 : 0 : this->aCount = 0;
104 : 0 : this->eDtor = 0;
105 : 0 : this->head = this->tail = this->cptr = 0;
106 : :
107 : 0 : return this;
108 : : }
109 : :
110 : 0 : void listDispose(list this) /*- dtor */
111 : : {
112 : : assert(this != 0);
113 : 0 : listClear(this);
114 : 0 : free(this);
115 : 0 : }
116 : :
117 : 0 : void listSetElementDtor(list this, list_destructor f)
118 : : {
119 : : assert(this != 0);
120 : 0 : this->eDtor = f;
121 : 0 : }
122 : :
123 : : /* calling this function on an empty list is a run-time error */
124 : 0 : void *listCurrent(list this)
125 : : {
126 : : assert(this != 0);
127 : : assert(this->cptr != 0);
128 : 0 : return this->cptr->value;
129 : : }
130 : :
131 : 0 : int listCount(list this)
132 : : {
133 : : assert(this != 0);
134 : 0 : return this->aCount;
135 : : }
136 : :
137 : 0 : int listIsEmpty(list this)
138 : : {
139 : : assert(this != 0);
140 : 0 : return this->aCount == 0;
141 : : }
142 : :
143 : 0 : int listNext(list this)
144 : : {
145 : 0 : return listSkipForward(this, 1);
146 : : }
147 : :
148 : 0 : int listSkipForward(list this, int n)
149 : : {
150 : 0 : int m = 0;
151 : : assert(this != 0);
152 : :
153 [ # # ]: 0 : if (this->cptr == 0) return 0;
154 : :
155 [ # # ]: 0 : while (n != 0) {
156 [ # # ]: 0 : if (this->cptr->next == 0) break;
157 : 0 : this->cptr = this->cptr->next;
158 : 0 : n--;
159 : 0 : m++;
160 : : }
161 : 0 : return m;
162 : : }
163 : :
164 : 0 : int listToFirst(list this)
165 : : {
166 : : assert(this != 0);
167 : :
168 [ # # ]: 0 : if (this->cptr != this->head) {
169 : 0 : this->cptr = this->head;
170 : 0 : return 1;
171 : : }
172 : 0 : return 0;
173 : : }
174 : :
175 : 0 : int listToLast(list this)
176 : : {
177 : : assert(this != 0);
178 : :
179 [ # # ]: 0 : if (this->cptr != this->tail) {
180 : 0 : this->cptr = this->tail;
181 : 0 : return 1;
182 : : }
183 : 0 : return 0;
184 : : }
185 : :
186 : 0 : list listAppend(list this, void *el)
187 : : {
188 : : assert(this != 0);
189 : :
190 : 0 : appendPrim(this, el);
191 : 0 : return this;
192 : : }
193 : :
194 : 0 : list listRemove(list this)
195 : : {
196 : 0 : lnode *ptr = 0;
197 [ # # ]: 0 : if (this->cptr == 0) return this;
198 : :
199 [ # # ]: 0 : if (this->cptr->next != 0) {
200 : 0 : ptr = this->cptr->next;
201 : 0 : this->cptr->next->prev = this->cptr->prev;
202 : : } else {
203 : 0 : this->tail = this->cptr->prev;
204 : : }
205 : :
206 [ # # ]: 0 : if (this->cptr->prev != 0) {
207 [ # # ]: 0 : if (ptr == 0) ptr = this->cptr->prev;
208 : 0 : this->cptr->prev->next = this->cptr->next;
209 : : } else {
210 : 0 : this->head = this->cptr->next;
211 : : }
212 : :
213 [ # # ]: 0 : if (this->eDtor) this->eDtor(this->cptr->value); /* call the dtor callback */
214 : :
215 : 0 : free(this->cptr);
216 : 0 : this->aCount--;
217 : 0 : this->cptr = ptr;
218 : 0 : return this;
219 : : }
220 : :
221 : 0 : list listClear(list this)
222 : : {
223 : 0 : lnode *node = this->head, *ptr;
224 : :
225 [ # # ]: 0 : while (node) {
226 : 0 : ptr = node->next;
227 [ # # ]: 0 : if (this->eDtor) this->eDtor(node->value); /* call the dtor callback */
228 : 0 : free(node);
229 : 0 : this->aCount--;
230 : 0 : node = ptr;
231 : : }
232 : :
233 : 0 : this->head = this->tail = this->cptr = 0;
234 : : assert(this->aCount == 0);
235 : 0 : return this;
236 : : }
237 : :
238 : : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
