ucommon
|
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 Object 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 isMember(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 public: 00189 OrderedIndex(); 00190 00194 virtual ~OrderedIndex(); 00195 00200 LinkedObject *find(unsigned offset) const; 00201 00206 unsigned count(void) const; 00207 00211 void purge(void); 00212 00216 void reset(void); 00217 00222 virtual void lock_index(void); 00223 00228 virtual void unlock_index(void); 00229 00236 LinkedObject **index(void) const; 00237 00243 LinkedObject *get(void); 00244 00249 void add(OrderedObject *ordered); 00250 00256 inline LinkedObject *getIndexed(unsigned index) const 00257 {return LinkedObject::getIndexed((LinkedObject*)head, index);}; 00258 00263 inline LinkedObject *begin(void) const 00264 {return (LinkedObject*)(head);}; 00265 00270 inline LinkedObject *end(void) const 00271 {return (LinkedObject*)(tail);}; 00272 00277 inline LinkedObject *operator*() const 00278 {return (LinkedObject*)(head);}; 00279 00284 void operator*=(OrderedObject *object); 00285 }; 00286 00293 class __EXPORT OrderedObject : public LinkedObject 00294 { 00295 protected: 00296 friend class LinkedList; 00297 friend class OrderedIndex; 00298 friend class DLinkedObject; 00299 friend class ObjectQueue; 00300 00305 OrderedObject(OrderedIndex *index); 00306 00310 OrderedObject(); 00311 00312 public: 00317 void enlistTail(OrderedIndex *index); 00318 00323 void enlistHead(OrderedIndex *index); 00324 00330 virtual void enlist(OrderedIndex *index); 00331 00336 void delist(OrderedIndex *index); 00337 00342 inline OrderedObject *getNext(void) const 00343 {return static_cast<OrderedObject *>(LinkedObject::getNext());}; 00344 }; 00345 00350 class __EXPORT DLinkedObject : public OrderedObject 00351 { 00352 public: 00353 friend class ObjectQueue; 00354 00358 DLinkedObject(); 00359 00360 protected: 00364 void delist(void); 00365 00366 private: 00367 DLinkedObject *prev; 00368 }; 00369 00384 class __EXPORT NamedObject : public OrderedObject 00385 { 00386 protected: 00387 char *id; 00388 00392 NamedObject(); 00393 00400 NamedObject(NamedObject **hash, char *name, unsigned size = 1); 00401 00408 NamedObject(OrderedIndex *index, char *name); 00409 00417 ~NamedObject(); 00418 00423 virtual void clearId(void); 00424 00425 public: 00432 void add(NamedObject **hash, char *name, unsigned size = 1); 00433 00439 static void purge(NamedObject **hash, unsigned size); 00440 00449 static NamedObject **index(NamedObject **hash, unsigned size); 00450 00456 static unsigned count(NamedObject **hash, unsigned size); 00457 00465 static NamedObject *find(NamedObject *root, const char *name); 00466 00473 static NamedObject *remove(NamedObject **root, const char *name); 00474 00482 static NamedObject *map(NamedObject **hash, const char *name, unsigned size); 00483 00491 static NamedObject *remove(NamedObject **hash, const char *name, unsigned size); 00492 00500 static NamedObject *skip(NamedObject **hash, NamedObject *current, unsigned size); 00501 00507 static unsigned keyindex(const char *name, unsigned size); 00508 00516 static NamedObject **sort(NamedObject **list, size_t count = 0); 00517 00522 inline NamedObject *getNext(void) const 00523 {return static_cast<NamedObject*>(LinkedObject::getNext());}; 00524 00529 inline char *getId(void) const 00530 {return id;}; 00531 00539 virtual bool compare(const char *name) const; 00540 00546 inline bool operator==(const char *name) const 00547 {return compare(name);}; 00548 00554 inline bool operator!=(const char *name) const 00555 {return !compare(name);}; 00556 }; 00557 00565 class __EXPORT NamedTree : public NamedObject 00566 { 00567 protected: 00568 NamedTree *parent; 00569 OrderedIndex child; 00570 00575 NamedTree(char *name = NULL); 00576 00582 NamedTree(NamedTree *parent, char *name); 00583 00588 NamedTree(const NamedTree& source); 00589 00595 virtual ~NamedTree(); 00596 00602 void purge(void); 00603 00604 public: 00613 NamedTree *find(const char *name) const; 00614 00625 NamedTree *path(const char *path) const; 00626 00634 NamedTree *leaf(const char *name) const; 00635 00641 NamedTree *getChild(const char *name) const; 00642 00649 NamedTree *getLeaf(const char *name) const; 00650 00657 inline NamedTree *getFirst(void) const 00658 {return static_cast<NamedTree *>(child.begin());}; 00659 00664 inline NamedTree *getParent(void) const 00665 {return parent;}; 00666 00672 inline NamedTree *getIndexed(unsigned index) const 00673 {return static_cast<NamedTree *>(child.getIndexed(index));}; 00674 00679 inline OrderedIndex *getIndex(void) const 00680 {return const_cast<OrderedIndex*>(&child);}; 00681 00686 inline operator bool() const 00687 {return (id != NULL);}; 00688 00693 inline bool operator!() const 00694 {return (id == NULL);}; 00695 00701 void setId(char *name); 00702 00707 void remove(void); 00708 00713 inline bool isLeaf(void) const 00714 {return (child.begin() == NULL);}; 00715 00720 inline bool isRoot(void) const 00721 {return (parent == NULL);}; 00722 00727 void relistTail(NamedTree *trunk); 00728 00733 void relistHead(NamedTree *trunk); 00734 00739 inline void relist(NamedTree *trunk = NULL) 00740 {relistTail(trunk);}; 00741 }; 00742 00749 class __EXPORT LinkedList : public OrderedObject 00750 { 00751 protected: 00752 friend class ObjectQueue; 00753 00754 LinkedList *prev; 00755 OrderedIndex *root; 00756 00761 LinkedList(OrderedIndex *index); 00762 00766 LinkedList(); 00767 00772 virtual ~LinkedList(); 00773 00774 public: 00778 void delist(void); 00779 00785 void enlistHead(OrderedIndex *index); 00786 00792 void enlistTail(OrderedIndex *index); 00793 00799 void enlist(OrderedIndex *index); 00800 00805 inline bool isHead(void) const 00806 {return root->head == (OrderedObject *)this;}; 00807 00812 inline bool isTail(void) const 00813 {return root->tail == (OrderedObject *)this;}; 00814 00819 inline LinkedList *getPrev(void) const 00820 {return prev;}; 00821 00826 inline LinkedList *getNext(void) const 00827 {return static_cast<LinkedList*>(LinkedObject::getNext());}; 00828 00833 void insertTail(LinkedList *object); 00834 00839 void insertHead(LinkedList *object); 00840 00845 virtual void insert(LinkedList *object); 00846 00851 inline void operator+=(LinkedList *object) 00852 {insertTail(object);}; 00853 00858 inline void operator-=(LinkedList *object) 00859 {insertHead(object);}; 00860 00865 inline void operator*=(LinkedList *object) 00866 {insert(object);}; 00867 }; 00868 00874 class __EXPORT ObjectQueue : public OrderedIndex 00875 { 00876 public: 00880 ObjectQueue(); 00881 00886 void add(DLinkedObject *object); 00887 00892 void push(DLinkedObject *object); 00893 00898 DLinkedObject *pull(void); 00899 00904 DLinkedObject *pop(void); 00905 }; 00906 00907 class __EXPORT ObjectStack 00908 { 00909 protected: 00910 LinkedObject *root; 00911 00912 public: 00916 ObjectStack(); 00917 00922 ObjectStack(LinkedObject *list); 00923 00928 void push(LinkedObject *object); 00929 00934 LinkedObject *pull(void); 00935 00940 inline LinkedObject *pop(void) 00941 {return ObjectStack::pull();}; 00942 }; 00943 00944 00950 class __EXPORT MultiMap : public ReusableObject 00951 { 00952 private: 00953 typedef struct { 00954 const char *key; 00955 size_t keysize; 00956 MultiMap *next; 00957 MultiMap **root; 00958 } link_t; 00959 00960 unsigned paths; 00961 link_t *links; 00962 00963 protected: 00968 MultiMap(unsigned count); 00969 00973 virtual ~MultiMap(); 00974 00982 virtual bool compare(unsigned path, caddr_t key, size_t size) const; 00983 00984 public: 00990 void enlist(unsigned path, MultiMap **root); 00991 01000 void enlist(unsigned path, MultiMap **index, caddr_t key, unsigned size, size_t keysize = 0); 01001 01006 void delist(unsigned path); 01007 01012 MultiMap *next(unsigned path) const; 01013 01021 static unsigned keyindex(caddr_t key, unsigned max, size_t size = 0); 01022 01032 static MultiMap *find(unsigned path, MultiMap **index, caddr_t key, unsigned max, size_t size = 0); 01033 }; 01034 01042 template <typename T, class O=NamedObject> 01043 class named_value : public object_value<T, O> 01044 { 01045 public: 01051 inline named_value(LinkedObject **root, char *name) 01052 {LinkedObject::enlist(root); O::id = name;}; 01053 01058 inline void operator=(const T& typed_value) 01059 {set(typed_value);}; 01060 01067 inline static named_value find(named_value *first, const char *name) 01068 {return static_cast<named_value *>(NamedObject::find(first, name));}; 01069 }; 01070 01079 template <typename T, class O=OrderedObject> 01080 class linked_value : public object_value<T, O> 01081 { 01082 public: 01086 inline linked_value() {}; 01087 01092 inline linked_value(LinkedObject **root) 01093 {LinkedObject::enlist(root);}; 01094 01099 inline linked_value(OrderedIndex *index) 01100 {O::enlist(index);}; 01101 01107 inline linked_value(LinkedObject **root, const T& typed_value) 01108 {LinkedObject::enlist(root); set(typed_value);}; 01109 01115 inline linked_value(OrderedIndex *index, const T& typed_value) 01116 {O::enlist(index); set(typed_value);}; 01117 01122 inline void operator=(const T& typed_value) 01123 {set(typed_value);}; 01124 }; 01125 01131 template <class T> 01132 class objstack : public ObjectStack 01133 { 01134 public: 01138 inline objstack() : ObjectStack() {} 01139 01143 inline objstack(T *list) : ObjectStack(list) {} 01144 01149 inline void push(T *object) 01150 {ObjectStack::push(object);} 01151 01156 inline void add(T *object) 01157 {ObjectStack::push(object);} 01158 01163 inline T *pull(void) 01164 {return (T *)ObjectStack::pull();} 01165 01170 inline T *pop(void) 01171 {return (T *)ObjectStack::pull();} 01172 }; 01173 01180 template <class T> 01181 class objfifo : public OrderedIndex 01182 { 01183 public: 01187 inline objfifo() : OrderedIndex() {} 01188 01193 inline void push(T *object) 01194 {OrderedIndex::add((OrderedObject *)object);} 01195 01200 inline void add(T *object) 01201 {OrderedIndex::add((OrderedObject *)object);} 01202 01207 inline T *pull(void) 01208 {return (T *)OrderedIndex::get();} 01209 01214 inline T *pop(void) 01215 {return (T *)OrderedIndex::get();} 01216 }; 01217 01223 template <class T> 01224 class objqueue : public ObjectQueue 01225 { 01226 public: 01230 inline objqueue() : ObjectQueue() {} 01231 01236 inline void push(T *object) 01237 {ObjectQueue::push((DLinkedObject *)object);} 01238 01243 inline void add(T *object) 01244 {ObjectQueue::add((DLinkedObject *)object);} 01245 01250 inline T *pull(void) 01251 {return (T *)ObjectQueue::pull();} 01252 01257 inline T *pop(void) 01258 {return (T *)ObjectQueue::pop();} 01259 }; 01260 01267 template <class T> 01268 class linked_pointer 01269 { 01270 private: 01271 T *ptr; 01272 01273 public: 01278 inline linked_pointer(T *pointer) 01279 {ptr = pointer;}; 01280 01285 inline linked_pointer(const linked_pointer &pointer) 01286 {ptr = pointer.ptr;}; 01287 01292 inline linked_pointer(LinkedObject *pointer) 01293 {ptr = static_cast<T*>(pointer);}; 01294 01299 inline linked_pointer(OrderedIndex *index) 01300 {ptr = static_cast<T*>(index->begin());}; 01301 01305 inline linked_pointer() 01306 {ptr = NULL;}; 01307 01312 inline void operator=(T *pointer) 01313 {ptr = pointer;}; 01314 01319 inline void operator=(linked_pointer &pointer) 01320 {ptr = pointer.ptr;}; 01321 01326 inline void operator=(OrderedIndex *index) 01327 {ptr = static_cast<T*>(index->begin());}; 01328 01333 inline void operator=(LinkedObject *pointer) 01334 {ptr = static_cast<T*>(pointer);}; 01335 01340 inline T* operator->() const 01341 {return ptr;}; 01342 01347 inline T* operator*() const 01348 {return ptr;}; 01349 01354 inline operator T*() const 01355 {return ptr;}; 01356 01360 inline void prev(void) 01361 {ptr = static_cast<T*>(ptr->getPrev());}; 01362 01366 inline void next(void) 01367 {ptr = static_cast<T*>(ptr->getNext());}; 01368 01373 inline T *getNext(void) const 01374 {return static_cast<T*>(ptr->getNext());}; 01375 01381 inline T *getPrev(void) const 01382 {return static_cast<T*>(ptr->getPrev());}; 01383 01387 inline void operator++() 01388 {ptr = static_cast<T*>(ptr->getNext());}; 01389 01393 inline void operator--() 01394 {ptr = static_cast<T*>(ptr->getPrev());}; 01395 01400 inline bool isNext(void) const 01401 {return (ptr->getNext() != NULL);}; 01402 01407 inline bool isPrev(void) const 01408 {return (ptr->getPrev() != NULL);}; 01409 01414 inline operator bool() const 01415 {return (ptr != NULL);}; 01416 01421 inline bool operator!() const 01422 {return (ptr == NULL);}; 01423 01428 inline LinkedObject **root(void) const 01429 {T **r = &ptr; return (LinkedObject**)r;}; 01430 }; 01431 01439 template <typename T, unsigned P> 01440 class multimap : public MultiMap 01441 { 01442 protected: 01443 T value; 01444 01445 public: 01449 inline multimap() : MultiMap(P) {}; 01450 01454 inline ~multimap() {}; 01455 01460 inline T &get(void) const 01461 {return value;}; 01462 01468 inline multimap *next(unsigned path) 01469 {return static_cast<multimap*>(MultiMap::next(path));}; 01470 01475 inline T& operator*() const 01476 {return value;}; 01477 01482 inline void setPointer(const T pointer) 01483 {value = pointer;}; 01484 01489 inline void set(const T &reference) 01490 {value = reference;}; 01491 01496 inline void operator=(const T& data) 01497 {value = data;}; 01498 01508 inline static multimap *find(unsigned path, MultiMap **index, caddr_t key, unsigned size, unsigned keysize = 0) 01509 {return static_cast<multimap*>(MultiMap::find(path, index, key, size, keysize));}; 01510 }; 01511 01529 template <typename T> 01530 class treemap : public NamedTree 01531 { 01532 protected: 01533 T value; 01534 01535 public: 01541 inline treemap(char *name = NULL) : NamedTree(name) {}; 01542 01547 inline treemap(const treemap& source) : NamedTree(source) 01548 {value = source.value;}; 01549 01555 inline treemap(treemap *parent, char *name) : NamedTree(parent, name) {}; 01556 01563 inline treemap(treemap *parent, char *name, T& reference) : 01564 NamedTree(parent, name) {value = reference;}; 01565 01570 inline const T& get(void) const 01571 {return value;}; 01572 01577 inline const T& operator*() const 01578 {return value;}; 01579 01585 static inline T getPointer(treemap *node) 01586 {return (node == NULL) ? NULL : node->value;}; 01587 01592 inline bool isAttribute(void) const 01593 {return (!child.begin() && value != NULL);}; 01594 01599 inline const T getPointer(void) const 01600 {return value;}; 01601 01606 inline const T& getData(void) const 01607 {return value;}; 01608 01613 inline void setPointer(const T pointer) 01614 {value = pointer;}; 01615 01620 inline void set(const T& reference) 01621 {value = reference;}; 01622 01627 inline void operator=(const T& data) 01628 {value = data;}; 01629 01635 inline treemap *getIndexed(unsigned index) const 01636 {return static_cast<treemap*>(child.getIndexed(index));}; 01637 01642 inline treemap *getParent(void) const 01643 {return static_cast<treemap*>(parent);}; 01644 01651 inline treemap *getChild(const char *name) const 01652 {return static_cast<treemap*>(NamedTree::getChild(name));}; 01653 01660 inline treemap *getLeaf(const char *name) const 01661 {return static_cast<treemap*>(NamedTree::getLeaf(name));}; 01662 01670 inline T getValue(const char *name) const 01671 {return getPointer(getLeaf(name));}; 01672 01679 inline treemap *find(const char *name) const 01680 {return static_cast<treemap*>(NamedTree::find(name));}; 01681 01688 inline treemap *path(const char *path) const 01689 {return static_cast<treemap*>(NamedTree::path(path));}; 01690 01697 inline treemap *leaf(const char *name) const 01698 {return static_cast<treemap*>(NamedTree::leaf(name));}; 01699 01704 inline treemap *getFirst(void) const 01705 {return static_cast<treemap*>(NamedTree::getFirst());}; 01706 }; 01707 01715 template <class T, unsigned M = 177> 01716 class keymap 01717 { 01718 private: 01719 NamedObject *idx[M]; 01720 01721 public: 01725 inline ~keymap() 01726 {NamedObject::purge(idx, M);}; 01727 01732 inline NamedObject **root(void) const 01733 {return idx;}; 01734 01739 inline unsigned limit(void) const 01740 {return M;}; 01741 01747 inline T *get(const char *name) const 01748 {return static_cast<T*>(NamedObject::map(idx, name, M));}; 01749 01755 inline T& operator[](const char *name) const 01756 {return static_cast<T*>(NamedObject::map(idx, name, M));}; 01757 01763 inline void add(const char *name, T& object) 01764 {object.NamedObject::add(idx, name, M);}; 01765 01771 inline void add(const char *name, T *object) 01772 {object->NamedObject::add(idx, name, M);}; 01773 01779 inline T *remove(const char *name) 01780 {return static_cast<T*>(NamedObject::remove(idx, name, M));}; 01781 01786 inline T *begin(void) const 01787 {return static_cast<T*>(NamedObject::skip(idx, NULL, M));}; 01788 01794 inline T *next(T *current) const 01795 {return static_cast<T*>(NamedObject::skip(idx, current, M));}; 01796 01801 inline unsigned count(void) const 01802 {return NamedObject::count(idx, M);}; 01803 01810 inline T **index(void) const 01811 {return NamedObject::index(idx, M);}; 01812 01819 inline T **sort(void) const 01820 {return NamedObject::sort(NamedObject::index(idx, M));}; 01821 }; 01822 01829 template <class T> 01830 class keylist : public OrderedIndex 01831 { 01832 public: 01837 inline NamedObject **root(void) 01838 {return static_cast<NamedObject*>(&head);}; 01839 01845 inline T *begin(void) 01846 {return static_cast<T*>(head);}; 01847 01853 inline T *end(void) 01854 {return static_cast<T*>(tail);}; 01855 01862 inline T *create(const char *name) 01863 {return new T(this, name);}; 01864 01870 inline T *next(LinkedObject *current) 01871 {return static_cast<T*>(current->getNext());}; 01872 01878 inline T *find(const char *name) 01879 {return static_cast<T*>(NamedObject::find(begin(), name));}; 01880 01881 inline T *offset(unsigned offset) 01882 {return static_cast<T*>(OrderedIndex::find(offset));}; 01883 01889 inline T& operator[](unsigned offset) 01890 {return static_cast<T&>(OrderedIndex::find(offset));}; 01891 01892 inline T& operator[](const char *name) 01893 {return static_cast<T&>(NamedObject::find(begin(), name));}; 01894 01901 inline T **index(void) 01902 {return static_cast<T**>(OrderedIndex::index());}; 01903 01910 inline T **sort(void) 01911 {return static_cast<T**>(NamedObject::sort(index()));}; 01912 }; 01913 01919 inline void push(ObjectStack& stack, LinkedObject *object) 01920 {stack.push(object);} 01921 01927 inline void add(ObjectStack& stack, LinkedObject *object) 01928 {stack.push(object);} 01929 01935 inline LinkedObject *pop(ObjectStack& stack) 01936 {return stack.pull();} 01937 01943 inline LinkedObject *pull(ObjectStack& stack) 01944 {return stack.pull();} 01945 01951 inline void push(OrderedIndex& fifo, LinkedObject *object) 01952 {fifo.add((OrderedObject *)object);} 01953 01959 inline void add(OrderedIndex& fifo, LinkedObject *object) 01960 {fifo.add((OrderedObject *)object);} 01961 01967 inline LinkedObject *pop(OrderedIndex& fifo) 01968 {return fifo.get();} 01969 01975 inline LinkedObject *pull(OrderedIndex& fifo) 01976 {return fifo.get();} 01977 01983 inline void push(ObjectQueue& queue, DLinkedObject *object) 01984 {queue.add(object);} 01985 01991 inline void add(ObjectQueue& queue, DLinkedObject *object) 01992 {queue.add(object);} 01993 01999 inline DLinkedObject *pop(ObjectQueue& queue) 02000 {return (DLinkedObject *)queue.pop();} 02001 02007 inline DLinkedObject *pull(ObjectQueue& queue) 02008 {return (DLinkedObject *)queue.pull();} 02009 02013 typedef LinkedObject *LinkedIndex; 02014 02018 typedef ObjectStack objstack_t; 02019 02023 typedef OrderedIndex objfifo_t; 02024 02028 typedef ObjectQueue objqueue_t; 02029 02030 END_NAMESPACE 02031 02032 #endif