UCommon
linked.h
Go to the documentation of this file.
1 // Copyright (C) 2006-2014 David Sugar, Tycho Softworks.
2 // Copyright (C) 2015 Cherokees of Idaho.
3 //
4 // This file is part of GNU uCommon C++.
5 //
6 // GNU uCommon C++ is free software: you can redistribute it and/or modify
7 // it under the terms of the GNU Lesser General Public License as published
8 // by the Free Software Foundation, either version 3 of the License, or
9 // (at your option) any later version.
10 //
11 // GNU uCommon C++ is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU Lesser General Public License for more details.
15 //
16 // You should have received a copy of the GNU Lesser General Public License
17 // along with GNU uCommon C++. If not, see <http://www.gnu.org/licenses/>.
18 
33 #ifndef _UCOMMON_LINKED_H_
34 #define _UCOMMON_LINKED_H_
35 
36 #ifndef _UCOMMON_CONFIG_H_
37 #include <ucommon/platform.h>
38 #endif
39 
40 #ifndef _UCOMMON_OBJECT_H_
41 #include <ucommon/object.h>
42 #endif
43 
44 #ifdef nil
45 #undef nil
46 #endif
47 
48 namespace ucommon {
49 
50 class OrderedObject;
51 
59 class __EXPORT LinkedObject : public ObjectProtocol
60 {
61 protected:
62  friend class OrderedIndex;
63  friend class LinkedRing;
64  friend class NamedObject;
65  friend class ObjectStack;
66 
67  LinkedObject *Next;
68 
73  LinkedObject(LinkedObject **root);
74 
80  LinkedObject();
81 
82 public:
83  static const LinkedObject *nil;
84  static const LinkedObject *inv;
86  virtual ~LinkedObject();
87 
91  virtual void release(void) __OVERRIDE;
92 
96  virtual void retain(void) __OVERRIDE;
97 
104  void enlist(LinkedObject **root);
105 
112  void delist(LinkedObject **root);
113 
118  bool is_member(LinkedObject *list) const;
119 
124  static void purge(LinkedObject *root);
125 
130  static unsigned count(const LinkedObject *root);
131 
138  static LinkedObject *getIndexed(LinkedObject *root, unsigned index);
139 
144  inline LinkedObject *getNext(void) const {
145  return Next;
146  }
147 };
148 
158 class __EXPORT ReusableObject : public LinkedObject
159 {
160  friend class ReusableAllocator;
161 
162 protected:
163  virtual void release(void) __OVERRIDE;
164 
165 public:
170  inline ReusableObject *getNext(void) {
171  return polypointer_cast<ReusableObject*>(LinkedObject::getNext());
172  }
173 };
174 
182 class __EXPORT OrderedIndex
183 {
184 protected:
185  friend class OrderedObject;
186  friend class DLinkedObject;
187  friend class LinkedList;
188  friend class NamedObject;
189 
190  OrderedObject *head, *tail;
191 
192 public:
193  void copy(const OrderedIndex& source);
194 
198  OrderedIndex();
199 
200  inline OrderedIndex(const OrderedIndex& source) {
201  copy(source);
202  }
203 
207  virtual ~OrderedIndex();
208 
213  LinkedObject *find(unsigned offset) const;
214 
219  unsigned count(void) const;
220 
224  void purge(void);
225 
229  void reset(void);
230 
235  virtual void lock_index(void);
236 
241  virtual void unlock_index(void);
242 
249  LinkedObject **index(void) const;
250 
256  LinkedObject *get(void);
257 
262  void add(OrderedObject *ordered);
263 
269  inline LinkedObject *getIndexed(unsigned index) const {
270  return LinkedObject::getIndexed(polystatic_cast<LinkedObject*>(head), index);
271  }
272 
277  inline LinkedObject *begin(void) const {
278  return polystatic_cast<LinkedObject*>(head);
279  }
280 
285  inline LinkedObject *end(void) const {
286  return polystatic_cast<LinkedObject*>(tail);
287  }
288 
293  inline LinkedObject *operator*() const {
294  return polystatic_cast<LinkedObject*>(head);
295  }
296 
302  copy(object);
303  return *this;
304  }
305 
310  void operator*=(OrderedObject *object);
311 };
312 
319 class __EXPORT OrderedObject : public LinkedObject
320 {
321 protected:
322  friend class LinkedList;
323  friend class OrderedIndex;
324  friend class DLinkedObject;
325  friend class ObjectQueue;
326 
331  OrderedObject(OrderedIndex *index);
332 
336  OrderedObject();
337 
338 public:
343  void enlistTail(OrderedIndex *index);
344 
349  void enlistHead(OrderedIndex *index);
350 
356  virtual void enlist(OrderedIndex *index);
357 
362  void delist(OrderedIndex *index);
363 
368  inline OrderedObject *getNext(void) const {
369  return static_cast<OrderedObject *>(LinkedObject::getNext());
370  }
371 };
372 
377 class __EXPORT DLinkedObject : public OrderedObject
378 {
379 public:
380  friend class ObjectQueue;
381 
385  DLinkedObject();
386 
387 protected:
391  void delist(void);
392 
393 private:
394  DLinkedObject *Prev;
395 };
396 
411 class __EXPORT NamedObject : public OrderedObject
412 {
413 protected:
414  char *Id;
415 
419  NamedObject();
420 
427  NamedObject(NamedObject **hash, char *name, unsigned size = 1);
428 
435  NamedObject(OrderedIndex *index, char *name);
436 
444  ~NamedObject();
445 
450  virtual void clearId(void);
451 
452 public:
459  void add(NamedObject **hash, char *name, unsigned size = 1);
460 
466  static void purge(NamedObject **hash, unsigned size);
467 
476  static NamedObject **index(NamedObject **hash, unsigned size);
477 
483  static unsigned count(NamedObject **hash, unsigned size);
484 
492  static NamedObject *find(NamedObject *root, const char *name);
493 
500  static NamedObject *remove(NamedObject **root, const char *name);
501 
509  static NamedObject *map(NamedObject **hash, const char *name, unsigned size);
510 
518  static NamedObject *remove(NamedObject **hash, const char *name, unsigned size);
519 
527  static NamedObject *skip(NamedObject **hash, NamedObject *current, unsigned size);
528 
534  static unsigned keyindex(const char *name, unsigned size);
535 
543  static NamedObject **sort(NamedObject **list, size_t count = 0);
544 
549  inline NamedObject *getNext(void) const {
550  return static_cast<NamedObject*>(LinkedObject::getNext());
551  }
552 
557  inline char *getId(void) const {
558  return Id;
559  };
560 
568  virtual int compare(const char *name) const;
569 
575  inline bool equal(const char *name) const {
576  return (compare(name) == 0);
577  }
578 
584  inline bool operator==(const char *name) const {
585  return compare(name) == 0;
586  }
587 
593  inline bool operator!=(const char *name) const {
594  return compare(name) != 0;
595  }
596 };
597 
605 class __EXPORT NamedTree : public NamedObject
606 {
607 protected:
608  NamedTree *Parent;
609  OrderedIndex Child;
610 
615  NamedTree(char *name = NULL);
616 
622  NamedTree(NamedTree *parent, char *name);
623 
628  NamedTree(const NamedTree& source);
629 
635  virtual ~NamedTree();
636 
642  void purge(void);
643 
644 public:
653  NamedTree *find(const char *name) const;
654 
665  NamedTree *path(const char *path) const;
666 
674  NamedTree *leaf(const char *name) const;
675 
681  NamedTree *getChild(const char *name) const;
682 
689  NamedTree *getLeaf(const char *name) const;
690 
697  inline NamedTree *getFirst(void) const {
698  return static_cast<NamedTree *>(Child.begin());
699  }
700 
705  inline NamedTree *getParent(void) const {
706  return static_cast<NamedTree *>(Parent);
707  };
708 
714  inline NamedTree *getIndexed(unsigned index) const {
715  return static_cast<NamedTree *>(Child.getIndexed(index));
716  }
717 
722  inline OrderedIndex *getIndex(void) const {
723  return const_cast<OrderedIndex*>(&Child);
724  }
725 
730  inline operator bool() const {
731  return (Id != NULL);
732  }
733 
738  inline bool operator!() const {
739  return (Id == NULL);
740  }
741 
747  void setId(char *name);
748 
753  void remove(void);
754 
759  inline bool is_leaf(void) const {
760  return (Child.begin() == NULL);
761  }
762 
767  inline bool is_root(void) const {
768  return (Parent == NULL);
769  }
770 
775  void relistTail(NamedTree *trunk);
776 
781  void relistHead(NamedTree *trunk);
782 
787  inline void relist(NamedTree *trunk = NULL) {
788  relistTail(trunk);
789  }
790 };
791 
798 class __EXPORT LinkedList : public OrderedObject
799 {
800 protected:
801  friend class ObjectQueue;
802 
803  LinkedList *Prev;
804  OrderedIndex *Root;
805 
810  LinkedList(OrderedIndex *index);
811 
815  LinkedList();
816 
821  virtual ~LinkedList();
822 
823 public:
827  void delist(void);
828 
834  void enlistHead(OrderedIndex *index);
835 
841  void enlistTail(OrderedIndex *index);
842 
848  void enlist(OrderedIndex *index);
849 
854  inline bool is_head(void) const {
855  return polypointer_cast<LinkedList *>(Root->head) == this;
856  }
857 
862  inline bool is_tail(void) const {
863  return polypointer_cast<LinkedList *>(Root->tail) == this;
864  }
865 
870  inline LinkedList *getPrev(void) const {
871  return static_cast<LinkedList*>(Prev);
872  }
873 
878  inline LinkedList *getNext(void) const {
879  return static_cast<LinkedList*>(LinkedObject::getNext());
880  }
881 
886  void insertTail(LinkedList *object);
887 
892  void insertHead(LinkedList *object);
893 
898  virtual void insert(LinkedList *object);
899 
904  inline void operator+=(LinkedList *object) {
905  insertTail(object);
906  }
907 
912  inline void operator-=(LinkedList *object) {
913  insertHead(object);
914  }
915 
920  inline void operator*=(LinkedList *object) {
921  insert(object);
922  }
923 };
924 
930 class __EXPORT ObjectQueue : public OrderedIndex
931 {
932 public:
936  ObjectQueue();
937 
942  void add(DLinkedObject *object);
943 
948  void push(DLinkedObject *object);
949 
954  DLinkedObject *pull(void);
955 
960  DLinkedObject *pop(void);
961 };
962 
963 class __EXPORT ObjectStack
964 {
965 protected:
966  LinkedObject *root;
967 
968 public:
972  ObjectStack();
973 
978  ObjectStack(LinkedObject *list);
979 
984  void push(LinkedObject *object);
985 
990  LinkedObject *pull(void);
991 
996  inline LinkedObject *pop(void) {
997  return ObjectStack::pull();
998  }
999 };
1000 
1001 
1007 class __EXPORT MultiMap : public ReusableObject
1008 {
1009 private:
1010  typedef struct {
1011  const char *key;
1012  size_t keysize;
1013  MultiMap *next;
1014  MultiMap **root;
1015  } link_t;
1016 
1017  unsigned paths;
1018  link_t *links;
1019 
1020 protected:
1025  MultiMap(unsigned count);
1026 
1030  virtual ~MultiMap();
1031 
1039  virtual bool equal(unsigned path, caddr_t key, size_t size) const;
1040 
1041 public:
1047  void enlist(unsigned path, MultiMap **root);
1048 
1057  void enlist(unsigned path, MultiMap **index, caddr_t key, unsigned size, size_t keysize = 0);
1058 
1063  void delist(unsigned path);
1064 
1069  MultiMap *next(unsigned path) const;
1070 
1078  static unsigned keyindex(caddr_t key, unsigned max, size_t size = 0);
1079 
1089  static MultiMap *find(unsigned path, MultiMap **index, caddr_t key, unsigned max, size_t size = 0);
1090 };
1091 
1099 template <typename T, class O=NamedObject>
1100 class named_value : public object_value<T, O>
1101 {
1102 public:
1108  inline named_value(LinkedObject **root, char *name) {
1109  LinkedObject::enlist(root);
1110  O::id = name;
1111  }
1112 
1117  inline void operator=(const T& typed_value) {
1118  this->set(typed_value);
1119  }
1120 
1127  inline static named_value find(named_value *first, const char *name) {
1128  return static_cast<named_value *>(NamedObject::find(first, name));
1129  }
1130 };
1131 
1140 template <typename T, class O=OrderedObject>
1141 class linked_value : public object_value<T, O>
1142 {
1143 public:
1147  inline linked_value() {}
1148 
1153  inline linked_value(LinkedObject **root) {
1154  LinkedObject::enlist(root);
1155  }
1156 
1161  inline linked_value(OrderedIndex *index) {
1162  O::enlist(index);
1163  }
1164 
1170  inline linked_value(LinkedObject **root, const T& typed_value) {
1171  LinkedObject::enlist(root);
1172  this->set(typed_value);
1173  }
1174 
1180  inline linked_value(OrderedIndex *index, const T& typed_value) {
1181  O::enlist(index);
1182  this->set(typed_value);
1183  }
1184 
1189  inline void operator=(const T& typed_value) {
1190  this->set(typed_value);
1191  }
1192 };
1193 
1199 template <class T>
1200 class objstack : public ObjectStack
1201 {
1202 public:
1206  inline objstack() : ObjectStack() {}
1207 
1211  inline objstack(T *list) : ObjectStack(list) {}
1212 
1217  inline void push(T *object) {
1218  ObjectStack::push(polypointer_cast<LinkedObject*>(object));
1219  }
1220 
1225  inline void add(T *object) {
1226  ObjectStack::push(polypointer_cast<LinkedObject*>(object));
1227  }
1228 
1233  inline T *pull(void) {
1234  return static_cast<T *>(ObjectStack::pull());
1235  }
1236 
1241  inline T *pop(void) {
1242  return static_cast<T *>(ObjectStack::pull());
1243  }
1244 };
1245 
1252 template <class T>
1253 class objfifo : public OrderedIndex
1254 {
1255 public:
1259  inline objfifo() : OrderedIndex() {}
1260 
1265  inline void push(T *object) {
1266  OrderedIndex::add(polypointer_cast<OrderedObject *>(object));
1267  }
1268 
1273  inline void add(T *object) {
1274  OrderedIndex::add(polypointer_cast<OrderedObject *>(object));
1275  }
1276 
1281  inline T *pull(void) {
1282  return static_cast<T *>(OrderedIndex::get());
1283  }
1284 
1289  inline T *pop(void) {
1290  return static_cast<T *>(OrderedIndex::get());
1291  }
1292 };
1293 
1299 template <class T>
1300 class objqueue : public ObjectQueue
1301 {
1302 public:
1306  inline objqueue() : ObjectQueue() {}
1307 
1312  inline void push(T *object) {
1313  ObjectQueue::push(polypointer_cast<DLinkedObject *>(object));
1314  }
1315 
1320  inline void add(T *object) {
1321  ObjectQueue::add(polypointer_cast<DLinkedObject *>(object));
1322  }
1323 
1328  inline T *pull(void) {
1329  return static_cast<T *>(ObjectQueue::pull());
1330  }
1331 
1336  inline T *pop(void) {
1337  return static_cast<T *>(ObjectQueue::pop());
1338  }
1339 };
1340 
1347 template <class T>
1349 {
1350 private:
1351  T *ptr;
1352 
1353 public:
1359  ptr = pointer;
1360  }
1361 
1367  ptr = pointer.ptr;
1368  }
1369 
1375  ptr = static_cast<T*>(pointer);
1376  }
1377 
1378  inline linked_pointer(const LinkedObject *pointer) {
1379  ptr = static_cast<T*>(pointer);
1380  }
1381 
1386  inline linked_pointer(OrderedIndex *index) {
1387  ptr = static_cast<T*>(index->begin());
1388  }
1389 
1393  inline linked_pointer() {
1394  ptr = NULL;
1395  }
1396 
1401  inline void operator=(T *pointer) {
1402  ptr = pointer;
1403  }
1404 
1410  ptr = pointer.ptr;
1411  }
1412 
1417  inline void operator=(OrderedIndex *index) {
1418  ptr = static_cast<T*>(index->begin());
1419  }
1420 
1426  ptr = static_cast<T*>(pointer);
1427  }
1428 
1433  inline T* operator->() const {
1434  return ptr;
1435  }
1436 
1441  inline T* operator*() const {
1442  return ptr;
1443  }
1444 
1449  inline operator T*() const {
1450  return ptr;
1451  }
1452 
1456  inline void prev(void) {
1457  ptr = static_cast<T*>(ptr->getPrev());
1458  }
1459 
1463  inline void next(void) {
1464  ptr = static_cast<T*>(ptr->getNext());
1465  }
1466 
1471  inline T *getNext(void) const {
1472  return static_cast<T*>(ptr->getNext());
1473  }
1474 
1480  inline T *getPrev(void) const {
1481  return static_cast<T*>(ptr->getPrev());
1482  }
1483 
1487  inline void operator++() {
1488  ptr = static_cast<T*>(ptr->getNext());
1489  }
1490 
1494  inline void operator--() {
1495  ptr = static_cast<T*>(ptr->getPrev());
1496  }
1497 
1502  inline bool is_next(void) const {
1503  return (ptr->getNext() != NULL);
1504  }
1505 
1510  inline bool is_prev(void) const {
1511  return (ptr->getPrev() != NULL);
1512  }
1513 
1518  inline operator bool() const {
1519  return (ptr != NULL);
1520  }
1521 
1526  inline bool operator!() const {
1527  return (ptr == NULL);
1528  }
1529 
1530  inline bool is() const {
1531  return (ptr != NULL);
1532  }
1533 
1538  inline LinkedObject **root(void) const {
1539  T **r = &ptr;
1540  return static_cast<LinkedObject**>(r);
1541  }
1542 };
1543 
1551 template <typename T, unsigned P>
1552 class multimap : public MultiMap
1553 {
1554 protected:
1555  T value;
1556 
1557 public:
1561  inline multimap() : MultiMap(P) {}
1562 
1566  inline ~multimap() {}
1567 
1572  inline T &get(void) const {
1573  return value;
1574  }
1575 
1581  inline multimap *next(unsigned path) {
1582  return static_cast<multimap*>(MultiMap::next(path));
1583  }
1584 
1589  inline T& operator*() const {
1590  return value;
1591  }
1592 
1597  inline void setPointer(const T pointer) {
1598  value = pointer;
1599  }
1600 
1605  inline void set(const T &reference) {
1606  value = reference;
1607  }
1608 
1613  inline void operator=(const T& data) {
1614  value = data;
1615  }
1616 
1626  inline static multimap *find(unsigned path, MultiMap **index, caddr_t key, unsigned size, unsigned keysize = 0) {
1627  return static_cast<multimap*>(MultiMap::find(path, index, key, size, keysize));
1628  }
1629 };
1630 
1648 template <typename T>
1649 class treemap : public NamedTree
1650 {
1651 protected:
1652  T value;
1653 
1654 public:
1660  inline treemap(char *name = NULL) : NamedTree(name) {}
1661 
1666  inline treemap(const treemap& source) : NamedTree(source) {
1667  value = source.value;
1668  };
1669 
1675  inline treemap(treemap *parent, char *name) : NamedTree(parent, name) {}
1676 
1683  inline treemap(treemap *parent, char *name, T& reference) : NamedTree(parent, name) {
1684  value = reference;
1685  }
1686 
1691  inline const T& get(void) const {
1692  return value;
1693  }
1694 
1699  inline const T& operator*() const {
1700  return value;
1701  }
1702 
1708  static inline T getPointer(treemap *node) {
1709  return (node == NULL) ? NULL : node->value;
1710  }
1711 
1716  inline bool is_attribute(void) const {
1717  return (!Child.begin() && value != NULL);
1718  }
1719 
1724  inline const T getPointer(void) const {
1725  return value;
1726  }
1727 
1732  inline const T& getData(void) const {
1733  return value;
1734  }
1735 
1740  inline void setPointer(const T pointer) {
1741  value = pointer;
1742  }
1743 
1748  inline void set(const T& reference) {
1749  value = reference;
1750  }
1751 
1756  inline void operator=(const T& data) {
1757  value = data;
1758  }
1759 
1765  inline treemap *getIndexed(unsigned index) const {
1766  return static_cast<treemap*>(Child.getIndexed(index));
1767  }
1768 
1773  inline treemap *getParent(void) const {
1774  return static_cast<treemap*>(Parent);
1775  }
1776 
1783  inline treemap *getChild(const char *name) const {
1784  return static_cast<treemap*>(NamedTree::getChild(name));
1785  }
1786 
1793  inline treemap *getLeaf(const char *name) const {
1794  return static_cast<treemap*>(NamedTree::getLeaf(name));
1795  }
1796 
1804  inline T getValue(const char *name) const {
1805  return getPointer(getLeaf(name));
1806  }
1807 
1814  inline treemap *find(const char *name) const {
1815  return static_cast<treemap*>(NamedTree::find(name));
1816  }
1817 
1824  inline treemap *path(const char *path) const {
1825  return static_cast<treemap*>(NamedTree::path(path));
1826  }
1827 
1834  inline treemap *leaf(const char *name) const {
1835  return static_cast<treemap*>(NamedTree::leaf(name));
1836  }
1837 
1842  inline treemap *getFirst(void) const {
1843  return static_cast<treemap*>(NamedTree::getFirst());
1844  }
1845 };
1846 
1854 template <class T, unsigned M = 177>
1855 class keymap
1856 {
1857 private:
1858  NamedObject *idx[M];
1859 
1860 public:
1864  inline ~keymap() {
1865  NamedObject::purge(idx, M);
1866  }
1867 
1872  inline NamedObject **root(void) const {
1873  return idx;
1874  }
1875 
1880  inline unsigned limit(void) const {
1881  return M;
1882  }
1883 
1889  inline T *get(const char *name) const {
1890  return static_cast<T*>(NamedObject::map(idx, name, M));
1891  }
1892 
1898  inline T& operator[](const char *name) const {
1899  return static_cast<T*>(NamedObject::map(idx, name, M));
1900  }
1901 
1907  inline void add(const char *name, T& object) {
1908  object.NamedObject::add(idx, name, M);
1909  }
1910 
1916  inline void add(const char *name, T *object) {
1917  object->NamedObject::add(idx, name, M);
1918  }
1919 
1925  inline T *remove(const char *name) {
1926  return static_cast<T*>(NamedObject::remove(idx, name, M));
1927  }
1928 
1933  inline T *begin(void) const {
1934  return static_cast<T*>(NamedObject::skip(idx, NULL, M));
1935  }
1936 
1942  inline T *next(T *current) const {
1943  return static_cast<T*>(NamedObject::skip(idx, current, M));
1944  }
1945 
1950  inline unsigned count(void) const {
1951  return NamedObject::count(idx, M);
1952  }
1953 
1960  inline T **index(void) const {
1961  return NamedObject::index(idx, M);
1962  }
1963 
1970  inline T **sort(void) const {
1971  return NamedObject::sort(NamedObject::index(idx, M));
1972  }
1973 
1978 };
1979 
1986 template <class T>
1987 class keylist : public OrderedIndex
1988 {
1989 public:
1994  inline NamedObject **root(void) {
1995  return static_cast<NamedObject**>(&head);
1996  }
1997 
2003  inline T *begin(void) {
2004  return static_cast<T*>(head);
2005  }
2006 
2012  inline T *end(void) {
2013  return static_cast<T*>(tail);
2014  }
2015 
2022  inline T *create(const char *name) {
2023  return new T(this, name);
2024  }
2025 
2031  inline T *next(LinkedObject *current) {
2032  return static_cast<T*>(current->getNext());
2033  }
2034 
2040  inline T *find(const char *name) {
2041  return static_cast<T*>(NamedObject::find(begin(), name));
2042  }
2043 
2044  inline T *offset(unsigned offset) {
2045  return static_cast<T*>(OrderedIndex::find(offset));
2046  }
2047 
2053  inline T& operator[](unsigned offset) {
2054  return static_cast<T&>(OrderedIndex::find(offset));
2055  }
2056 
2057  inline T& operator[](const char *name) {
2058  return static_cast<T&>(NamedObject::find(begin(), name));
2059  }
2060 
2067  inline T **index(void) {
2068  return static_cast<T**>(OrderedIndex::index());
2069  }
2070 
2077  inline T **sort(void) {
2078  return static_cast<T**>(NamedObject::sort(index()));
2079  }
2080 
2085 };
2086 
2091 
2095 typedef ObjectStack objstack_t;
2096 
2101 
2106 
2107 } // namespace ucommon
2108 
2109 #endif
treemap(treemap *parent, char *name)
Construct a child node on an existing tree.
Definition: linked.h:1675
NamedTree * getFirst(void) const
Get first child node in our ordered list of children.
Definition: linked.h:697
bool is_next(void) const
Test for next member in linked list.
Definition: linked.h:1502
treemap * leaf(const char *name) const
Search for a leaf node of our node.
Definition: linked.h:1834
linked_value(LinkedObject **root)
Construct embedded object on a linked list.
Definition: linked.h:1153
const T & operator*() const
Return typed value of this node by pointer reference.
Definition: linked.h:1699
ObjectStack objstack_t
Convenience type for a stack of linked objects.
Definition: linked.h:2095
void release(SharedAccess &object)
Convenience function to unlock shared object through it's protocol.
Definition: access.h:280
T ** sort(void)
Convert our linked list into an alphabetically sorted linear object pointer array.
Definition: linked.h:2077
objstack()
Create a new object stack.
Definition: linked.h:1206
static void purge(NamedObject **hash, unsigned size)
Purge a hash indexed table of named objects.
Template for typesafe basic object queue container.
Definition: linked.h:1300
void operator=(OrderedIndex *index)
Assign our pointer from the start of an ordered index.
Definition: linked.h:1417
NamedTree * find(const char *name) const
Find a child node of our object with the specified name.
A queue of double linked object.
Definition: linked.h:930
NamedTree * path(const char *path) const
Find a subnode by a dot separated list of node names.
void operator+=(LinkedList *object)
Insert object behind our object.
Definition: linked.h:904
objstack(T *list)
Create an object stack from a list of objects.
Definition: linked.h:1211
Various miscellaneous platform specific headers and defines.
void add(T *object)
Add an object onto the object stack.
Definition: linked.h:1225
const T getPointer(void) const
Get the pointer of a pointer based value tree.
Definition: linked.h:1724
void relist(NamedTree *trunk=((void *) 0))
Default relist is by tail...
Definition: linked.h:787
void add(T *object)
Add an object onto the object fifo.
Definition: linked.h:1273
multimap * next(unsigned path)
Return next multimap typed object.
Definition: linked.h:1581
LinkedObject * operator*() const
Return head object pointer.
Definition: linked.h:293
bool operator==(const char *name) const
Comparison operator between our name and a string.
Definition: linked.h:584
void setPointer(const T pointer)
Set the pointer of a pointer based value tree.
Definition: linked.h:1597
T * pull(void)
Pull an object from the object stack.
Definition: linked.h:1281
Template value class to embed data structure into a linked list.
Definition: linked.h:1141
T * operator*() const
Return object we currently point to.
Definition: linked.h:1441
NamedTree * getLeaf(const char *name) const
Find a direct leaf node on our node.
void add(const char *name, T &object)
Add a typed object derived from NamedObject to the hash map by name.
Definition: linked.h:1907
treemap * find(const char *name) const
Find a subnode from our node by name.
Definition: linked.h:1814
static T getPointer(treemap *node)
Return value from tree element when value is a pointer.
Definition: linked.h:1708
bool is_root(void) const
Test if node is root node.
Definition: linked.h:767
NamedObject ** root(void)
Return a root node pointer to use in NamedObject constructors.
Definition: linked.h:1994
void push(DLinkedObject *object)
Push an object to the front of the queue.
Common base class for all objects that can be formed into a linked list.
Definition: linked.h:59
static MultiMap * find(unsigned path, MultiMap **index, caddr_t key, unsigned max, size_t size=0)
Find a multikey node.
bool operator!() const
Test if this node is unnamed.
Definition: linked.h:738
objqueue()
Create a new object stack.
Definition: linked.h:1306
void add(const char *name, T *object)
Add a typed object derived from NamedObject to the hash map by name.
Definition: linked.h:1916
T * next(LinkedObject *current)
Iterate next object in list.
Definition: linked.h:2031
treemap(treemap *parent, char *name, T &reference)
Construct a child node on an existing tree and assign it's value.
Definition: linked.h:1683
Embed data objects into a multipap structured memory database.
Definition: linked.h:1552
void add(OrderedObject *ordered)
Add an object into the ordered index.
treemap * getLeaf(const char *name) const
Find a direct typed leaf node on our node.
Definition: linked.h:1793
void operator=(T *pointer)
Assign our typed iterative pointer from a matching typed object.
Definition: linked.h:1401
linked_pointer(LinkedObject *pointer)
Create a linked pointer assigned from a raw linked object pointer.
Definition: linked.h:1374
A linked object base class for ordered objects.
Definition: linked.h:319
const T & getData(void) const
Get the data value of a data based value tree.
Definition: linked.h:1732
DLinkedObject * pull(void)
Pull an object from the front of the queue.
T * pull(void)
Pull an object from the object stack.
Definition: linked.h:1233
NamedObject * getNext(void) const
Get next effective object when iterating.
Definition: linked.h:549
treemap(const treemap &source)
Construct a copy of the treemap object.
Definition: linked.h:1666
LinkedObject * end(void) const
Return last object in list for iterators.
Definition: linked.h:285
Template value class to embed data structure into a named list.
Definition: linked.h:1100
void prev(void)
Move (iterate) pointer to previous member in double linked list.
Definition: linked.h:1456
void set(const T &object)
Assign our value from a typed data object.
Definition: object.h:331
ObjectProtocol * copy(ObjectProtocol *object)
Convenience function to access object copy.
Definition: object.h:510
void operator=(LinkedObject *pointer)
Assign our pointer from a generic linked object pointer.
Definition: linked.h:1425
bool is_head(void) const
Test if we are at the head of a list.
Definition: linked.h:854
bool is_leaf(void) const
Test if node has children.
Definition: linked.h:759
unsigned limit(void) const
Retrieve key size to use in NamedObject constructors.
Definition: linked.h:1880
ObjectQueue objqueue_t
Convenience type for a queue of linked objects.
Definition: linked.h:2105
objfifo()
Create a new object stack.
Definition: linked.h:1259
static NamedObject * map(NamedObject **hash, const char *name, unsigned size)
Find a named object through a hash map table.
NamedTree * getIndexed(unsigned index) const
Get child by index number.
Definition: linked.h:714
LinkedList * getNext(void) const
Get next node in the list when iterating.
Definition: linked.h:878
LinkedObject * getNext(void) const
Get next effective object when iterating.
Definition: linked.h:144
DLinkedObject * pop(void)
Pop an object from the end of the queue.
NamedObject ** root(void) const
Retrieve root of index to use in NamedObject constructors.
Definition: linked.h:1872
LinkedObject * LinkedIndex
Convenience typedef for root pointers of single linked lists.
Definition: linked.h:2090
bool operator!() const
Test if linked list is empty/we are at end of list.
Definition: linked.h:1526
void operator*=(LinkedList *object)
Insert object in list with our object.
Definition: linked.h:920
T * find(const char *name)
Find a specific object by name.
Definition: linked.h:2040
A common base class for all managed objects.
Definition: protocols.h:545
Embed data objects into a tree structured memory database.
Definition: linked.h:1649
A double linked list object.
Definition: linked.h:798
LinkedObject * get(void)
Get (pull) object off the list.
~keymap()
Destroy the hash map by puring the index chains.
Definition: linked.h:1864
A common object base class with auto-pointer support.
Reusable objects for forming private heaps.
Definition: linked.h:158
OrderedIndex * getIndex(void) const
Get the ordered index of our child nodes.
Definition: linked.h:722
bool is_tail(void) const
Test if we are at the end of a list.
Definition: linked.h:862
An index container for maintaining an ordered list of objects.
Definition: linked.h:182
linked_pointer(const linked_pointer &pointer)
Create a copy of an existing linked pointer.
Definition: linked.h:1366
T ** sort(void) const
Convert our hash map into an alphabetically sorted linear object pointer array.
Definition: linked.h:1970
void operator=(const T &typed_value)
Assign embedded value from related type.
Definition: linked.h:1117
treemap * getChild(const char *name) const
Get direct typed child node of our node of specified name.
Definition: linked.h:1783
T * begin(void)
Return first item in ordered list.
Definition: linked.h:2003
treemap(char *name=((void *) 0))
Construct a typed root node for the tree.
Definition: linked.h:1660
bool equal(const char *name) const
Equal function which calls compare.
Definition: linked.h:575
void add(T *object)
Add an object to the end of the object queue.
Definition: linked.h:1320
MultiMap * next(unsigned path) const
Get next node from single chain.
Generic smart pointer class.
Definition: generics.h:54
NamedTree * getParent(void) const
Get parent node we are listed as a child on.
Definition: linked.h:705
T ** index(void) const
Convert our hash map into a linear object pointer array.
Definition: linked.h:1960
bool is_prev(void) const
Test for previous member in double linked list.
Definition: linked.h:1510
multimap()
Construct a multimap node.
Definition: linked.h:1561
static const LinkedObject * nil
Marker for end of linked list.
Definition: linked.h:83
T & operator*() const
Return typed value of this node by pointer reference.
Definition: linked.h:1589
unsigned count(void) const
Count the number of typed objects in our hash map.
Definition: linked.h:1950
static LinkedObject * getIndexed(LinkedObject *root, unsigned index)
Get member by index.
NamedTree * getChild(const char *name) const
Find a direct child of our node which matches the specified name.
T * create(const char *name)
Create a new typed named object with default constructor.
Definition: linked.h:2022
Common namespace for all ucommon objects.
Definition: access.h:47
A double-linked Object, used for certain kinds of lists.
Definition: linked.h:377
treemap * getParent(void) const
Get the typed parent node for our node.
Definition: linked.h:1773
treemap * path(const char *path) const
Find a subnode by pathname.
Definition: linked.h:1824
void set(const T &reference)
Set the value of a data based value tree.
Definition: linked.h:1605
T * begin(void) const
Find first typed object in hash map to iterate.
Definition: linked.h:1933
OrderedIndex & operator=(const OrderedIndex &object)
Assign ordered index.
Definition: linked.h:301
static NamedObject * remove(NamedObject **root, const char *name)
Remove a named object from a simple list.
static unsigned count(NamedObject **hash, unsigned size)
Count the total named objects in a hash table.
void retain(ObjectProtocol *object)
Convenience function to access object retention.
Definition: object.h:492
static multimap * find(unsigned path, MultiMap **index, caddr_t key, unsigned size, unsigned keysize=0)
Find multimap key entry.
Definition: linked.h:1626
bool operator!=(const char *name) const
Comparison operator between our name and a string.
Definition: linked.h:593
A template class for a hash map.
Definition: linked.h:1855
treemap * getFirst(void) const
Get first child of our node.
Definition: linked.h:1842
void next(void)
Move (iterate) pointer to next member in linked list.
Definition: linked.h:1463
NamedTree * leaf(const char *name) const
Find a child leaf node of our object with the specified name.
Class for resource bound memory pools between threads.
Definition: thread.h:704
treemap * getIndexed(unsigned index) const
Get child member node by index.
Definition: linked.h:1765
T * getPrev(void) const
Get the previous member in double linked list.
Definition: linked.h:1480
void operator=(linked_pointer &pointer)
Assign our pointer from another pointer.
Definition: linked.h:1409
OrderedIndex objfifo_t
Convenience type for a fifo of linked objects.
Definition: linked.h:2100
static NamedObject ** index(NamedObject **hash, unsigned size)
Convert a hash index into a linear object pointer array.
bool is_attribute(void) const
Test if this node is a leaf node for a tree pointer table.
Definition: linked.h:1716
The named tree class is used to form a tree oriented list of associated objects.
Definition: linked.h:605
void enlist(LinkedObject **root)
Add our object to an existing linked list through a pointer.
A smart pointer template for iterating linked lists.
Definition: linked.h:1348
T * pop(void)
Pull (pop) an object from the object stack.
Definition: linked.h:1289
static NamedObject ** sort(NamedObject **list, size_t count=0)
Sort an array of named objects in alphabetical order.
linked_value(OrderedIndex *index)
Construct embedded object on an ordered list.
Definition: linked.h:1161
void operator=(const T &data)
Assign the value of our node.
Definition: linked.h:1756
LinkedList * getPrev(void) const
Get previous node in the list for reverse iteration.
Definition: linked.h:870
static NamedObject * skip(NamedObject **hash, NamedObject *current, unsigned size)
Iterate through a hash map table.
void operator--()
Move (iterate) pointer to previous member in double linked list.
Definition: linked.h:1494
void operator-=(LinkedList *object)
Insert object in front of our object.
Definition: linked.h:912
T & operator[](unsigned offset)
Retrieve a specific object by position in list.
Definition: linked.h:2053
linked_value(OrderedIndex *index, const T &typed_value)
Assign embedded value from related type and add to list.
Definition: linked.h:1180
void push(T *object)
Push an object onto the object fifo.
Definition: linked.h:1265
T * pop(void)
Pop an object from the end of the object queue.
Definition: linked.h:1336
T * pop(void)
Pull (pop) an object from the object stack.
Definition: linked.h:1241
T getValue(const char *name) const
Get the value pointer of a leaf node of a pointer tree.
Definition: linked.h:1804
Template for embedding a data structure into a reference counted object.
Definition: object.h:324
static NamedObject * find(NamedObject *root, const char *name)
Find a named object from a simple list.
T * operator->() const
Return member from typed object our pointer references.
Definition: linked.h:1433
linked_pointer< T > iterator
Convenience typedef for iterative pointer.
Definition: linked.h:1977
LinkedObject ** root(void) const
Return pointer to our linked pointer to use as root node of a chain.
Definition: linked.h:1538
Template for typesafe basic object stack container.
Definition: linked.h:1200
linked_pointer()
Create a linked pointer not attached to a list.
Definition: linked.h:1393
static const LinkedObject * inv
Marker for invalid list pointer.
Definition: linked.h:84
Template for typesafe basic object fifo container.
Definition: linked.h:1253
T &() max(T &o1, T &o2)
Convenience function to return max of two objects.
Definition: generics.h:414
OrderedObject * getNext(void) const
Get next ordered member when iterating.
Definition: linked.h:368
void push(T *object)
Push an object onto the object stack.
Definition: linked.h:1217
linked_pointer(T *pointer)
Create a linked pointer and assign to start of a list.
Definition: linked.h:1358
LinkedObject * begin(void) const
Return first object in list for iterators.
Definition: linked.h:277
T & operator[](const char *name) const
Find a typed object derived from NamedObject in the hash map by name.
Definition: linked.h:1898
LinkedObject * getIndexed(unsigned index) const
Get an indexed member from the ordered index.
Definition: linked.h:269
T * getNext(void) const
Get the next member in linked list.
Definition: linked.h:1471
void operator=(const T &typed_value)
Assign embedded value from related type.
Definition: linked.h:1189
T * pull(void)
Pull an object from the start of the object queue.
Definition: linked.h:1328
linked_pointer< T > iterator
Convenience typedef for iterative pointer.
Definition: linked.h:2084
A multipath linked list where membership is managed in multiple lists.
Definition: linked.h:1007
linked_pointer(OrderedIndex *index)
Create a linked pointer to examine an ordered index.
Definition: linked.h:1386
A template for ordered index of typed name key mapped objects.
Definition: linked.h:1987
T * next(T *current) const
Find next typed object in hash map for iteration.
Definition: linked.h:1942
LinkedObject ** index(void) const
Return a pointer to the head of the list.
named_value(LinkedObject **root, char *name)
Construct embedded named object on a linked list.
Definition: linked.h:1108
linked_value(LinkedObject **root, const T &typed_value)
Assign embedded value from related type and link to list.
Definition: linked.h:1170
T * end(void)
Return last item in ordered list.
Definition: linked.h:2012
static named_value find(named_value *first, const char *name)
Find embedded object in chain by name.
Definition: linked.h:1127
T ** index(void)
Convert our linked list into a linear object pointer array.
Definition: linked.h:2067
void push(T *object)
Push an object to start of queue.
Definition: linked.h:1312
ReusableObject * getNext(void)
Get next effective reusable object when iterating.
Definition: linked.h:170
A linked object base class with members found by name.
Definition: linked.h:411
LinkedObject * find(unsigned offset) const
Find a specific member in the ordered list.
void operator++()
Move (iterate) pointer to next member in linked list.
Definition: linked.h:1487
void set(const T &reference)
Set the value of a data based value tree.
Definition: linked.h:1748
void setPointer(const T pointer)
Set the pointer of a pointer based value tree.
Definition: linked.h:1740
~multimap()
Destroy a multimap object.
Definition: linked.h:1566
char * getId(void) const
Get the named id string of this object.
Definition: linked.h:557
void operator=(const T &data)
Assign the value of our node.
Definition: linked.h:1613
linked_value()
Create embedded value object unlinked.
Definition: linked.h:1147
void add(DLinkedObject *object)
Add an object to the end of the queue.