UCommon
|
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