]>
Commit | Line | Data |
---|---|---|
f12361a1 | 1 | /* |
b8bad68c | 2 | * $Id: Array.h,v 1.16 2003/09/22 08:50:51 robertc Exp $ |
f12361a1 | 3 | * |
4 | * AUTHOR: Alex Rousskov | |
5 | * | |
2b6662ba | 6 | * SQUID Web Proxy Cache http://www.squid-cache.org/ |
7 | * ---------------------------------------------------------- | |
f12361a1 | 8 | * |
2b6662ba | 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. | |
f12361a1 | 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 | |
cbdec147 | 30 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. |
f12361a1 | 31 | * |
32 | */ | |
33 | ||
b5638623 | 34 | #ifndef SQUID_ARRAY_H |
35 | #define SQUID_ARRAY_H | |
f12361a1 | 36 | |
75faaa7a | 37 | /* iterator support */ |
ec2436ff | 38 | |
75faaa7a | 39 | template <class C> |
ec2436ff | 40 | |
75faaa7a | 41 | class VectorIteratorBase |
42 | { | |
43 | ||
44 | public: | |
ec2436ff | 45 | VectorIteratorBase(); |
46 | VectorIteratorBase(C &); | |
47 | VectorIteratorBase(size_t, C &); | |
48 | VectorIteratorBase & operator =(VectorIteratorBase const &); | |
49 | bool operator != (VectorIteratorBase const &rhs); | |
50 | bool operator == (VectorIteratorBase const &rhs); | |
51 | VectorIteratorBase & operator ++(); | |
52 | VectorIteratorBase operator ++(int); | |
7d9b0628 | 53 | typename C::value_type & operator *() const |
75faaa7a | 54 | { |
55 | return theVector->items[pos]; | |
56 | } | |
57 | ||
58 | typename C::value_type * operator -> () const | |
59 | { | |
60 | return &theVector->items[pos]; | |
61 | } | |
62 | ||
ec2436ff | 63 | ssize_t operator - (VectorIteratorBase const &rhs) const; |
64 | bool incrementable() const; | |
75faaa7a | 65 | |
66 | private: | |
ec2436ff | 67 | size_t pos; |
68 | C * theVector; | |
69 | }; | |
75faaa7a | 70 | |
ec2436ff | 71 | template<class E> |
75faaa7a | 72 | |
73 | class Vector | |
74 | { | |
75 | ||
ec2436ff | 76 | public: |
77 | typedef E value_type; | |
78 | typedef E* pointer; | |
79 | typedef VectorIteratorBase<Vector<E> > iterator; | |
80 | typedef VectorIteratorBase<Vector<E> const> const_iterator; | |
75faaa7a | 81 | |
ec2436ff | 82 | void *operator new (size_t); |
83 | void operator delete (void *); | |
75faaa7a | 84 | |
ec2436ff | 85 | Vector(); |
86 | ~Vector(); | |
87 | Vector(Vector const &); | |
88 | Vector &operator = (Vector const &); | |
89 | void clean(); | |
90 | void reserve (size_t capacity); | |
91 | void push_back (E); | |
92 | E &back(); | |
93 | E pop_back(); | |
94 | void preAppend(int app_count); | |
95 | bool empty() const; | |
96 | size_t size() const; | |
97 | iterator begin(); | |
98 | const_iterator begin () const; | |
99 | iterator end(); | |
100 | const_iterator end () const; | |
75faaa7a | 101 | |
b67e2c8c | 102 | /* Do not change these, until the entry C struct is removed */ |
ec2436ff | 103 | size_t capacity; |
104 | size_t count; | |
105 | E *items; | |
106 | }; | |
f12361a1 | 107 | |
ec2436ff | 108 | template<class E> |
109 | void * | |
110 | Vector<E>::operator new(size_t size) | |
111 | { | |
112 | return xmalloc (size); | |
113 | } | |
114 | ||
115 | template<class E> | |
116 | void | |
117 | Vector<E>::operator delete (void *address) | |
118 | { | |
119 | xfree (address); | |
120 | } | |
121 | ||
122 | template<class E> | |
123 | Vector<E>::Vector() : capacity (0), count(0), items (NULL) | |
75faaa7a | 124 | {} |
ec2436ff | 125 | |
126 | template<class E> | |
75faaa7a | 127 | Vector<E>::~Vector() |
ec2436ff | 128 | { |
129 | clean(); | |
130 | } | |
131 | ||
132 | template<class E> | |
133 | void | |
134 | Vector<E>::clean() | |
135 | { | |
136 | /* could also warn if some objects are left */ | |
137 | delete[] items; | |
138 | items = NULL; | |
139 | capacity = 0; | |
140 | count = 0; | |
141 | } | |
142 | ||
143 | /* grows internal buffer to satisfy required minimal capacity */ | |
144 | template<class E> | |
145 | void | |
146 | Vector<E>::reserve(size_t min_capacity) | |
147 | { | |
148 | const int min_delta = 16; | |
149 | int delta; | |
75faaa7a | 150 | |
ec2436ff | 151 | if (capacity >= min_capacity) |
75faaa7a | 152 | return; |
153 | ||
ec2436ff | 154 | delta = min_capacity; |
75faaa7a | 155 | |
ec2436ff | 156 | /* make delta a multiple of min_delta */ |
157 | delta += min_delta - 1; | |
75faaa7a | 158 | |
ec2436ff | 159 | delta /= min_delta; |
75faaa7a | 160 | |
ec2436ff | 161 | delta *= min_delta; |
75faaa7a | 162 | |
ec2436ff | 163 | /* actual grow */ |
164 | if (delta < 0) | |
75faaa7a | 165 | delta = min_capacity - capacity; |
166 | ||
ec2436ff | 167 | E*newitems = new E[capacity + delta]; |
75faaa7a | 168 | |
ec2436ff | 169 | for (size_t counter = 0; counter < size(); ++counter) { |
75faaa7a | 170 | newitems[counter] = items[counter]; |
ec2436ff | 171 | } |
75faaa7a | 172 | |
ec2436ff | 173 | capacity += delta; |
174 | delete[]items; | |
175 | items = newitems; | |
176 | } | |
177 | ||
178 | template<class E> | |
179 | void | |
180 | Vector<E>::push_back(E obj) | |
181 | { | |
182 | if (size() >= capacity) | |
75faaa7a | 183 | reserve (size() + 1); |
184 | ||
ec2436ff | 185 | items[count++] = obj; |
186 | } | |
187 | ||
188 | template<class E> | |
189 | E | |
190 | Vector<E>::pop_back() | |
191 | { | |
192 | assert (size()); | |
193 | value_type result = items[--count]; | |
194 | items[count] = value_type(); | |
195 | return result; | |
196 | } | |
197 | ||
198 | template<class E> | |
199 | E & | |
200 | Vector<E>::back() | |
201 | { | |
202 | assert (size()); | |
203 | return items[size() - 1]; | |
204 | } | |
205 | ||
206 | /* if you are going to append a known and large number of items, call this first */ | |
207 | template<class E> | |
208 | void | |
209 | Vector<E>::preAppend(int app_count) | |
210 | { | |
211 | if (size() + app_count > capacity) | |
75faaa7a | 212 | reserve(size() + app_count); |
ec2436ff | 213 | } |
214 | ||
b8bad68c | 215 | template<class E> |
216 | Vector<E>::Vector<E> (Vector const &rhs) | |
217 | { | |
218 | items = NULL; | |
219 | capacity = 0; | |
220 | count = 0; | |
221 | reserve (rhs.size()); | |
222 | ||
223 | for (size_t counter = 0; counter < rhs.size(); ++counter) | |
224 | push_back (rhs.items[counter]); | |
225 | } | |
226 | ||
ec2436ff | 227 | template<class E> |
228 | Vector<E> & | |
229 | Vector<E>::operator = (Vector const &old) | |
230 | { | |
231 | clean(); | |
232 | reserve (old.size()); | |
75faaa7a | 233 | |
ec2436ff | 234 | for (size_t counter = 0; counter < old.size(); ++counter) |
75faaa7a | 235 | push_back (old.items[counter]); |
236 | ||
ec2436ff | 237 | return *this; |
238 | } | |
239 | ||
240 | template<class E> | |
241 | bool | |
242 | Vector<E>::empty() const | |
243 | { | |
244 | return size() == 0; | |
245 | } | |
246 | ||
247 | template<class E> | |
248 | size_t | |
249 | Vector<E>::size() const | |
250 | { | |
251 | return count; | |
252 | } | |
253 | ||
254 | template<class E> | |
6f0aa791 | 255 | typename Vector<E>::iterator |
ec2436ff | 256 | Vector<E>::begin() |
257 | { | |
258 | return iterator (0, *this); | |
259 | } | |
260 | ||
261 | template<class E> | |
6f0aa791 | 262 | typename Vector<E>::iterator |
ec2436ff | 263 | Vector<E>::end() |
264 | { | |
265 | return iterator(size(), *this); | |
266 | } | |
267 | ||
268 | template<class E> | |
6f0aa791 | 269 | typename Vector<E>::const_iterator |
ec2436ff | 270 | Vector<E>::begin() const |
271 | { | |
272 | return const_iterator (0, *this); | |
273 | } | |
274 | ||
275 | template<class E> | |
6f0aa791 | 276 | typename Vector<E>::const_iterator |
ec2436ff | 277 | Vector<E>::end() const |
278 | { | |
279 | return const_iterator(size(), *this); | |
280 | } | |
281 | ||
282 | ||
283 | template<class C> | |
284 | VectorIteratorBase<C>::VectorIteratorBase() : pos(0), theVector(NULL) | |
75faaa7a | 285 | {} |
ec2436ff | 286 | |
287 | template<class C> | |
288 | VectorIteratorBase<C>::VectorIteratorBase(C &container) : pos(container.begin()), theVector(&container) | |
75faaa7a | 289 | {} |
ec2436ff | 290 | |
291 | template<class C> | |
292 | VectorIteratorBase<C>::VectorIteratorBase(size_t aPos, C &container) : pos(aPos), theVector(&container) {} | |
293 | ||
294 | template<class C> | |
295 | bool VectorIteratorBase<C>:: operator != (VectorIteratorBase const &rhs) | |
296 | { | |
297 | assert (theVector); | |
298 | return pos != rhs.pos; | |
299 | } | |
300 | ||
301 | template<class C> | |
302 | bool VectorIteratorBase<C>:: operator == (VectorIteratorBase const &rhs) | |
303 | { | |
304 | assert (theVector); | |
305 | return pos == rhs.pos; | |
306 | } | |
307 | ||
308 | template<class C> | |
75faaa7a | 309 | bool |
ec2436ff | 310 | VectorIteratorBase<C>::incrementable() const |
311 | { | |
312 | assert (theVector); | |
313 | return pos != theVector->size(); | |
314 | } | |
315 | ||
316 | template<class C> | |
317 | VectorIteratorBase<C> & VectorIteratorBase<C>:: operator ++() | |
318 | { | |
319 | assert (theVector); | |
75faaa7a | 320 | |
ec2436ff | 321 | if (!incrementable()) |
75faaa7a | 322 | fatal ("domain error"); |
323 | ||
ec2436ff | 324 | ++pos; |
75faaa7a | 325 | |
ec2436ff | 326 | return *this; |
327 | } | |
328 | ||
329 | template<class C> | |
330 | VectorIteratorBase<C> VectorIteratorBase<C>:: operator ++(int) | |
331 | { | |
332 | VectorIteratorBase result(*this); | |
333 | ++*this; | |
334 | return result; | |
335 | } | |
336 | ||
ec2436ff | 337 | template<class C> |
338 | VectorIteratorBase<C>& | |
75faaa7a | 339 | VectorIteratorBase<C>::operator =(VectorIteratorBase const &old) |
340 | { | |
ec2436ff | 341 | pos = old.pos; |
342 | theVector = old.theVector; | |
343 | return *this; | |
344 | } | |
345 | ||
346 | template<class C> | |
347 | ssize_t | |
348 | VectorIteratorBase<C>::operator - (VectorIteratorBase const &rhs) const | |
349 | { | |
350 | assert(theVector == rhs.theVector); | |
351 | return pos - rhs.pos; | |
352 | } | |
f12361a1 | 353 | |
b5638623 | 354 | #endif /* SQUID_ARRAY_H */ |