UCommon
/usr/src/RPM/BUILD/ucommon-6.3.3/inc/ucommon/linked.h
Go to the documentation of this file.
00001 // Copyright (C) 2006-2014 David Sugar, Tycho Softworks.
00002 // Copyright (C) 2015 Cherokees of Idaho.
00003 //
00004 // This file is part of GNU uCommon C++.
00005 //
00006 // GNU uCommon C++ is free software: you can redistribute it and/or modify
00007 // it under the terms of the GNU Lesser General Public License as published
00008 // by the Free Software Foundation, either version 3 of the License, or
00009 // (at your option) any later version.
00010 //
00011 // GNU uCommon C++ is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU Lesser General Public License for more details.
00015 //
00016 // You should have received a copy of the GNU Lesser General Public License
00017 // along with GNU uCommon C++.  If not, see <http://www.gnu.org/licenses/>.
00018 
00033 #ifndef _UCOMMON_LINKED_H_
00034 #define _UCOMMON_LINKED_H_
00035 
00036 #ifndef _UCOMMON_CONFIG_H_
00037 #include <ucommon/platform.h>
00038 #endif
00039 
00040 #ifndef _UCOMMON_OBJECT_H_
00041 #include <ucommon/object.h>
00042 #endif
00043 
00044 #ifdef nil
00045 #undef nil
00046 #endif
00047 
00048 namespace ucommon {
00049 
00050 class OrderedObject;
00051 
00059 class __EXPORT LinkedObject : public ObjectProtocol
00060 {
00061 protected:
00062     friend class OrderedIndex;
00063     friend class LinkedRing;
00064     friend class NamedObject;
00065     friend class ObjectStack;
00066 
00067     LinkedObject *Next;
00068 
00073     LinkedObject(LinkedObject **root);
00074 
00080     LinkedObject();
00081 
00082 public:
00083     static const LinkedObject *nil; 
00084     static const LinkedObject *inv; 
00086     virtual ~LinkedObject();
00087 
00091     virtual void release(void);
00092 
00096     virtual void retain(void);
00097 
00104     void enlist(LinkedObject **root);
00105 
00112     void delist(LinkedObject **root);
00113 
00118     bool is_member(LinkedObject *list) const;
00119 
00124     static void purge(LinkedObject *root);
00125 
00130     static unsigned count(const LinkedObject *root);
00131 
00138     static LinkedObject *getIndexed(LinkedObject *root, unsigned index);
00139 
00144     inline LinkedObject *getNext(void) const
00145         {return Next;}
00146 };
00147 
00157 class __EXPORT ReusableObject : public LinkedObject
00158 {
00159     friend class ReusableAllocator;
00160 
00161 protected:
00162     virtual void release(void);
00163 
00164 public:
00169     inline ReusableObject *getNext(void)
00170         {return static_cast<ReusableObject*>(LinkedObject::getNext());}
00171 };
00172 
00180 class __EXPORT OrderedIndex
00181 {
00182 protected:
00183     friend class OrderedObject;
00184     friend class DLinkedObject;
00185     friend class LinkedList;
00186     friend class NamedObject;
00187 
00188     OrderedObject *head, *tail;
00189 
00190     void copy(const OrderedIndex& source);
00191 
00192 public:
00196     OrderedIndex();
00197 
00198     inline OrderedIndex(const OrderedIndex& source)
00199         {copy(source);}
00200 
00204     virtual ~OrderedIndex();
00205 
00210     LinkedObject *find(unsigned offset) const;
00211 
00216     unsigned count(void) const;
00217 
00221     void purge(void);
00222 
00226     void reset(void);
00227 
00232     virtual void lock_index(void);
00233 
00238     virtual void unlock_index(void);
00239 
00246     LinkedObject **index(void) const;
00247 
00253     LinkedObject *get(void);
00254 
00259     void add(OrderedObject *ordered);
00260 
00266     inline LinkedObject *getIndexed(unsigned index) const
00267         {return LinkedObject::getIndexed((LinkedObject*)head, index);}
00268 
00273     inline LinkedObject *begin(void) const
00274         {return (LinkedObject*)(head);}
00275 
00280     inline LinkedObject *end(void) const
00281         {return (LinkedObject*)(tail);}
00282 
00287     inline LinkedObject *operator*() const
00288         {return (LinkedObject*)(head);}
00289 
00294     OrderedIndex& operator=(const OrderedIndex& object)
00295         {copy(object); return *this;}
00296 
00301     void operator*=(OrderedObject *object);
00302 };
00303 
00310 class __EXPORT OrderedObject : public LinkedObject
00311 {
00312 protected:
00313     friend class LinkedList;
00314     friend class OrderedIndex;
00315     friend class DLinkedObject;
00316     friend class ObjectQueue;
00317 
00322     OrderedObject(OrderedIndex *index);
00323 
00327     OrderedObject();
00328 
00329 public:
00334     void enlistTail(OrderedIndex *index);
00335 
00340     void enlistHead(OrderedIndex *index);
00341 
00347     virtual void enlist(OrderedIndex *index);
00348 
00353     void delist(OrderedIndex *index);
00354 
00359     inline OrderedObject *getNext(void) const
00360         {return static_cast<OrderedObject *>(LinkedObject::getNext());}
00361 };
00362 
00367 class __EXPORT DLinkedObject : public OrderedObject
00368 {
00369 public:
00370     friend class ObjectQueue;
00371 
00375     DLinkedObject();
00376 
00377 protected:
00381     void delist(void);
00382 
00383 private:
00384     DLinkedObject *Prev;
00385 };
00386 
00401 class __EXPORT NamedObject : public OrderedObject
00402 {
00403 protected:
00404     char *Id;
00405 
00409     NamedObject();
00410 
00417     NamedObject(NamedObject **hash, char *name, unsigned size = 1);
00418 
00425     NamedObject(OrderedIndex *index, char *name);
00426 
00434     ~NamedObject();
00435 
00440     virtual void clearId(void);
00441 
00442 public:
00449     void add(NamedObject **hash, char *name, unsigned size = 1);
00450 
00456     static void purge(NamedObject **hash, unsigned size);
00457 
00466     static NamedObject **index(NamedObject **hash, unsigned size);
00467 
00473     static unsigned count(NamedObject **hash, unsigned size);
00474 
00482     static NamedObject *find(NamedObject *root, const char *name);
00483 
00490     static NamedObject *remove(NamedObject **root, const char *name);
00491 
00499     static NamedObject *map(NamedObject **hash, const char *name, unsigned size);
00500 
00508     static NamedObject *remove(NamedObject **hash, const char *name, unsigned size);
00509 
00517     static NamedObject *skip(NamedObject **hash, NamedObject *current, unsigned size);
00518 
00524     static unsigned keyindex(const char *name, unsigned size);
00525 
00533     static NamedObject **sort(NamedObject **list, size_t count = 0);
00534 
00539     inline NamedObject *getNext(void) const
00540         {return static_cast<NamedObject*>(LinkedObject::getNext());}
00541 
00546     inline char *getId(void) const
00547         {return Id;};
00548 
00556     virtual int compare(const char *name) const;
00557 
00563     inline bool equal(const char *name) const
00564         {return (compare(name) == 0);}
00565 
00571     inline bool operator==(const char *name) const
00572         {return compare(name) == 0;}
00573 
00579     inline bool operator!=(const char *name) const
00580         {return compare(name) != 0;}
00581 };
00582 
00590 class __EXPORT NamedTree : public NamedObject
00591 {
00592 protected:
00593     NamedTree *Parent;
00594     OrderedIndex Child;
00595 
00600     NamedTree(char *name = NULL);
00601 
00607     NamedTree(NamedTree *parent, char *name);
00608 
00613     NamedTree(const NamedTree& source);
00614 
00620     virtual ~NamedTree();
00621 
00627     void purge(void);
00628 
00629 public:
00638     NamedTree *find(const char *name) const;
00639 
00650     NamedTree *path(const char *path) const;
00651 
00659     NamedTree *leaf(const char *name) const;
00660 
00666     NamedTree *getChild(const char *name) const;
00667 
00674     NamedTree *getLeaf(const char *name) const;
00675 
00682     inline NamedTree *getFirst(void) const
00683         {return static_cast<NamedTree *>(Child.begin());}
00684 
00689     inline NamedTree *getParent(void) const
00690         {return Parent;};
00691 
00697     inline NamedTree *getIndexed(unsigned index) const
00698         {return static_cast<NamedTree *>(Child.getIndexed(index));}
00699 
00704     inline OrderedIndex *getIndex(void) const
00705         {return const_cast<OrderedIndex*>(&Child);}
00706 
00711     inline operator bool() const
00712         {return (Id != NULL);}
00713 
00718     inline bool operator!() const
00719         {return (Id == NULL);}
00720 
00726     void setId(char *name);
00727 
00732     void remove(void);
00733 
00738     inline bool is_leaf(void) const
00739         {return (Child.begin() == NULL);}
00740 
00745     inline bool is_root(void) const
00746         {return (Parent == NULL);}
00747 
00752     void relistTail(NamedTree *trunk);
00753 
00758     void relistHead(NamedTree *trunk);
00759 
00764     inline void relist(NamedTree *trunk = NULL)
00765         {relistTail(trunk);}
00766 };
00767 
00774 class __EXPORT LinkedList : public OrderedObject
00775 {
00776 protected:
00777     friend class ObjectQueue;
00778 
00779     LinkedList *Prev;
00780     OrderedIndex *Root;
00781 
00786     LinkedList(OrderedIndex *index);
00787 
00791     LinkedList();
00792 
00797     virtual ~LinkedList();
00798 
00799 public:
00803     void delist(void);
00804 
00810     void enlistHead(OrderedIndex *index);
00811 
00817     void enlistTail(OrderedIndex *index);
00818 
00824     void enlist(OrderedIndex *index);
00825 
00830     inline bool is_head(void) const
00831         {return Root->head == (OrderedObject *)this;}
00832 
00837     inline bool is_tail(void) const
00838         {return Root->tail == (OrderedObject *)this;}
00839 
00844     inline LinkedList *getPrev(void) const
00845         {return Prev;}
00846 
00851     inline LinkedList *getNext(void) const
00852         {return static_cast<LinkedList*>(LinkedObject::getNext());}
00853 
00858     void insertTail(LinkedList *object);
00859 
00864     void insertHead(LinkedList *object);
00865 
00870     virtual void insert(LinkedList *object);
00871 
00876     inline void operator+=(LinkedList *object)
00877         {insertTail(object);}
00878 
00883     inline void operator-=(LinkedList *object)
00884         {insertHead(object);}
00885 
00890     inline void operator*=(LinkedList *object)
00891         {insert(object);}
00892 };
00893 
00899 class __EXPORT ObjectQueue : public OrderedIndex
00900 {
00901 public:
00905     ObjectQueue();
00906 
00911     void add(DLinkedObject *object);
00912 
00917     void push(DLinkedObject *object);
00918 
00923     DLinkedObject *pull(void);
00924 
00929     DLinkedObject *pop(void);
00930 };
00931 
00932 class __EXPORT ObjectStack
00933 {
00934 protected:
00935     LinkedObject *root;
00936 
00937 public:
00941     ObjectStack();
00942 
00947     ObjectStack(LinkedObject *list);
00948 
00953     void push(LinkedObject *object);
00954 
00959     LinkedObject *pull(void);
00960 
00965     inline LinkedObject *pop(void)
00966         {return ObjectStack::pull();}
00967 };
00968 
00969 
00975 class __EXPORT MultiMap : public ReusableObject
00976 {
00977 private:
00978     typedef struct {
00979         const char *key;
00980         size_t keysize;
00981         MultiMap *next;
00982         MultiMap **root;
00983     }   link_t;
00984 
00985     unsigned paths;
00986     link_t *links;
00987 
00988 protected:
00993     MultiMap(unsigned count);
00994 
00998     virtual ~MultiMap();
00999 
01007     virtual bool equal(unsigned path, caddr_t key, size_t size) const;
01008 
01009 public:
01015     void enlist(unsigned path, MultiMap **root);
01016 
01025     void enlist(unsigned path, MultiMap **index, caddr_t key, unsigned size, size_t keysize = 0);
01026 
01031     void delist(unsigned path);
01032 
01037     MultiMap *next(unsigned path) const;
01038 
01046     static unsigned keyindex(caddr_t key, unsigned max, size_t size = 0);
01047 
01057     static MultiMap *find(unsigned path, MultiMap **index, caddr_t key, unsigned max, size_t size = 0);
01058 };
01059 
01067 template <typename T, class O=NamedObject>
01068 class named_value : public object_value<T, O>
01069 {
01070 public:
01076     inline named_value(LinkedObject **root, char *name)
01077         {LinkedObject::enlist(root); O::id = name;}
01078 
01083     inline void operator=(const T& typed_value)
01084         {this->set(typed_value);}
01085 
01092     inline static named_value find(named_value *first, const char *name)
01093         {return static_cast<named_value *>(NamedObject::find(first, name));}
01094 };
01095 
01104 template <typename T, class O=OrderedObject>
01105 class linked_value : public object_value<T, O>
01106 {
01107 public:
01111     inline linked_value() {}
01112 
01117     inline linked_value(LinkedObject **root)
01118         {LinkedObject::enlist(root);}
01119 
01124     inline linked_value(OrderedIndex *index)
01125         {O::enlist(index);}
01126 
01132     inline linked_value(LinkedObject **root, const T& typed_value)
01133         {LinkedObject::enlist(root); this->set(typed_value);}
01134 
01140     inline linked_value(OrderedIndex *index, const T& typed_value)
01141         {O::enlist(index); this->set(typed_value);}
01142 
01147     inline void operator=(const T& typed_value)
01148         {this->set(typed_value);}
01149 };
01150 
01156 template <class T>
01157 class objstack : public ObjectStack
01158 {
01159 public:
01163     inline objstack() : ObjectStack() {}
01164 
01168     inline objstack(T *list) : ObjectStack(list) {}
01169 
01174     inline void push(T *object)
01175         {ObjectStack::push(object);}
01176 
01181     inline void add(T *object)
01182         {ObjectStack::push(object);}
01183 
01188     inline T *pull(void)
01189         {return (T *)ObjectStack::pull();}
01190 
01195     inline T *pop(void)
01196         {return (T *)ObjectStack::pull();}
01197 };
01198 
01205 template <class T>
01206 class objfifo : public OrderedIndex
01207 {
01208 public:
01212     inline objfifo() : OrderedIndex() {}
01213 
01218     inline void push(T *object)
01219         {OrderedIndex::add((OrderedObject *)object);}
01220 
01225     inline void add(T *object)
01226         {OrderedIndex::add((OrderedObject *)object);}
01227 
01232     inline T *pull(void)
01233         {return (T *)OrderedIndex::get();}
01234 
01239     inline T *pop(void)
01240         {return (T *)OrderedIndex::get();}
01241 };
01242 
01248 template <class T>
01249 class objqueue : public ObjectQueue
01250 {
01251 public:
01255     inline objqueue() : ObjectQueue() {}
01256 
01261     inline void push(T *object)
01262         {ObjectQueue::push((DLinkedObject *)object);}
01263 
01268     inline void add(T *object)
01269         {ObjectQueue::add((DLinkedObject *)object);}
01270 
01275     inline T *pull(void)
01276         {return (T *)ObjectQueue::pull();}
01277 
01282     inline T *pop(void)
01283         {return (T *)ObjectQueue::pop();}
01284 };
01285 
01292 template <class T>
01293 class linked_pointer
01294 {
01295 private:
01296     T *ptr;
01297 
01298 public:
01303     inline linked_pointer(T *pointer)
01304         {ptr = pointer;}
01305 
01310     inline linked_pointer(const linked_pointer &pointer)
01311         {ptr = pointer.ptr;}
01312 
01317     inline linked_pointer(LinkedObject *pointer)
01318         {ptr = static_cast<T*>(pointer);}
01319 
01320     inline linked_pointer(const LinkedObject *pointer)
01321         {ptr = static_cast<T*>(pointer);}
01322 
01327     inline linked_pointer(OrderedIndex *index)
01328         {ptr = static_cast<T*>(index->begin());}
01329 
01333     inline linked_pointer()
01334         {ptr = NULL;}
01335 
01340     inline void operator=(T *pointer)
01341         {ptr = pointer;}
01342 
01347     inline void operator=(linked_pointer &pointer)
01348         {ptr = pointer.ptr;}
01349 
01354     inline void operator=(OrderedIndex *index)
01355         {ptr = static_cast<T*>(index->begin());}
01356 
01361     inline void operator=(LinkedObject *pointer)
01362         {ptr = static_cast<T*>(pointer);}
01363 
01368     inline T* operator->() const
01369         {return ptr;}
01370 
01375     inline T* operator*() const
01376         {return ptr;}
01377 
01382     inline operator T*() const
01383         {return ptr;}
01384 
01388     inline void prev(void)
01389         {ptr = static_cast<T*>(ptr->getPrev());}
01390 
01394     inline void next(void)
01395         {ptr = static_cast<T*>(ptr->getNext());}
01396 
01401     inline T *getNext(void) const
01402         {return static_cast<T*>(ptr->getNext());}
01403 
01409     inline T *getPrev(void) const
01410         {return static_cast<T*>(ptr->getPrev());}
01411 
01415     inline void operator++()
01416         {ptr = static_cast<T*>(ptr->getNext());}
01417 
01421     inline void operator--()
01422         {ptr = static_cast<T*>(ptr->getPrev());}
01423 
01428     inline bool is_next(void) const
01429         {return (ptr->getNext() != NULL);}
01430 
01435     inline bool is_prev(void) const
01436         {return (ptr->getPrev() != NULL);}
01437 
01442     inline operator bool() const
01443         {return (ptr != NULL);}
01444 
01449     inline bool operator!() const
01450         {return (ptr == NULL);}
01451 
01456     inline LinkedObject **root(void) const
01457         {T **r = &ptr; return (LinkedObject**)r;}
01458 };
01459 
01467 template <typename T, unsigned P>
01468 class multimap : public MultiMap
01469 {
01470 protected:
01471     T value;
01472 
01473 public:
01477     inline multimap() : MultiMap(P) {}
01478 
01482     inline ~multimap() {}
01483 
01488     inline T &get(void) const
01489         {return value;}
01490 
01496     inline multimap *next(unsigned path)
01497         {return static_cast<multimap*>(MultiMap::next(path));}
01498 
01503     inline T& operator*() const
01504         {return value;}
01505 
01510     inline void setPointer(const T pointer)
01511         {value = pointer;}
01512 
01517     inline void set(const T &reference)
01518         {value = reference;}
01519 
01524     inline void operator=(const T& data)
01525         {value = data;}
01526 
01536     inline static multimap *find(unsigned path, MultiMap **index, caddr_t key, unsigned size, unsigned keysize = 0)
01537         {return static_cast<multimap*>(MultiMap::find(path, index, key, size, keysize));}
01538 };
01539 
01557 template <typename T>
01558 class treemap : public NamedTree
01559 {
01560 protected:
01561     T value;
01562 
01563 public:
01569     inline treemap(char *name = NULL) : NamedTree(name) {}
01570 
01575     inline treemap(const treemap& source) : NamedTree(source)
01576         {value = source.value;};
01577 
01583     inline treemap(treemap *parent, char *name) : NamedTree(parent, name) {}
01584 
01591     inline treemap(treemap *parent, char *name, T& reference) :
01592         NamedTree(parent, name) {value = reference;}
01593 
01598     inline const T& get(void) const
01599         {return value;}
01600 
01605     inline const T& operator*() const
01606         {return value;}
01607 
01613     static inline T getPointer(treemap *node)
01614         {return (node == NULL) ? NULL : node->value;}
01615 
01620     inline bool is_attribute(void) const
01621         {return (!Child.begin() && value != NULL);}
01622 
01627     inline const T getPointer(void) const
01628         {return value;}
01629 
01634     inline const T& getData(void) const
01635         {return value;}
01636 
01641     inline void setPointer(const T pointer)
01642         {value = pointer;}
01643 
01648     inline void set(const T& reference)
01649         {value = reference;}
01650 
01655     inline void operator=(const T& data)
01656         {value = data;}
01657 
01663     inline treemap *getIndexed(unsigned index) const
01664         {return static_cast<treemap*>(Child.getIndexed(index));}
01665 
01670     inline treemap *getParent(void) const
01671         {return static_cast<treemap*>(Parent);}
01672 
01679     inline treemap *getChild(const char *name) const
01680         {return static_cast<treemap*>(NamedTree::getChild(name));}
01681 
01688     inline treemap *getLeaf(const char *name) const
01689         {return static_cast<treemap*>(NamedTree::getLeaf(name));}
01690 
01698     inline T getValue(const char *name) const
01699         {return getPointer(getLeaf(name));}
01700 
01707     inline treemap *find(const char *name) const
01708         {return static_cast<treemap*>(NamedTree::find(name));}
01709 
01716     inline treemap *path(const char *path) const
01717         {return static_cast<treemap*>(NamedTree::path(path));}
01718 
01725     inline treemap *leaf(const char *name) const
01726         {return static_cast<treemap*>(NamedTree::leaf(name));}
01727 
01732     inline treemap *getFirst(void) const
01733         {return static_cast<treemap*>(NamedTree::getFirst());}
01734 };
01735 
01743 template <class T, unsigned M = 177>
01744 class keymap
01745 {
01746 private:
01747     NamedObject *idx[M];
01748 
01749 public:
01753     inline ~keymap()
01754         {NamedObject::purge(idx, M);}
01755 
01760     inline NamedObject **root(void) const
01761         {return idx;}
01762 
01767     inline unsigned limit(void) const
01768         {return M;}
01769 
01775     inline T *get(const char *name) const
01776         {return static_cast<T*>(NamedObject::map(idx, name, M));}
01777 
01783     inline T& operator[](const char *name) const
01784         {return static_cast<T*>(NamedObject::map(idx, name, M));}
01785 
01791     inline void add(const char *name, T& object)
01792         {object.NamedObject::add(idx, name, M);}
01793 
01799     inline void add(const char *name, T *object)
01800         {object->NamedObject::add(idx, name, M);}
01801 
01807     inline T *remove(const char *name)
01808         {return static_cast<T*>(NamedObject::remove(idx, name, M));}
01809 
01814     inline T *begin(void) const
01815         {return static_cast<T*>(NamedObject::skip(idx, NULL, M));}
01816 
01822     inline T *next(T *current) const
01823         {return static_cast<T*>(NamedObject::skip(idx, current, M));}
01824 
01829     inline unsigned count(void) const
01830         {return NamedObject::count(idx, M);}
01831 
01838     inline T **index(void) const
01839         {return NamedObject::index(idx, M);}
01840 
01847     inline T **sort(void) const
01848         {return NamedObject::sort(NamedObject::index(idx, M));}
01849 
01853     typedef linked_pointer<T> iterator;
01854 };
01855 
01862 template <class T>
01863 class keylist : public OrderedIndex
01864 {
01865 public:
01870     inline NamedObject **root(void)
01871         {return static_cast<NamedObject**>(&head);}
01872 
01878     inline T *begin(void)
01879         {return static_cast<T*>(head);}
01880 
01886     inline T *end(void)
01887         {return static_cast<T*>(tail);}
01888 
01895     inline T *create(const char *name)
01896         {return new T(this, name);}
01897 
01903     inline T *next(LinkedObject *current)
01904         {return static_cast<T*>(current->getNext());}
01905 
01911     inline T *find(const char *name)
01912         {return static_cast<T*>(NamedObject::find(begin(), name));}
01913 
01914     inline T *offset(unsigned offset)
01915         {return static_cast<T*>(OrderedIndex::find(offset));}
01916 
01922     inline T& operator[](unsigned offset)
01923         {return static_cast<T&>(OrderedIndex::find(offset));}
01924 
01925     inline T& operator[](const char *name)
01926         {return static_cast<T&>(NamedObject::find(begin(), name));}
01927 
01934     inline T **index(void)
01935         {return static_cast<T**>(OrderedIndex::index());}
01936 
01943     inline T **sort(void)
01944         {return static_cast<T**>(NamedObject::sort(index()));}
01945 
01949     typedef linked_pointer<T> iterator;
01950 };
01951 
01955 typedef LinkedObject *LinkedIndex;
01956 
01960 typedef ObjectStack objstack_t;
01961 
01965 typedef OrderedIndex objfifo_t;
01966 
01970 typedef ObjectQueue objqueue_t;
01971 
01972 } // namespace ucommon
01973 
01974 #endif