Logo Search packages:      
Sourcecode: bbppp version File versions  Download package

LinkedList.cc

// LinkedList.cc for Blackbox - an X11 Window manager
// Copyright (c) 1997 - 2000 Brad Hughes (bhughes@tcac.net)
//
// Permission is hereby granted, free of charge, to any person obtaining a
// copy of this software and associated documentation files (the "Software"),
// to deal in the Software without restriction, including without limitation
// the rights to use, copy, modify, merge, publish, distribute, sublicense,
// and/or sell copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
// DEALINGS IN THE SOFTWARE.

// stupid macros needed to access some functions in version 2 of the GNU C
// library
#ifndef   _GNU_SOURCE
#define   _GNU_SOURCE
#endif // _GNU_SOURCE

#include "LinkedList.hh"

#ifdef    HAVE_CONFIG_H
#  include "../config.h"
#endif // HAVE_CONFIG_H

#ifdef    HAVE_STDIO_H
#  include <stdio.h>
#endif // HAVE_STDIO_H


__llist_iterator::__llist_iterator(__llist *l)
{
      // initialize the iterator...
      list = l;

      if (list) {
            if (! list->iterators)
                  list->iterators = new __llist;

            list->iterators->insert(this);
      }

      reset();
}


__llist_iterator::~__llist_iterator(void)
{
      if (list && list->iterators)
            list->iterators->remove(this);
}


void *__llist_iterator::current(void)
{
      // return the current node data... if any
      return ((node) ? node->getData() : 0);
}


void __llist_iterator::reset(void)
{
      // update the iterator's current node to the first node in the linked list
      if (list)
            node = list->_first;
}


const int __llist_iterator::set(const int index)
{
      // set the current node to index
      if (list) {
            if (index < list->elements && index >= 0 && list->_first) {
                  node = list->_first;

                  for (register int i = 0; i < index; i++)
                        node = node->getNext();

                  return 1;
            }
      }

      node = (__llist_node *) 0;
      return 0;
}


void __llist_iterator::operator++(void)
{
      // iterate to the next node in the list...
      node = ((node) ? node->getNext() : 0);
}


void __llist_iterator::operator++(int)
{
      // iterate to the next node in the list...
      node = ((node) ? node->getNext() : 0);
}


__llist::__llist(void *d)
{
      // initialize the linked list...
      _first = (__llist_node *) 0;
      _last = (__llist_node *) 0;
      iterators = (__llist *) 0;
      elements = 0;

      if (d) insert(d);
}


__llist::~__llist(void)
{
      // remove all the items in the list...
      for (register int i = 0, r = elements; i < r; i++)
            remove(0);

      if (iterators) {
            __llist_node *n = iterators->_first;

            while (n) {
                  ((__llist_iterator *) n->getData())->list = (__llist *) 0;
                  ((__llist_iterator *) n->getData())->node = (__llist_node *) 0;

                  n = n->getNext();
            }

            delete iterators;
      }
}


const int __llist::insert(void *d, int index)
{
      // insert item into linked list at specified index...

      if ((! _first) || (! _last)) {
            // list is empty... insert the item as the first item, regardless of the
            // index given
            _first = new __llist_node;
            _first->setData(d);
            _first->setNext((__llist_node *) 0);
            _last = _first;
      } else {
            if (index == 0) {
                  // if index is 0... prepend the data on the list
                  __llist_node *nnode = new __llist_node;

                  nnode->setData(d);
                  nnode->setNext(_first);

                  _first = nnode;
            } else if ((index == -1) || (index == elements)) {
                  // if index is -1... append the data on the list
                  __llist_node *nnode = new __llist_node;

                  nnode->setData(d);
                  nnode->setNext((__llist_node *) 0);
                  _last->setNext(nnode);

                  _last = nnode;
            } else if (index < elements) {
                  // otherwise... insert the item at the position specified by index
                  __llist_node *nnode = new __llist_node, *inode = _first->getNext();

                  if (! nnode)
                        return -1;

                  nnode->setData(d);

                  for (register int i = 1; i < index; i++)
                        if (inode)
                              inode = inode->getNext();
                        else {
                              delete nnode;
                              return -1;
                        }

                  if ((! inode) || inode == _last) {
                        nnode->setNext((__llist_node *) 0);
                        _last->setNext(nnode);

                        _last = nnode;
                  } else {
                        nnode->setNext(inode->getNext());
                        inode->setNext(nnode);
                  }
            }
      }

      return ++elements;
}


const int __llist::remove(void *d)
{
      // remove list item whose data pointer address matches the pointer address
      // given

      if ((! _first) || (! _last))
            return -1;
      else if (_first->getData() == d) {
            // remove the first item in the list...
            __llist_node *node = _first;
            _first = _first->getNext();

            if (iterators && iterators->_first) {
                  __llist_node *n = iterators->_first;
                  while (n) {
                        ((__llist_iterator *) n->getData())->reset();
                        n = n->getNext();
                  }
            }

            --elements;
            delete node;
            return 0;
      } else {
            // iterate through the list and remove the first occurance of the item

            // NOTE: we don't validate _first in this assignment, because it is checked
            // for validity above...
            __llist_node *rnode = _first->getNext(), *prev = _first;

            for (register int i = 1; i < elements; i++)
                  if (rnode)
                        if (rnode->getData() == d) {
                              // we found the item... update the previous node and delete the
                              // now useless rnode...
                              prev->setNext(rnode->getNext());

                              if (rnode == _last)
                                    _last = prev;

                              if (iterators && iterators->_first) {
                                    __llist_node *n = iterators->_first;
                                    while (n) {
                                          ((__llist_iterator *) n->getData())->reset();
                                          n = n->getNext();
                                    }
                              }

                              --elements;
                              delete rnode;
                              return i;
                        } else {
                              prev = rnode;
                              rnode = rnode->getNext();
                        }

            return -1;
      }
}


void *__llist::remove(const int index)
{
      if (index >= elements || index < 0 || (! _first) || (! _last))
            return (void *) 0;

      // remove list item at specified index within the list
      if (index == 0) {
            // remove the first item in the list...
            __llist_node *node = _first;
            void *data_return = _first->getData();

            _first = _first->getNext();

            if (iterators && iterators->_first) {
                  __llist_node *n = iterators->_first;
                  while (n) {
                        ((__llist_iterator *) n->getData())->reset();
                        n = n->getNext();
                  }
            }

            --elements;
            delete node;

            return data_return;
      } else {
            __llist_node *rnode = _first->getNext(), *prev = _first;
            void *data_return = (void *) 0;

            for (register int i = 1; i < index; i++)
                  if (rnode) {
                        prev = rnode;
                        rnode = rnode->getNext();
                  } else
                        return (void *) 0;

            if (! rnode) return (void *) 0;

            prev->setNext(rnode->getNext());
            data_return = rnode->getData();

            if (rnode == _last)
                  _last = prev;

            if (iterators && iterators->_first) {
                  __llist_node *n = iterators->_first;
                  while (n) {
                        ((__llist_iterator *) n->getData())->reset();
                        n = n->getNext();
                  }
            }

            --elements;
            data_return = rnode->getData();
            delete rnode;
            return data_return;
      }

      return (void *) 0;
}


void *__llist::find(const int index)
{
      if (index >= elements || index < 0 || (! _first) || (! _last))
            return (void *) 0;

      if (index == 0) {
            // return the first item
            return first();
      } else if (index == (elements - 1)) {
            // return the last item
            return last();
      } else {
            __llist_node *fnode = _first->getNext();

            for (register int i = 1; i < index; i++)
                  if (fnode)
                        fnode = fnode->getNext();
                  else
                        return (void *) 0;

            return fnode->getData();
      }

      return (void *) 0;
}


void *__llist::first(void)
{
      if (_first)
            return _first->getData();

      return (void *) 0;
}


void *__llist::last(void)
{
      if (_last)
            return _last->getData();

      return (void *) 0;
}

Generated by  Doxygen 1.6.0   Back to index