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 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 END_NAMESPACE
01968
01969 #endif