Initial revision

1 files changed, 354 insertions, 0 deletions

diff --git a/src/LinkedList.cc b/src/LinkedList.cc
new file mode 100644
index 0000000..bd958d7
--- /dev/null
+++ b/src/LinkedList.cc
@@ -0,0 +1,354 @@
+// 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;
+}