]>
Commit | Line | Data |
---|---|---|
94f895e4 | 1 | /* |
63be0a78 | 2 | * $Id: List.h,v 1.8 2008/02/26 21:49:33 amosjeffries Exp $ |
94f895e4 | 3 | * |
4 | * | |
5 | * SQUID Web Proxy Cache http://www.squid-cache.org/ | |
6 | * ---------------------------------------------------------- | |
7 | * | |
8 | * Squid is the result of efforts by numerous individuals from | |
9 | * the Internet community; see the CONTRIBUTORS file for full | |
10 | * details. Many organizations have provided support for Squid's | |
11 | * development; see the SPONSORS file for full details. Squid is | |
12 | * Copyrighted (C) 2001 by the Regents of the University of | |
13 | * California; see the COPYRIGHT file for full details. Squid | |
14 | * incorporates software developed and/or copyrighted by other | |
15 | * sources; see the CREDITS file for full details. | |
16 | * | |
17 | * This program is free software; you can redistribute it and/or modify | |
18 | * it under the terms of the GNU General Public License as published by | |
19 | * the Free Software Foundation; either version 2 of the License, or | |
20 | * (at your option) any later version. | |
21 | * | |
22 | * This program is distributed in the hope that it will be useful, | |
23 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
24 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
25 | * GNU General Public License for more details. | |
26 | * | |
27 | * You should have received a copy of the GNU General Public License | |
28 | * along with this program; if not, write to the Free Software | |
29 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. | |
30 | * | |
31 | */ | |
32 | ||
33 | #ifndef SQUID_LIST_H | |
34 | #define SQUID_LIST_H | |
35 | ||
e1f7507e AJ |
36 | /** \todo FUBAR: cbdata.h is over in src/ */ |
37 | #include "../src/cbdata.h" | |
aa839030 | 38 | |
63be0a78 | 39 | /// \ingroup POD |
94f895e4 | 40 | template <class C> |
41 | class List | |
42 | { | |
43 | ||
44 | public: | |
00d77d6b | 45 | void *operator new (size_t); |
46 | void operator delete (void *); | |
47 | List (C const &); | |
48 | ~List(); | |
49 | ||
50 | bool find(C const &)const; | |
51 | bool findAndTune(C const &); | |
52 | List *next; | |
53 | C element; | |
54687084 | 54 | bool empty() const { return this == NULL; } |
00d77d6b | 55 | |
94f895e4 | 56 | private: |
00d77d6b | 57 | CBDATA_CLASS(List); |
94f895e4 | 58 | }; |
59 | ||
63be0a78 | 60 | /// \ingroup POD |
a46d2c0e | 61 | template<class C> |
62 | class ListContainer | |
63 | { | |
00d77d6b | 64 | |
65 | public: | |
a46d2c0e | 66 | ListContainer(); |
67 | ~ListContainer(); | |
68 | List<C> *push_back (C const &); | |
69 | C pop_front(); | |
70 | bool empty() const; | |
71 | ||
72 | List<C> *head; | |
73 | }; | |
94f895e4 | 74 | |
63be0a78 | 75 | /// \ingroup POD |
54687084 | 76 | template<class C> |
77 | class ListIterator | |
78 | { | |
79 | public: | |
80 | ListIterator(ListContainer<C> const &list) : next_entry(list.head) {} | |
81 | const C & next() { | |
82 | List<C> *entry = next_entry; | |
83 | if (entry) | |
84 | next_entry = entry->next; | |
85 | return entry->element; | |
86 | } | |
87 | bool end() { | |
86087129 | 88 | return next_entry == NULL; |
54687084 | 89 | } |
90 | ||
91 | private: | |
92 | List<C> *next_entry; | |
93 | }; | |
94 | ||
a46d2c0e | 95 | /* implementation follows */ |
00d77d6b | 96 | |
63be0a78 | 97 | /** \cond AUTODOCS-IGNORE */ |
a46d2c0e | 98 | template <class C> |
99 | cbdata_type List<C>::CBDATA_List = CBDATA_UNKNOWN; | |
63be0a78 | 100 | /** \endcond */ |
94f895e4 | 101 | |
102 | template <class C> | |
103 | void * | |
104 | List<C>::operator new (size_t byteCount) | |
105 | { | |
a46d2c0e | 106 | CBDATA_INIT_TYPE(List); |
00d77d6b | 107 | |
a46d2c0e | 108 | List<C> *result = cbdataAlloc(List); |
00d77d6b | 109 | |
a46d2c0e | 110 | return result; |
94f895e4 | 111 | } |
112 | ||
113 | template <class C> | |
114 | void | |
115 | List<C>::operator delete (void *address) | |
116 | { | |
a46d2c0e | 117 | cbdataFree(address); |
94f895e4 | 118 | } |
119 | ||
94f895e4 | 120 | template <class C> |
121 | List<C>::List(C const &value) : next(NULL), element (value) | |
00d77d6b | 122 | {} |
94f895e4 | 123 | |
124 | template <class C> | |
125 | List<C>::~List() | |
126 | { | |
127 | if (next) | |
00d77d6b | 128 | delete next; |
94f895e4 | 129 | } |
130 | ||
131 | template <class C> | |
132 | bool | |
133 | List<C>::find (C const &toFind) const | |
134 | { | |
135 | List<C> const *node = NULL; | |
00d77d6b | 136 | |
94f895e4 | 137 | for (node = this; node; node = node->next) |
00d77d6b | 138 | if (node->element == toFind) |
139 | return true; | |
140 | ||
94f895e4 | 141 | return false; |
142 | } | |
143 | ||
144 | template <class C> | |
145 | bool | |
146 | List<C>::findAndTune(C const & toFind) | |
147 | { | |
148 | List<C> *prev = NULL; | |
00d77d6b | 149 | |
150 | for (List<C> *node = this; node; node = node-> | |
151 | next) { | |
152 | if (node->element == toFind) { | |
153 | if (prev != NULL) { | |
154 | /* shift the element just found to the second position | |
155 | * in the list */ | |
156 | prev->next = node->next; | |
157 | node->next = this->next; | |
158 | this->next = node; | |
159 | } | |
160 | ||
161 | return true; | |
162 | } | |
163 | ||
164 | prev = node; | |
94f895e4 | 165 | } |
00d77d6b | 166 | |
94f895e4 | 167 | return false; |
168 | } | |
169 | ||
a46d2c0e | 170 | template <class C> |
171 | ListContainer<C>::ListContainer() : head (NULL) | |
00d77d6b | 172 | {} |
a46d2c0e | 173 | |
174 | template <class C> | |
175 | ListContainer<C>::~ListContainer() | |
176 | { | |
177 | if (head) | |
00d77d6b | 178 | delete head; |
a46d2c0e | 179 | } |
180 | ||
181 | template <class C> | |
182 | List<C> * | |
183 | ListContainer<C>::push_back (C const &element) | |
184 | { | |
185 | List<C> *node = new List<C> (element); | |
00d77d6b | 186 | |
a46d2c0e | 187 | if (head) { |
00d77d6b | 188 | List<C> *tempNode = NULL; |
189 | ||
190 | for (tempNode = head; tempNode->next; tempNode = tempNode->next) | |
191 | ||
192 | ; | |
193 | tempNode->next = node; | |
a46d2c0e | 194 | } else |
00d77d6b | 195 | head = node; |
196 | ||
a46d2c0e | 197 | return node; |
198 | } | |
199 | ||
200 | template <class C> | |
00d77d6b | 201 | C |
a46d2c0e | 202 | ListContainer<C>::pop_front() |
203 | { | |
204 | if (head) { | |
00d77d6b | 205 | C result = head->element; |
206 | List<C> *node = head; | |
207 | head = head->next; | |
208 | node->next = NULL; | |
209 | delete node; | |
210 | return result; | |
a46d2c0e | 211 | } |
00d77d6b | 212 | |
a46d2c0e | 213 | return C(); |
214 | } | |
215 | ||
216 | template <class C> | |
00d77d6b | 217 | bool |
a46d2c0e | 218 | ListContainer<C>::empty() const |
219 | { | |
220 | return head == NULL; | |
221 | } | |
00d77d6b | 222 | |
94f895e4 | 223 | #endif /* SQUID_LIST_H */ |