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 isMember(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 public:
189  OrderedIndex();
190 
194  virtual ~OrderedIndex();
195 
200  LinkedObject *find(unsigned offset) const;
201 
206  unsigned count(void) const;
207 
211  void purge(void);
212 
216  void reset(void);
217 
222  virtual void lock_index(void);
223 
228  virtual void unlock_index(void);
229 
236  LinkedObject **index(void) const;
237 
243  LinkedObject *get(void);
244 
249  void add(OrderedObject *ordered);
250 
256  inline LinkedObject *getIndexed(unsigned index) const
257  {return LinkedObject::getIndexed((LinkedObject*)head, index);};
258 
263  inline LinkedObject *begin(void) const
264  {return (LinkedObject*)(head);};
265 
270  inline LinkedObject *end(void) const
271  {return (LinkedObject*)(tail);};
272 
277  inline LinkedObject *operator*() const
278  {return (LinkedObject*)(head);};
279 
284  void operator*=(OrderedObject *object);
285 };
286 
293 class __EXPORT OrderedObject : public LinkedObject
294 {
295 protected:
296  friend class LinkedList;
297  friend class OrderedIndex;
298  friend class DLinkedObject;
299  friend class ObjectQueue;
300 
305  OrderedObject(OrderedIndex *index);
306 
310  OrderedObject();
311 
312 public:
317  void enlistTail(OrderedIndex *index);
318 
323  void enlistHead(OrderedIndex *index);
324 
330  virtual void enlist(OrderedIndex *index);
331 
336  void delist(OrderedIndex *index);
337 
342  inline OrderedObject *getNext(void) const
343  {return static_cast<OrderedObject *>(LinkedObject::getNext());};
344 };
345 
350 class __EXPORT DLinkedObject : public OrderedObject
351 {
352 public:
353  friend class ObjectQueue;
354 
358  DLinkedObject();
359 
360 protected:
364  void delist(void);
365 
366 private:
367  DLinkedObject *prev;
368 };
369 
384 class __EXPORT NamedObject : public OrderedObject
385 {
386 protected:
387  char *id;
388 
392  NamedObject();
393 
400  NamedObject(NamedObject **hash, char *name, unsigned size = 1);
401 
408  NamedObject(OrderedIndex *index, char *name);
409 
417  ~NamedObject();
418 
423  virtual void clearId(void);
424 
425 public:
432  void add(NamedObject **hash, char *name, unsigned size = 1);
433 
439  static void purge(NamedObject **hash, unsigned size);
440 
449  static NamedObject **index(NamedObject **hash, unsigned size);
450 
456  static unsigned count(NamedObject **hash, unsigned size);
457 
465  static NamedObject *find(NamedObject *root, const char *name);
466 
473  static NamedObject *remove(NamedObject **root, const char *name);
474 
482  static NamedObject *map(NamedObject **hash, const char *name, unsigned size);
483 
491  static NamedObject *remove(NamedObject **hash, const char *name, unsigned size);
492 
500  static NamedObject *skip(NamedObject **hash, NamedObject *current, unsigned size);
501 
507  static unsigned keyindex(const char *name, unsigned size);
508 
516  static NamedObject **sort(NamedObject **list, size_t count = 0);
517 
522  inline NamedObject *getNext(void) const
523  {return static_cast<NamedObject*>(LinkedObject::getNext());};
524 
529  inline char *getId(void) const
530  {return id;};
531 
539  virtual int compare(const char *name) const;
540 
546  inline bool equal(const char *name) const
547  {return (compare(name) == 0);};
548 
554  inline bool operator==(const char *name) const
555  {return compare(name) == 0;};
556 
562  inline bool operator!=(const char *name) const
563  {return compare(name) != 0;};
564 };
565 
573 class __EXPORT NamedTree : public NamedObject
574 {
575 protected:
576  NamedTree *parent;
577  OrderedIndex child;
578 
583  NamedTree(char *name = NULL);
584 
590  NamedTree(NamedTree *parent, char *name);
591 
596  NamedTree(const NamedTree& source);
597 
603  virtual ~NamedTree();
604 
610  void purge(void);
611 
612 public:
621  NamedTree *find(const char *name) const;
622 
633  NamedTree *path(const char *path) const;
634 
642  NamedTree *leaf(const char *name) const;
643 
649  NamedTree *getChild(const char *name) const;
650 
657  NamedTree *getLeaf(const char *name) const;
658 
665  inline NamedTree *getFirst(void) const
666  {return static_cast<NamedTree *>(child.begin());};
667 
672  inline NamedTree *getParent(void) const
673  {return parent;};
674 
680  inline NamedTree *getIndexed(unsigned index) const
681  {return static_cast<NamedTree *>(child.getIndexed(index));};
682 
687  inline OrderedIndex *getIndex(void) const
688  {return const_cast<OrderedIndex*>(&child);};
689 
694  inline operator bool() const
695  {return (id != NULL);};
696 
701  inline bool operator!() const
702  {return (id == NULL);};
703 
709  void setId(char *name);
710 
715  void remove(void);
716 
721  inline bool isLeaf(void) const
722  {return (child.begin() == NULL);};
723 
728  inline bool isRoot(void) const
729  {return (parent == NULL);};
730 
735  void relistTail(NamedTree *trunk);
736 
741  void relistHead(NamedTree *trunk);
742 
747  inline void relist(NamedTree *trunk = NULL)
748  {relistTail(trunk);};
749 };
750 
757 class __EXPORT LinkedList : public OrderedObject
758 {
759 protected:
760  friend class ObjectQueue;
761 
762  LinkedList *prev;
763  OrderedIndex *root;
764 
769  LinkedList(OrderedIndex *index);
770 
774  LinkedList();
775 
780  virtual ~LinkedList();
781 
782 public:
786  void delist(void);
787 
793  void enlistHead(OrderedIndex *index);
794 
800  void enlistTail(OrderedIndex *index);
801 
807  void enlist(OrderedIndex *index);
808 
813  inline bool isHead(void) const
814  {return root->head == (OrderedObject *)this;};
815 
820  inline bool isTail(void) const
821  {return root->tail == (OrderedObject *)this;};
822 
827  inline LinkedList *getPrev(void) const
828  {return prev;};
829 
834  inline LinkedList *getNext(void) const
835  {return static_cast<LinkedList*>(LinkedObject::getNext());};
836 
841  void insertTail(LinkedList *object);
842 
847  void insertHead(LinkedList *object);
848 
853  virtual void insert(LinkedList *object);
854 
859  inline void operator+=(LinkedList *object)
860  {insertTail(object);};
861 
866  inline void operator-=(LinkedList *object)
867  {insertHead(object);};
868 
873  inline void operator*=(LinkedList *object)
874  {insert(object);};
875 };
876 
882 class __EXPORT ObjectQueue : public OrderedIndex
883 {
884 public:
888  ObjectQueue();
889 
894  void add(DLinkedObject *object);
895 
900  void push(DLinkedObject *object);
901 
906  DLinkedObject *pull(void);
907 
912  DLinkedObject *pop(void);
913 };
914 
915 class __EXPORT ObjectStack
916 {
917 protected:
918  LinkedObject *root;
919 
920 public:
924  ObjectStack();
925 
930  ObjectStack(LinkedObject *list);
931 
936  void push(LinkedObject *object);
937 
942  LinkedObject *pull(void);
943 
948  inline LinkedObject *pop(void)
949  {return ObjectStack::pull();};
950 };
951 
952 
958 class __EXPORT MultiMap : public ReusableObject
959 {
960 private:
961  typedef struct {
962  const char *key;
963  size_t keysize;
964  MultiMap *next;
965  MultiMap **root;
966  } link_t;
967 
968  unsigned paths;
969  link_t *links;
970 
971 protected:
976  MultiMap(unsigned count);
977 
981  virtual ~MultiMap();
982 
990  virtual bool equal(unsigned path, caddr_t key, size_t size) const;
991 
992 public:
998  void enlist(unsigned path, MultiMap **root);
999 
1008  void enlist(unsigned path, MultiMap **index, caddr_t key, unsigned size, size_t keysize = 0);
1009 
1014  void delist(unsigned path);
1015 
1020  MultiMap *next(unsigned path) const;
1021 
1029  static unsigned keyindex(caddr_t key, unsigned max, size_t size = 0);
1030 
1040  static MultiMap *find(unsigned path, MultiMap **index, caddr_t key, unsigned max, size_t size = 0);
1041 };
1042 
1050 template <typename T, class O=NamedObject>
1051 class named_value : public object_value<T, O>
1052 {
1053 public:
1059  inline named_value(LinkedObject **root, char *name)
1060  {LinkedObject::enlist(root); O::id = name;};
1061 
1066  inline void operator=(const T& typed_value)
1067  {this->set(typed_value);};
1068 
1075  inline static named_value find(named_value *first, const char *name)
1076  {return static_cast<named_value *>(NamedObject::find(first, name));};
1077 };
1078 
1087 template <typename T, class O=OrderedObject>
1088 class linked_value : public object_value<T, O>
1089 {
1090 public:
1094  inline linked_value() {};
1095 
1101  {LinkedObject::enlist(root);};
1102 
1108  {O::enlist(index);};
1109 
1115  inline linked_value(LinkedObject **root, const T& typed_value)
1116  {LinkedObject::enlist(root); this->set(typed_value);};
1117 
1123  inline linked_value(OrderedIndex *index, const T& typed_value)
1124  {O::enlist(index); this->set(typed_value);};
1125 
1130  inline void operator=(const T& typed_value)
1131  {this->set(typed_value);};
1132 };
1133 
1139 template <class T>
1140 class objstack : public ObjectStack
1141 {
1142 public:
1146  inline objstack() : ObjectStack() {}
1147 
1151  inline objstack(T *list) : ObjectStack(list) {}
1152 
1157  inline void push(T *object)
1158  {ObjectStack::push(object);}
1159 
1164  inline void add(T *object)
1165  {ObjectStack::push(object);}
1166 
1171  inline T *pull(void)
1172  {return (T *)ObjectStack::pull();}
1173 
1178  inline T *pop(void)
1179  {return (T *)ObjectStack::pull();}
1180 };
1181 
1188 template <class T>
1189 class objfifo : public OrderedIndex
1190 {
1191 public:
1195  inline objfifo() : OrderedIndex() {}
1196 
1201  inline void push(T *object)
1202  {OrderedIndex::add((OrderedObject *)object);}
1203 
1208  inline void add(T *object)
1209  {OrderedIndex::add((OrderedObject *)object);}
1210 
1215  inline T *pull(void)
1216  {return (T *)OrderedIndex::get();}
1217 
1222  inline T *pop(void)
1223  {return (T *)OrderedIndex::get();}
1224 };
1225 
1231 template <class T>
1232 class objqueue : public ObjectQueue
1233 {
1234 public:
1238  inline objqueue() : ObjectQueue() {}
1239 
1244  inline void push(T *object)
1245  {ObjectQueue::push((DLinkedObject *)object);}
1246 
1251  inline void add(T *object)
1252  {ObjectQueue::add((DLinkedObject *)object);}
1253 
1258  inline T *pull(void)
1259  {return (T *)ObjectQueue::pull();}
1260 
1265  inline T *pop(void)
1266  {return (T *)ObjectQueue::pop();}
1267 };
1268 
1275 template <class T>
1277 {
1278 private:
1279  T *ptr;
1280 
1281 public:
1287  {ptr = pointer;};
1288 
1294  {ptr = pointer.ptr;};
1295 
1301  {ptr = static_cast<T*>(pointer);};
1302 
1308  {ptr = static_cast<T*>(index->begin());};
1309 
1314  {ptr = NULL;};
1315 
1320  inline void operator=(T *pointer)
1321  {ptr = pointer;};
1322 
1327  inline void operator=(linked_pointer &pointer)
1328  {ptr = pointer.ptr;};
1329 
1334  inline void operator=(OrderedIndex *index)
1335  {ptr = static_cast<T*>(index->begin());};
1336 
1341  inline void operator=(LinkedObject *pointer)
1342  {ptr = static_cast<T*>(pointer);};
1343 
1348  inline T* operator->() const
1349  {return ptr;};
1350 
1355  inline T* operator*() const
1356  {return ptr;};
1357 
1362  inline operator T*() const
1363  {return ptr;};
1364 
1368  inline void prev(void)
1369  {ptr = static_cast<T*>(ptr->getPrev());};
1370 
1374  inline void next(void)
1375  {ptr = static_cast<T*>(ptr->getNext());};
1376 
1381  inline T *getNext(void) const
1382  {return static_cast<T*>(ptr->getNext());};
1383 
1389  inline T *getPrev(void) const
1390  {return static_cast<T*>(ptr->getPrev());};
1391 
1395  inline void operator++()
1396  {ptr = static_cast<T*>(ptr->getNext());};
1397 
1401  inline void operator--()
1402  {ptr = static_cast<T*>(ptr->getPrev());};
1403 
1408  inline bool isNext(void) const
1409  {return (ptr->getNext() != NULL);};
1410 
1415  inline bool isPrev(void) const
1416  {return (ptr->getPrev() != NULL);};
1417 
1422  inline operator bool() const
1423  {return (ptr != NULL);};
1424 
1429  inline bool operator!() const
1430  {return (ptr == NULL);};
1431 
1436  inline LinkedObject **root(void) const
1437  {T **r = &ptr; return (LinkedObject**)r;};
1438 };
1439 
1447 template <typename T, unsigned P>
1448 class multimap : public MultiMap
1449 {
1450 protected:
1451  T value;
1452 
1453 public:
1457  inline multimap() : MultiMap(P) {};
1458 
1462  inline ~multimap() {};
1463 
1468  inline T &get(void) const
1469  {return value;};
1470 
1476  inline multimap *next(unsigned path)
1477  {return static_cast<multimap*>(MultiMap::next(path));};
1478 
1483  inline T& operator*() const
1484  {return value;};
1485 
1490  inline void setPointer(const T pointer)
1491  {value = pointer;};
1492 
1497  inline void set(const T &reference)
1498  {value = reference;};
1499 
1504  inline void operator=(const T& data)
1505  {value = data;};
1506 
1516  inline static multimap *find(unsigned path, MultiMap **index, caddr_t key, unsigned size, unsigned keysize = 0)
1517  {return static_cast<multimap*>(MultiMap::find(path, index, key, size, keysize));};
1518 };
1519 
1537 template <typename T>
1538 class treemap : public NamedTree
1539 {
1540 protected:
1541  T value;
1542 
1543 public:
1549  inline treemap(char *name = NULL) : NamedTree(name) {};
1550 
1555  inline treemap(const treemap& source) : NamedTree(source)
1556  {value = source.value;};
1557 
1563  inline treemap(treemap *parent, char *name) : NamedTree(parent, name) {};
1564 
1571  inline treemap(treemap *parent, char *name, T& reference) :
1572  NamedTree(parent, name) {value = reference;};
1573 
1578  inline const T& get(void) const
1579  {return value;};
1580 
1585  inline const T& operator*() const
1586  {return value;};
1587 
1593  static inline T getPointer(treemap *node)
1594  {return (node == NULL) ? NULL : node->value;};
1595 
1600  inline bool isAttribute(void) const
1601  {return (!child.begin() && value != NULL);};
1602 
1607  inline const T getPointer(void) const
1608  {return value;};
1609 
1614  inline const T& getData(void) const
1615  {return value;};
1616 
1621  inline void setPointer(const T pointer)
1622  {value = pointer;};
1623 
1628  inline void set(const T& reference)
1629  {value = reference;};
1630 
1635  inline void operator=(const T& data)
1636  {value = data;};
1637 
1643  inline treemap *getIndexed(unsigned index) const
1644  {return static_cast<treemap*>(child.getIndexed(index));};
1645 
1650  inline treemap *getParent(void) const
1651  {return static_cast<treemap*>(parent);};
1652 
1659  inline treemap *getChild(const char *name) const
1660  {return static_cast<treemap*>(NamedTree::getChild(name));};
1661 
1668  inline treemap *getLeaf(const char *name) const
1669  {return static_cast<treemap*>(NamedTree::getLeaf(name));};
1670 
1678  inline T getValue(const char *name) const
1679  {return getPointer(getLeaf(name));};
1680 
1687  inline treemap *find(const char *name) const
1688  {return static_cast<treemap*>(NamedTree::find(name));};
1689 
1696  inline treemap *path(const char *path) const
1697  {return static_cast<treemap*>(NamedTree::path(path));};
1698 
1705  inline treemap *leaf(const char *name) const
1706  {return static_cast<treemap*>(NamedTree::leaf(name));};
1707 
1712  inline treemap *getFirst(void) const
1713  {return static_cast<treemap*>(NamedTree::getFirst());};
1714 };
1715 
1723 template <class T, unsigned M = 177>
1724 class keymap
1725 {
1726 private:
1727  NamedObject *idx[M];
1728 
1729 public:
1733  inline ~keymap()
1734  {NamedObject::purge(idx, M);};
1735 
1740  inline NamedObject **root(void) const
1741  {return idx;};
1742 
1747  inline unsigned limit(void) const
1748  {return M;};
1749 
1755  inline T *get(const char *name) const
1756  {return static_cast<T*>(NamedObject::map(idx, name, M));};
1757 
1763  inline T& operator[](const char *name) const
1764  {return static_cast<T*>(NamedObject::map(idx, name, M));};
1765 
1771  inline void add(const char *name, T& object)
1772  {object.NamedObject::add(idx, name, M);};
1773 
1779  inline void add(const char *name, T *object)
1780  {object->NamedObject::add(idx, name, M);};
1781 
1787  inline T *remove(const char *name)
1788  {return static_cast<T*>(NamedObject::remove(idx, name, M));};
1789 
1794  inline T *begin(void) const
1795  {return static_cast<T*>(NamedObject::skip(idx, NULL, M));};
1796 
1802  inline T *next(T *current) const
1803  {return static_cast<T*>(NamedObject::skip(idx, current, M));};
1804 
1809  inline unsigned count(void) const
1810  {return NamedObject::count(idx, M);};
1811 
1818  inline T **index(void) const
1819  {return NamedObject::index(idx, M);};
1820 
1827  inline T **sort(void) const
1828  {return NamedObject::sort(NamedObject::index(idx, M));};
1829 };
1830 
1837 template <class T>
1838 class keylist : public OrderedIndex
1839 {
1840 public:
1845  inline NamedObject **root(void)
1846  {return static_cast<NamedObject*>(&head);};
1847 
1853  inline T *begin(void)
1854  {return static_cast<T*>(head);};
1855 
1861  inline T *end(void)
1862  {return static_cast<T*>(tail);};
1863 
1870  inline T *create(const char *name)
1871  {return new T(this, name);};
1872 
1878  inline T *next(LinkedObject *current)
1879  {return static_cast<T*>(current->getNext());};
1880 
1886  inline T *find(const char *name)
1887  {return static_cast<T*>(NamedObject::find(begin(), name));};
1888 
1889  inline T *offset(unsigned offset)
1890  {return static_cast<T*>(OrderedIndex::find(offset));};
1891 
1897  inline T& operator[](unsigned offset)
1898  {return static_cast<T&>(OrderedIndex::find(offset));};
1899 
1900  inline T& operator[](const char *name)
1901  {return static_cast<T&>(NamedObject::find(begin(), name));};
1902 
1909  inline T **index(void)
1910  {return static_cast<T**>(OrderedIndex::index());};
1911 
1918  inline T **sort(void)
1919  {return static_cast<T**>(NamedObject::sort(index()));};
1920 };
1921 
1927 inline void push(ObjectStack& stack, LinkedObject *object)
1928  {stack.push(object);}
1929 
1935 inline void add(ObjectStack& stack, LinkedObject *object)
1936  {stack.push(object);}
1937 
1943 inline LinkedObject *pop(ObjectStack& stack)
1944  {return stack.pull();}
1945 
1951 inline LinkedObject *pull(ObjectStack& stack)
1952  {return stack.pull();}
1953 
1959 inline void push(OrderedIndex& fifo, LinkedObject *object)
1960  {fifo.add((OrderedObject *)object);}
1961 
1967 inline void add(OrderedIndex& fifo, LinkedObject *object)
1968  {fifo.add((OrderedObject *)object);}
1969 
1976  {return fifo.get();}
1977 
1984  {return fifo.get();}
1985 
1991 inline void push(ObjectQueue& queue, DLinkedObject *object)
1992  {queue.add(object);}
1993 
1999 inline void add(ObjectQueue& queue, DLinkedObject *object)
2000  {queue.add(object);}
2001 
2008  {return (DLinkedObject *)queue.pop();}
2009 
2016  {return (DLinkedObject *)queue.pull();}
2017 
2022 
2026 typedef ObjectStack objstack_t;
2027 
2032 
2037 
2038 END_NAMESPACE
2039 
2040 #endif