summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/LinkedList.cc354
-rw-r--r--src/LinkedList.hh131
2 files changed, 0 insertions, 485 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}
diff --git a/src/LinkedList.hh b/src/LinkedList.hh
deleted file mode 100644
index fa6d570..0000000
--- a/src/LinkedList.hh
+++ /dev/null
@@ -1,131 +0,0 @@
1// LinkedList.hh 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#ifndef LINKEDLIST_HH
23#define LINKEDLIST_HH
24
25
26class __llist_node {
27private:
28 __llist_node *next;
29 void *data;
30
31protected:
32
33public:
34 __llist_node(void) { next = (__llist_node *) 0; data = (void *) 0; }
35
36 inline __llist_node *getNext(void) { return next; }
37
38 inline void *getData(void) { return data; }
39 inline void setData(void *d) { data = d; }
40 inline void setNext(__llist_node *n) { next = n; }
41};
42
43
44// forward declaration
45class __llist;
46
47
48class __llist_iterator {
49private:
50 __llist *list;
51 __llist_node *node;
52
53 friend class __llist;
54
55
56protected:
57 __llist_iterator(__llist *);
58 ~__llist_iterator(void);
59
60 const int set(const int);
61
62 void *current(void);
63 void reset(void);
64
65 void operator++(void);
66 void operator++(int);
67};
68
69
70class __llist {
71private:
72 int elements;
73 __llist_node *_first, *_last;
74 __llist *iterators;
75
76 friend class __llist_iterator;
77
78
79protected:
80 __llist(void * = 0);
81 ~__llist(void);
82
83 inline const int &count(void) const { return elements; }
84 inline const int empty(void) const { return (elements == 0); }
85
86 const int insert(void *, int = -1);
87 const int remove(void *);
88
89 void *find(const int);
90 void *remove(const int);
91 void *first(void);
92 void *last(void);
93};
94
95
96template <class Z>
97class LinkedListIterator : public __llist_iterator {
98public:
99 LinkedListIterator(__llist *d = 0) : __llist_iterator(d) { return; }
100
101 inline Z *current(void) { return (Z *) __llist_iterator::current(); }
102
103 inline const int set(const int i) { return __llist_iterator::set(i); }
104
105 inline void reset(void) { __llist_iterator::reset(); }
106
107 inline void operator++(void) { __llist_iterator::operator++(); }
108 inline void operator++(int) { __llist_iterator::operator++(0); }
109};
110
111
112template <class Z>
113class LinkedList : public __llist {
114public:
115 LinkedList(Z *d = 0) : __llist(d) { return; }
116
117 inline Z *find(const int i) { return (Z *) __llist::find(i); }
118 inline Z *remove(const int i) { return (Z *) __llist::remove(i); }
119 inline Z *first(void) { return (Z *) __llist::first(); }
120 inline Z *last(void) { return (Z *) __llist::last(); }
121
122 inline const int count(void) const { return __llist::count(); }
123 inline const int empty(void) const { return __llist::empty(); }
124
125 inline const int insert(Z *d, int i = -1) { return __llist::insert((void *) d, i); }
126 inline const int remove(Z *d) { return __llist::remove((void *) d); }
127};
128
129
130#endif // _LINKEDLIST_HH_
131
generated by cgit v0.11.2 at 2024-11-20 07:17:30 (GMT)