1 // LinkedList.cc for Blackbox - an X11 Window manager
2 // Copyright (c) 1997 - 2000 Brad Hughes (bhughes@tcac.net)
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:
11 // The above copyright notice and this permission notice shall be included in
12 // all copies or substantial portions of the Software.
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.
22 // stupid macros needed to access some functions in version 2 of the GNU C
28 #include "LinkedList.hh"
31 # include "../config.h"
32 #endif // HAVE_CONFIG_H
36 #endif // HAVE_STDIO_H
39 __llist_iterator::__llist_iterator(__llist
*l
) {
40 // initialize the iterator...
44 if (! list
->iterators
)
45 list
->iterators
= new __llist
;
47 list
->iterators
->insert(this);
54 __llist_iterator::~__llist_iterator(void) {
55 if (list
&& list
->iterators
)
56 list
->iterators
->remove(this);
60 void *__llist_iterator::current(void) {
61 // return the current node data... if any
62 return ((node
) ? node
->getData() : 0);
66 void __llist_iterator::reset(void) {
67 // update the iterator's current node to the first node in the linked list
73 const int __llist_iterator::set(const int index
) {
74 // set the current node to index
76 if (index
< list
->elements
&& index
>= 0 && list
->_first
) {
79 for (register int i
= 0; i
< index
; i
++)
80 node
= node
->getNext();
86 node
= (__llist_node
*) 0;
91 void __llist_iterator::operator++(void) {
92 // iterate to the next node in the list...
93 node
= ((node
) ? node
->getNext() : 0);
97 void __llist_iterator::operator++(int) {
98 // iterate to the next node in the list...
99 node
= ((node
) ? node
->getNext() : 0);
103 __llist::__llist(void *d
) {
104 // initialize the linked list...
105 _first
= (__llist_node
*) 0;
106 _last
= (__llist_node
*) 0;
107 iterators
= (__llist
*) 0;
114 __llist::~__llist(void) {
115 // remove all the items in the list...
116 for (register int i
= 0, r
= elements
; i
< r
; i
++)
120 __llist_node
*n
= iterators
->_first
;
123 ((__llist_iterator
*) n
->getData())->list
= (__llist
*) 0;
124 ((__llist_iterator
*) n
->getData())->node
= (__llist_node
*) 0;
134 const int __llist::insert(void *d
, int index
) {
135 // insert item into linked list at specified index...
137 if ((! _first
) || (! _last
)) {
138 // list is empty... insert the item as the first item, regardless of the
140 _first
= new __llist_node
;
142 _first
->setNext((__llist_node
*) 0);
146 // if index is 0... prepend the data on the list
147 __llist_node
*nnode
= new __llist_node
;
150 nnode
->setNext(_first
);
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
;
158 nnode
->setNext((__llist_node
*) 0);
159 _last
->setNext(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
;
171 for (register int i
= 1; i
< index
; i
++)
173 inode
= inode
->getNext();
179 if ((! inode
) || inode
== _last
) {
180 nnode
->setNext((__llist_node
*) 0);
181 _last
->setNext(nnode
);
185 nnode
->setNext(inode
->getNext());
186 inode
->setNext(nnode
);
195 const int __llist::remove(void *d
) {
196 // remove list item whose data pointer address matches the pointer address
199 if ((! _first
) || (! _last
))
201 else if (_first
->getData() == d
) {
202 // remove the first item in the list...
203 __llist_node
*node
= _first
;
204 _first
= _first
->getNext();
206 if (iterators
&& iterators
->_first
) {
207 __llist_node
*n
= iterators
->_first
;
209 ((__llist_iterator
*) n
->getData())->reset();
218 // iterate through the list and remove the first occurance of the item
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
;
224 for (register int i
= 1; i
< elements
; i
++)
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());
234 if (iterators
&& iterators
->_first
) {
235 __llist_node
*n
= iterators
->_first
;
237 ((__llist_iterator
*) n
->getData())->reset();
247 rnode
= rnode
->getNext();
255 void *__llist::remove(const int index
) {
256 if (index
>= elements
|| index
< 0 || (! _first
) || (! _last
))
259 // remove list item at specified index within the list
261 // remove the first item in the list...
262 __llist_node
*node
= _first
;
263 void *data_return
= _first
->getData();
265 _first
= _first
->getNext();
267 if (iterators
&& iterators
->_first
) {
268 __llist_node
*n
= iterators
->_first
;
270 ((__llist_iterator
*) n
->getData())->reset();
280 __llist_node
*rnode
= _first
->getNext(), *prev
= _first
;
281 void *data_return
= (void *) 0;
283 for (register int i
= 1; i
< index
; i
++)
286 rnode
= rnode
->getNext();
290 if (! rnode
) return (void *) 0;
292 prev
->setNext(rnode
->getNext());
293 data_return
= rnode
->getData();
298 if (iterators
&& iterators
->_first
) {
299 __llist_node
*n
= iterators
->_first
;
301 ((__llist_iterator
*) n
->getData())->reset();
307 data_return
= rnode
->getData();
316 void *__llist::find(const int index
) {
317 if (index
>= elements
|| index
< 0 || (! _first
) || (! _last
))
321 // return the first item
323 } else if (index
== (elements
- 1)) {
324 // return the last item
327 __llist_node
*fnode
= _first
->getNext();
329 for (register int i
= 1; i
< index
; i
++)
331 fnode
= fnode
->getNext();
335 return fnode
->getData();
342 void *__llist::first(void) {
344 return _first
->getData();
350 void *__llist::last(void) {
352 return _last
->getData();