src/LinkedList.cc

   1 // LinkedList.cc for Openbox
   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.h"
  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; i < elements; i++)
 117     remove(0);
 118
 119   if (iterators) {
 120     __llist_node *n = iterators->_first;
 121
 122     while (n) {
 123       __llist_iterator *p = (__llist_iterator *) n->getData();
 124       p->list = (__llist *) 0;
 125       p->node = (__llist_node *) 0;
 126
 127       n = n->getNext();
 128     }
 129
 130     delete iterators;
 131   }
 132 }
 133
 134
 135 const int __llist::insert(void *d, int index) {
 136   // insert item into linked list at specified index...
 137
 138   __llist_node *nnode = new __llist_node;
 139   if (! nnode) return -1;
 140
 141   if ((! _first) || (! _last)) {
 142     // list is empty... insert the item as the first item, regardless of the
 143     // index given
 144     _first = nnode;
 145     _first->setData(d);
 146     _first->setNext((__llist_node *) 0);
 147     _last = _first;
 148   } else {
 149     if (index == 0) {
 150       // if index is 0... prepend the data on the list
 151
 152       nnode->setData(d);
 153       nnode->setNext(_first);
 154
 155       _first = nnode;
 156     } else if ((index == -1) || (index == elements)) {
 157       // if index is -1... append the data on the list
 158
 159       nnode->setData(d);
 160       nnode->setNext((__llist_node *) 0);
 161       _last->setNext(nnode);
 162
 163       _last = nnode;
 164     } else if (index < elements) {
 165       // otherwise... insert the item at the position specified by index
 166       __llist_node *inode = _first;
 167
 168       for (register int i = 1; i < index; i++) {
 169         if (inode) {
 170           inode = inode->getNext();
 171         } else {
 172           delete nnode;
 173           return -1;
 174         }
 175       }
 176
 177       nnode->setData(d);
 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
 202   if (_first->getData() == d) {
 203     // remove the first item in the list...
 204     __llist_node *node = _first;
 205     _first = _first->getNext();
 206
 207     if (iterators && iterators->_first) {
 208       __llist_node *n = iterators->_first;
 209       while (n) {
 210         ((__llist_iterator *) n->getData())->reset();
 211         n = n->getNext();
 212       }
 213     }
 214
 215     --elements;
 216     delete node;
 217     return 0;
 218   } else {
 219     // iterate through the list and remove the first occurance of the item
 220
 221     // NOTE: we don't validate _first in this assignment, because it is checked
 222     // for validity above...
 223     __llist_node *rnode = _first->getNext(), *prev = _first;
 224
 225     for (register int i = 1; i < elements; i++) {
 226       if (rnode) {
 227         if (rnode->getData() == d) {
 228           // we found the item... update the previous node and delete the
 229           // now useless rnode...
 230           prev->setNext(rnode->getNext());
 231
 232           if (rnode == _last)
 233             _last = prev;
 234
 235           if (iterators && iterators->_first) {
 236             __llist_node *n = iterators->_first;
 237             while (n) {
 238               ((__llist_iterator *) n->getData())->reset();
 239               n = n->getNext();
 240             }
 241           }
 242
 243           --elements;
 244           delete rnode;
 245           return i;
 246         } else {
 247           prev = rnode;
 248           rnode = rnode->getNext();
 249         }
 250       }
 251     }
 252
 253     return -1;
 254   }
 255 }
 256
 257
 258 void *__llist::remove(const int index) {
 259   if (index >= elements || index < 0 || (! _first) || (! _last))
 260     return (void *) 0;
 261
 262   // remove list item at specified index within the list
 263   if (index == 0) {
 264     // remove the first item in the list...
 265     __llist_node *node = _first;
 266     void *data_return = _first->getData();
 267
 268     _first = _first->getNext();
 269
 270     if (iterators && iterators->_first) {
 271       __llist_node *n = iterators->_first;
 272       while (n) {
 273         ((__llist_iterator *) n->getData())->reset();
 274         n = n->getNext();
 275       }
 276     }
 277
 278     --elements;
 279     delete node;
 280
 281     return data_return;
 282   } else {
 283     __llist_node *rnode = _first->getNext(), *prev = _first;
 284     void *data_return = (void *) 0;
 285
 286     for (register int i = 1; i < index; i++) {
 287       if (rnode) {
 288         prev = rnode;
 289         rnode = rnode->getNext();
 290       } else {
 291         return (void *) 0;
 292       }
 293     }
 294
 295     if (! rnode) return (void *) 0;
 296
 297     prev->setNext(rnode->getNext());
 298     data_return = rnode->getData();
 299
 300     if (rnode == _last)
 301       _last = prev;
 302
 303     if (iterators && iterators->_first) {
 304       __llist_node *n = iterators->_first;
 305       while (n) {
 306         ((__llist_iterator *) n->getData())->reset();
 307         n = n->getNext();
 308       }
 309     }
 310
 311     --elements;
 312     data_return = rnode->getData();
 313     delete rnode;
 314     return data_return;
 315   }
 316
 317   return (void *) 0;
 318 }
 319
 320
 321 void *__llist::find(const int index) {
 322   if (index >= elements || index < 0 || (! _first) || (! _last))
 323     return (void *) 0;
 324
 325   if (index == 0)                 // return the first item
 326     return first();
 327   if (index == (elements - 1))    // return the last item
 328     return last();
 329
 330   __llist_node *fnode = _first->getNext();
 331
 332   for (register int i = 1; i < index; i++) {
 333     if (fnode)
 334       fnode = fnode->getNext();
 335     else
 336       return (void *) 0;
 337   }
 338
 339   return fnode->getData();
 340 }
 341
 342
 343 void *__llist::first(void) {
 344   if (_first)
 345     return _first->getData();
 346
 347   return (void *) 0;
 348 }
 349
 350
 351 void *__llist::last(void) {
 352   if (_last)
 353     return _last->getData();
 354
 355   return (void *) 0;
 356 }