UCommon
linked.h
Go to the documentation of this file.
1// Copyright (C) 2006-2014 David Sugar, Tycho Softworks.
2// Copyright (C) 2015-2020 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
44namespace ucommon {
45
46class OrderedObject;
47
55class __EXPORT LinkedObject : public __PROTOCOL ObjectProtocol
56{
57private:
58 friend class OrderedIndex;
59 friend class NamedObject;
60
61protected:
62 LinkedObject *Next;
63
68 LinkedObject(LinkedObject **root);
69
75 LinkedObject();
76
77 LinkedObject(const LinkedObject& from);
78
79public:
80 virtual ~LinkedObject();
81
85 virtual void release(void) __OVERRIDE;
86
90 virtual void retain(void) __OVERRIDE;
91
98 void enlist(LinkedObject **root);
99
106 void delist(LinkedObject **root);
107
112 bool is_member(LinkedObject *list) const;
113
118 static void purge(LinkedObject *root);
119
124 static unsigned count(const LinkedObject *root);
125
132 static LinkedObject *getIndexed(LinkedObject *root, unsigned index);
133
138 inline LinkedObject *getNext(void) const {
139 return Next;
140 }
141};
142
152class __EXPORT ReusableObject : public LinkedObject
153{
154 friend class ReusableAllocator;
155
156protected:
157 virtual void release(void) __OVERRIDE;
158
159public:
164 inline ReusableObject *getNext(void) {
165 return polypointer_cast<ReusableObject*>(LinkedObject::getNext());
166 }
167};
168
176class __EXPORT OrderedIndex
177{
178protected:
179 friend class OrderedObject;
180 friend class DLinkedObject;
181 friend class NamedObject;
182
183 OrderedObject *head, *tail;
184
185public:
186 void copy(const OrderedIndex& source);
187
191 OrderedIndex();
192
193 inline OrderedIndex(const OrderedIndex& source) {
194 copy(source);
195 }
196
200 virtual ~OrderedIndex();
201
206 LinkedObject *find(unsigned offset) const;
207
212 unsigned count(void) const;
213
217 void purge(void);
218
222 void reset(void);
223
228 virtual void lock_index(void);
229
234 virtual void unlock_index(void);
235
242 LinkedObject **index(void) const;
243
249 LinkedObject *get(void);
250
255 void add(OrderedObject *ordered);
256
262 inline LinkedObject *getIndexed(unsigned index) const {
263 return LinkedObject::getIndexed(polystatic_cast<LinkedObject*>(head), index);
264 }
265
270 inline LinkedObject *begin(void) const {
271 return polystatic_cast<LinkedObject*>(head);
272 }
273
278 inline LinkedObject *end(void) const {
279 return polystatic_cast<LinkedObject*>(tail);
280 }
281
286 inline LinkedObject *operator*() const {
287 return polystatic_cast<LinkedObject*>(head);
288 }
289
294 OrderedIndex& operator=(const OrderedIndex& object) {
295 copy(object);
296 return *this;
297 }
298
303 void operator*=(OrderedObject *object);
304};
305
312class __EXPORT OrderedObject : public LinkedObject
313{
314private:
315 friend class DLinkedObject;
316 friend class OrderedIndex;
317
318protected:
323 OrderedObject(OrderedIndex *index);
324
328 OrderedObject();
329
330 OrderedObject(const OrderedObject& from);
331
332public:
337 void enlistTail(OrderedIndex *index);
338
343 void enlistHead(OrderedIndex *index);
344
350 virtual void enlist(OrderedIndex *index);
351
356 void delist(OrderedIndex *index);
357
362 inline OrderedObject *getNext(void) const {
363 return static_cast<OrderedObject *>(LinkedObject::getNext());
364 }
365};
366
381class __EXPORT NamedObject : public OrderedObject
382{
383protected:
384 char *Id;
385
389 NamedObject();
390
397 NamedObject(NamedObject **hash, char *name, unsigned size = 1);
398
405 NamedObject(OrderedIndex *index, char *name);
406
414 ~NamedObject();
415
420 virtual void clearId(void);
421
422public:
429 void add(NamedObject **hash, char *name, unsigned size = 1);
430
436 static void purge(NamedObject **hash, unsigned size);
437
446 static NamedObject **index(NamedObject **hash, unsigned size);
447
453 static unsigned count(NamedObject **hash, unsigned size);
454
462 static NamedObject *find(NamedObject *root, const char *name);
463
470 static NamedObject *remove(NamedObject **root, const char *name);
471
479 static NamedObject *map(NamedObject **hash, const char *name, unsigned size);
480
488 static NamedObject *remove(NamedObject **hash, const char *name, unsigned size);
489
497 static NamedObject *skip(NamedObject **hash, NamedObject *current, unsigned size);
498
504 static unsigned keyindex(const char *name, unsigned size);
505
513 static NamedObject **sort(NamedObject **list, size_t count = 0);
514
519 inline NamedObject *getNext(void) const {
520 return static_cast<NamedObject*>(LinkedObject::getNext());
521 }
522
527 inline char *getId(void) const {
528 return Id;
529 };
530
538 virtual int compare(const char *name) const;
539
545 inline bool equal(const char *name) const {
546 return (compare(name) == 0);
547 }
548
554 inline bool operator==(const char *name) const {
555 return compare(name) == 0;
556 }
557
563 inline bool operator!=(const char *name) const {
564 return compare(name) != 0;
565 }
566};
567
575class __EXPORT NamedTree : public NamedObject
576{
577protected:
578 NamedTree *Parent;
579 OrderedIndex Child;
580
585 NamedTree(char *name = NULL);
586
592 NamedTree(NamedTree *parent, char *name);
593
598 NamedTree(const NamedTree& source);
599
605 virtual ~NamedTree();
606
612 void purge(void);
613
614public:
623 NamedTree *find(const char *name) const;
624
635 NamedTree *path(const char *path) const;
636
644 NamedTree *leaf(const char *name) const;
645
651 NamedTree *getChild(const char *name) const;
652
659 NamedTree *getLeaf(const char *name) const;
660
667 inline NamedTree *getFirst(void) const {
668 return static_cast<NamedTree *>(Child.begin());
669 }
670
675 inline NamedTree *getParent(void) const {
676 return static_cast<NamedTree *>(Parent);
677 };
678
684 inline NamedTree *getIndexed(unsigned index) const {
685 return static_cast<NamedTree *>(Child.getIndexed(index));
686 }
687
692 inline OrderedIndex *getIndex(void) const {
693 return const_cast<OrderedIndex*>(&Child);
694 }
695
700 inline operator bool() const {
701 return (Id != NULL);
702 }
703
708 inline bool operator!() const {
709 return (Id == NULL);
710 }
711
717 void setId(char *name);
718
723 void remove(void);
724
729 inline bool is_leaf(void) const {
730 return (Child.begin() == NULL);
731 }
732
737 inline bool is_root(void) const {
738 return (Parent == NULL);
739 }
740
745 void relistTail(NamedTree *trunk);
746
751 void relistHead(NamedTree *trunk);
752
757 inline void relist(NamedTree *trunk = NULL) {
758 relistTail(trunk);
759 }
760};
761
768class __EXPORT DLinkedObject : public OrderedObject
769{
770protected:
771 friend class ObjectQueue;
772
773 DLinkedObject *Prev;
774 OrderedIndex *Root;
775
780 DLinkedObject(OrderedIndex *index);
781
785 DLinkedObject();
786
787 DLinkedObject(const DLinkedObject& from);
788
793 virtual ~DLinkedObject();
794
795public:
799 void delist(void);
800
806 void enlistHead(OrderedIndex *index);
807
813 void enlistTail(OrderedIndex *index);
814
820 void enlist(OrderedIndex *index);
821
826 inline bool is_head(void) const {
827 return polypointer_cast<DLinkedObject *>(Root->head) == this;
828 }
829
834 inline bool is_tail(void) const {
835 return polypointer_cast<DLinkedObject *>(Root->tail) == this;
836 }
837
842 inline DLinkedObject *getPrev(void) const {
843 return static_cast<DLinkedObject*>(Prev);
844 }
845
850 inline DLinkedObject *getNext(void) const {
851 return static_cast<DLinkedObject*>(LinkedObject::getNext());
852 }
853
858 void insertTail(DLinkedObject *object);
859
864 void insertHead(DLinkedObject *object);
865
870 virtual void insert(DLinkedObject *object);
871
876 inline DLinkedObject& operator+=(DLinkedObject *object) {
877 insertTail(object);
878 return *this;
879 }
880
885 inline DLinkedObject& operator-=(DLinkedObject *object) {
886 insertHead(object);
887 return *this;
888 }
889
894 inline DLinkedObject& operator*=(DLinkedObject *object) {
895 insert(object);
896 return *this;
897 }
898};
899
908template <typename T, class O = LinkedObject>
909class linked_value : public O
910{
911protected:
912 __DELETE_COPY(linked_value);
913
914public:
915 T value;
916
920 inline linked_value() {}
921
926 inline linked_value(LinkedObject **root) {
927 LinkedObject::enlist(root);
928 }
929
934 inline linked_value(OrderedIndex *index) {
935 O::enlist(index);
936 }
937
943 inline linked_value(LinkedObject **root, const T& typed_value) {
944 LinkedObject::enlist(root);
945 value = typed_value;
946 }
947
953 inline linked_value(OrderedIndex *index, const T& typed_value) {
954 O::enlist(index);
955 value = typed_value;
956 }
957
958 inline void set(const T& typed_value) {
959 value = typed_value;
960 }
961
966 inline linked_value& operator=(const T& typed_value) {
967 value = typed_value;
968 return *this;
969 }
970
971 inline T& operator*() {
972 return value;
973 }
974
975 inline operator T&() {
976 return value;
977 }
978
979 inline void operator()(const T data) {
980 value = data;
981 }
982};
983
990template <class T>
992{
993private:
994 T *ptr;
995
996public:
1002 ptr = pointer;
1003 }
1004
1010 ptr = pointer.ptr;
1011 }
1012
1017 inline linked_pointer(LinkedObject *pointer) {
1018 ptr = static_cast<T*>(pointer);
1019 }
1020
1021 inline linked_pointer(const LinkedObject *pointer) {
1022 ptr = static_cast<T*>(pointer);
1023 }
1024
1029 inline linked_pointer(OrderedIndex *index) {
1030 ptr = static_cast<T*>(index->begin());
1031 }
1032
1037 ptr = NULL;
1038 }
1039
1044 inline void operator=(T *pointer) {
1045 ptr = pointer;
1046 }
1047
1053 ptr = pointer.ptr;
1054 }
1055
1060 inline void operator=(OrderedIndex *index) {
1061 ptr = static_cast<T*>(index->begin());
1062 }
1063
1068 inline void operator=(LinkedObject *pointer) {
1069 ptr = static_cast<T*>(pointer);
1070 }
1071
1076 inline T* operator->() const {
1077 return ptr;
1078 }
1079
1084 inline T* operator*() const {
1085 return ptr;
1086 }
1087
1092 inline operator T*() const {
1093 return ptr;
1094 }
1095
1099 inline void prev(void) {
1100 ptr = static_cast<T*>(ptr->getPrev());
1101 }
1102
1106 inline void next(void) {
1107 ptr = static_cast<T*>(ptr->getNext());
1108 }
1109
1114 inline T *getNext(void) const {
1115 return static_cast<T*>(ptr->getNext());
1116 }
1117
1123 inline T *getPrev(void) const {
1124 return static_cast<T*>(ptr->getPrev());
1125 }
1126
1130 inline void operator++() {
1131 ptr = static_cast<T*>(ptr->getNext());
1132 }
1133
1137 inline void operator--() {
1138 ptr = static_cast<T*>(ptr->getPrev());
1139 }
1140
1145 inline bool is_next(void) const {
1146 return (ptr->getNext() != NULL);
1147 }
1148
1153 inline bool is_prev(void) const {
1154 return (ptr->getPrev() != NULL);
1155 }
1156
1161 inline operator bool() const {
1162 return (ptr != NULL);
1163 }
1164
1169 inline bool operator!() const {
1170 return (ptr == NULL);
1171 }
1172
1173 inline bool is() const {
1174 return (ptr != NULL);
1175 }
1176
1181 inline LinkedObject **root(void) const {
1182 T **r = &ptr;
1183 return static_cast<LinkedObject**>(r);
1184 }
1185};
1186
1204template <typename T>
1205class treemap : public NamedTree
1206{
1207protected:
1208 T value;
1209
1210public:
1216 inline treemap(char *name = NULL) : NamedTree(name) {}
1217
1222 inline treemap(const treemap& source) : NamedTree(source) {
1223 value = source.value;
1224 };
1225
1231 inline treemap(treemap *parent, char *name) : NamedTree(parent, name) {}
1232
1239 inline treemap(treemap *parent, char *name, T& reference) : NamedTree(parent, name) {
1240 value = reference;
1241 }
1242
1247 inline const T& get(void) const {
1248 return value;
1249 }
1250
1255 inline const T& operator*() const {
1256 return value;
1257 }
1258
1264 static inline T getPointer(treemap *node) {
1265 return (node == NULL) ? NULL : node->value;
1266 }
1267
1272 inline bool is_attribute(void) const {
1273 return (!Child.begin() && value != NULL);
1274 }
1275
1280 inline const T getPointer(void) const {
1281 return value;
1282 }
1283
1288 inline const T& getData(void) const {
1289 return value;
1290 }
1291
1296 inline void setPointer(const T pointer) {
1297 value = pointer;
1298 }
1299
1304 inline void set(const T& reference) {
1305 value = reference;
1306 }
1307
1312 inline void operator=(const T& data) {
1313 value = data;
1314 }
1315
1321 inline treemap *getIndexed(unsigned index) const {
1322 return static_cast<treemap*>(Child.getIndexed(index));
1323 }
1324
1329 inline treemap *getParent(void) const {
1330 return static_cast<treemap*>(Parent);
1331 }
1332
1339 inline treemap *getChild(const char *name) const {
1340 return static_cast<treemap*>(NamedTree::getChild(name));
1341 }
1342
1349 inline treemap *getLeaf(const char *name) const {
1350 return static_cast<treemap*>(NamedTree::getLeaf(name));
1351 }
1352
1360 inline T getValue(const char *name) const {
1361 return getPointer(getLeaf(name));
1362 }
1363
1370 inline treemap *find(const char *name) const {
1371 return static_cast<treemap*>(NamedTree::find(name));
1372 }
1373
1380 inline treemap *path(const char *path) const {
1381 return static_cast<treemap*>(NamedTree::path(path));
1382 }
1383
1390 inline treemap *leaf(const char *name) const {
1391 return static_cast<treemap*>(NamedTree::leaf(name));
1392 }
1393
1398 inline treemap *getFirst(void) const {
1399 return static_cast<treemap*>(NamedTree::getFirst());
1400 }
1401};
1402
1406typedef LinkedObject *LinkedIndex;
1407
1408typedef DLinkedObject LinkedList; // compatibility for older code
1409
1410} // namespace ucommon
1411
1412#endif
Various miscellaneous platform specific headers and defines.
Common namespace for all ucommon objects.
Definition access.h:47
LinkedObject * LinkedIndex
Convenience typedef for root pointers of single linked lists.
Definition linked.h:1406
T copy(const T &src)
Convenience function to copy objects.
Definition generics.h:400
Generic smart pointer class.
Definition generics.h:60
A linked object base class for ordered objects.
Definition linked.h:910
linked_value(OrderedIndex *index)
Construct embedded object on an ordered list.
Definition linked.h:934
linked_value(LinkedObject **root, const T &typed_value)
Assign embedded value from related type and link to list.
Definition linked.h:943
linked_value(LinkedObject **root)
Construct embedded object on a linked list.
Definition linked.h:926
linked_value(OrderedIndex *index, const T &typed_value)
Assign embedded value from related type and add to list.
Definition linked.h:953
linked_value()
Create embedded value object unlinked.
Definition linked.h:920
linked_value & operator=(const T &typed_value)
Assign embedded value from related type.
Definition linked.h:966
A smart pointer template for iterating linked lists.
Definition linked.h:992
linked_pointer(T *pointer)
Create a linked pointer and assign to start of a list.
Definition linked.h:1001
void operator=(T *pointer)
Assign our typed iterative pointer from a matching typed object.
Definition linked.h:1044
linked_pointer(OrderedIndex *index)
Create a linked pointer to examine an ordered index.
Definition linked.h:1029
void prev(void)
Move (iterate) pointer to previous member in double linked list.
Definition linked.h:1099
T * getNext(void) const
Get the next member in linked list.
Definition linked.h:1114
void operator++()
Move (iterate) pointer to next member in linked list.
Definition linked.h:1130
void operator=(linked_pointer &pointer)
Assign our pointer from another pointer.
Definition linked.h:1052
void operator--()
Move (iterate) pointer to previous member in double linked list.
Definition linked.h:1137
void operator=(LinkedObject *pointer)
Assign our pointer from a generic linked object pointer.
Definition linked.h:1068
T * operator->() const
Return member from typed object our pointer references.
Definition linked.h:1076
linked_pointer()
Create a linked pointer not attached to a list.
Definition linked.h:1036
LinkedObject ** root(void) const
Return pointer to our linked pointer to use as root node of a chain.
Definition linked.h:1181
void next(void)
Move (iterate) pointer to next member in linked list.
Definition linked.h:1106
T * operator*() const
Return object we currently point to.
Definition linked.h:1084
linked_pointer(LinkedObject *pointer)
Create a linked pointer assigned from a raw linked object pointer.
Definition linked.h:1017
bool is_next(void) const
Test for next member in linked list.
Definition linked.h:1145
linked_pointer(const linked_pointer &pointer)
Create a copy of an existing linked pointer.
Definition linked.h:1009
void operator=(OrderedIndex *index)
Assign our pointer from the start of an ordered index.
Definition linked.h:1060
bool operator!() const
Test if linked list is empty/we are at end of list.
Definition linked.h:1169
bool is_prev(void) const
Test for previous member in double linked list.
Definition linked.h:1153
T * getPrev(void) const
Get the previous member in double linked list.
Definition linked.h:1123
Embed data objects into a tree structured memory database.
Definition linked.h:1206
treemap * getIndexed(unsigned index) const
Get child member node by index.
Definition linked.h:1321
treemap(char *name=NULL)
Construct a typed root node for the tree.
Definition linked.h:1216
treemap * getLeaf(const char *name) const
Find a direct typed leaf node on our node.
Definition linked.h:1349
const T & operator*() const
Return typed value of this node by pointer reference.
Definition linked.h:1255
treemap * find(const char *name) const
Find a subnode from our node by name.
Definition linked.h:1370
treemap * getFirst(void) const
Get first child of our node.
Definition linked.h:1398
void operator=(const T &data)
Assign the value of our node.
Definition linked.h:1312
T getValue(const char *name) const
Get the value pointer of a leaf node of a pointer tree.
Definition linked.h:1360
treemap(const treemap &source)
Construct a copy of the treemap object.
Definition linked.h:1222
static T getPointer(treemap *node)
Return value from tree element when value is a pointer.
Definition linked.h:1264
treemap * getChild(const char *name) const
Get direct typed child node of our node of specified name.
Definition linked.h:1339
const T getPointer(void) const
Get the pointer of a pointer based value tree.
Definition linked.h:1280
bool is_attribute(void) const
Test if this node is a leaf node for a tree pointer table.
Definition linked.h:1272
void set(const T &reference)
Set the value of a data based value tree.
Definition linked.h:1304
treemap(treemap *parent, char *name)
Construct a child node on an existing tree.
Definition linked.h:1231
treemap * leaf(const char *name) const
Search for a leaf node of our node.
Definition linked.h:1390
void setPointer(const T pointer)
Set the pointer of a pointer based value tree.
Definition linked.h:1296
const T & getData(void) const
Get the data value of a data based value tree.
Definition linked.h:1288
treemap * getParent(void) const
Get the typed parent node for our node.
Definition linked.h:1329
const T & get(void) const
Return the typed value of this node.
Definition linked.h:1247
treemap(treemap *parent, char *name, T &reference)
Construct a child node on an existing tree and assign it's value.
Definition linked.h:1239
treemap * path(const char *path) const
Find a subnode by pathname.
Definition linked.h:1380
A common object base class with auto-pointer support.