aboutsummaryrefslogtreecommitdiff
path: root/src/LinkedList.cc
diff options
context:
space:
mode:
Diffstat (limited to 'src/LinkedList.cc')
-rw-r--r--src/LinkedList.cc354
1 files changed, 0 insertions, 354 deletions
diff --git a/src/LinkedList.cc b/src/LinkedList.cc
deleted file mode 100644
index bd958d7..0000000
--- a/src/LinkedList.cc
+++ /dev/null
@@ -1,354 +0,0 @@
1// LinkedList.cc for Blackbox - an X11 Window manager
2// Copyright (c) 1997 - 2000 Brad Hughes (bhughes@tcac.net)
3//
4// Permission is hereby granted, free of charge, to any person obtaining a
5// copy of this software and associated documentation files (the "Software"),
6// to deal in the Software without restriction, including without limitation
7// the rights to use, copy, modify, merge, publish, distribute, sublicense,
8// and/or sell copies of the Software, and to permit persons to whom the
9// Software is furnished to do so, subject to the following conditions:
10//
11// The above copyright notice and this permission notice shall be included in
12// all copies or substantial portions of the Software.
13//
14// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
17// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
20// DEALINGS IN THE SOFTWARE.
21
22// stupid macros needed to access some functions in version 2 of the GNU C
23// library
24#ifndef _GNU_SOURCE
25#define _GNU_SOURCE
26#endif // _GNU_SOURCE
27
28#include "LinkedList.hh"
29
30#ifdef HAVE_CONFIG_H
31# include "../config.h"
32#endif // HAVE_CONFIG_H
33
34#ifdef HAVE_STDIO_H
35# include <stdio.h>
36#endif // HAVE_STDIO_H
37
38
39__llist_iterator::__llist_iterator(__llist *l) {
40 // initialize the iterator...
41 list = l;
42
43 if (list) {
44 if (! list->iterators)
45 list->iterators = new __llist;
46
47 list->iterators->insert(this);
48 }
49
50 reset();
51}
52
53
54__llist_iterator::~__llist_iterator(void) {
55 if (list && list->iterators)
56 list->iterators->remove(this);
57}
58
59
60void *__llist_iterator::current(void) {
61 // return the current node data... if any
62 return ((node) ? node->getData() : 0);
63}
64
65
66void __llist_iterator::reset(void) {
67 // update the iterator's current node to the first node in the linked list
68 if (list)
69 node = list->_first;
70}
71
72
73const int __llist_iterator::set(const int index) {
74 // set the current node to index
75 if (list) {
76 if (index < list->elements && index >= 0 && list->_first) {
77 node = list->_first;
78
79 for (register int i = 0; i < index; i++)
80 node = node->getNext();
81
82 return 1;
83 }
84 }
85
86 node = (__llist_node *) 0;
87 return 0;
88}
89
90
91void __llist_iterator::operator++(void) {
92 // iterate to the next node in the list...
93 node = ((node) ? node->getNext() : 0);
94}
95
96
97void __llist_iterator::operator++(int) {
98 // iterate to the next node in the list...
99 node = ((node) ? node->getNext() : 0);
100}
101
102
103__llist::__llist(void *d) {
104 // initialize the linked list...
105 _first = (__llist_node *) 0;
106 _last = (__llist_node *) 0;
107 iterators = (__llist *) 0;
108 elements = 0;
109
110 if (d) insert(d);
111}
112
113
114__llist::~__llist(void) {
115 // remove all the items in the list...
116 for (register int i = 0, r = elements; i < r; i++)
117 remove(0);
118
119 if (iterators) {
120 __llist_node *n = iterators->_first;
121
122 while (n) {
123 ((__llist_iterator *) n->getData())->list = (__llist *) 0;
124 ((__llist_iterator *) n->getData())->node = (__llist_node *) 0;
125
126 n = n->getNext();
127 }
128
129 delete iterators;
130 }
131}
132
133
134const int __llist::insert(void *d, int index) {
135 // insert item into linked list at specified index...
136
137 if ((! _first) || (! _last)) {
138 // list is empty... insert the item as the first item, regardless of the
139 // index given
140 _first = new __llist_node;
141 _first->setData(d);
142 _first->setNext((__llist_node *) 0);
143 _last = _first;
144 } else {
145 if (index == 0) {
146 // if index is 0... prepend the data on the list
147 __llist_node *nnode = new __llist_node;
148
149 nnode->setData(d);
150 nnode->setNext(_first);
151
152 _first = nnode;
153 } else if ((index == -1) || (index == elements)) {
154 // if index is -1... append the data on the list
155 __llist_node *nnode = new __llist_node;
156
157 nnode->setData(d);
158 nnode->setNext((__llist_node *) 0);
159 _last->setNext(nnode);
160
161 _last = nnode;
162 } else if (index < elements) {
163 // otherwise... insert the item at the position specified by index
164 __llist_node *nnode = new __llist_node, *inode = _first->getNext();
165
166 if (! nnode)
167 return -1;
168
169 nnode->setData(d);
170
171 for (register int i = 1; i < index; i++)
172 if (inode)
173 inode = inode->getNext();
174 else {
175 delete nnode;
176 return -1;
177 }
178
179 if ((! inode) || inode == _last) {
180 nnode->setNext((__llist_node *) 0);
181 _last->setNext(nnode);
182
183 _last = nnode;
184 } else {
185 nnode->setNext(inode->getNext());
186 inode->setNext(nnode);
187 }
188 }
189 }
190
191 return ++elements;
192}
193
194
195const int __llist::remove(void *d) {
196 // remove list item whose data pointer address matches the pointer address
197 // given
198
199 if ((! _first) || (! _last))
200 return -1;
201 else if (_first->getData() == d) {
202 // remove the first item in the list...
203 __llist_node *node = _first;
204 _first = _first->getNext();
205
206 if (iterators && iterators->_first) {
207 __llist_node *n = iterators->_first;
208 while (n) {
209 ((__llist_iterator *) n->getData())->reset();
210 n = n->getNext();
211 }
212 }
213
214 --elements;
215 delete node;
216 return 0;
217 } else {
218 // iterate through the list and remove the first occurance of the item
219
220 // NOTE: we don't validate _first in this assignment, because it is checked
221 // for validity above...
222 __llist_node *rnode = _first->getNext(), *prev = _first;
223
224 for (register int i = 1; i < elements; i++)
225 if (rnode)
226 if (rnode->getData() == d) {
227 // we found the item... update the previous node and delete the
228 // now useless rnode...
229 prev->setNext(rnode->getNext());
230
231 if (rnode == _last)
232 _last = prev;
233
234 if (iterators && iterators->_first) {
235 __llist_node *n = iterators->_first;
236 while (n) {
237 ((__llist_iterator *) n->getData())->reset();
238 n = n->getNext();
239 }
240 }
241
242 --elements;
243 delete rnode;
244 return i;
245 } else {
246 prev = rnode;
247 rnode = rnode->getNext();
248 }
249
250 return -1;
251 }
252}
253
254
255void *__llist::remove(const int index) {
256 if (index >= elements || index < 0 || (! _first) || (! _last))
257 return (void *) 0;
258
259 // remove list item at specified index within the list
260 if (index == 0) {
261 // remove the first item in the list...
262 __llist_node *node = _first;
263 void *data_return = _first->getData();
264
265 _first = _first->getNext();
266
267 if (iterators && iterators->_first) {
268 __llist_node *n = iterators->_first;
269 while (n) {
270 ((__llist_iterator *) n->getData())->reset();
271 n = n->getNext();
272 }
273 }
274
275 --elements;
276 delete node;
277
278 return data_return;
279 } else {
280 __llist_node *rnode = _first->getNext(), *prev = _first;
281 void *data_return = (void *) 0;
282
283 for (register int i = 1; i < index; i++)
284 if (rnode) {
285 prev = rnode;
286 rnode = rnode->getNext();
287 } else
288 return (void *) 0;
289
290 if (! rnode) return (void *) 0;
291
292 prev->setNext(rnode->getNext());
293 data_return = rnode->getData();
294
295 if (rnode == _last)
296 _last = prev;
297
298 if (iterators && iterators->_first) {
299 __llist_node *n = iterators->_first;
300 while (n) {
301 ((__llist_iterator *) n->getData())->reset();
302 n = n->getNext();
303 }
304 }
305
306 --elements;
307 data_return = rnode->getData();
308 delete rnode;
309 return data_return;
310 }
311
312 return (void *) 0;
313}
314
315void *__llist::find(const int index) {
316 if (index >= elements || index < 0 || (! _first) || (! _last))
317 return (void *) 0;
318
319 if (index == 0) {
320 // return the first item
321 return first();
322 } else if (index == (elements - 1)) {
323 // return the last item
324 return last();
325 } else {
326 __llist_node *fnode = _first->getNext();
327
328 for (register int i = 1; i < index; i++)
329 if (fnode)
330 fnode = fnode->getNext();
331 else
332 return (void *) 0;
333
334 return fnode->getData();
335 }
336
337 return (void *) 0;
338}
339
340
341void *__llist::first(void) {
342 if (_first)
343 return _first->getData();
344
345 return (void *) 0;
346}
347
348
349void *__llist::last(void) {
350 if (_last)
351 return _last->getData();
352
353 return (void *) 0;
354}
generated by cgit v0.11.2 at 2024-06-30 17:47:28 (GMT)