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
00217 virtual void lock_index(void);
00218
00223 virtual void unlock_index(void);
00224
00231 LinkedObject **index(void) const;
00232
00238 LinkedObject *get(void);
00239
00244 void add(OrderedObject *ordered);
00245
00251 inline LinkedObject *getIndexed(unsigned index) const
00252 {return LinkedObject::getIndexed((LinkedObject*)head, index);};
00253
00258 inline LinkedObject *begin(void) const
00259 {return (LinkedObject*)(head);};
00260
00265 inline LinkedObject *end(void) const
00266 {return (LinkedObject*)(tail);};
00267
00272 inline LinkedObject *operator*() const
00273 {return (LinkedObject*)(head);};
00274
00279 void operator*=(OrderedObject *object);
00280 };
00281
00288 class __EXPORT OrderedObject : public LinkedObject
00289 {
00290 protected:
00291 friend class LinkedList;
00292 friend class OrderedIndex;
00293 friend class DLinkedObject;
00294 friend class ObjectQueue;
00295
00300 OrderedObject(OrderedIndex *index);
00301
00305 OrderedObject();
00306
00307 public:
00312 void enlistTail(OrderedIndex *index);
00313
00318 void enlistHead(OrderedIndex *index);
00319
00325 virtual void enlist(OrderedIndex *index);
00326
00331 void delist(OrderedIndex *index);
00332
00337 inline OrderedObject *getNext(void) const
00338 {return static_cast<OrderedObject *>(LinkedObject::getNext());};
00339 };
00340
00345 class __EXPORT DLinkedObject : public OrderedObject
00346 {
00347 public:
00348 friend class ObjectQueue;
00349
00353 DLinkedObject();
00354
00355 protected:
00359 void delist(void);
00360
00361 private:
00362 DLinkedObject *prev;
00363 };
00364
00379 class __EXPORT NamedObject : public OrderedObject
00380 {
00381 protected:
00382 char *id;
00383
00387 NamedObject();
00388
00395 NamedObject(NamedObject **hash, char *name, unsigned size = 1);
00396
00403 NamedObject(OrderedIndex *index, char *name);
00404
00412 ~NamedObject();
00413
00418 virtual void clearId(void);
00419
00420 public:
00427 void add(NamedObject **hash, char *name, unsigned size = 1);
00428
00434 static void purge(NamedObject **hash, unsigned size);
00435
00444 static NamedObject **index(NamedObject **hash, unsigned size);
00445
00451 static unsigned count(NamedObject **hash, unsigned size);
00452
00460 static NamedObject *find(NamedObject *root, const char *name);
00461
00468 static NamedObject *remove(NamedObject **root, const char *name);
00469
00477 static NamedObject *map(NamedObject **hash, const char *name, unsigned size);
00478
00486 static NamedObject *remove(NamedObject **hash, const char *name, unsigned size);
00487
00495 static NamedObject *skip(NamedObject **hash, NamedObject *current, unsigned size);
00496
00502 static unsigned keyindex(const char *name, unsigned size);
00503
00511 static NamedObject **sort(NamedObject **list, size_t count = 0);
00512
00517 inline NamedObject *getNext(void) const
00518 {return static_cast<NamedObject*>(LinkedObject::getNext());};
00519
00524 inline char *getId(void) const
00525 {return id;};
00526
00534 virtual bool compare(const char *name) const;
00535
00541 inline bool operator==(const char *name) const
00542 {return compare(name);};
00543
00549 inline bool operator!=(const char *name) const
00550 {return !compare(name);};
00551 };
00552
00560 class __EXPORT NamedTree : public NamedObject
00561 {
00562 protected:
00563 NamedTree *parent;
00564 OrderedIndex child;
00565
00570 NamedTree(char *name = NULL);
00571
00577 NamedTree(NamedTree *parent, char *name);
00578
00583 NamedTree(const NamedTree& source);
00584
00590 virtual ~NamedTree();
00591
00597 void purge(void);
00598
00599 public:
00608 NamedTree *find(const char *name) const;
00609
00620 NamedTree *path(const char *path) const;
00621
00629 NamedTree *leaf(const char *name) const;
00630
00636 NamedTree *getChild(const char *name) const;
00637
00644 NamedTree *getLeaf(const char *name) const;
00645
00652 inline NamedTree *getFirst(void) const
00653 {return static_cast<NamedTree *>(child.begin());};
00654
00659 inline NamedTree *getParent(void) const
00660 {return parent;};
00661
00667 inline NamedTree *getIndexed(unsigned index) const
00668 {return static_cast<NamedTree *>(child.getIndexed(index));};
00669
00674 inline OrderedIndex *getIndex(void) const
00675 {return const_cast<OrderedIndex*>(&child);};
00676
00681 inline operator bool() const
00682 {return (id != NULL);};
00683
00688 inline bool operator!() const
00689 {return (id == NULL);};
00690
00696 void setId(char *name);
00697
00702 void remove(void);
00703
00708 inline bool isLeaf(void) const
00709 {return (child.begin() == NULL);};
00710
00715 inline bool isRoot(void) const
00716 {return (parent == NULL);};
00717
00722 void relistTail(NamedTree *trunk);
00723
00728 void relistHead(NamedTree *trunk);
00729
00734 inline void relist(NamedTree *trunk = NULL)
00735 {relistTail(trunk);};
00736 };
00737
00744 class __EXPORT LinkedList : public OrderedObject
00745 {
00746 protected:
00747 friend class ObjectQueue;
00748
00749 LinkedList *prev;
00750 OrderedIndex *root;
00751
00756 LinkedList(OrderedIndex *index);
00757
00761 LinkedList();
00762
00767 virtual ~LinkedList();
00768
00769 public:
00773 void delist(void);
00774
00780 void enlistHead(OrderedIndex *index);
00781
00787 void enlistTail(OrderedIndex *index);
00788
00794 void enlist(OrderedIndex *index);
00795
00800 inline bool isHead(void) const
00801 {return root->head == (OrderedObject *)this;};
00802
00807 inline bool isTail(void) const
00808 {return root->tail == (OrderedObject *)this;};
00809
00814 inline LinkedList *getPrev(void) const
00815 {return prev;};
00816
00821 inline LinkedList *getNext(void) const
00822 {return static_cast<LinkedList*>(LinkedObject::getNext());};
00823
00828 void insertTail(LinkedList *object);
00829
00834 void insertHead(LinkedList *object);
00835
00840 virtual void insert(LinkedList *object);
00841
00846 inline void operator+=(LinkedList *object)
00847 {insertTail(object);};
00848
00853 inline void operator-=(LinkedList *object)
00854 {insertHead(object);};
00855
00860 inline void operator*=(LinkedList *object)
00861 {insert(object);};
00862 };
00863
00869 class __EXPORT ObjectQueue : public OrderedIndex
00870 {
00871 public:
00875 ObjectQueue();
00876
00881 void add(DLinkedObject *object);
00882
00887 void push(DLinkedObject *object);
00888
00893 DLinkedObject *pull(void);
00894
00899 DLinkedObject *pop(void);
00900 };
00901
00902 class __EXPORT ObjectStack
00903 {
00904 protected:
00905 LinkedObject *root;
00906
00907 public:
00911 ObjectStack();
00912
00917 ObjectStack(LinkedObject *list);
00918
00923 void push(LinkedObject *object);
00924
00929 LinkedObject *pull(void);
00930
00935 inline LinkedObject *pop(void)
00936 {return ObjectStack::pull();};
00937 };
00938
00939
00945 class __EXPORT MultiMap : public ReusableObject
00946 {
00947 private:
00948 typedef struct {
00949 const char *key;
00950 size_t keysize;
00951 MultiMap *next;
00952 MultiMap **root;
00953 } link_t;
00954
00955 unsigned paths;
00956 link_t *links;
00957
00958 protected:
00963 MultiMap(unsigned count);
00964
00968 virtual ~MultiMap();
00969
00977 virtual bool compare(unsigned path, caddr_t key, size_t size) const;
00978
00979 public:
00985 void enlist(unsigned path, MultiMap **root);
00986
00995 void enlist(unsigned path, MultiMap **index, caddr_t key, unsigned size, size_t keysize = 0);
00996
01001 void delist(unsigned path);
01002
01007 MultiMap *next(unsigned path) const;
01008
01016 static unsigned keyindex(caddr_t key, unsigned max, size_t size = 0);
01017
01027 static MultiMap *find(unsigned path, MultiMap **index, caddr_t key, unsigned max, size_t size = 0);
01028 };
01029
01037 template <class T, class O=NamedObject>
01038 class named_value : public object_value<T, O>
01039 {
01040 public:
01046 inline named_value(LinkedObject **root, char *name)
01047 {LinkedObject::enlist(root); O::id = name;};
01048
01053 inline void operator=(const T& typed_value)
01054 {set(typed_value);};
01055
01062 inline static named_value find(named_value *first, const char *name)
01063 {return static_cast<named_value *>(NamedObject::find(first, name));};
01064 };
01065
01074 template <class T, class O=OrderedObject>
01075 class linked_value : public object_value<T, O>
01076 {
01077 public:
01081 inline linked_value() {};
01082
01087 inline linked_value(LinkedObject **root)
01088 {LinkedObject::enlist(root);};
01089
01094 inline linked_value(OrderedIndex *index)
01095 {O::enlist(index);};
01096
01102 inline linked_value(LinkedObject **root, const T& typed_value)
01103 {LinkedObject::enlist(root); set(typed_value);};
01104
01110 inline linked_value(OrderedIndex *index, const T& typed_value)
01111 {O::enlist(index); set(typed_value);};
01112
01117 inline void operator=(const T& typed_value)
01118 {set(typed_value);};
01119 };
01120
01126 template <class T>
01127 class objstack : public ObjectStack
01128 {
01129 public:
01133 inline objstack() : ObjectStack() {}
01134
01138 inline objstack(T *list) : ObjectStack(list) {}
01139
01144 inline void push(T *object)
01145 {ObjectStack::push(object);}
01146
01151 inline void add(T *object)
01152 {ObjectStack::push(object);}
01153
01158 inline T *pull(void)
01159 {return (T *)ObjectStack::pull();}
01160
01165 inline T *pop(void)
01166 {return (T *)ObjectStack::pull();}
01167 };
01168
01175 template <class T>
01176 class objfifo : public OrderedIndex
01177 {
01178 public:
01182 inline objfifo() : OrderedIndex() {}
01183
01188 inline void push(T *object)
01189 {OrderedIndex::add((OrderedObject *)object);}
01190
01195 inline void add(T *object)
01196 {OrderedIndex::add((OrderedObject *)object);}
01197
01202 inline T *pull(void)
01203 {return (T *)OrderedIndex::get();}
01204
01209 inline T *pop(void)
01210 {return (T *)OrderedIndex::get();}
01211 };
01212
01218 template <class T>
01219 class objqueue : public ObjectQueue
01220 {
01221 public:
01225 inline objqueue() : ObjectQueue() {}
01226
01231 inline void push(T *object)
01232 {ObjectQueue::push((DLinkedObject *)object);}
01233
01238 inline void add(T *object)
01239 {ObjectQueue::add((DLinkedObject *)object);}
01240
01245 inline T *pull(void)
01246 {return (T *)ObjectQueue::pull();}
01247
01252 inline T *pop(void)
01253 {return (T *)ObjectQueue::pop();}
01254 };
01255
01256
01263 template <class T>
01264 class linked_pointer
01265 {
01266 private:
01267 T *ptr;
01268
01269 public:
01274 inline linked_pointer(T *pointer)
01275 {ptr = pointer;};
01276
01281 inline linked_pointer(const linked_pointer &pointer)
01282 {ptr = pointer.ptr;};
01283
01288 inline linked_pointer(LinkedObject *pointer)
01289 {ptr = static_cast<T*>(pointer);};
01290
01295 inline linked_pointer(OrderedIndex *index)
01296 {ptr = static_cast<T*>(index->begin());};
01297
01301 inline linked_pointer()
01302 {ptr = NULL;};
01303
01308 inline void operator=(T *pointer)
01309 {ptr = pointer;};
01310
01315 inline void operator=(linked_pointer &pointer)
01316 {ptr = pointer.ptr;};
01317
01322 inline void operator=(OrderedIndex *index)
01323 {ptr = static_cast<T*>(index->begin());};
01324
01329 inline void operator=(LinkedObject *pointer)
01330 {ptr = static_cast<T*>(pointer);};
01331
01336 inline T* operator->() const
01337 {return ptr;};
01338
01343 inline T* operator*() const
01344 {return ptr;};
01345
01350 inline operator T*() const
01351 {return ptr;};
01352
01356 inline void prev(void)
01357 {ptr = static_cast<T*>(ptr->getPrev());};
01358
01362 inline void next(void)
01363 {ptr = static_cast<T*>(ptr->getNext());};
01364
01369 inline T *getNext(void) const
01370 {return static_cast<T*>(ptr->getNext());};
01371
01377 inline T *getPrev(void) const
01378 {return static_cast<T*>(ptr->getPrev());};
01379
01383 inline void operator++()
01384 {ptr = static_cast<T*>(ptr->getNext());};
01385
01389 inline void operator--()
01390 {ptr = static_cast<T*>(ptr->getPrev());};
01391
01396 inline bool isNext(void) const
01397 {return (ptr->getNext() != NULL);};
01398
01403 inline bool isPrev(void) const
01404 {return (ptr->getPrev() != NULL);};
01405
01410 inline operator bool() const
01411 {return (ptr != NULL);};
01412
01417 inline bool operator!() const
01418 {return (ptr == NULL);};
01419
01424 inline LinkedObject **root(void) const
01425 {T **r = &ptr; return (LinkedObject**)r;};
01426 };
01427
01435 template <class T, unsigned P>
01436 class multimap : public MultiMap
01437 {
01438 protected:
01439 T value;
01440
01441 public:
01445 inline multimap() : MultiMap(P) {};
01446
01450 inline ~multimap() {};
01451
01456 inline T &get(void) const
01457 {return value;};
01458
01464 inline multimap *next(unsigned path)
01465 {return static_cast<multimap*>(MultiMap::next(path));};
01466
01471 inline T operator*() const
01472 {return value;};
01473
01478 inline void setPointer(const T pointer)
01479 {value = pointer;};
01480
01485 inline void set(const T &reference)
01486 {value = reference;};
01487
01492 inline void operator=(const T& data)
01493 {value = data;};
01494
01504 inline static multimap *find(unsigned path, MultiMap **index, caddr_t key, unsigned size, unsigned keysize = 0)
01505 {return static_cast<multimap*>(MultiMap::find(path, index, key, size, keysize));};
01506 };
01507
01525 template <class T>
01526 class treemap : public NamedTree
01527 {
01528 protected:
01529 T value;
01530
01531 public:
01537 inline treemap(char *name = NULL) : NamedTree(name) {};
01538
01543 inline treemap(const treemap& source) : NamedTree(source)
01544 {value = source.value;};
01545
01551 inline treemap(treemap *parent, char *name) : NamedTree(parent, name) {};
01552
01559 inline treemap(treemap *parent, char *name, T& reference) :
01560 NamedTree(parent, name) {value = reference;};
01561
01566 inline T& get(void) const
01567 {return value;};
01568
01573 inline T& operator*() const
01574 {return value;};
01575
01581 static inline T getPointer(treemap *node)
01582 {(node == NULL) ? NULL : node->value;};
01583
01588 inline bool isAttribute(void) const
01589 {return (!child.begin() && value != NULL);};
01590
01595 inline T getPointer(void) const
01596 {return value;};
01597
01602 inline T& getData(void) const
01603 {return value;};
01604
01609 inline void setPointer(const T pointer)
01610 {value = pointer;};
01611
01616 inline void set(const T& reference)
01617 {value = reference;};
01618
01623 inline void operator=(const T& data)
01624 {value = data;};
01625
01631 inline treemap *getIndexed(unsigned index) const
01632 {return static_cast<treemap*>(child.getIndexed(index));};
01633
01638 inline treemap *getParent(void) const
01639 {return static_cast<treemap*>(parent);};
01640
01647 inline treemap *getChild(const char *name) const
01648 {return static_cast<treemap*>(NamedTree::getChild(name));};
01649
01656 inline treemap *getLeaf(const char *name) const
01657 {return static_cast<treemap*>(NamedTree::getLeaf(name));};
01658
01666 inline T getValue(const char *name) const
01667 {return getPointer(getLeaf(name));};
01668
01675 inline treemap *find(const char *name) const
01676 {return static_cast<treemap*>(NamedTree::find(name));};
01677
01684 inline treemap *path(const char *path) const
01685 {return static_cast<treemap*>(NamedTree::path(path));};
01686
01693 inline treemap *leaf(const char *name) const
01694 {return static_cast<treemap*>(NamedTree::leaf(name));};
01695
01700 inline treemap *getFirst(void) const
01701 {return static_cast<treemap*>(NamedTree::getFirst());};
01702 };
01703
01711 template <class T, unsigned M = 177>
01712 class keymap
01713 {
01714 private:
01715 NamedObject *idx[M];
01716
01717 public:
01721 inline ~keymap()
01722 {NamedObject::purge(idx, M);};
01723
01728 inline NamedObject **root(void) const
01729 {return idx;};
01730
01735 inline unsigned limit(void) const
01736 {return M;};
01737
01743 inline T *get(const char *name) const
01744 {return static_cast<T*>(NamedObject::map(idx, name, M));};
01745
01751 inline T *operator[](const char *name) const
01752 {return static_cast<T*>(NamedObject::map(idx, name, M));};
01753
01759 inline void add(const char *name, T& object)
01760 {object.NamedObject::add(idx, name, M);};
01761
01767 inline void add(const char *name, T *object)
01768 {object->NamedObject::add(idx, name, M);};
01769
01775 inline T *remove(const char *name)
01776 {return static_cast<T*>(NamedObject::remove(idx, name, M));};
01777
01782 inline T *begin(void) const
01783 {return static_cast<T*>(NamedObject::skip(idx, NULL, M));};
01784
01790 inline T *next(T *current) const
01791 {return static_cast<T*>(NamedObject::skip(idx, current, M));};
01792
01797 inline unsigned count(void) const
01798 {return NamedObject::count(idx, M);};
01799
01806 inline T **index(void) const
01807 {return NamedObject::index(idx, M);};
01808
01815 inline T **sort(void) const
01816 {return NamedObject::sort(NamedObject::index(idx, M));};
01817 };
01818
01825 template <class T>
01826 class keylist : public OrderedIndex
01827 {
01828 public:
01833 inline NamedObject **root(void)
01834 {return static_cast<NamedObject*>(&head);};
01835
01841 inline T *begin(void)
01842 {return static_cast<T*>(head);};
01843
01849 inline T *end(void)
01850 {return static_cast<T*>(tail);};
01851
01858 inline T *create(const char *name)
01859 {return new T(this, name);};
01860
01866 inline T *next(LinkedObject *current)
01867 {return static_cast<T*>(current->getNext());};
01868
01874 inline T *find(const char *name)
01875 {return static_cast<T*>(NamedObject::find(begin(), name));};
01876
01882 inline T *operator[](unsigned offset)
01883 {return static_cast<T*>(OrderedIndex::find(offset));};
01884
01891 inline T **index(void)
01892 {return static_cast<T**>(OrderedIndex::index());};
01893
01900 inline T **sort(void)
01901 {return static_cast<T**>(NamedObject::sort(index()));};
01902 };
01903
01909 inline void push(ObjectStack& stack, LinkedObject *object)
01910 {stack.push(object);}
01911
01917 inline void add(ObjectStack& stack, LinkedObject *object)
01918 {stack.push(object);}
01919
01925 inline LinkedObject *pop(ObjectStack& stack)
01926 {return stack.pull();}
01927
01933 inline LinkedObject *pull(ObjectStack& stack)
01934 {return stack.pull();}
01935
01941 inline void push(OrderedIndex& fifo, LinkedObject *object)
01942 {fifo.add((OrderedObject *)object);}
01943
01949 inline void add(OrderedIndex& fifo, LinkedObject *object)
01950 {fifo.add((OrderedObject *)object);}
01951
01957 inline LinkedObject *pop(OrderedIndex& fifo)
01958 {return fifo.get();}
01959
01965 inline LinkedObject *pull(OrderedIndex& fifo)
01966 {return fifo.get();}
01967
01973 inline void push(ObjectQueue& queue, DLinkedObject *object)
01974 {queue.add(object);}
01975
01981 inline void add(ObjectQueue& queue, DLinkedObject *object)
01982 {queue.add(object);}
01983
01989 inline DLinkedObject *pop(ObjectQueue& queue)
01990 {return (DLinkedObject *)queue.pop();}
01991
01997 inline DLinkedObject *pull(ObjectQueue& queue)
01998 {return (DLinkedObject *)queue.pull();}
01999
02003 typedef LinkedObject *LinkedIndex;
02004
02008 typedef ObjectStack objstack_t;
02009
02013 typedef OrderedIndex objfifo_t;
02014
02018 typedef ObjectQueue objqueue_t;
02019
02020 END_NAMESPACE
02021
02022 #endif