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.
24 // stupid macros needed to access some functions in version 2 of the GNU C
30 #include "LinkedList.hh"
33 # include "../config.h"
34 #endif // HAVE_CONFIG_H
38 #endif // HAVE_STDIO_H
41 __llist_iterator::__llist_iterator(__llist
*l
) {
42 // initialize the iterator...
46 if (! list
->iterators
)
47 list
->iterators
= new __llist
;
49 list
->iterators
->insert(this);
56 __llist_iterator::~__llist_iterator(void) {
57 if (list
&& list
->iterators
)
58 list
->iterators
->remove(this);
62 void *__llist_iterator::current(void) {
63 // return the current node data... if any
64 return ((node
) ? node
->getData() : 0);
68 void __llist_iterator::reset(void) {
69 // update the iterator's current node to the first node in the linked list
75 const int __llist_iterator::set(const int index
) {
76 // set the current node to index
78 if (index
< list
->elements
&& index
>= 0 && list
->_first
) {
81 for (register int i
= 0; i
< index
; i
++)
82 node
= node
->getNext();
88 node
= (__llist_node
*) 0;
93 void __llist_iterator::operator++(void) {
94 // iterate to the next node in the list...
95 node
= ((node
) ? node
->getNext() : 0);
99 void __llist_iterator::operator++(int) {
100 // iterate to the next node in the list...
101 node
= ((node
) ? node
->getNext() : 0);
105 __llist::__llist(void *d
) {
106 // initialize the linked list...
107 _first
= (__llist_node
*) 0;
108 _last
= (__llist_node
*) 0;
109 iterators
= (__llist
*) 0;
116 __llist::~__llist(void) {
117 // remove all the items in the list...
118 for (register int i
= 0, r
= elements
; i
< r
; i
++)
122 __llist_node
*n
= iterators
->_first
;
125 ((__llist_iterator
*) n
->getData())->list
= (__llist
*) 0;
126 ((__llist_iterator
*) n
->getData())->node
= (__llist_node
*) 0;
136 const int __llist::insert(void *d
, int index
) {
137 // insert item into linked list at specified index...
139 if ((! _first
) || (! _last
)) {
140 // list is empty... insert the item as the first item, regardless of the
142 _first
= new __llist_node
;
144 _first
->setNext((__llist_node
*) 0);
148 // if index is 0... prepend the data on the list
149 __llist_node
*nnode
= new __llist_node
;
152 nnode
->setNext(_first
);
155 } else if ((index
== -1) || (index
== elements
)) {
156 // if index is -1... append the data on the list
157 __llist_node
*nnode
= new __llist_node
;
160 nnode
->setNext((__llist_node
*) 0);
161 _last
->setNext(nnode
);
164 } else if (index
< elements
) {
165 // otherwise... insert the item at the position specified by index
166 __llist_node
*nnode
= new __llist_node
, *inode
= _first
;
173 for (register int i
= 1; i
< index
; i
++)
175 inode
= inode
->getNext();
181 if ((! inode
) || inode
== _last
) {
182 nnode
->setNext((__llist_node
*) 0);
183 _last
->setNext(nnode
);
187 nnode
->setNext(inode
->getNext());
188 inode
->setNext(nnode
);
197 const int __llist::remove(void *d
) {
198 // remove list item whose data pointer address matches the pointer address
201 if ((! _first
) || (! _last
))
203 else if (_first
->getData() == d
) {
204 // remove the first item in the list...
205 __llist_node
*node
= _first
;
206 _first
= _first
->getNext();
208 if (iterators
&& iterators
->_first
) {
209 __llist_node
*n
= iterators
->_first
;
211 ((__llist_iterator
*) n
->getData())->reset();
220 // iterate through the list and remove the first occurance of the item
222 // NOTE: we don't validate _first in this assignment, because it is checked
223 // for validity above...
224 __llist_node
*rnode
= _first
->getNext(), *prev
= _first
;
226 for (register int i
= 1; i
< elements
; i
++)
228 if (rnode
->getData() == d
) {
229 // we found the item... update the previous node and delete the
230 // now useless rnode...
231 prev
->setNext(rnode
->getNext());
236 if (iterators
&& iterators
->_first
) {
237 __llist_node
*n
= iterators
->_first
;
239 ((__llist_iterator
*) n
->getData())->reset();
249 rnode
= rnode
->getNext();
257 void *__llist::remove(const int index
) {
258 if (index
>= elements
|| index
< 0 || (! _first
) || (! _last
))
261 // remove list item at specified index within the list
263 // remove the first item in the list...
264 __llist_node
*node
= _first
;
265 void *data_return
= _first
->getData();
267 _first
= _first
->getNext();
269 if (iterators
&& iterators
->_first
) {
270 __llist_node
*n
= iterators
->_first
;
272 ((__llist_iterator
*) n
->getData())->reset();
282 __llist_node
*rnode
= _first
->getNext(), *prev
= _first
;
283 void *data_return
= (void *) 0;
285 for (register int i
= 1; i
< index
; i
++)
288 rnode
= rnode
->getNext();
292 if (! rnode
) return (void *) 0;
294 prev
->setNext(rnode
->getNext());
295 data_return
= rnode
->getData();
300 if (iterators
&& iterators
->_first
) {
301 __llist_node
*n
= iterators
->_first
;
303 ((__llist_iterator
*) n
->getData())->reset();
309 data_return
= rnode
->getData();
318 void *__llist::find(const int index
) {
319 if (index
>= elements
|| index
< 0 || (! _first
) || (! _last
))
323 // return the first item
325 } else if (index
== (elements
- 1)) {
326 // return the last item
329 __llist_node
*fnode
= _first
->getNext();
331 for (register int i
= 1; i
< index
; i
++)
333 fnode
= fnode
->getNext();
337 return fnode
->getData();
344 void *__llist::first(void) {
346 return _first
->getData();
352 void *__llist::last(void) {
354 return _last
->getData();