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 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 T& get(void) const
01571 {return value;};
01572
01577 inline T& operator*() const
01578 {return value;};
01579
01585 static inline T getPointer(treemap *node)
01586 {(node == NULL) ? NULL : node->value;};
01587
01592 inline bool isAttribute(void) const
01593 {return (!child.begin() && value != NULL);};
01594
01599 inline T getPointer(void) const
01600 {return value;};
01601
01606 inline 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