00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
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 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 int compare(const char *name) const;
00540
00546 inline bool equal(const char *name) const
00547 {return (compare(name) == 0);};
00548
00554 inline bool operator==(const char *name) const
00555 {return compare(name) == 0;};
00556
00562 inline bool operator!=(const char *name) const
00563 {return compare(name) != 0;};
00564 };
00565
00573 class __EXPORT NamedTree : public NamedObject
00574 {
00575 protected:
00576 NamedTree *parent;
00577 OrderedIndex child;
00578
00583 NamedTree(char *name = NULL);
00584
00590 NamedTree(NamedTree *parent, char *name);
00591
00596 NamedTree(const NamedTree& source);
00597
00603 virtual ~NamedTree();
00604
00610 void purge(void);
00611
00612 public:
00621 NamedTree *find(const char *name) const;
00622
00633 NamedTree *path(const char *path) const;
00634
00642 NamedTree *leaf(const char *name) const;
00643
00649 NamedTree *getChild(const char *name) const;
00650
00657 NamedTree *getLeaf(const char *name) const;
00658
00665 inline NamedTree *getFirst(void) const
00666 {return static_cast<NamedTree *>(child.begin());};
00667
00672 inline NamedTree *getParent(void) const
00673 {return parent;};
00674
00680 inline NamedTree *getIndexed(unsigned index) const
00681 {return static_cast<NamedTree *>(child.getIndexed(index));};
00682
00687 inline OrderedIndex *getIndex(void) const
00688 {return const_cast<OrderedIndex*>(&child);};
00689
00694 inline operator bool() const
00695 {return (id != NULL);};
00696
00701 inline bool operator!() const
00702 {return (id == NULL);};
00703
00709 void setId(char *name);
00710
00715 void remove(void);
00716
00721 inline bool isLeaf(void) const
00722 {return (child.begin() == NULL);};
00723
00728 inline bool isRoot(void) const
00729 {return (parent == NULL);};
00730
00735 void relistTail(NamedTree *trunk);
00736
00741 void relistHead(NamedTree *trunk);
00742
00747 inline void relist(NamedTree *trunk = NULL)
00748 {relistTail(trunk);};
00749 };
00750
00757 class __EXPORT LinkedList : public OrderedObject
00758 {
00759 protected:
00760 friend class ObjectQueue;
00761
00762 LinkedList *prev;
00763 OrderedIndex *root;
00764
00769 LinkedList(OrderedIndex *index);
00770
00774 LinkedList();
00775
00780 virtual ~LinkedList();
00781
00782 public:
00786 void delist(void);
00787
00793 void enlistHead(OrderedIndex *index);
00794
00800 void enlistTail(OrderedIndex *index);
00801
00807 void enlist(OrderedIndex *index);
00808
00813 inline bool isHead(void) const
00814 {return root->head == (OrderedObject *)this;};
00815
00820 inline bool isTail(void) const
00821 {return root->tail == (OrderedObject *)this;};
00822
00827 inline LinkedList *getPrev(void) const
00828 {return prev;};
00829
00834 inline LinkedList *getNext(void) const
00835 {return static_cast<LinkedList*>(LinkedObject::getNext());};
00836
00841 void insertTail(LinkedList *object);
00842
00847 void insertHead(LinkedList *object);
00848
00853 virtual void insert(LinkedList *object);
00854
00859 inline void operator+=(LinkedList *object)
00860 {insertTail(object);};
00861
00866 inline void operator-=(LinkedList *object)
00867 {insertHead(object);};
00868
00873 inline void operator*=(LinkedList *object)
00874 {insert(object);};
00875 };
00876
00882 class __EXPORT ObjectQueue : public OrderedIndex
00883 {
00884 public:
00888 ObjectQueue();
00889
00894 void add(DLinkedObject *object);
00895
00900 void push(DLinkedObject *object);
00901
00906 DLinkedObject *pull(void);
00907
00912 DLinkedObject *pop(void);
00913 };
00914
00915 class __EXPORT ObjectStack
00916 {
00917 protected:
00918 LinkedObject *root;
00919
00920 public:
00924 ObjectStack();
00925
00930 ObjectStack(LinkedObject *list);
00931
00936 void push(LinkedObject *object);
00937
00942 LinkedObject *pull(void);
00943
00948 inline LinkedObject *pop(void)
00949 {return ObjectStack::pull();};
00950 };
00951
00952
00958 class __EXPORT MultiMap : public ReusableObject
00959 {
00960 private:
00961 typedef struct {
00962 const char *key;
00963 size_t keysize;
00964 MultiMap *next;
00965 MultiMap **root;
00966 } link_t;
00967
00968 unsigned paths;
00969 link_t *links;
00970
00971 protected:
00976 MultiMap(unsigned count);
00977
00981 virtual ~MultiMap();
00982
00990 virtual bool equal(unsigned path, caddr_t key, size_t size) const;
00991
00992 public:
00998 void enlist(unsigned path, MultiMap **root);
00999
01008 void enlist(unsigned path, MultiMap **index, caddr_t key, unsigned size, size_t keysize = 0);
01009
01014 void delist(unsigned path);
01015
01020 MultiMap *next(unsigned path) const;
01021
01029 static unsigned keyindex(caddr_t key, unsigned max, size_t size = 0);
01030
01040 static MultiMap *find(unsigned path, MultiMap **index, caddr_t key, unsigned max, size_t size = 0);
01041 };
01042
01050 template <typename T, class O=NamedObject>
01051 class named_value : public object_value<T, O>
01052 {
01053 public:
01059 inline named_value(LinkedObject **root, char *name)
01060 {LinkedObject::enlist(root); O::id = name;};
01061
01066 inline void operator=(const T& typed_value)
01067 {this->set(typed_value);};
01068
01075 inline static named_value find(named_value *first, const char *name)
01076 {return static_cast<named_value *>(NamedObject::find(first, name));};
01077 };
01078
01087 template <typename T, class O=OrderedObject>
01088 class linked_value : public object_value<T, O>
01089 {
01090 public:
01094 inline linked_value() {};
01095
01100 inline linked_value(LinkedObject **root)
01101 {LinkedObject::enlist(root);};
01102
01107 inline linked_value(OrderedIndex *index)
01108 {O::enlist(index);};
01109
01115 inline linked_value(LinkedObject **root, const T& typed_value)
01116 {LinkedObject::enlist(root); this->set(typed_value);};
01117
01123 inline linked_value(OrderedIndex *index, const T& typed_value)
01124 {O::enlist(index); this->set(typed_value);};
01125
01130 inline void operator=(const T& typed_value)
01131 {this->set(typed_value);};
01132 };
01133
01139 template <class T>
01140 class objstack : public ObjectStack
01141 {
01142 public:
01146 inline objstack() : ObjectStack() {}
01147
01151 inline objstack(T *list) : ObjectStack(list) {}
01152
01157 inline void push(T *object)
01158 {ObjectStack::push(object);}
01159
01164 inline void add(T *object)
01165 {ObjectStack::push(object);}
01166
01171 inline T *pull(void)
01172 {return (T *)ObjectStack::pull();}
01173
01178 inline T *pop(void)
01179 {return (T *)ObjectStack::pull();}
01180 };
01181
01188 template <class T>
01189 class objfifo : public OrderedIndex
01190 {
01191 public:
01195 inline objfifo() : OrderedIndex() {}
01196
01201 inline void push(T *object)
01202 {OrderedIndex::add((OrderedObject *)object);}
01203
01208 inline void add(T *object)
01209 {OrderedIndex::add((OrderedObject *)object);}
01210
01215 inline T *pull(void)
01216 {return (T *)OrderedIndex::get();}
01217
01222 inline T *pop(void)
01223 {return (T *)OrderedIndex::get();}
01224 };
01225
01231 template <class T>
01232 class objqueue : public ObjectQueue
01233 {
01234 public:
01238 inline objqueue() : ObjectQueue() {}
01239
01244 inline void push(T *object)
01245 {ObjectQueue::push((DLinkedObject *)object);}
01246
01251 inline void add(T *object)
01252 {ObjectQueue::add((DLinkedObject *)object);}
01253
01258 inline T *pull(void)
01259 {return (T *)ObjectQueue::pull();}
01260
01265 inline T *pop(void)
01266 {return (T *)ObjectQueue::pop();}
01267 };
01268
01275 template <class T>
01276 class linked_pointer
01277 {
01278 private:
01279 T *ptr;
01280
01281 public:
01286 inline linked_pointer(T *pointer)
01287 {ptr = pointer;};
01288
01293 inline linked_pointer(const linked_pointer &pointer)
01294 {ptr = pointer.ptr;};
01295
01300 inline linked_pointer(LinkedObject *pointer)
01301 {ptr = static_cast<T*>(pointer);};
01302
01307 inline linked_pointer(OrderedIndex *index)
01308 {ptr = static_cast<T*>(index->begin());};
01309
01313 inline linked_pointer()
01314 {ptr = NULL;};
01315
01320 inline void operator=(T *pointer)
01321 {ptr = pointer;};
01322
01327 inline void operator=(linked_pointer &pointer)
01328 {ptr = pointer.ptr;};
01329
01334 inline void operator=(OrderedIndex *index)
01335 {ptr = static_cast<T*>(index->begin());};
01336
01341 inline void operator=(LinkedObject *pointer)
01342 {ptr = static_cast<T*>(pointer);};
01343
01348 inline T* operator->() const
01349 {return ptr;};
01350
01355 inline T* operator*() const
01356 {return ptr;};
01357
01362 inline operator T*() const
01363 {return ptr;};
01364
01368 inline void prev(void)
01369 {ptr = static_cast<T*>(ptr->getPrev());};
01370
01374 inline void next(void)
01375 {ptr = static_cast<T*>(ptr->getNext());};
01376
01381 inline T *getNext(void) const
01382 {return static_cast<T*>(ptr->getNext());};
01383
01389 inline T *getPrev(void) const
01390 {return static_cast<T*>(ptr->getPrev());};
01391
01395 inline void operator++()
01396 {ptr = static_cast<T*>(ptr->getNext());};
01397
01401 inline void operator--()
01402 {ptr = static_cast<T*>(ptr->getPrev());};
01403
01408 inline bool isNext(void) const
01409 {return (ptr->getNext() != NULL);};
01410
01415 inline bool isPrev(void) const
01416 {return (ptr->getPrev() != NULL);};
01417
01422 inline operator bool() const
01423 {return (ptr != NULL);};
01424
01429 inline bool operator!() const
01430 {return (ptr == NULL);};
01431
01436 inline LinkedObject **root(void) const
01437 {T **r = &ptr; return (LinkedObject**)r;};
01438 };
01439
01447 template <typename T, unsigned P>
01448 class multimap : public MultiMap
01449 {
01450 protected:
01451 T value;
01452
01453 public:
01457 inline multimap() : MultiMap(P) {};
01458
01462 inline ~multimap() {};
01463
01468 inline T &get(void) const
01469 {return value;};
01470
01476 inline multimap *next(unsigned path)
01477 {return static_cast<multimap*>(MultiMap::next(path));};
01478
01483 inline T& operator*() const
01484 {return value;};
01485
01490 inline void setPointer(const T pointer)
01491 {value = pointer;};
01492
01497 inline void set(const T &reference)
01498 {value = reference;};
01499
01504 inline void operator=(const T& data)
01505 {value = data;};
01506
01516 inline static multimap *find(unsigned path, MultiMap **index, caddr_t key, unsigned size, unsigned keysize = 0)
01517 {return static_cast<multimap*>(MultiMap::find(path, index, key, size, keysize));};
01518 };
01519
01537 template <typename T>
01538 class treemap : public NamedTree
01539 {
01540 protected:
01541 T value;
01542
01543 public:
01549 inline treemap(char *name = NULL) : NamedTree(name) {};
01550
01555 inline treemap(const treemap& source) : NamedTree(source)
01556 {value = source.value;};
01557
01563 inline treemap(treemap *parent, char *name) : NamedTree(parent, name) {};
01564
01571 inline treemap(treemap *parent, char *name, T& reference) :
01572 NamedTree(parent, name) {value = reference;};
01573
01578 inline const T& get(void) const
01579 {return value;};
01580
01585 inline const T& operator*() const
01586 {return value;};
01587
01593 static inline T getPointer(treemap *node)
01594 {return (node == NULL) ? NULL : node->value;};
01595
01600 inline bool isAttribute(void) const
01601 {return (!child.begin() && value != NULL);};
01602
01607 inline const T getPointer(void) const
01608 {return value;};
01609
01614 inline const T& getData(void) const
01615 {return value;};
01616
01621 inline void setPointer(const T pointer)
01622 {value = pointer;};
01623
01628 inline void set(const T& reference)
01629 {value = reference;};
01630
01635 inline void operator=(const T& data)
01636 {value = data;};
01637
01643 inline treemap *getIndexed(unsigned index) const
01644 {return static_cast<treemap*>(child.getIndexed(index));};
01645
01650 inline treemap *getParent(void) const
01651 {return static_cast<treemap*>(parent);};
01652
01659 inline treemap *getChild(const char *name) const
01660 {return static_cast<treemap*>(NamedTree::getChild(name));};
01661
01668 inline treemap *getLeaf(const char *name) const
01669 {return static_cast<treemap*>(NamedTree::getLeaf(name));};
01670
01678 inline T getValue(const char *name) const
01679 {return getPointer(getLeaf(name));};
01680
01687 inline treemap *find(const char *name) const
01688 {return static_cast<treemap*>(NamedTree::find(name));};
01689
01696 inline treemap *path(const char *path) const
01697 {return static_cast<treemap*>(NamedTree::path(path));};
01698
01705 inline treemap *leaf(const char *name) const
01706 {return static_cast<treemap*>(NamedTree::leaf(name));};
01707
01712 inline treemap *getFirst(void) const
01713 {return static_cast<treemap*>(NamedTree::getFirst());};
01714 };
01715
01723 template <class T, unsigned M = 177>
01724 class keymap
01725 {
01726 private:
01727 NamedObject *idx[M];
01728
01729 public:
01733 inline ~keymap()
01734 {NamedObject::purge(idx, M);};
01735
01740 inline NamedObject **root(void) const
01741 {return idx;};
01742
01747 inline unsigned limit(void) const
01748 {return M;};
01749
01755 inline T *get(const char *name) const
01756 {return static_cast<T*>(NamedObject::map(idx, name, M));};
01757
01763 inline T& operator[](const char *name) const
01764 {return static_cast<T*>(NamedObject::map(idx, name, M));};
01765
01771 inline void add(const char *name, T& object)
01772 {object.NamedObject::add(idx, name, M);};
01773
01779 inline void add(const char *name, T *object)
01780 {object->NamedObject::add(idx, name, M);};
01781
01787 inline T *remove(const char *name)
01788 {return static_cast<T*>(NamedObject::remove(idx, name, M));};
01789
01794 inline T *begin(void) const
01795 {return static_cast<T*>(NamedObject::skip(idx, NULL, M));};
01796
01802 inline T *next(T *current) const
01803 {return static_cast<T*>(NamedObject::skip(idx, current, M));};
01804
01809 inline unsigned count(void) const
01810 {return NamedObject::count(idx, M);};
01811
01818 inline T **index(void) const
01819 {return NamedObject::index(idx, M);};
01820
01827 inline T **sort(void) const
01828 {return NamedObject::sort(NamedObject::index(idx, M));};
01829 };
01830
01837 template <class T>
01838 class keylist : public OrderedIndex
01839 {
01840 public:
01845 inline NamedObject **root(void)
01846 {return static_cast<NamedObject*>(&head);};
01847
01853 inline T *begin(void)
01854 {return static_cast<T*>(head);};
01855
01861 inline T *end(void)
01862 {return static_cast<T*>(tail);};
01863
01870 inline T *create(const char *name)
01871 {return new T(this, name);};
01872
01878 inline T *next(LinkedObject *current)
01879 {return static_cast<T*>(current->getNext());};
01880
01886 inline T *find(const char *name)
01887 {return static_cast<T*>(NamedObject::find(begin(), name));};
01888
01889 inline T *offset(unsigned offset)
01890 {return static_cast<T*>(OrderedIndex::find(offset));};
01891
01897 inline T& operator[](unsigned offset)
01898 {return static_cast<T&>(OrderedIndex::find(offset));};
01899
01900 inline T& operator[](const char *name)
01901 {return static_cast<T&>(NamedObject::find(begin(), name));};
01902
01909 inline T **index(void)
01910 {return static_cast<T**>(OrderedIndex::index());};
01911
01918 inline T **sort(void)
01919 {return static_cast<T**>(NamedObject::sort(index()));};
01920 };
01921
01927 inline void push(ObjectStack& stack, LinkedObject *object)
01928 {stack.push(object);}
01929
01935 inline void add(ObjectStack& stack, LinkedObject *object)
01936 {stack.push(object);}
01937
01943 inline LinkedObject *pop(ObjectStack& stack)
01944 {return stack.pull();}
01945
01951 inline LinkedObject *pull(ObjectStack& stack)
01952 {return stack.pull();}
01953
01959 inline void push(OrderedIndex& fifo, LinkedObject *object)
01960 {fifo.add((OrderedObject *)object);}
01961
01967 inline void add(OrderedIndex& fifo, LinkedObject *object)
01968 {fifo.add((OrderedObject *)object);}
01969
01975 inline LinkedObject *pop(OrderedIndex& fifo)
01976 {return fifo.get();}
01977
01983 inline LinkedObject *pull(OrderedIndex& fifo)
01984 {return fifo.get();}
01985
01991 inline void push(ObjectQueue& queue, DLinkedObject *object)
01992 {queue.add(object);}
01993
01999 inline void add(ObjectQueue& queue, DLinkedObject *object)
02000 {queue.add(object);}
02001
02007 inline DLinkedObject *pop(ObjectQueue& queue)
02008 {return (DLinkedObject *)queue.pop();}
02009
02015 inline DLinkedObject *pull(ObjectQueue& queue)
02016 {return (DLinkedObject *)queue.pull();}
02017
02021 typedef LinkedObject *LinkedIndex;
02022
02026 typedef ObjectStack objstack_t;
02027
02031 typedef OrderedIndex objfifo_t;
02032
02036 typedef ObjectQueue objqueue_t;
02037
02038 END_NAMESPACE
02039
02040 #endif