]>
Commit | Line | Data |
---|---|---|
94f895e4 | 1 | |
2 | /* | |
a46d2c0e | 3 | * $Id: List.h,v 1.2 2003/03/04 01:40:22 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 | ||
37 | template <class C> | |
38 | class List | |
39 | { | |
40 | ||
41 | public: | |
42 | void *operator new (size_t); | |
43 | void operator delete (void *); | |
44 | void deleteSelf() const; | |
45 | List (C const &); | |
46 | ~List(); | |
47 | ||
48 | bool find(C const &)const; | |
49 | bool findAndTune(C const &); | |
50 | List *next; | |
51 | C element; | |
52 | private: | |
a46d2c0e | 53 | CBDATA_CLASS(List); |
54 | #if 0 | |
94f895e4 | 55 | static MemPool *Pool; |
a46d2c0e | 56 | #endif |
94f895e4 | 57 | }; |
58 | ||
a46d2c0e | 59 | template<class C> |
60 | class ListContainer | |
61 | { | |
62 | public: | |
63 | ListContainer(); | |
64 | ~ListContainer(); | |
65 | List<C> *push_back (C const &); | |
66 | C pop_front(); | |
67 | bool empty() const; | |
68 | ||
69 | List<C> *head; | |
70 | }; | |
94f895e4 | 71 | |
a46d2c0e | 72 | /* implementation follows */ |
73 | #if 0 | |
94f895e4 | 74 | template <class C> |
75 | MemPool *List<C>::Pool(NULL); | |
a46d2c0e | 76 | #endif |
77 | template <class C> | |
78 | cbdata_type List<C>::CBDATA_List = CBDATA_UNKNOWN; | |
94f895e4 | 79 | |
80 | template <class C> | |
81 | void * | |
82 | List<C>::operator new (size_t byteCount) | |
83 | { | |
a46d2c0e | 84 | #if 0 |
94f895e4 | 85 | /* derived classes with different sizes must implement their own new */ |
86 | assert (byteCount == sizeof (List<C>)); | |
87 | if (!Pool) | |
88 | Pool = memPoolCreate("List", sizeof (List<C>)); | |
89 | return memPoolAlloc(Pool); | |
a46d2c0e | 90 | #endif |
91 | CBDATA_INIT_TYPE(List); | |
92 | List<C> *result = cbdataAlloc(List); | |
93 | return result; | |
94f895e4 | 94 | } |
95 | ||
96 | template <class C> | |
97 | void | |
98 | List<C>::operator delete (void *address) | |
99 | { | |
a46d2c0e | 100 | // MemPoolFree |
101 | // List<C> *t = static_cast<List<C> *>(address); | |
102 | cbdataFree(address); | |
94f895e4 | 103 | } |
104 | ||
105 | template <class C> | |
106 | void | |
107 | List<C>::deleteSelf() const | |
108 | { | |
109 | delete this; | |
110 | } | |
111 | ||
112 | template <class C> | |
113 | List<C>::List(C const &value) : next(NULL), element (value) | |
114 | { | |
115 | } | |
116 | ||
117 | template <class C> | |
118 | List<C>::~List() | |
119 | { | |
120 | if (next) | |
121 | next->deleteSelf(); | |
122 | } | |
123 | ||
124 | template <class C> | |
125 | bool | |
126 | List<C>::find (C const &toFind) const | |
127 | { | |
128 | List<C> const *node = NULL; | |
129 | for (node = this; node; node = node->next) | |
130 | if (node->element == toFind) | |
131 | return true; | |
132 | return false; | |
133 | } | |
134 | ||
135 | template <class C> | |
136 | bool | |
137 | List<C>::findAndTune(C const & toFind) | |
138 | { | |
139 | List<C> *prev = NULL; | |
140 | for (List<C> *node = this; node; node = node->next) { | |
141 | if (node->element == toFind) { | |
142 | if (prev != NULL) { | |
143 | /* shift the element just found to the second position | |
144 | * in the list */ | |
145 | prev->next = node->next; | |
146 | node->next = this->next; | |
147 | this->next = node; | |
148 | } | |
149 | return true; | |
150 | } | |
151 | prev = node; | |
152 | } | |
153 | return false; | |
154 | } | |
155 | ||
a46d2c0e | 156 | template <class C> |
157 | ListContainer<C>::ListContainer() : head (NULL) | |
158 | { | |
159 | } | |
160 | ||
161 | template <class C> | |
162 | ListContainer<C>::~ListContainer() | |
163 | { | |
164 | if (head) | |
165 | head->deleteSelf(); | |
166 | } | |
167 | ||
168 | template <class C> | |
169 | List<C> * | |
170 | ListContainer<C>::push_back (C const &element) | |
171 | { | |
172 | List<C> *node = new List<C> (element); | |
173 | if (head) { | |
174 | List<C> *tempNode = NULL; | |
175 | for (tempNode = head; tempNode->next; tempNode = tempNode->next); | |
176 | tempNode->next = node; | |
177 | } else | |
178 | head = node; | |
179 | return node; | |
180 | } | |
181 | ||
182 | template <class C> | |
183 | C | |
184 | ListContainer<C>::pop_front() | |
185 | { | |
186 | if (head) { | |
187 | C result = head->element; | |
188 | List<C> *node = head; | |
189 | head = head->next; | |
190 | node->next = NULL; | |
191 | node->deleteSelf(); | |
192 | return result; | |
193 | } | |
194 | return C(); | |
195 | } | |
196 | ||
197 | template <class C> | |
198 | bool | |
199 | ListContainer<C>::empty() const | |
200 | { | |
201 | return head == NULL; | |
202 | } | |
94f895e4 | 203 | #endif /* SQUID_LIST_H */ |