ucommon
linked.h
Go to the documentation of this file.
1 // Copyright (C) 2006-2010 David Sugar, Tycho Softworks.
2 //
3 // This file is part of GNU uCommon C++.
4 //
5 // GNU uCommon C++ is free software: you can redistribute it and/or modify
6 // it under the terms of the GNU Lesser General Public License as published
7 // by the Free Software Foundation, either version 3 of the License, or
8 // (at your option) any later version.
9 //
10 // GNU uCommon C++ is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU Lesser General Public License for more details.
14 //
15 // You should have received a copy of the GNU Lesser General Public License
16 // along with GNU uCommon C++. If not, see <http://www.gnu.org/licenses/>.
17 
32 #ifndef _UCOMMON_LINKED_H_
33 #define _UCOMMON_LINKED_H_
34 
35 #ifndef _UCOMMON_CONFIG_H_
36 #include <ucommon/platform.h>
37 #endif
38 
39 #ifndef _UCOMMON_OBJECT_H_
40 #include <ucommon/object.h>
41 #endif
42 
43 NAMESPACE_UCOMMON
44 
45 class OrderedObject;
46 
54 class __EXPORT LinkedObject : public ObjectProtocol
55 {
56 protected:
57  friend class OrderedIndex;
58  friend class LinkedRing;
59  friend class NamedObject;
60  friend class ObjectStack;
61 
62  LinkedObject *Next;
63 
68  LinkedObject(LinkedObject **root);
69 
75  LinkedObject();
76 
77 public:
78  static const LinkedObject *nil;
79  static const LinkedObject *inv;
81  virtual ~LinkedObject();
82 
86  virtual void release(void);
87 
91  virtual void retain(void);
92 
99  void enlist(LinkedObject **root);
100 
107  void delist(LinkedObject **root);
108 
113  bool is_member(LinkedObject *list) const;
114 
119  static void purge(LinkedObject *root);
120 
125  static unsigned count(const LinkedObject *root);
126 
133  static LinkedObject *getIndexed(LinkedObject *root, unsigned index);
134 
139  inline LinkedObject *getNext(void) const
140  {return Next;};
141 };
142 
152 class __EXPORT ReusableObject : public LinkedObject
153 {
154  friend class ReusableAllocator;
155 
156 protected:
157  virtual void release(void);
158 
159 public:
164  inline ReusableObject *getNext(void)
165  {return static_cast<ReusableObject*>(LinkedObject::getNext());};
166 };
167 
175 class __EXPORT OrderedIndex
176 {
177 protected:
178  friend class OrderedObject;
179  friend class DLinkedObject;
180  friend class LinkedList;
181  friend class NamedObject;
182 
183  OrderedObject *head, *tail;
184 
185  void copy(const OrderedIndex& source);
186 
187 public:
191  OrderedIndex();
192 
193  inline OrderedIndex(const OrderedIndex& source)
194  {copy(source);}
195 
199  virtual ~OrderedIndex();
200 
205  LinkedObject *find(unsigned offset) const;
206 
211  unsigned count(void) const;
212 
216  void purge(void);
217 
221  void reset(void);
222 
227  virtual void lock_index(void);
228 
233  virtual void unlock_index(void);
234 
241  LinkedObject **index(void) const;
242 
248  LinkedObject *get(void);
249 
254  void add(OrderedObject *ordered);
255 
261  inline LinkedObject *getIndexed(unsigned index) const
262  {return LinkedObject::getIndexed((LinkedObject*)head, index);};
263 
268  inline LinkedObject *begin(void) const
269  {return (LinkedObject*)(head);};
270 
275  inline LinkedObject *end(void) const
276  {return (LinkedObject*)(tail);};
277 
282  inline LinkedObject *operator*() const
283  {return (LinkedObject*)(head);};
284 
289  OrderedIndex& operator=(const OrderedIndex& object)
290  {copy(object); return *this;}
291 
296  void operator*=(OrderedObject *object);
297 };
298 
305 class __EXPORT OrderedObject : public LinkedObject
306 {
307 protected:
308  friend class LinkedList;
309  friend class OrderedIndex;
310  friend class DLinkedObject;
311  friend class ObjectQueue;
312 
317  OrderedObject(OrderedIndex *index);
318 
322  OrderedObject();
323 
324 public:
329  void enlistTail(OrderedIndex *index);
330 
335  void enlistHead(OrderedIndex *index);
336 
342  virtual void enlist(OrderedIndex *index);
343 
348  void delist(OrderedIndex *index);
349 
354  inline OrderedObject *getNext(void) const
355  {return static_cast<OrderedObject *>(LinkedObject::getNext());};
356 };
357 
362 class __EXPORT DLinkedObject : public OrderedObject
363 {
364 public:
365  friend class ObjectQueue;
366 
370  DLinkedObject();
371 
372 protected:
376  void delist(void);
377 
378 private:
379  DLinkedObject *Prev;
380 };
381 
396 class __EXPORT NamedObject : public OrderedObject
397 {
398 protected:
399  char *Id;
400 
404  NamedObject();
405 
412  NamedObject(NamedObject **hash, char *name, unsigned size = 1);
413 
420  NamedObject(OrderedIndex *index, char *name);
421 
429  ~NamedObject();
430 
435  virtual void clearId(void);
436 
437 public:
444  void add(NamedObject **hash, char *name, unsigned size = 1);
445 
451  static void purge(NamedObject **hash, unsigned size);
452 
461  static NamedObject **index(NamedObject **hash, unsigned size);
462 
468  static unsigned count(NamedObject **hash, unsigned size);
469 
477  static NamedObject *find(NamedObject *root, const char *name);
478 
485  static NamedObject *remove(NamedObject **root, const char *name);
486 
494  static NamedObject *map(NamedObject **hash, const char *name, unsigned size);
495 
503  static NamedObject *remove(NamedObject **hash, const char *name, unsigned size);
504 
512  static NamedObject *skip(NamedObject **hash, NamedObject *current, unsigned size);
513 
519  static unsigned keyindex(const char *name, unsigned size);
520 
528  static NamedObject **sort(NamedObject **list, size_t count = 0);
529 
534  inline NamedObject *getNext(void) const
535  {return static_cast<NamedObject*>(LinkedObject::getNext());};
536 
541  inline char *getId(void) const
542  {return Id;};
543 
551  virtual int compare(const char *name) const;
552 
558  inline bool equal(const char *name) const
559  {return (compare(name) == 0);};
560 
566  inline bool operator==(const char *name) const
567  {return compare(name) == 0;};
568 
574  inline bool operator!=(const char *name) const
575  {return compare(name) != 0;};
576 };
577 
585 class __EXPORT NamedTree : public NamedObject
586 {
587 protected:
588  NamedTree *Parent;
589  OrderedIndex Child;
590 
595  NamedTree(char *name = NULL);
596 
602  NamedTree(NamedTree *parent, char *name);
603 
608  NamedTree(const NamedTree& source);
609 
615  virtual ~NamedTree();
616 
622  void purge(void);
623 
624 public:
633  NamedTree *find(const char *name) const;
634 
645  NamedTree *path(const char *path) const;
646 
654  NamedTree *leaf(const char *name) const;
655 
661  NamedTree *getChild(const char *name) const;
662 
669  NamedTree *getLeaf(const char *name) const;
670 
677  inline NamedTree *getFirst(void) const
678  {return static_cast<NamedTree *>(Child.begin());};
679 
684  inline NamedTree *getParent(void) const
685  {return Parent;};
686 
692  inline NamedTree *getIndexed(unsigned index) const
693  {return static_cast<NamedTree *>(Child.getIndexed(index));};
694 
699  inline OrderedIndex *getIndex(void) const
700  {return const_cast<OrderedIndex*>(&Child);};
701 
706  inline operator bool() const
707  {return (Id != NULL);};
708 
713  inline bool operator!() const
714  {return (Id == NULL);};
715 
721  void setId(char *name);
722 
727  void remove(void);
728 
733  inline bool is_leaf(void) const
734  {return (Child.begin() == NULL);};
735 
740  inline bool is_root(void) const
741  {return (Parent == NULL);};
742 
747  void relistTail(NamedTree *trunk);
748 
753  void relistHead(NamedTree *trunk);
754 
759  inline void relist(NamedTree *trunk = NULL)
760  {relistTail(trunk);};
761 };
762 
769 class __EXPORT LinkedList : public OrderedObject
770 {
771 protected:
772  friend class ObjectQueue;
773 
774  LinkedList *Prev;
775  OrderedIndex *Root;
776 
781  LinkedList(OrderedIndex *index);
782 
786  LinkedList();
787 
792  virtual ~LinkedList();
793 
794 public:
798  void delist(void);
799 
805  void enlistHead(OrderedIndex *index);
806 
812  void enlistTail(OrderedIndex *index);
813 
819  void enlist(OrderedIndex *index);
820 
825  inline bool is_head(void) const
826  {return Root->head == (OrderedObject *)this;};
827 
832  inline bool is_tail(void) const
833  {return Root->tail == (OrderedObject *)this;};
834 
839  inline LinkedList *getPrev(void) const
840  {return Prev;};
841 
846  inline LinkedList *getNext(void) const
847  {return static_cast<LinkedList*>(LinkedObject::getNext());};
848 
853  void insertTail(LinkedList *object);
854 
859  void insertHead(LinkedList *object);
860 
865  virtual void insert(LinkedList *object);
866 
871  inline void operator+=(LinkedList *object)
872  {insertTail(object);};
873 
878  inline void operator-=(LinkedList *object)
879  {insertHead(object);};
880 
885  inline void operator*=(LinkedList *object)
886  {insert(object);};
887 };
888 
894 class __EXPORT ObjectQueue : public OrderedIndex
895 {
896 public:
900  ObjectQueue();
901 
906  void add(DLinkedObject *object);
907 
912  void push(DLinkedObject *object);
913 
918  DLinkedObject *pull(void);
919 
924  DLinkedObject *pop(void);
925 };
926 
927 class __EXPORT ObjectStack
928 {
929 protected:
930  LinkedObject *root;
931 
932 public:
936  ObjectStack();
937 
942  ObjectStack(LinkedObject *list);
943 
948  void push(LinkedObject *object);
949 
954  LinkedObject *pull(void);
955 
960  inline LinkedObject *pop(void)
961  {return ObjectStack::pull();};
962 };
963 
964 
970 class __EXPORT MultiMap : public ReusableObject
971 {
972 private:
973  typedef struct {
974  const char *key;
975  size_t keysize;
976  MultiMap *next;
977  MultiMap **root;
978  } link_t;
979 
980  unsigned paths;
981  link_t *links;
982 
983 protected:
988  MultiMap(unsigned count);
989 
993  virtual ~MultiMap();
994 
1002  virtual bool equal(unsigned path, caddr_t key, size_t size) const;
1003 
1004 public:
1010  void enlist(unsigned path, MultiMap **root);
1011 
1020  void enlist(unsigned path, MultiMap **index, caddr_t key, unsigned size, size_t keysize = 0);
1021 
1026  void delist(unsigned path);
1027 
1032  MultiMap *next(unsigned path) const;
1033 
1041  static unsigned keyindex(caddr_t key, unsigned max, size_t size = 0);
1042 
1052  static MultiMap *find(unsigned path, MultiMap **index, caddr_t key, unsigned max, size_t size = 0);
1053 };
1054 
1062 template <typename T, class O=NamedObject>
1063 class named_value : public object_value<T, O>
1064 {
1065 public:
1071  inline named_value(LinkedObject **root, char *name)
1072  {LinkedObject::enlist(root); O::id = name;};
1073 
1078  inline void operator=(const T& typed_value)
1079  {this->set(typed_value);};
1080 
1087  inline static named_value find(named_value *first, const char *name)
1088  {return static_cast<named_value *>(NamedObject::find(first, name));};
1089 };
1090 
1099 template <typename T, class O=OrderedObject>
1100 class linked_value : public object_value<T, O>
1101 {
1102 public:
1106  inline linked_value() {};
1107 
1113  {LinkedObject::enlist(root);};
1114 
1120  {O::enlist(index);};
1121 
1127  inline linked_value(LinkedObject **root, const T& typed_value)
1128  {LinkedObject::enlist(root); this->set(typed_value);};
1129 
1135  inline linked_value(OrderedIndex *index, const T& typed_value)
1136  {O::enlist(index); this->set(typed_value);};
1137 
1142  inline void operator=(const T& typed_value)
1143  {this->set(typed_value);};
1144 };
1145 
1151 template <class T>
1152 class objstack : public ObjectStack
1153 {
1154 public:
1158  inline objstack() : ObjectStack() {}
1159 
1163  inline objstack(T *list) : ObjectStack(list) {}
1164 
1169  inline void push(T *object)
1170  {ObjectStack::push(object);}
1171 
1176  inline void add(T *object)
1177  {ObjectStack::push(object);}
1178 
1183  inline T *pull(void)
1184  {return (T *)ObjectStack::pull();}
1185 
1190  inline T *pop(void)
1191  {return (T *)ObjectStack::pull();}
1192 };
1193 
1200 template <class T>
1201 class objfifo : public OrderedIndex
1202 {
1203 public:
1207  inline objfifo() : OrderedIndex() {}
1208 
1213  inline void push(T *object)
1214  {OrderedIndex::add((OrderedObject *)object);}
1215 
1220  inline void add(T *object)
1221  {OrderedIndex::add((OrderedObject *)object);}
1222 
1227  inline T *pull(void)
1228  {return (T *)OrderedIndex::get();}
1229 
1234  inline T *pop(void)
1235  {return (T *)OrderedIndex::get();}
1236 };
1237 
1243 template <class T>
1244 class objqueue : public ObjectQueue
1245 {
1246 public:
1250  inline objqueue() : ObjectQueue() {}
1251 
1256  inline void push(T *object)
1257  {ObjectQueue::push((DLinkedObject *)object);}
1258 
1263  inline void add(T *object)
1264  {ObjectQueue::add((DLinkedObject *)object);}
1265 
1270  inline T *pull(void)
1271  {return (T *)ObjectQueue::pull();}
1272 
1277  inline T *pop(void)
1278  {return (T *)ObjectQueue::pop();}
1279 };
1280 
1287 template <class T>
1289 {
1290 private:
1291  T *ptr;
1292 
1293 public:
1299  {ptr = pointer;};
1300 
1306  {ptr = pointer.ptr;};
1307 
1313  {ptr = static_cast<T*>(pointer);};
1314 
1315  inline linked_pointer(const LinkedObject *pointer)
1316  {ptr = static_cast<T*>(pointer);};
1317 
1323  {ptr = static_cast<T*>(index->begin());};
1324 
1329  {ptr = NULL;};
1330 
1335  inline void operator=(T *pointer)
1336  {ptr = pointer;};
1337 
1342  inline void operator=(linked_pointer &pointer)
1343  {ptr = pointer.ptr;};
1344 
1349  inline void operator=(OrderedIndex *index)
1350  {ptr = static_cast<T*>(index->begin());};
1351 
1356  inline void operator=(LinkedObject *pointer)
1357  {ptr = static_cast<T*>(pointer);};
1358 
1363  inline T* operator->() const
1364  {return ptr;};
1365 
1370  inline T* operator*() const
1371  {return ptr;};
1372 
1377  inline operator T*() const
1378  {return ptr;};
1379 
1383  inline void prev(void)
1384  {ptr = static_cast<T*>(ptr->getPrev());};
1385 
1389  inline void next(void)
1390  {ptr = static_cast<T*>(ptr->getNext());};
1391 
1396  inline T *getNext(void) const
1397  {return static_cast<T*>(ptr->getNext());};
1398 
1404  inline T *getPrev(void) const
1405  {return static_cast<T*>(ptr->getPrev());};
1406 
1410  inline void operator++()
1411  {ptr = static_cast<T*>(ptr->getNext());};
1412 
1416  inline void operator--()
1417  {ptr = static_cast<T*>(ptr->getPrev());};
1418 
1423  inline bool is_next(void) const
1424  {return (ptr->getNext() != NULL);};
1425 
1430  inline bool is_prev(void) const
1431  {return (ptr->getPrev() != NULL);};
1432 
1437  inline operator bool() const
1438  {return (ptr != NULL);};
1439 
1444  inline bool operator!() const
1445  {return (ptr == NULL);};
1446 
1451  inline LinkedObject **root(void) const
1452  {T **r = &ptr; return (LinkedObject**)r;};
1453 };
1454 
1462 template <typename T, unsigned P>
1463 class multimap : public MultiMap
1464 {
1465 protected:
1466  T value;
1467 
1468 public:
1472  inline multimap() : MultiMap(P) {};
1473 
1477  inline ~multimap() {};
1478 
1483  inline T &get(void) const
1484  {return value;};
1485 
1491  inline multimap *next(unsigned path)
1492  {return static_cast<multimap*>(MultiMap::next(path));};
1493 
1498  inline T& operator*() const
1499  {return value;};
1500 
1505  inline void setPointer(const T pointer)
1506  {value = pointer;};
1507 
1512  inline void set(const T &reference)
1513  {value = reference;};
1514 
1519  inline void operator=(const T& data)
1520  {value = data;};
1521 
1531  inline static multimap *find(unsigned path, MultiMap **index, caddr_t key, unsigned size, unsigned keysize = 0)
1532  {return static_cast<multimap*>(MultiMap::find(path, index, key, size, keysize));};
1533 };
1534 
1552 template <typename T>
1553 class treemap : public NamedTree
1554 {
1555 protected:
1556  T value;
1557 
1558 public:
1564  inline treemap(char *name = NULL) : NamedTree(name) {};
1565 
1570  inline treemap(const treemap& source) : NamedTree(source)
1571  {value = source.value;};
1572 
1578  inline treemap(treemap *parent, char *name) : NamedTree(parent, name) {};
1579 
1586  inline treemap(treemap *parent, char *name, T& reference) :
1587  NamedTree(parent, name) {value = reference;};
1588 
1593  inline const T& get(void) const
1594  {return value;};
1595 
1600  inline const T& operator*() const
1601  {return value;};
1602 
1608  static inline T getPointer(treemap *node)
1609  {return (node == NULL) ? NULL : node->value;};
1610 
1615  inline bool is_attribute(void) const
1616  {return (!Child.begin() && value != NULL);};
1617 
1622  inline const T getPointer(void) const
1623  {return value;};
1624 
1629  inline const T& getData(void) const
1630  {return value;};
1631 
1636  inline void setPointer(const T pointer)
1637  {value = pointer;};
1638 
1643  inline void set(const T& reference)
1644  {value = reference;};
1645 
1650  inline void operator=(const T& data)
1651  {value = data;};
1652 
1658  inline treemap *getIndexed(unsigned index) const
1659  {return static_cast<treemap*>(Child.getIndexed(index));};
1660 
1665  inline treemap *getParent(void) const
1666  {return static_cast<treemap*>(Parent);};
1667 
1674  inline treemap *getChild(const char *name) const
1675  {return static_cast<treemap*>(NamedTree::getChild(name));};
1676 
1683  inline treemap *getLeaf(const char *name) const
1684  {return static_cast<treemap*>(NamedTree::getLeaf(name));};
1685 
1693  inline T getValue(const char *name) const
1694  {return getPointer(getLeaf(name));};
1695 
1702  inline treemap *find(const char *name) const
1703  {return static_cast<treemap*>(NamedTree::find(name));};
1704 
1711  inline treemap *path(const char *path) const
1712  {return static_cast<treemap*>(NamedTree::path(path));};
1713 
1720  inline treemap *leaf(const char *name) const
1721  {return static_cast<treemap*>(NamedTree::leaf(name));};
1722 
1727  inline treemap *getFirst(void) const
1728  {return static_cast<treemap*>(NamedTree::getFirst());};
1729 };
1730 
1738 template <class T, unsigned M = 177>
1739 class keymap
1740 {
1741 private:
1742  NamedObject *idx[M];
1743 
1744 public:
1748  inline ~keymap()
1749  {NamedObject::purge(idx, M);};
1750 
1755  inline NamedObject **root(void) const
1756  {return idx;};
1757 
1762  inline unsigned limit(void) const
1763  {return M;};
1764 
1770  inline T *get(const char *name) const
1771  {return static_cast<T*>(NamedObject::map(idx, name, M));};
1772 
1778  inline T& operator[](const char *name) const
1779  {return static_cast<T*>(NamedObject::map(idx, name, M));};
1780 
1786  inline void add(const char *name, T& object)
1787  {object.NamedObject::add(idx, name, M);};
1788 
1794  inline void add(const char *name, T *object)
1795  {object->NamedObject::add(idx, name, M);};
1796 
1802  inline T *remove(const char *name)
1803  {return static_cast<T*>(NamedObject::remove(idx, name, M));};
1804 
1809  inline T *begin(void) const
1810  {return static_cast<T*>(NamedObject::skip(idx, NULL, M));};
1811 
1817  inline T *next(T *current) const
1818  {return static_cast<T*>(NamedObject::skip(idx, current, M));};
1819 
1824  inline unsigned count(void) const
1825  {return NamedObject::count(idx, M);};
1826 
1833  inline T **index(void) const
1834  {return NamedObject::index(idx, M);};
1835 
1842  inline T **sort(void) const
1843  {return NamedObject::sort(NamedObject::index(idx, M));};
1844 
1848  typedef linked_pointer<T> iterator;
1849 };
1850 
1857 template <class T>
1858 class keylist : public OrderedIndex
1859 {
1860 public:
1865  inline NamedObject **root(void)
1866  {return static_cast<NamedObject**>(&head);};
1867 
1873  inline T *begin(void)
1874  {return static_cast<T*>(head);};
1875 
1881  inline T *end(void)
1882  {return static_cast<T*>(tail);};
1883 
1890  inline T *create(const char *name)
1891  {return new T(this, name);};
1892 
1898  inline T *next(LinkedObject *current)
1899  {return static_cast<T*>(current->getNext());};
1900 
1906  inline T *find(const char *name)
1907  {return static_cast<T*>(NamedObject::find(begin(), name));};
1908 
1909  inline T *offset(unsigned offset)
1910  {return static_cast<T*>(OrderedIndex::find(offset));};
1911 
1917  inline T& operator[](unsigned offset)
1918  {return static_cast<T&>(OrderedIndex::find(offset));};
1919 
1920  inline T& operator[](const char *name)
1921  {return static_cast<T&>(NamedObject::find(begin(), name));};
1922 
1929  inline T **index(void)
1930  {return static_cast<T**>(OrderedIndex::index());};
1931 
1938  inline T **sort(void)
1939  {return static_cast<T**>(NamedObject::sort(index()));};
1940 
1944  typedef linked_pointer<T> iterator;
1945 };
1946 
1951 
1955 typedef ObjectStack objstack_t;
1956 
1961 
1966 
1967 END_NAMESPACE
1968 
1969 #endif