← Back to branch summary

~ubuntu-branches/ubuntu/warty/fluxbox/warty

« back to all changes in this revision

Viewing changes to src/LinkedList.cc

  • Committer: Bazaar Package Importer
  • Author(s): Matt Hope
  • Date: 2002-04-12 22:08:52 UTC
  • Revision ID: james.westby@ubuntu.com-20020412220852-0gbqxr57mgu63qdh
Tags: upstream-0.1.7
Import upstream version 0.1.7

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/LinkedList.cc
 
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
 
 
60
void *__llist_iterator::current(void) {
 
61
  // return the current node data... if any
 
62
  return ((node) ? node->getData() : 0);
 
63
}
 
64
 
 
65
 
 
66
void __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
 
 
73
const 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
 
 
91
void __llist_iterator::operator++(void) {
 
92
  // iterate to the next node in the list...
 
93
  node = ((node) ? node->getNext() : 0);
 
94
}     
 
95
 
 
96
 
 
97
void __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
 
 
134
const 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
 
 
195
const 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
 
 
255
void *__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
 
 
315
void *__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
 
 
341
void *__llist::first(void) {
 
342
  if (_first)
 
343
    return _first->getData();
 
344
  
 
345
  return (void *) 0;
 
346
}
 
347
 
 
348
 
 
349
void *__llist::last(void) {
 
350
  if (_last)
 
351
    return _last->getData();
 
352
  
 
353
  return (void *) 0;
 
354
}