ucommon/linked.h

Go to the documentation of this file.
00001 // Copyright (C) 2006-2010 David Sugar, Tycho Softworks.
00002 //
00003 // This file is part of GNU uCommon C++.
00004 //
00005 // GNU uCommon C++ is free software: you can redistribute it and/or modify
00006 // it under the terms of the GNU Lesser General Public License as published
00007 // by the Free Software Foundation, either version 3 of the License, or
00008 // (at your option) any later version.
00009 //
00010 // GNU uCommon C++ is distributed in the hope that it will be useful,
00011 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00012 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00013 // GNU Lesser General Public License for more details.
00014 //
00015 // You should have received a copy of the GNU Lesser General Public License
00016 // along with GNU uCommon C++.  If not, see <http://www.gnu.org/licenses/>.
00017 
00032 #ifndef _UCOMMON_LINKED_H_
00033 #define _UCOMMON_LINKED_H_
00034 
00035 #ifndef _UCOMMON_CONFIG_H_
00036 #include <ucommon/platform.h>
00037 #endif
00038 
00039 #ifndef _UCOMMON_OBJECT_H_
00040 #include <ucommon/object.h>
00041 #endif
00042 
00043 NAMESPACE_UCOMMON
00044 
00045 class OrderedObject;
00046 
00054 class __EXPORT LinkedObject : public ObjectProtocol
00055 {
00056 protected:
00057     friend class OrderedIndex;
00058     friend class LinkedRing;
00059     friend class NamedObject;
00060     friend class ObjectStack;
00061 
00062     LinkedObject *Next;
00063 
00068     LinkedObject(LinkedObject **root);
00069 
00075     LinkedObject();
00076 
00077 public:
00078     static const LinkedObject *nil; 
00079     static const LinkedObject *inv; 
00081     virtual ~LinkedObject();
00082 
00086     virtual void release(void);
00087 
00091     virtual void retain(void);
00092 
00099     void enlist(LinkedObject **root);
00100 
00107     void delist(LinkedObject **root);
00108 
00113     bool is_member(LinkedObject *list) const;
00114 
00119     static void purge(LinkedObject *root);
00120 
00125     static unsigned count(const LinkedObject *root);
00126 
00133     static LinkedObject *getIndexed(LinkedObject *root, unsigned index);
00134 
00139     inline LinkedObject *getNext(void) const
00140         {return Next;};
00141 };
00142 
00152 class __EXPORT ReusableObject : public LinkedObject
00153 {
00154     friend class ReusableAllocator;
00155 
00156 protected:
00157     virtual void release(void);
00158 
00159 public:
00164     inline ReusableObject *getNext(void)
00165         {return static_cast<ReusableObject*>(LinkedObject::getNext());};
00166 };
00167 
00175 class __EXPORT OrderedIndex
00176 {
00177 protected:
00178     friend class OrderedObject;
00179     friend class DLinkedObject;
00180     friend class LinkedList;
00181     friend class NamedObject;
00182 
00183     OrderedObject *head, *tail;
00184 
00185     void copy(const OrderedIndex& source);
00186 
00187 public:
00191     OrderedIndex();
00192 
00193     inline OrderedIndex(const OrderedIndex& source)
00194         {copy(source);}
00195 
00199     virtual ~OrderedIndex();
00200 
00205     LinkedObject *find(unsigned offset) const;
00206 
00211     unsigned count(void) const;
00212 
00216     void purge(void);
00217 
00221     void reset(void);
00222 
00227     virtual void lock_index(void);
00228 
00233     virtual void unlock_index(void);
00234 
00241     LinkedObject **index(void) const;
00242 
00248     LinkedObject *get(void);
00249 
00254     void add(OrderedObject *ordered);
00255 
00261     inline LinkedObject *getIndexed(unsigned index) const
00262         {return LinkedObject::getIndexed((LinkedObject*)head, index);};
00263 
00268     inline LinkedObject *begin(void) const
00269         {return (LinkedObject*)(head);};
00270 
00275     inline LinkedObject *end(void) const
00276         {return (LinkedObject*)(tail);};
00277 
00282     inline LinkedObject *operator*() const
00283         {return (LinkedObject*)(head);};
00284 
00289     OrderedIndex& operator=(const OrderedIndex& object)
00290         {copy(object); return *this;}
00291 
00296     void operator*=(OrderedObject *object);
00297 };
00298 
00305 class __EXPORT OrderedObject : public LinkedObject
00306 {
00307 protected:
00308     friend class LinkedList;
00309     friend class OrderedIndex;
00310     friend class DLinkedObject;
00311     friend class ObjectQueue;
00312 
00317     OrderedObject(OrderedIndex *index);
00318 
00322     OrderedObject();
00323 
00324 public:
00329     void enlistTail(OrderedIndex *index);
00330 
00335     void enlistHead(OrderedIndex *index);
00336 
00342     virtual void enlist(OrderedIndex *index);
00343 
00348     void delist(OrderedIndex *index);
00349 
00354     inline OrderedObject *getNext(void) const
00355         {return static_cast<OrderedObject *>(LinkedObject::getNext());};
00356 };
00357 
00362 class __EXPORT DLinkedObject : public OrderedObject
00363 {
00364 public:
00365     friend class ObjectQueue;
00366 
00370     DLinkedObject();
00371 
00372 protected:
00376     void delist(void);
00377 
00378 private:
00379     DLinkedObject *Prev;
00380 };
00381 
00396 class __EXPORT NamedObject : public OrderedObject
00397 {
00398 protected:
00399     char *Id;
00400 
00404     NamedObject();
00405 
00412     NamedObject(NamedObject **hash, char *name, unsigned size = 1);
00413 
00420     NamedObject(OrderedIndex *index, char *name);
00421 
00429     ~NamedObject();
00430 
00435     virtual void clearId(void);
00436 
00437 public:
00444     void add(NamedObject **hash, char *name, unsigned size = 1);
00445 
00451     static void purge(NamedObject **hash, unsigned size);
00452 
00461     static NamedObject **index(NamedObject **hash, unsigned size);
00462 
00468     static unsigned count(NamedObject **hash, unsigned size);
00469 
00477     static NamedObject *find(NamedObject *root, const char *name);
00478 
00485     static NamedObject *remove(NamedObject **root, const char *name);
00486 
00494     static NamedObject *map(NamedObject **hash, const char *name, unsigned size);
00495 
00503     static NamedObject *remove(NamedObject **hash, const char *name, unsigned size);
00504 
00512     static NamedObject *skip(NamedObject **hash, NamedObject *current, unsigned size);
00513 
00519     static unsigned keyindex(const char *name, unsigned size);
00520 
00528     static NamedObject **sort(NamedObject **list, size_t count = 0);
00529 
00534     inline NamedObject *getNext(void) const
00535         {return static_cast<NamedObject*>(LinkedObject::getNext());};
00536 
00541     inline char *getId(void) const
00542         {return Id;};
00543 
00551     virtual int compare(const char *name) const;
00552 
00558     inline bool equal(const char *name) const
00559         {return (compare(name) == 0);};
00560 
00566     inline bool operator==(const char *name) const
00567         {return compare(name) == 0;};
00568 
00574     inline bool operator!=(const char *name) const
00575         {return compare(name) != 0;};
00576 };
00577 
00585 class __EXPORT NamedTree : public NamedObject
00586 {
00587 protected:
00588     NamedTree *Parent;
00589     OrderedIndex Child;
00590 
00595     NamedTree(char *name = NULL);
00596 
00602     NamedTree(NamedTree *parent, char *name);
00603 
00608     NamedTree(const NamedTree& source);
00609 
00615     virtual ~NamedTree();
00616 
00622     void purge(void);
00623 
00624 public:
00633     NamedTree *find(const char *name) const;
00634 
00645     NamedTree *path(const char *path) const;
00646 
00654     NamedTree *leaf(const char *name) const;
00655 
00661     NamedTree *getChild(const char *name) const;
00662 
00669     NamedTree *getLeaf(const char *name) const;
00670 
00677     inline NamedTree *getFirst(void) const
00678         {return static_cast<NamedTree *>(Child.begin());};
00679 
00684     inline NamedTree *getParent(void) const
00685         {return Parent;};
00686 
00692     inline NamedTree *getIndexed(unsigned index) const
00693         {return static_cast<NamedTree *>(Child.getIndexed(index));};
00694 
00699     inline OrderedIndex *getIndex(void) const
00700         {return const_cast<OrderedIndex*>(&Child);};
00701 
00706     inline operator bool() const
00707         {return (Id != NULL);};
00708 
00713     inline bool operator!() const
00714         {return (Id == NULL);};
00715 
00721     void setId(char *name);
00722 
00727     void remove(void);
00728 
00733     inline bool is_leaf(void) const
00734         {return (Child.begin() == NULL);};
00735 
00740     inline bool is_root(void) const
00741         {return (Parent == NULL);};
00742 
00747     void relistTail(NamedTree *trunk);
00748 
00753     void relistHead(NamedTree *trunk);
00754 
00759     inline void relist(NamedTree *trunk = NULL)
00760         {relistTail(trunk);};
00761 };
00762 
00769 class __EXPORT LinkedList : public OrderedObject
00770 {
00771 protected:
00772     friend class ObjectQueue;
00773 
00774     LinkedList *Prev;
00775     OrderedIndex *Root;
00776 
00781     LinkedList(OrderedIndex *index);
00782 
00786     LinkedList();
00787 
00792     virtual ~LinkedList();
00793 
00794 public:
00798     void delist(void);
00799 
00805     void enlistHead(OrderedIndex *index);
00806 
00812     void enlistTail(OrderedIndex *index);
00813 
00819     void enlist(OrderedIndex *index);
00820 
00825     inline bool is_head(void) const
00826         {return Root->head == (OrderedObject *)this;};
00827 
00832     inline bool is_tail(void) const
00833         {return Root->tail == (OrderedObject *)this;};
00834 
00839     inline LinkedList *getPrev(void) const
00840         {return Prev;};
00841 
00846     inline LinkedList *getNext(void) const
00847         {return static_cast<LinkedList*>(LinkedObject::getNext());};
00848 
00853     void insertTail(LinkedList *object);
00854 
00859     void insertHead(LinkedList *object);
00860 
00865     virtual void insert(LinkedList *object);
00866 
00871     inline void operator+=(LinkedList *object)
00872         {insertTail(object);};
00873 
00878     inline void operator-=(LinkedList *object)
00879         {insertHead(object);};
00880 
00885     inline void operator*=(LinkedList *object)
00886         {insert(object);};
00887 };
00888 
00894 class __EXPORT ObjectQueue : public OrderedIndex
00895 {
00896 public:
00900     ObjectQueue();
00901 
00906     void add(DLinkedObject *object);
00907 
00912     void push(DLinkedObject *object);
00913 
00918     DLinkedObject *pull(void);
00919 
00924     DLinkedObject *pop(void);
00925 };
00926 
00927 class __EXPORT ObjectStack
00928 {
00929 protected:
00930     LinkedObject *root;
00931 
00932 public:
00936     ObjectStack();
00937 
00942     ObjectStack(LinkedObject *list);
00943 
00948     void push(LinkedObject *object);
00949 
00954     LinkedObject *pull(void);
00955 
00960     inline LinkedObject *pop(void)
00961         {return ObjectStack::pull();};
00962 };
00963 
00964 
00970 class __EXPORT MultiMap : public ReusableObject
00971 {
00972 private:
00973     typedef struct {
00974         const char *key;
00975         size_t keysize;
00976         MultiMap *next;
00977         MultiMap **root;
00978     }   link_t;
00979 
00980     unsigned paths;
00981     link_t *links;
00982 
00983 protected:
00988     MultiMap(unsigned count);
00989 
00993     virtual ~MultiMap();
00994 
01002     virtual bool equal(unsigned path, caddr_t key, size_t size) const;
01003 
01004 public:
01010     void enlist(unsigned path, MultiMap **root);
01011 
01020     void enlist(unsigned path, MultiMap **index, caddr_t key, unsigned size, size_t keysize = 0);
01021 
01026     void delist(unsigned path);
01027 
01032     MultiMap *next(unsigned path) const;
01033 
01041     static unsigned keyindex(caddr_t key, unsigned max, size_t size = 0);
01042 
01052     static MultiMap *find(unsigned path, MultiMap **index, caddr_t key, unsigned max, size_t size = 0);
01053 };
01054 
01062 template <typename T, class O=NamedObject>
01063 class named_value : public object_value<T, O>
01064 {
01065 public:
01071     inline named_value(LinkedObject **root, char *name)
01072         {LinkedObject::enlist(root); O::id = name;};
01073 
01078     inline void operator=(const T& typed_value)
01079         {this->set(typed_value);};
01080 
01087     inline static named_value find(named_value *first, const char *name)
01088         {return static_cast<named_value *>(NamedObject::find(first, name));};
01089 };
01090 
01099 template <typename T, class O=OrderedObject>
01100 class linked_value : public object_value<T, O>
01101 {
01102 public:
01106     inline linked_value() {};
01107 
01112     inline linked_value(LinkedObject **root)
01113         {LinkedObject::enlist(root);};
01114 
01119     inline linked_value(OrderedIndex *index)
01120         {O::enlist(index);};
01121 
01127     inline linked_value(LinkedObject **root, const T& typed_value)
01128         {LinkedObject::enlist(root); this->set(typed_value);};
01129 
01135     inline linked_value(OrderedIndex *index, const T& typed_value)
01136         {O::enlist(index); this->set(typed_value);};
01137 
01142     inline void operator=(const T& typed_value)
01143         {this->set(typed_value);};
01144 };
01145 
01151 template <class T>
01152 class objstack : public ObjectStack
01153 {
01154 public:
01158     inline objstack() : ObjectStack() {}
01159 
01163     inline objstack(T *list) : ObjectStack(list) {}
01164 
01169     inline void push(T *object)
01170         {ObjectStack::push(object);}
01171 
01176     inline void add(T *object)
01177         {ObjectStack::push(object);}
01178 
01183     inline T *pull(void)
01184         {return (T *)ObjectStack::pull();}
01185 
01190     inline T *pop(void)
01191         {return (T *)ObjectStack::pull();}
01192 };
01193 
01200 template <class T>
01201 class objfifo : public OrderedIndex
01202 {
01203 public:
01207     inline objfifo() : OrderedIndex() {}
01208 
01213     inline void push(T *object)
01214         {OrderedIndex::add((OrderedObject *)object);}
01215 
01220     inline void add(T *object)
01221         {OrderedIndex::add((OrderedObject *)object);}
01222 
01227     inline T *pull(void)
01228         {return (T *)OrderedIndex::get();}
01229 
01234     inline T *pop(void)
01235         {return (T *)OrderedIndex::get();}
01236 };
01237 
01243 template <class T>
01244 class objqueue : public ObjectQueue
01245 {
01246 public:
01250     inline objqueue() : ObjectQueue() {}
01251 
01256     inline void push(T *object)
01257         {ObjectQueue::push((DLinkedObject *)object);}
01258 
01263     inline void add(T *object)
01264         {ObjectQueue::add((DLinkedObject *)object);}
01265 
01270     inline T *pull(void)
01271         {return (T *)ObjectQueue::pull();}
01272 
01277     inline T *pop(void)
01278         {return (T *)ObjectQueue::pop();}
01279 };
01280 
01287 template <class T>
01288 class linked_pointer
01289 {
01290 private:
01291     T *ptr;
01292 
01293 public:
01298     inline linked_pointer(T *pointer)
01299         {ptr = pointer;};
01300 
01305     inline linked_pointer(const linked_pointer &pointer)
01306         {ptr = pointer.ptr;};
01307 
01312     inline linked_pointer(LinkedObject *pointer)
01313         {ptr = static_cast<T*>(pointer);};
01314 
01315     inline linked_pointer(const LinkedObject *pointer)
01316         {ptr = static_cast<T*>(pointer);};
01317 
01322     inline linked_pointer(OrderedIndex *index)
01323         {ptr = static_cast<T*>(index->begin());};
01324 
01328     inline linked_pointer()
01329         {ptr = NULL;};
01330 
01335     inline void operator=(T *pointer)
01336         {ptr = pointer;};
01337 
01342     inline void operator=(linked_pointer &pointer)
01343         {ptr = pointer.ptr;};
01344 
01349     inline void operator=(OrderedIndex *index)
01350         {ptr = static_cast<T*>(index->begin());};
01351 
01356     inline void operator=(LinkedObject *pointer)
01357         {ptr = static_cast<T*>(pointer);};
01358 
01363     inline T* operator->() const
01364         {return ptr;};
01365 
01370     inline T* operator*() const
01371         {return ptr;};
01372 
01377     inline operator T*() const
01378         {return ptr;};
01379 
01383     inline void prev(void)
01384         {ptr = static_cast<T*>(ptr->getPrev());};
01385 
01389     inline void next(void)
01390         {ptr = static_cast<T*>(ptr->getNext());};
01391 
01396     inline T *getNext(void) const
01397         {return static_cast<T*>(ptr->getNext());};
01398 
01404     inline T *getPrev(void) const
01405         {return static_cast<T*>(ptr->getPrev());};
01406 
01410     inline void operator++()
01411         {ptr = static_cast<T*>(ptr->getNext());};
01412 
01416     inline void operator--()
01417         {ptr = static_cast<T*>(ptr->getPrev());};
01418 
01423     inline bool is_next(void) const
01424         {return (ptr->getNext() != NULL);};
01425 
01430     inline bool is_prev(void) const
01431         {return (ptr->getPrev() != NULL);};
01432 
01437     inline operator bool() const
01438         {return (ptr != NULL);};
01439 
01444     inline bool operator!() const
01445         {return (ptr == NULL);};
01446 
01451     inline LinkedObject **root(void) const
01452         {T **r = &ptr; return (LinkedObject**)r;};
01453 };
01454 
01462 template <typename T, unsigned P>
01463 class multimap : public MultiMap
01464 {
01465 protected:
01466     T value;
01467 
01468 public:
01472     inline multimap() : MultiMap(P) {};
01473 
01477     inline ~multimap() {};
01478 
01483     inline T &get(void) const
01484         {return value;};
01485 
01491     inline multimap *next(unsigned path)
01492         {return static_cast<multimap*>(MultiMap::next(path));};
01493 
01498     inline T& operator*() const
01499         {return value;};
01500 
01505     inline void setPointer(const T pointer)
01506         {value = pointer;};
01507 
01512     inline void set(const T &reference)
01513         {value = reference;};
01514 
01519     inline void operator=(const T& data)
01520         {value = data;};
01521 
01531     inline static multimap *find(unsigned path, MultiMap **index, caddr_t key, unsigned size, unsigned keysize = 0)
01532         {return static_cast<multimap*>(MultiMap::find(path, index, key, size, keysize));};
01533 };
01534 
01552 template <typename T>
01553 class treemap : public NamedTree
01554 {
01555 protected:
01556     T value;
01557 
01558 public:
01564     inline treemap(char *name = NULL) : NamedTree(name) {};
01565 
01570     inline treemap(const treemap& source) : NamedTree(source)
01571         {value = source.value;};
01572 
01578     inline treemap(treemap *parent, char *name) : NamedTree(parent, name) {};
01579 
01586     inline treemap(treemap *parent, char *name, T& reference) :
01587         NamedTree(parent, name) {value = reference;};
01588 
01593     inline const T& get(void) const
01594         {return value;};
01595 
01600     inline const T& operator*() const
01601         {return value;};
01602 
01608     static inline T getPointer(treemap *node)
01609         {return (node == NULL) ? NULL : node->value;};
01610 
01615     inline bool is_attribute(void) const
01616         {return (!Child.begin() && value != NULL);};
01617 
01622     inline const T getPointer(void) const
01623         {return value;};
01624 
01629     inline const T& getData(void) const
01630         {return value;};
01631 
01636     inline void setPointer(const T pointer)
01637         {value = pointer;};
01638 
01643     inline void set(const T& reference)
01644         {value = reference;};
01645 
01650     inline void operator=(const T& data)
01651         {value = data;};
01652 
01658     inline treemap *getIndexed(unsigned index) const
01659         {return static_cast<treemap*>(Child.getIndexed(index));};
01660 
01665     inline treemap *getParent(void) const
01666         {return static_cast<treemap*>(Parent);};
01667 
01674     inline treemap *getChild(const char *name) const
01675         {return static_cast<treemap*>(NamedTree::getChild(name));};
01676 
01683     inline treemap *getLeaf(const char *name) const
01684         {return static_cast<treemap*>(NamedTree::getLeaf(name));};
01685 
01693     inline T getValue(const char *name) const
01694         {return getPointer(getLeaf(name));};
01695 
01702     inline treemap *find(const char *name) const
01703         {return static_cast<treemap*>(NamedTree::find(name));};
01704 
01711     inline treemap *path(const char *path) const
01712         {return static_cast<treemap*>(NamedTree::path(path));};
01713 
01720     inline treemap *leaf(const char *name) const
01721         {return static_cast<treemap*>(NamedTree::leaf(name));};
01722 
01727     inline treemap *getFirst(void) const
01728         {return static_cast<treemap*>(NamedTree::getFirst());};
01729 };
01730 
01738 template <class T, unsigned M = 177>
01739 class keymap
01740 {
01741 private:
01742     NamedObject *idx[M];
01743 
01744 public:
01748     inline ~keymap()
01749         {NamedObject::purge(idx, M);};
01750 
01755     inline NamedObject **root(void) const
01756         {return idx;};
01757 
01762     inline unsigned limit(void) const
01763         {return M;};
01764 
01770     inline T *get(const char *name) const
01771         {return static_cast<T*>(NamedObject::map(idx, name, M));};
01772 
01778     inline T& operator[](const char *name) const
01779         {return static_cast<T*>(NamedObject::map(idx, name, M));};
01780 
01786     inline void add(const char *name, T& object)
01787         {object.NamedObject::add(idx, name, M);};
01788 
01794     inline void add(const char *name, T *object)
01795         {object->NamedObject::add(idx, name, M);};
01796 
01802     inline T *remove(const char *name)
01803         {return static_cast<T*>(NamedObject::remove(idx, name, M));};
01804 
01809     inline T *begin(void) const
01810         {return static_cast<T*>(NamedObject::skip(idx, NULL, M));};
01811 
01817     inline T *next(T *current) const
01818         {return static_cast<T*>(NamedObject::skip(idx, current, M));};
01819 
01824     inline unsigned count(void) const
01825         {return NamedObject::count(idx, M);};
01826 
01833     inline T **index(void) const
01834         {return NamedObject::index(idx, M);};
01835 
01842     inline T **sort(void) const
01843         {return NamedObject::sort(NamedObject::index(idx, M));};
01844 
01848     typedef linked_pointer<T> iterator;
01849 };
01850 
01857 template <class T>
01858 class keylist : public OrderedIndex
01859 {
01860 public:
01865     inline NamedObject **root(void)
01866         {return static_cast<NamedObject**>(&head);};
01867 
01873     inline T *begin(void)
01874         {return static_cast<T*>(head);};
01875 
01881     inline T *end(void)
01882         {return static_cast<T*>(tail);};
01883 
01890     inline T *create(const char *name)
01891         {return new T(this, name);};
01892 
01898     inline T *next(LinkedObject *current)
01899         {return static_cast<T*>(current->getNext());};
01900 
01906     inline T *find(const char *name)
01907         {return static_cast<T*>(NamedObject::find(begin(), name));};
01908 
01909     inline T *offset(unsigned offset)
01910         {return static_cast<T*>(OrderedIndex::find(offset));};
01911 
01917     inline T& operator[](unsigned offset)
01918         {return static_cast<T&>(OrderedIndex::find(offset));};
01919 
01920     inline T& operator[](const char *name)
01921         {return static_cast<T&>(NamedObject::find(begin(), name));};
01922 
01929     inline T **index(void)
01930         {return static_cast<T**>(OrderedIndex::index());};
01931 
01938     inline T **sort(void)
01939         {return static_cast<T**>(NamedObject::sort(index()));};
01940 
01944     typedef linked_pointer<T> iterator;
01945 };
01946 
01950 typedef LinkedObject *LinkedIndex;
01951 
01955 typedef ObjectStack objstack_t;
01956 
01960 typedef OrderedIndex objfifo_t;
01961 
01965 typedef ObjectQueue objqueue_t;
01966 
01967 END_NAMESPACE
01968 
01969 #endif

Generated on 14 Aug 2013 for UCommon by  doxygen 1.4.7