ucommon
|
00001 // Copyright (C) 2006-2014 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 } // namespace ucommon 01968 01969 #endif