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