linked.h

Go to the documentation of this file.

// Copyright (C) 2006-2014 David Sugar, Tycho Softworks.
// Copyright (C) 2015 Cherokees of Idaho.
//
// This file is part of GNU uCommon C++.
//
// GNU uCommon C++ is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as published
// by the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// GNU uCommon C++ is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with GNU uCommon C++.  If not, see <http://www.gnu.org/licenses/>.
 
#ifndef _UCOMMON_LINKED_H_
#define _UCOMMON_LINKED_H_
 
#ifndef _UCOMMON_CONFIG_H_
#include <ucommon/platform.h>
#endif
 
#ifndef _UCOMMON_OBJECT_H_
#include <ucommon/object.h>
#endif
 
namespace ucommon {
 
class OrderedObject;
 
class __EXPORT LinkedObject : public __PROTOCOL ObjectProtocol
{
private:
    friend class OrderedIndex;
    friend class NamedObject;
 
protected:
    LinkedObject *Next;
 
    LinkedObject(LinkedObject **root);
 
    LinkedObject();
 
    LinkedObject(const LinkedObject& from);
 
public:
    virtual ~LinkedObject();
 
    virtual void release(void) __OVERRIDE;
 
    virtual void retain(void) __OVERRIDE;
 
    void enlist(LinkedObject **root);
 
    void delist(LinkedObject **root);
 
    bool is_member(LinkedObject *list) const;
 
    static void purge(LinkedObject *root);
 
    static unsigned count(const LinkedObject *root);
 
    static LinkedObject *getIndexed(LinkedObject *root, unsigned index);
 
    inline LinkedObject *getNext(void) const {
        return Next;
    }
};
 
class __EXPORT ReusableObject : public LinkedObject
{
    friend class ReusableAllocator;
 
protected:
    virtual void release(void) __OVERRIDE;
 
public:
    inline ReusableObject *getNext(void) {
        return polypointer_cast<ReusableObject*>(LinkedObject::getNext());
    }
};
 
class __EXPORT OrderedIndex
{
protected:
    friend class OrderedObject;
    friend class DLinkedObject;
    friend class NamedObject;
 
    OrderedObject *head, *tail;
 
public:
    void copy(const OrderedIndex& source);
 
    OrderedIndex();
 
    inline OrderedIndex(const OrderedIndex& source) {
        copy(source);
    }
 
    virtual ~OrderedIndex();
 
    LinkedObject *find(unsigned offset) const;
 
    unsigned count(void) const;
 
    void purge(void);
 
    void reset(void);
 
    virtual void lock_index(void);
 
    virtual void unlock_index(void);
 
    LinkedObject **index(void) const;
 
    LinkedObject *get(void);
 
    void add(OrderedObject *ordered);
 
    inline LinkedObject *getIndexed(unsigned index) const {
        return LinkedObject::getIndexed(polystatic_cast<LinkedObject*>(head), index);
    }
 
    inline LinkedObject *begin(void) const {
        return polystatic_cast<LinkedObject*>(head);
    }
 
    inline LinkedObject *end(void) const {
        return polystatic_cast<LinkedObject*>(tail);
    }
 
    inline LinkedObject *operator*() const {
        return polystatic_cast<LinkedObject*>(head);
    }
 
    OrderedIndex& operator=(const OrderedIndex& object) {
        copy(object); 
        return *this;
    }
 
    void operator*=(OrderedObject *object);
};
 
class __EXPORT OrderedObject : public LinkedObject
{
private:
    friend class DLinkedObject;
    friend class OrderedIndex;
 
protected:
    OrderedObject(OrderedIndex *index);
 
    OrderedObject();
 
    OrderedObject(const OrderedObject& from);
 
public:
    void enlistTail(OrderedIndex *index);
 
    void enlistHead(OrderedIndex *index);
 
    virtual void enlist(OrderedIndex *index);
 
    void delist(OrderedIndex *index);
 
    inline OrderedObject *getNext(void) const {
        return static_cast<OrderedObject *>(LinkedObject::getNext());
    }
};
 
class __EXPORT NamedObject : public OrderedObject
{
protected:
    char *Id;
 
    NamedObject();
 
    NamedObject(NamedObject **hash, char *name, unsigned size = 1);
 
    NamedObject(OrderedIndex *index, char *name);
 
    ~NamedObject();
 
    virtual void clearId(void);
 
public:
    void add(NamedObject **hash, char *name, unsigned size = 1);
 
    static void purge(NamedObject **hash, unsigned size);
 
    static NamedObject **index(NamedObject **hash, unsigned size);
 
    static unsigned count(NamedObject **hash, unsigned size);
 
    static NamedObject *find(NamedObject *root, const char *name);
 
    static NamedObject *remove(NamedObject **root, const char *name);
 
    static NamedObject *map(NamedObject **hash, const char *name, unsigned size);
 
    static NamedObject *remove(NamedObject **hash, const char *name, unsigned size);
 
    static NamedObject *skip(NamedObject **hash, NamedObject *current, unsigned size);
 
    static unsigned keyindex(const char *name, unsigned size);
 
    static NamedObject **sort(NamedObject **list, size_t count = 0);
 
    inline NamedObject *getNext(void) const {
        return static_cast<NamedObject*>(LinkedObject::getNext());
    }
 
    inline char *getId(void) const {
        return Id;
    };
 
    virtual int compare(const char *name) const;
 
    inline bool equal(const char *name) const {
        return (compare(name) == 0);
    }
 
    inline bool operator==(const char *name) const {
        return compare(name) == 0;
    }
 
    inline bool operator!=(const char *name) const {
        return compare(name) != 0;
    }
};
 
class __EXPORT NamedTree : public NamedObject
{
protected:
    NamedTree *Parent;
    OrderedIndex Child;
 
    NamedTree(char *name = NULL);
 
    NamedTree(NamedTree *parent, char *name);
 
    NamedTree(const NamedTree& source);
 
    virtual ~NamedTree();
 
    void purge(void);
 
public:
    NamedTree *find(const char *name) const;
 
    NamedTree *path(const char *path) const;
 
    NamedTree *leaf(const char *name) const;
 
    NamedTree *getChild(const char *name) const;
 
    NamedTree *getLeaf(const char *name) const;
 
    inline NamedTree *getFirst(void) const {
        return static_cast<NamedTree *>(Child.begin());
    }
 
    inline NamedTree *getParent(void) const {
        return static_cast<NamedTree *>(Parent);
    };
 
    inline NamedTree *getIndexed(unsigned index) const {
        return static_cast<NamedTree *>(Child.getIndexed(index));
    }
 
    inline OrderedIndex *getIndex(void) const {
        return const_cast<OrderedIndex*>(&Child);
    }
 
    inline operator bool() const {
        return (Id != NULL);
    }
 
    inline bool operator!() const {
        return (Id == NULL);
    }
 
    void setId(char *name);
 
    void remove(void);
 
    inline bool is_leaf(void) const {
        return (Child.begin() == NULL);
    }
 
    inline bool is_root(void) const {
        return (Parent == NULL);
    }
 
    void relistTail(NamedTree *trunk);
 
    void relistHead(NamedTree *trunk);
 
    inline void relist(NamedTree *trunk = NULL) {
        relistTail(trunk);
    }
};
 
class __EXPORT DLinkedObject : public OrderedObject
{
protected:
    friend class ObjectQueue;
 
    DLinkedObject *Prev;
    OrderedIndex *Root;
 
    DLinkedObject(OrderedIndex *index);
 
    DLinkedObject();
 
    DLinkedObject(const DLinkedObject& from);
 
    virtual ~DLinkedObject();
 
public:
    void delist(void);
 
    void enlistHead(OrderedIndex *index);
 
    void enlistTail(OrderedIndex *index);
 
    void enlist(OrderedIndex *index);
 
    inline bool is_head(void) const {
        return polypointer_cast<DLinkedObject *>(Root->head) == this;
    }
 
    inline bool is_tail(void) const {
        return polypointer_cast<DLinkedObject *>(Root->tail) == this;
    }
 
    inline DLinkedObject *getPrev(void) const {
        return static_cast<DLinkedObject*>(Prev);
    }
 
    inline DLinkedObject *getNext(void) const {
        return static_cast<DLinkedObject*>(LinkedObject::getNext());
    }
 
    void insertTail(DLinkedObject *object);
 
    void insertHead(DLinkedObject *object);
 
    virtual void insert(DLinkedObject *object);
 
    inline DLinkedObject& operator+=(DLinkedObject *object) {
        insertTail(object);
        return *this;
    }
 
    inline DLinkedObject& operator-=(DLinkedObject *object) {
        insertHead(object);
        return *this;
    }
 
    inline DLinkedObject& operator*=(DLinkedObject *object) {
        insert(object);
        return *this;
    }
};
 
template <typename T, class O = LinkedObject>
class linked_value : public O
{
protected:
    __DELETE_COPY(linked_value);
 
public:
    T value;
 
    inline linked_value() {}
 
    inline linked_value(LinkedObject **root) {
        LinkedObject::enlist(root);
    }
 
    inline linked_value(OrderedIndex *index) {
        O::enlist(index);
    }
 
    inline linked_value(LinkedObject **root, const T& typed_value) {
        LinkedObject::enlist(root); 
        value = typed_value;
    }
 
    inline linked_value(OrderedIndex *index, const T& typed_value) {
        O::enlist(index);
        value = typed_value; 
    }
 
    inline void set(const T& typed_value) {
        value = typed_value;
    }
 
    inline linked_value& operator=(const T& typed_value) {
        value = typed_value;
        return *this;
    }
 
    inline T& operator*() {
        return value;
    }
 
    inline operator T&() {
        return value;
    }
 
    inline void operator()(const T data) {
        value = data;
    }
};
 
template <class T>
class linked_pointer
{
private:
    T *ptr;
 
public:
    inline linked_pointer(T *pointer) {
        ptr = pointer;
    }
 
    inline linked_pointer(const linked_pointer &pointer) {
        ptr = pointer.ptr;
    }
 
    inline linked_pointer(LinkedObject *pointer) {
        ptr = static_cast<T*>(pointer);
    }
 
    inline linked_pointer(const LinkedObject *pointer) {
        ptr = static_cast<T*>(pointer);
    }
 
    inline linked_pointer(OrderedIndex *index) {
        ptr = static_cast<T*>(index->begin());
    }
 
    inline linked_pointer() {
        ptr = NULL;
    }
 
    inline void operator=(T *pointer) {
        ptr = pointer;
    }
 
    inline void operator=(linked_pointer &pointer) {
        ptr = pointer.ptr;
    }
 
    inline void operator=(OrderedIndex *index) {
        ptr = static_cast<T*>(index->begin());
    }
 
    inline void operator=(LinkedObject *pointer) {
        ptr = static_cast<T*>(pointer);
    }
 
    inline T* operator->() const {
        return ptr;
    }
 
    inline T* operator*() const {
        return ptr;
    }
 
    inline operator T*() const {
        return ptr;
    }
 
    inline void prev(void) {
        ptr = static_cast<T*>(ptr->getPrev());
    }
 
    inline void next(void) {
        ptr = static_cast<T*>(ptr->getNext());
    }
 
    inline T *getNext(void) const {
        return static_cast<T*>(ptr->getNext());
    }
 
    inline T *getPrev(void) const {
        return static_cast<T*>(ptr->getPrev());
    }
 
    inline void operator++() {
        ptr = static_cast<T*>(ptr->getNext());
    }
 
    inline void operator--() {
        ptr = static_cast<T*>(ptr->getPrev());
    }
 
    inline bool is_next(void) const {
        return (ptr->getNext() != NULL);
    }
 
    inline bool is_prev(void) const {
        return (ptr->getPrev() != NULL);
    }
 
    inline operator bool() const {
        return (ptr != NULL);
    }
 
    inline bool operator!() const {
        return (ptr == NULL);
    }
 
    inline bool is() const {
        return (ptr != NULL);
    }
 
    inline LinkedObject **root(void) const {
        T **r = &ptr;
        return static_cast<LinkedObject**>(r);
    }
};
 
template <typename T>
class treemap : public NamedTree
{
protected:
    T value;
 
public:
    inline treemap(char *name = NULL) : NamedTree(name) {}
 
    inline treemap(const treemap& source) : NamedTree(source) {
        value = source.value;
    };
 
    inline treemap(treemap *parent, char *name) : NamedTree(parent, name) {}
 
    inline treemap(treemap *parent, char *name, T& reference) : NamedTree(parent, name) {
        value = reference;
    }
 
    inline const T& get(void) const {
        return value;
    }
 
    inline const T& operator*() const {
        return value;
    }
 
    static inline T getPointer(treemap *node) {
        return (node == NULL) ? NULL : node->value;
    }
 
    inline bool is_attribute(void) const {
        return (!Child.begin() && value != NULL);
    }
 
    inline const T getPointer(void) const {
        return value;
    }
 
    inline const T& getData(void) const {
        return value;
    }
 
    inline void setPointer(const T pointer) {
        value = pointer;
    }
 
    inline void set(const T& reference) {
        value = reference;
    }
 
    inline void operator=(const T& data) {
        value = data;
    }
 
    inline treemap *getIndexed(unsigned index) const {
        return static_cast<treemap*>(Child.getIndexed(index));
    }
 
    inline treemap *getParent(void) const {
        return static_cast<treemap*>(Parent);
    }
 
    inline treemap *getChild(const char *name) const {
        return static_cast<treemap*>(NamedTree::getChild(name));
    }
 
    inline treemap *getLeaf(const char *name) const {
        return static_cast<treemap*>(NamedTree::getLeaf(name));
    }
 
    inline T getValue(const char *name) const {
        return getPointer(getLeaf(name));
    }
 
    inline treemap *find(const char *name) const {
        return static_cast<treemap*>(NamedTree::find(name));
    }
 
    inline treemap *path(const char *path) const {
        return static_cast<treemap*>(NamedTree::path(path));
    }
 
    inline treemap *leaf(const char *name) const {
        return static_cast<treemap*>(NamedTree::leaf(name));
    }
 
    inline treemap *getFirst(void) const {
        return static_cast<treemap*>(NamedTree::getFirst());
    }
};
 
typedef LinkedObject *LinkedIndex;
 
typedef DLinkedObject LinkedList;   // compatibility for older code
 
} // namespace ucommon
 
#endif