include/Array.h

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