List.h

Go to the documentation of this file.

/*
 * Copyright (c) 2005 Palmsource, Inc.
 * 
 * This software is licensed as described in the file LICENSE, which
 * you should have received as part of this distribution. The terms
 * are also available at http://www.openbinder.org/license.html.
 * 
 * This software consists of voluntary contributions made by many
 * individuals. For the exact contribution history, see the revision
 * history and logs, available at http://www.openbinder.org
 */

#ifndef _SUPPORT_LIST_H
#define _SUPPORT_LIST_H

#include <support/SupportDefs.h>
#include <support/TypeFuncs.h>

#if _SUPPORTS_NAMESPACE
namespace palmos {
namespace support {
#endif

// *************************************************************************

class SAbstractList
{
public:
                                SAbstractList(const size_t itemSize);
                                SAbstractList(const SAbstractList& o);
    virtual                     ~SAbstractList(void);
    
            SAbstractList&      Duplicate(const SAbstractList& o);
    
            size_t              ItemSize(void) const;
            size_t              CountItems(void) const;
            bool                IsEmpty(void) const;
            
struct _ListNode;
class AbstractIterator;
    
            _ListNode*          Add(const void* newItem);
            _ListNode*          AddAt(const void* newItem, const AbstractIterator& i);
            _ListNode*          Splice(SAbstractList& subList);
            _ListNode*          SpliceAt(SAbstractList& subList, const AbstractIterator& i);
    
            AbstractIterator    Remove(AbstractIterator& i);
    
            AbstractIterator    Begin(void) const;
            AbstractIterator    End(void) const;
    
            void                MakeEmpty(void);
    
protected:
    virtual void                PerformConstruct(void* base, size_t count) const = 0;
    virtual void                PerformCopy(void* to, const void* from, size_t count) const = 0;
    virtual void                PerformDestroy(void* base, size_t count) const = 0;
    virtual void                PerformAssign(void* to, const void* from, size_t count) const = 0;
    
private:
            void                Insert(_ListNode* node, _ListNode* before = NULL);
            void                SpliceNodes(_ListNode* sublist_head, _ListNode* sublist_tail = NULL, _ListNode* before = NULL);
            void                Extract(_ListNode* node);

    virtual status_t            _ReservedAbstractList1();
    virtual status_t            _ReservedAbstractList2();
    virtual status_t            _ReservedAbstractList3();
    virtual status_t            _ReservedAbstractList4();
    virtual status_t            _ReservedAbstractList5();
    virtual status_t            _ReservedAbstractList6();
    virtual status_t            _ReservedAbstractList7();
    virtual status_t            _ReservedAbstractList8();
    virtual status_t            _ReservedAbstractList9();
    virtual status_t            _ReservedAbstractList10();
    
            size_t              m_itemSize;
            size_t              m_numItems;

            _ListNode*          m_end; // sentinel -- does not contain a valid list item
};

// *************************************************************************

class SAbstractList::AbstractIterator 
{
public:
                                AbstractIterator(SAbstractList const * domain);
                                AbstractIterator(SAbstractList const * domain, _ListNode* node);
                                AbstractIterator(const AbstractIterator& o);
    virtual                     ~AbstractIterator(void);
    
            _ListNode*          operator*(void) const;

            AbstractIterator&   operator++(void); // prefix
            AbstractIterator    operator++(int); // postfix
            AbstractIterator&   operator--(void); // prefix
            AbstractIterator    operator--(int); // postfix

            AbstractIterator&   operator=(const AbstractIterator& o);

            bool                operator==(const AbstractIterator& o) const;
            bool                operator!=(const AbstractIterator& o) const;
    
            const void*         Data(void) const;
            void*               EditData(void) const;
            
            SAbstractList const * Domain() const;
    
private:
            _ListNode*          m_current;
            SAbstractList const * m_domain;
};

// *************************************************************************

template<class TYPE>
class _Iterator;


template<class TYPE>
class SList : public SAbstractList
{
public:
            typedef TYPE    value_type;

public:
                                SList(void);
                                SList(const SList<TYPE>& o);
    virtual                     ~SList(void);
    
            SList<TYPE>&        operator=(const SList<TYPE>& o);
            
typedef class _Iterator<TYPE> const iterator;
typedef class _Iterator<TYPE> edit_iterator;
    
//typedef typename const _Iterator<TYPE> iterator;
//typedef typename _Iterator<TYPE> edit_iterator;
            typename SList::edit_iterator       IndexOf(const TYPE& item);
    
            typename SList::edit_iterator       AddItem(const TYPE& item);
            typename SList::edit_iterator       AddItemAt(const TYPE& item, const edit_iterator& i);

            typename SList::edit_iterator       SpliceList(SList<TYPE> &sublist);
            typename SList::edit_iterator       SpliceListAt(SList<TYPE> &sublist, const iterator& i);
    
            typename SList::edit_iterator       RemoveItemFor(const TYPE& item);
            typename SList::edit_iterator       RemoveAllItemsFor(const TYPE& item);

            typename SList::edit_iterator       RemoveItemAt(edit_iterator& i);
            
            typename SList::edit_iterator       Begin(void);
            typename SList::edit_iterator       End(void);
            typename SList::iterator            Begin(void) const;
            typename SList::iterator            End(void) const;

            void                MakeEmpty(void);

protected:
    virtual void                PerformConstruct(void* base, size_t count) const;
    virtual void                PerformCopy(void* to, const void* from, size_t count) const;
    virtual void                PerformDestroy(void* base, size_t count) const;
    virtual void                PerformAssign(void* to, const void* from, size_t count) const;
};


template<class TYPE>
class _Iterator : public SAbstractList::AbstractIterator
{
public:
                                _Iterator(SAbstractList const * domain);
                                _Iterator(SAbstractList const * domain, SAbstractList::_ListNode* node);

typedef _Iterator<TYPE> self;

            TYPE&               operator*(void);
            const TYPE&         operator*(void) const;
            TYPE*               operator->(void);
            const TYPE*         operator->(void) const; // not super useful.

            self&               operator++(void); // prefix
            self                operator++(int); // postfix
            self&               operator--(void); // prefix
            self                operator--(int); // postfix
};

/* No user-serviceable parts below ****************************************/

template<class TYPE>
inline _Iterator<TYPE>::_Iterator(SAbstractList const * domain)
    : SAbstractList::AbstractIterator(domain)
{
}

template<class TYPE>
inline _Iterator<TYPE>::_Iterator(SAbstractList const * domain, SAbstractList::_ListNode* node)
    : SAbstractList::AbstractIterator(domain, node)
{
}

template<class TYPE>
inline TYPE& _Iterator<TYPE>::operator*(void)
{
    return *static_cast<TYPE*>(EditData());
}

template<class TYPE>
inline const TYPE& _Iterator<TYPE>::operator*(void) const
{
    return *static_cast<TYPE*>(Data());
}

template<class TYPE>
inline TYPE* _Iterator<TYPE>::operator->(void)
{
    return static_cast<TYPE*>(EditData());
}

template<class TYPE>
inline const TYPE* _Iterator<TYPE>::operator->(void) const
{
    return static_cast<TYPE*>(Data());
}

template<class TYPE>
inline _Iterator<TYPE>& _Iterator<TYPE>::operator++(void)
{
    SAbstractList::AbstractIterator::operator++();
    
    return *this;
}

template<class TYPE>
inline _Iterator<TYPE> _Iterator<TYPE>::operator++(int o)
{
    return _Iterator<TYPE>(Domain(), *SAbstractList::AbstractIterator::operator++(o));
}

template<class TYPE>
inline _Iterator<TYPE>& _Iterator<TYPE>::operator--(void)
{
    SAbstractList::AbstractIterator::operator--();
    
    return *this;
}

template<class TYPE>
inline _Iterator<TYPE> _Iterator<TYPE>::operator--(int o)
{
    return _Iterator<TYPE>(Domain(), *SAbstractList::AbstractIterator::operator--(o));
}

template<class TYPE>
inline SList<TYPE>::SList(void)
    : SAbstractList(sizeof (TYPE[2])/2)
{
}

template<class TYPE>
inline SList<TYPE>::SList(const SList<TYPE>& o)
    : SAbstractList(o.ItemSize())
{
    Duplicate(o);
}   

template<class TYPE>
inline SList<TYPE>::~SList(void)
{
    MakeEmpty();
}

template<class TYPE>
inline SList<TYPE>& SList<TYPE>::operator=(const SList<TYPE>& o)
{
    Duplicate(o);
    
    return *this;
}

template<class TYPE>
typename SList<TYPE>::edit_iterator SList<TYPE>::IndexOf(const TYPE& item)
{
    typename SList<TYPE>::edit_iterator i = Begin();
    for (; i != End(); i++) {
        if (*i == item) return i;
    }
    
    return End();
}

template<class TYPE>
inline typename SList<TYPE>::edit_iterator SList<TYPE>::AddItem(const TYPE& item)
{
    return edit_iterator(this, Add(&item));
}

template<class TYPE>
inline typename SList<TYPE>::edit_iterator SList<TYPE>::AddItemAt(const TYPE& item,
    const edit_iterator& i)
{
    edit_iterator r = edit_iterator(this, AddAt(&item, i));
    return r;
}

template<class TYPE>
inline typename SList<TYPE>::edit_iterator 
SList<TYPE>::SpliceList(SList<TYPE> &sublist)
{
    return edit_iterator(this, Splice(sublist));
}

template<class TYPE>
inline typename SList<TYPE>::edit_iterator 
SList<TYPE>::SpliceListAt(SList<TYPE> &sublist, const iterator &i)
{
    return edit_iterator(this, SpliceAt(sublist, i));
}

template<class TYPE>
typename SList<TYPE>::edit_iterator SList<TYPE>::RemoveItemFor(const TYPE& item)
{
    typename SList<TYPE>::edit_iterator i = Begin();
    for (; i != End(); i++) {
        if (*i == item) return edit_iterator(this, *Remove(i));
    }
    
    // otherwise, return End()
    return edit_iterator(End());
}

template<class TYPE>
typename SList<TYPE>::edit_iterator SList<TYPE>::RemoveAllItemsFor(const TYPE& item)
{
    typename SList<TYPE>::edit_iterator i = Begin();
    for (; i != End();) {
        if (*i == item) i = edit_iterator(this, *Remove(i));
        else i++;
    }
    
    return i;
}

template<class TYPE>
inline typename SList<TYPE>::edit_iterator SList<TYPE>::RemoveItemAt(edit_iterator& i)
{
    return edit_iterator(this, *Remove(i));
}

template<class TYPE>
inline typename SList<TYPE>::edit_iterator SList<TYPE>::Begin(void)
{
    return edit_iterator(this, *SAbstractList::Begin());
}

template<class TYPE>
inline typename SList<TYPE>::edit_iterator SList<TYPE>::End(void)
{
    return edit_iterator(this, *SAbstractList::End());
}

template<class TYPE>
inline typename SList<TYPE>::iterator SList<TYPE>::Begin(void) const
{
    return iterator(this, *SAbstractList::Begin());
}

template<class TYPE>
inline typename SList<TYPE>::iterator SList<TYPE>::End(void) const
{
    return iterator(this, *SAbstractList::End());
}

template<class TYPE> inline
void SList<TYPE>::MakeEmpty(void)
{
    SAbstractList::MakeEmpty();
}

template<class TYPE>
void SList<TYPE>::PerformConstruct(void* base, size_t count) const
{
    BConstruct(static_cast<TYPE*>(base), count);
}

template<class TYPE>
void SList<TYPE>::PerformCopy(void* to, const void* from, size_t count) const
{
    BCopy(static_cast<TYPE*>(to), static_cast<const TYPE*>(from), count);
}

template<class TYPE>
void SList<TYPE>::PerformDestroy(void* base, size_t count) const
{
    BDestroy(static_cast<TYPE*>(base), count);
}

template<class TYPE>
void SList<TYPE>::PerformAssign(void* to, const void* from, size_t count) const
{
    BAssign(static_cast<TYPE*>(to), static_cast<const TYPE*>(from), count);
}

struct SAbstractList::_ListNode {
    _ListNode(void);
    ~_ListNode(void);

    _ListNode* _next;
    _ListNode* _prev;

// This was _data[0] but the ADS compiler dose not seem to like it.
// Someone needs to verify that this has not changed the behavihor
// of List XXX--jparks
    uint8_t _data[1];
};

#if _SUPPORTS_NAMESPACE
} } // namespace palmos::support
#endif

#endif // #ifndef _SUPPORT_LIST_H

---

Generated on Wed Dec 28 22:33:28 2005 by Doxygen 1.4.4 for OpenBinder Documentation Version 1.0

PalmSource, Inc. © 2005