00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00027 #ifndef _UCOMMON_LINKED_H_
00028 #define _UCOMMON_LINKED_H_
00029
00030 #ifndef _UCOMMON_OBJECT_H_
00031 #include <ucommon/object.h>
00032 #endif
00033
00034 NAMESPACE_UCOMMON
00035
00036 class OrderedObject;
00037
00045 class __EXPORT LinkedObject : public Object
00046 {
00047 protected:
00048 friend class OrderedIndex;
00049 friend class LinkedRing;
00050 friend class NamedObject;
00051
00052 LinkedObject *next;
00053
00058 LinkedObject(LinkedObject **root);
00059
00065 LinkedObject();
00066
00067 public:
00068 static const LinkedObject *nil;
00069 static const LinkedObject *inv;
00071 virtual ~LinkedObject();
00072
00076 virtual void release(void);
00077
00081 virtual void retain(void);
00082
00089 void enlist(LinkedObject **root);
00090
00097 void delist(LinkedObject **root);
00098
00103 bool isMember(LinkedObject *list) const;
00104
00109 static void purge(LinkedObject *root);
00110
00115 static unsigned count(LinkedObject *root);
00116
00123 static LinkedObject *getIndexed(LinkedObject *root, unsigned index);
00124
00129 inline LinkedObject *getNext(void) const
00130 {return next;};
00131 };
00132
00142 class __EXPORT ReusableObject : public LinkedObject
00143 {
00144 friend class ReusableAllocator;
00145
00146 protected:
00147 virtual void release(void);
00148
00149 public:
00154 inline ReusableObject *getNext(void)
00155 {return static_cast<ReusableObject*>(LinkedObject::getNext());};
00156 };
00157
00165 class __EXPORT OrderedIndex
00166 {
00167 protected:
00168 friend class OrderedObject;
00169 friend class LinkedList;
00170 friend class NamedObject;
00171
00172 OrderedObject *head, *tail;
00173
00174 public:
00178 OrderedIndex();
00179
00183 virtual ~OrderedIndex();
00184
00189 LinkedObject *find(unsigned offset) const;
00190
00195 unsigned count(void) const;
00196
00200 void purge(void);
00201
00206 virtual void lock_index(void);
00207
00212 virtual void unlock_index(void);
00213
00220 LinkedObject **index(void) const;
00221
00227 LinkedObject *get(void);
00228
00234 inline LinkedObject *getIndexed(unsigned index) const
00235 {return LinkedObject::getIndexed((LinkedObject*)head, index);};
00236
00241 inline LinkedObject *begin(void) const
00242 {return (LinkedObject*)(head);};
00243
00248 inline LinkedObject *end(void) const
00249 {return (LinkedObject*)(tail);};
00250
00255 inline LinkedObject *operator*() const
00256 {return (LinkedObject*)(head);};
00257
00262 void operator*=(OrderedObject *object);
00263 };
00264
00271 class __EXPORT OrderedObject : public LinkedObject
00272 {
00273 protected:
00274 friend class LinkedList;
00275 friend class OrderedIndex;
00276
00281 OrderedObject(OrderedIndex *index);
00282
00286 OrderedObject();
00287
00288 public:
00293 void enlistTail(OrderedIndex *index);
00294
00299 void enlistHead(OrderedIndex *index);
00300
00306 virtual void enlist(OrderedIndex *index);
00307
00312 void delist(OrderedIndex *index);
00313
00318 inline OrderedObject *getNext(void) const
00319 {return static_cast<OrderedObject *>(LinkedObject::getNext());};
00320 };
00321
00336 class __EXPORT NamedObject : public OrderedObject
00337 {
00338 protected:
00339 char *id;
00340
00344 NamedObject();
00345
00352 NamedObject(NamedObject **hash, char *name, unsigned size = 1);
00353
00360 NamedObject(OrderedIndex *index, char *name);
00361
00369 ~NamedObject();
00370
00375 virtual void clearId(void);
00376
00377 public:
00383 static void purge(NamedObject **hash, unsigned size);
00384
00393 static NamedObject **index(NamedObject **hash, unsigned size);
00394
00400 static unsigned count(NamedObject **hash, unsigned size);
00401
00409 static NamedObject *find(NamedObject *root, const char *name);
00410
00417 static NamedObject *map(NamedObject **hash, const char *name, unsigned size);
00418
00426 static NamedObject *skip(NamedObject **hash, NamedObject *current, unsigned size);
00427
00433 static unsigned keyindex(const char *name, unsigned size);
00434
00442 static NamedObject **sort(NamedObject **list, size_t count = 0);
00443
00448 inline NamedObject *getNext(void) const
00449 {return static_cast<NamedObject*>(LinkedObject::getNext());};
00450
00455 inline char *getId(void) const
00456 {return id;};
00457
00465 virtual bool compare(const char *name) const;
00466
00472 inline bool operator==(const char *name) const
00473 {return compare(name);};
00474
00480 inline bool operator!=(const char *name) const
00481 {return !compare(name);};
00482 };
00483
00491 class __EXPORT NamedTree : public NamedObject
00492 {
00493 protected:
00494 NamedTree *parent;
00495 OrderedIndex child;
00496
00501 NamedTree(char *name = NULL);
00502
00508 NamedTree(NamedTree *parent, char *name);
00509
00515 virtual ~NamedTree();
00516
00522 void purge(void);
00523
00524 public:
00533 NamedTree *find(const char *name) const;
00534
00545 NamedTree *path(const char *path) const;
00546
00554 NamedTree *leaf(const char *name) const;
00555
00561 NamedTree *getChild(const char *name) const;
00562
00569 NamedTree *getLeaf(const char *name) const;
00570
00577 inline NamedTree *getFirst(void) const
00578 {return static_cast<NamedTree *>(child.begin());};
00579
00584 inline NamedTree *getParent(void) const
00585 {return parent;};
00586
00592 inline NamedTree *getIndexed(unsigned index) const
00593 {return static_cast<NamedTree *>(child.getIndexed(index));};
00594
00599 inline OrderedIndex *getIndex(void) const
00600 {return const_cast<OrderedIndex*>(&child);};
00601
00606 inline operator bool() const
00607 {return (id != NULL);};
00608
00613 inline bool operator!() const
00614 {return (id == NULL);};
00615
00621 void setId(char *name);
00622
00627 void remove(void);
00628
00633 inline bool isLeaf(void) const
00634 {return (child.begin() == NULL);};
00635
00640 inline bool isRoot(void) const
00641 {return (parent == NULL);};
00642
00647 void relistTail(NamedTree *trunk);
00648
00653 void relistHead(NamedTree *trunk);
00654
00659 inline void relist(NamedTree *trunk = NULL)
00660 {relistTail(trunk);};
00661 };
00662
00669 class __EXPORT LinkedList : public OrderedObject
00670 {
00671 protected:
00672 LinkedList *prev;
00673 OrderedIndex *root;
00674
00679 LinkedList(OrderedIndex *index);
00680
00684 LinkedList();
00685
00690 virtual ~LinkedList();
00691
00692 public:
00696 void delist(void);
00697
00703 void enlistHead(OrderedIndex *index);
00704
00710 void enlistTail(OrderedIndex *index);
00711
00717 void enlist(OrderedIndex *index);
00718
00723 inline bool isHead(void) const
00724 {return root->head == (OrderedObject *)this;};
00725
00730 inline bool isTail(void) const
00731 {return root->tail == (OrderedObject *)this;};
00732
00737 inline LinkedList *getPrev(void) const
00738 {return prev;};
00739
00744 inline LinkedList *getNext(void) const
00745 {return static_cast<LinkedList*>(LinkedObject::getNext());};
00746
00751 void insertTail(LinkedList *object);
00752
00757 void insertHead(LinkedList *object);
00758
00763 virtual void insert(LinkedList *object);
00764
00769 inline void operator+=(LinkedList *object)
00770 {insertTail(object);};
00771
00776 inline void operator-=(LinkedList *object)
00777 {insertHead(object);};
00778
00783 inline void operator*=(LinkedList *object)
00784 {insert(object);};
00785 };
00786
00792 class __EXPORT MultiMap : public ReusableObject
00793 {
00794 private:
00795 typedef struct {
00796 const char *key;
00797 size_t keysize;
00798 MultiMap *next;
00799 MultiMap **root;
00800 } link_t;
00801
00802 unsigned paths;
00803 link_t *links;
00804
00805 protected:
00810 MultiMap(unsigned count);
00811
00815 virtual ~MultiMap();
00816
00824 virtual bool compare(unsigned path, caddr_t key, size_t size);
00825
00826 public:
00832 void enlist(unsigned path, MultiMap **root);
00833
00842 void enlist(unsigned path, MultiMap **index, caddr_t key, unsigned size, size_t keysize = 0);
00843
00848 void delist(unsigned path);
00849
00854 MultiMap *next(unsigned path);
00855
00863 static unsigned keyindex(caddr_t key, unsigned max, size_t size = 0);
00864
00874 static MultiMap *find(unsigned path, MultiMap **index, caddr_t key, unsigned max, size_t size = 0);
00875 };
00876
00884 template <class T, class O=NamedObject>
00885 class named_value : public object_value<T, O>
00886 {
00887 public:
00893 inline named_value(LinkedObject **root, char *name)
00894 {LinkedObject::enlist(root); O::id = name;};
00895
00900 inline void operator=(const T& typed_value)
00901 {set(typed_value);};
00902
00909 inline static named_value find(named_value *first, const char *name)
00910 {return static_cast<named_value *>(NamedObject::find(first, name));};
00911 };
00912
00921 template <class T, class O=OrderedObject>
00922 class linked_value : public object_value<T, O>
00923 {
00924 public:
00928 inline linked_value() {};
00929
00934 inline linked_value(LinkedObject **root)
00935 {LinkedObject::enlist(root);};
00936
00941 inline linked_value(OrderedIndex *index)
00942 {O::enlist(index);};
00943
00949 inline linked_value(LinkedObject **root, const T& typed_value)
00950 {LinkedObject::enlist(root); set(typed_value);};
00951
00957 inline linked_value(OrderedIndex *index, const T& typed_value)
00958 {O::enlist(index); set(typed_value);};
00959
00964 inline void operator=(const T& typed_value)
00965 {set(typed_value);};
00966 };
00967
00974 template <class T>
00975 class linked_pointer
00976 {
00977 private:
00978 T *ptr;
00979
00980 public:
00985 inline linked_pointer(T *pointer)
00986 {ptr = pointer;};
00987
00992 inline linked_pointer(const linked_pointer &pointer)
00993 {ptr = pointer.ptr;};
00994
00999 inline linked_pointer(LinkedObject *pointer)
01000 {ptr = static_cast<T*>(pointer);};
01001
01006 inline linked_pointer(OrderedIndex *index)
01007 {ptr = static_cast<T*>(index->begin());};
01008
01012 inline linked_pointer()
01013 {ptr = NULL;};
01014
01019 inline void operator=(T *pointer)
01020 {ptr = pointer;};
01021
01026 inline void operator=(linked_pointer &pointer)
01027 {ptr = pointer.ptr;};
01028
01033 inline void operator=(OrderedIndex *index)
01034 {ptr = static_cast<T*>(index->begin());};
01035
01040 inline void operator=(LinkedObject *pointer)
01041 {ptr = static_cast<T*>(pointer);};
01042
01047 inline T* operator->() const
01048 {return ptr;};
01049
01054 inline T* operator*() const
01055 {return ptr;};
01056
01061 inline operator T*() const
01062 {return ptr;};
01063
01067 inline void prev(void)
01068 {ptr = static_cast<T*>(ptr->getPrev());};
01069
01073 inline void next(void)
01074 {ptr = static_cast<T*>(ptr->getNext());};
01075
01080 inline T *getNext(void) const
01081 {return static_cast<T*>(ptr->getNext());};
01082
01088 inline T *getPrev(void) const
01089 {return static_cast<T*>(ptr->getPrev());};
01090
01094 inline void operator++()
01095 {ptr = static_cast<T*>(ptr->getNext());};
01096
01100 inline void operator--()
01101 {ptr = static_cast<T*>(ptr->getPrev());};
01102
01107 inline bool isNext(void) const
01108 {return (ptr->getNext() != NULL);};
01109
01114 inline bool isPrev(void) const
01115 {return (ptr->getPrev() != NULL);};
01116
01121 inline operator bool() const
01122 {return (ptr != NULL);};
01123
01128 inline bool operator!() const
01129 {return (ptr == NULL);};
01130
01135 inline LinkedObject **root(void) const
01136 {T **r = &ptr; return (LinkedObject**)r;};
01137 };
01138
01146 template <class T, unsigned P>
01147 class multimap : public MultiMap
01148 {
01149 protected:
01150 T value;
01151
01152 public:
01156 inline multimap() : MultiMap(P) {};
01157
01161 inline ~multimap() {};
01162
01167 inline T &get(void) const
01168 {return value;};
01169
01175 inline multimap *next(unsigned path)
01176 {return static_cast<multimap*>(MultiMap::next(path));};
01177
01182 inline T operator*() const
01183 {return value;};
01184
01189 inline void setPointer(const T pointer)
01190 {value = pointer;};
01191
01196 inline void set(const T &reference)
01197 {value = reference;};
01198
01203 inline void operator=(const T& data)
01204 {value = data;};
01205
01215 inline static multimap *find(unsigned path, MultiMap **index, caddr_t key, unsigned size, unsigned keysize = 0)
01216 {return static_cast<multimap*>(MultiMap::find(path, index, key, size, keysize));};
01217 };
01218
01236 template <class T>
01237 class treemap : public NamedTree
01238 {
01239 protected:
01240 T value;
01241
01242 public:
01248 inline treemap(char *name = NULL) : NamedTree(name) {};
01249
01255 inline treemap(treemap *parent, char *name) : NamedTree(parent, name) {};
01256
01263 inline treemap(treemap *parent, char *name, T& reference) :
01264 NamedTree(parent, name) {value = reference;};
01265
01270 inline T& get(void) const
01271 {return value;};
01272
01277 inline T& operator*() const
01278 {return value;};
01279
01285 static inline T getPointer(treemap *node)
01286 {(node == NULL) ? NULL : node->value;};
01287
01292 inline bool isAttribute(void) const
01293 {return (!child.begin() && value != NULL);};
01294
01299 inline T getPointer(void) const
01300 {return value;};
01301
01306 inline T& getData(void) const
01307 {return value;};
01308
01313 inline void setPointer(const T pointer)
01314 {value = pointer;};
01315
01320 inline void set(const T& reference)
01321 {value = reference;};
01322
01327 inline void operator=(const T& data)
01328 {value = data;};
01329
01335 inline treemap *getIndexed(unsigned index) const
01336 {return static_cast<treemap*>(child.getIndexed(index));};
01337
01342 inline treemap *getParent(void) const
01343 {return static_cast<treemap*>(parent);};
01344
01351 inline treemap *getChild(const char *name) const
01352 {return static_cast<treemap*>(NamedTree::getChild(name));};
01353
01360 inline treemap *getLeaf(const char *name) const
01361 {return static_cast<treemap*>(NamedTree::getLeaf(name));};
01362
01370 inline T getValue(const char *name) const
01371 {return getPointer(getLeaf(name));};
01372
01379 inline treemap *find(const char *name) const
01380 {return static_cast<treemap*>(NamedTree::find(name));};
01381
01388 inline treemap *path(const char *path) const
01389 {return static_cast<treemap*>(NamedTree::path(path));};
01390
01397 inline treemap *leaf(const char *name) const
01398 {return static_cast<treemap*>(NamedTree::leaf(name));};
01399
01404 inline treemap *getFirst(void) const
01405 {return static_cast<treemap*>(NamedTree::getFirst());};
01406 };
01407
01415 template <class T, unsigned M = 177>
01416 class keymap
01417 {
01418 private:
01419 NamedObject *idx[M];
01420
01421 public:
01425 inline ~keymap()
01426 {NamedObject::purge(idx, M);};
01427
01432 inline NamedObject **root(void) const
01433 {return idx;};
01434
01439 inline unsigned limit(void) const
01440 {return M;};
01441
01447 inline T *get(const char *name) const
01448 {return static_cast<T*>(NamedObject::map(idx, name, M));};
01449
01454 inline T *begin(void) const
01455 {return static_cast<T*>(NamedObject::skip(idx, NULL, M));};
01456
01462 inline T *next(T *current) const
01463 {return static_cast<T*>(NamedObject::skip(idx, current, M));};
01464
01469 inline unsigned count(void) const
01470 {return NamedObject::count(idx, M);};
01471
01478 inline T **index(void) const
01479 {return NamedObject::index(idx, M);};
01480
01487 inline T **sort(void) const
01488 {return NamedObject::sort(NamedObject::index(idx, M));};
01489 };
01490
01497 template <class T>
01498 class keylist : public OrderedIndex
01499 {
01500 public:
01505 inline NamedObject **root(void)
01506 {return static_cast<NamedObject*>(&head);};
01507
01513 inline T *begin(void)
01514 {return static_cast<T*>(head);};
01515
01521 inline T *end(void)
01522 {return static_cast<T*>(tail);};
01523
01530 inline T *create(const char *name)
01531 {return new T(this, name);};
01532
01538 inline T *next(LinkedObject *current)
01539 {return static_cast<T*>(current->getNext());};
01540
01546 inline T *find(const char *name)
01547 {return static_cast<T*>(NamedObject::find(begin(), name));};
01548
01554 inline T *operator[](unsigned offset)
01555 {return static_cast<T*>(OrderedIndex::find(offset));};
01556
01563 inline T **index(void)
01564 {return static_cast<T**>(OrderedIndex::index());};
01565
01572 inline T **sort(void)
01573 {return static_cast<T**>(NamedObject::sort(index()));};
01574 };
01575
01579 typedef LinkedObject *LinkedIndex;
01580
01581 END_NAMESPACE
01582
01583 #endif