]>
Commit | Line | Data |
---|---|---|
1 | /* | |
2 | * Copyright (C) 1996-2017 The Squid Software Foundation and contributors | |
3 | * | |
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. | |
7 | */ | |
8 | ||
9 | #ifndef SQUID_CBDATALIST_H | |
10 | #define SQUID_CBDATALIST_H | |
11 | ||
12 | #include "cbdata.h" | |
13 | ||
14 | template <class C> | |
15 | class CbDataList | |
16 | { | |
17 | CBDATA_CLASS(CbDataList); | |
18 | ||
19 | public: | |
20 | CbDataList(C const &); | |
21 | ~CbDataList(); | |
22 | ||
23 | /// If element is already in the list, returns false. | |
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); | |
27 | bool find(C const &)const; | |
28 | bool findAndTune(C const &); | |
29 | /// Iterates the entire list to return the last element holder. | |
30 | CbDataList *tail(); | |
31 | CbDataList *next; | |
32 | C element; | |
33 | bool empty() const { return this == NULL; } | |
34 | }; | |
35 | ||
36 | template<class C> | |
37 | class CbDataListContainer | |
38 | { | |
39 | ||
40 | public: | |
41 | CbDataListContainer(); | |
42 | ~CbDataListContainer(); | |
43 | CbDataList<C> *push_back (C const &); | |
44 | C pop_front(); | |
45 | bool empty() const; | |
46 | ||
47 | CbDataList<C> *head; | |
48 | }; | |
49 | ||
50 | template<class C> | |
51 | class CbDataListIterator | |
52 | { | |
53 | public: | |
54 | CbDataListIterator(CbDataListContainer<C> const &list) : next_entry(list.head) {} | |
55 | const C & next() { | |
56 | CbDataList<C> *entry = next_entry; | |
57 | if (entry) | |
58 | next_entry = entry->next; | |
59 | return entry->element; | |
60 | } | |
61 | bool end() { | |
62 | return next_entry == NULL; | |
63 | } | |
64 | ||
65 | private: | |
66 | CbDataList<C> *next_entry; | |
67 | }; | |
68 | ||
69 | /** \cond AUTODOCS_IGNORE */ | |
70 | template <class C> | |
71 | cbdata_type CbDataList<C>::CBDATA_CbDataList = CBDATA_UNKNOWN; | |
72 | /** \endcond */ | |
73 | ||
74 | template <class C> | |
75 | CbDataList<C>::CbDataList(C const &value) : next(NULL), element (value) | |
76 | {} | |
77 | ||
78 | template <class C> | |
79 | CbDataList<C>::~CbDataList() | |
80 | { | |
81 | if (next) | |
82 | delete next; | |
83 | } | |
84 | ||
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 | ||
95 | last->next = new CbDataList<C>(toAdd); | |
96 | return true; | |
97 | } | |
98 | ||
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 | ||
108 | template <class C> | |
109 | bool | |
110 | CbDataList<C>::find (C const &toFind) const | |
111 | { | |
112 | CbDataList<C> const *node = NULL; | |
113 | ||
114 | for (node = this; node; node = node->next) | |
115 | if (node->element == toFind) | |
116 | return true; | |
117 | ||
118 | return false; | |
119 | } | |
120 | ||
121 | template <class C> | |
122 | bool | |
123 | CbDataList<C>::findAndTune(C const & toFind) | |
124 | { | |
125 | CbDataList<C> *prev = NULL; | |
126 | ||
127 | for (CbDataList<C> *node = this; node; node = node-> | |
128 | next) { | |
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; | |
142 | } | |
143 | ||
144 | return false; | |
145 | } | |
146 | ||
147 | template <class C> | |
148 | CbDataListContainer<C>::CbDataListContainer() : head (NULL) | |
149 | {} | |
150 | ||
151 | template <class C> | |
152 | CbDataListContainer<C>::~CbDataListContainer() | |
153 | { | |
154 | if (head) | |
155 | delete head; | |
156 | } | |
157 | ||
158 | template <class C> | |
159 | CbDataList<C> * | |
160 | CbDataListContainer<C>::push_back (C const &element) | |
161 | { | |
162 | CbDataList<C> *node = new CbDataList<C> (element); | |
163 | ||
164 | if (head) { | |
165 | CbDataList<C> *tempNode = NULL; | |
166 | ||
167 | for (tempNode = head; tempNode->next; tempNode = tempNode->next); | |
168 | tempNode->next = node; | |
169 | } else | |
170 | head = node; | |
171 | ||
172 | return node; | |
173 | } | |
174 | ||
175 | template <class C> | |
176 | C | |
177 | CbDataListContainer<C>::pop_front() | |
178 | { | |
179 | if (head) { | |
180 | C result = head->element; | |
181 | CbDataList<C> *node = head; | |
182 | head = head->next; | |
183 | node->next = NULL; | |
184 | delete node; | |
185 | return result; | |
186 | } | |
187 | ||
188 | return C(); | |
189 | } | |
190 | ||
191 | template <class C> | |
192 | bool | |
193 | CbDataListContainer<C>::empty() const | |
194 | { | |
195 | return head == NULL; | |
196 | } | |
197 | ||
198 | #endif /* SQUID_CBDATALIST_H */ | |
199 |