]>
Commit | Line | Data |
---|---|---|
94f895e4 | 1 | /* |
bf95c10a | 2 | * Copyright (C) 1996-2022 The Squid Software Foundation and contributors |
94f895e4 | 3 | * |
5c193dec AJ |
4 | * Squid software is distributed under GPLv2+ license and includes |
5 | * contributions from numerous individuals and organizations. | |
6 | * Please see the COPYING and CONTRIBUTORS files for details. | |
94f895e4 | 7 | */ |
8 | ||
5c2f68b7 AJ |
9 | #ifndef SQUID_CBDATALIST_H |
10 | #define SQUID_CBDATALIST_H | |
94f895e4 | 11 | |
b0c2361b | 12 | #include "cbdata.h" |
aa839030 | 13 | |
94f895e4 | 14 | template <class C> |
2236466c | 15 | class CbDataList |
94f895e4 | 16 | { |
5c2f68b7 | 17 | CBDATA_CLASS(CbDataList); |
94f895e4 | 18 | |
19 | public: | |
5c2f68b7 | 20 | CbDataList(C const &); |
2236466c | 21 | ~CbDataList(); |
00d77d6b | 22 | |
23bb0ebf | 23 | /// If element is already in the list, returns false. |
7a957a93 AR |
24 | /// Otherwise, adds the element to the end of the list and returns true. |
25 | /// Exists to avoid double iteration of find() and push() combo. | |
26 | bool push_back_unique(C const &element); | |
00d77d6b | 27 | bool find(C const &)const; |
28 | bool findAndTune(C const &); | |
7a957a93 | 29 | /// Iterates the entire list to return the last element holder. |
cf1c09f6 | 30 | CbDataList *tail(); |
2236466c | 31 | CbDataList *next; |
00d77d6b | 32 | C element; |
54687084 | 33 | bool empty() const { return this == NULL; } |
94f895e4 | 34 | }; |
35 | ||
a46d2c0e | 36 | template<class C> |
2236466c | 37 | class CbDataListContainer |
a46d2c0e | 38 | { |
00d77d6b | 39 | |
40 | public: | |
2236466c AJ |
41 | CbDataListContainer(); |
42 | ~CbDataListContainer(); | |
43 | CbDataList<C> *push_back (C const &); | |
a46d2c0e | 44 | C pop_front(); |
45 | bool empty() const; | |
46 | ||
2236466c | 47 | CbDataList<C> *head; |
a46d2c0e | 48 | }; |
94f895e4 | 49 | |
54687084 | 50 | template<class C> |
2236466c | 51 | class CbDataListIterator |
54687084 | 52 | { |
53 | public: | |
2236466c | 54 | CbDataListIterator(CbDataListContainer<C> const &list) : next_entry(list.head) {} |
54687084 | 55 | const C & next() { |
c5dd4956 AJ |
56 | CbDataList<C> *entry = next_entry; |
57 | if (entry) | |
58 | next_entry = entry->next; | |
59 | return entry->element; | |
54687084 | 60 | } |
61 | bool end() { | |
aee3523a | 62 | return next_entry == nullptr; |
54687084 | 63 | } |
64 | ||
65 | private: | |
2236466c | 66 | CbDataList<C> *next_entry; |
54687084 | 67 | }; |
68 | ||
d6d0eb11 | 69 | /** \cond AUTODOCS_IGNORE */ |
a46d2c0e | 70 | template <class C> |
2236466c | 71 | cbdata_type CbDataList<C>::CBDATA_CbDataList = CBDATA_UNKNOWN; |
63be0a78 | 72 | /** \endcond */ |
94f895e4 | 73 | |
94f895e4 | 74 | template <class C> |
aee3523a | 75 | CbDataList<C>::CbDataList(C const &value) : next(nullptr), element (value) |
00d77d6b | 76 | {} |
94f895e4 | 77 | |
78 | template <class C> | |
2236466c | 79 | CbDataList<C>::~CbDataList() |
94f895e4 | 80 | { |
81 | if (next) | |
00d77d6b | 82 | delete next; |
94f895e4 | 83 | } |
84 | ||
4fb72cb9 CT |
85 | template <class C> |
86 | bool | |
87 | CbDataList<C>::push_back_unique(C const &toAdd) | |
88 | { | |
89 | CbDataList<C> *last; | |
90 | for (last = this; last->next; last = last->next) { | |
91 | if (last->element == toAdd) | |
92 | return false; | |
93 | } | |
94 | ||
23bb0ebf | 95 | last->next = new CbDataList<C>(toAdd); |
4fb72cb9 CT |
96 | return true; |
97 | } | |
98 | ||
cf1c09f6 CT |
99 | template <class C> |
100 | CbDataList<C> * | |
101 | CbDataList<C>::tail() | |
102 | { | |
103 | CbDataList<C> *last; | |
104 | for (last = this; last->next; last = last->next); | |
105 | return last; | |
106 | } | |
107 | ||
94f895e4 | 108 | template <class C> |
109 | bool | |
2236466c | 110 | CbDataList<C>::find (C const &toFind) const |
94f895e4 | 111 | { |
aee3523a | 112 | CbDataList<C> const *node = nullptr; |
00d77d6b | 113 | |
94f895e4 | 114 | for (node = this; node; node = node->next) |
00d77d6b | 115 | if (node->element == toFind) |
116 | return true; | |
117 | ||
94f895e4 | 118 | return false; |
119 | } | |
120 | ||
121 | template <class C> | |
122 | bool | |
2236466c | 123 | CbDataList<C>::findAndTune(C const & toFind) |
94f895e4 | 124 | { |
2236466c | 125 | CbDataList<C> *prev = NULL; |
00d77d6b | 126 | |
2236466c | 127 | for (CbDataList<C> *node = this; node; node = node-> |
c5dd4956 | 128 | next) { |
00d77d6b | 129 | if (node->element == toFind) { |
130 | if (prev != NULL) { | |
131 | /* shift the element just found to the second position | |
132 | * in the list */ | |
133 | prev->next = node->next; | |
134 | node->next = this->next; | |
135 | this->next = node; | |
136 | } | |
137 | ||
138 | return true; | |
139 | } | |
140 | ||
141 | prev = node; | |
94f895e4 | 142 | } |
00d77d6b | 143 | |
94f895e4 | 144 | return false; |
145 | } | |
146 | ||
a46d2c0e | 147 | template <class C> |
aee3523a | 148 | CbDataListContainer<C>::CbDataListContainer() : head (nullptr) |
00d77d6b | 149 | {} |
a46d2c0e | 150 | |
151 | template <class C> | |
2236466c | 152 | CbDataListContainer<C>::~CbDataListContainer() |
a46d2c0e | 153 | { |
154 | if (head) | |
00d77d6b | 155 | delete head; |
a46d2c0e | 156 | } |
157 | ||
158 | template <class C> | |
2236466c AJ |
159 | CbDataList<C> * |
160 | CbDataListContainer<C>::push_back (C const &element) | |
a46d2c0e | 161 | { |
2236466c | 162 | CbDataList<C> *node = new CbDataList<C> (element); |
00d77d6b | 163 | |
a46d2c0e | 164 | if (head) { |
aee3523a | 165 | CbDataList<C> *tempNode = nullptr; |
00d77d6b | 166 | |
3d0ac046 | 167 | for (tempNode = head; tempNode->next; tempNode = tempNode->next); |
00d77d6b | 168 | tempNode->next = node; |
a46d2c0e | 169 | } else |
00d77d6b | 170 | head = node; |
171 | ||
a46d2c0e | 172 | return node; |
173 | } | |
174 | ||
175 | template <class C> | |
00d77d6b | 176 | C |
2236466c | 177 | CbDataListContainer<C>::pop_front() |
a46d2c0e | 178 | { |
179 | if (head) { | |
00d77d6b | 180 | C result = head->element; |
2236466c | 181 | CbDataList<C> *node = head; |
00d77d6b | 182 | head = head->next; |
183 | node->next = NULL; | |
184 | delete node; | |
185 | return result; | |
a46d2c0e | 186 | } |
00d77d6b | 187 | |
a46d2c0e | 188 | return C(); |
189 | } | |
190 | ||
191 | template <class C> | |
00d77d6b | 192 | bool |
2236466c | 193 | CbDataListContainer<C>::empty() const |
a46d2c0e | 194 | { |
aee3523a | 195 | return head == nullptr; |
a46d2c0e | 196 | } |
00d77d6b | 197 | |
5c2f68b7 | 198 | #endif /* SQUID_CBDATALIST_H */ |
f53969cc | 199 |