ApacheTrafficServer: Vec.h Source File

Go to the documentation of this file.
00001 /** @file
00002 
00003   Vector and Set templates with qsort.
00004 
00005   @section license License
00006 
00007   Licensed to the Apache Software Foundation (ASF) under one
00008   or more contributor license agreements.  See the NOTICE file
00009   distributed with this work for additional information
00010   regarding copyright ownership.  The ASF licenses this file
00011   to you under the Apache License, Version 2.0 (the
00012   "License"); you may not use this file except in compliance
00013   with the License.  You may obtain a copy of the License at
00014 
00015       http://www.apache.org/licenses/LICENSE-2.0
00016 
00017   Unless required by applicable law or agreed to in writing, software
00018   distributed under the License is distributed on an "AS IS" BASIS,
00019   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00020   See the License for the specific language governing permissions and
00021   limitations under the License.
00022 */
00023 
00024 #ifndef _vec_H_
00025 #define _vec_H_
00026 
00027 #include <string.h>
00028 #include <stdlib.h>
00029 #include <unistd.h>
00030 #include <sys/types.h>
00031 #include "defalloc.h"
00032 #include "ink_assert.h"
00033 
00034 // Simple Vector class, also supports open hashed sets
00035 
00036 #define VEC_INTEGRAL_SHIFT_DEFAULT      2               /* power of 2 (1 << VEC_INTEGRAL_SHIFT)*/
00037 #define VEC_INTEGRAL_SIZE               (1 << (S))
00038 #define VEC_INITIAL_SHIFT               ((S)+1)
00039 #define VEC_INITIAL_SIZE                (1 << VEC_INITIAL_SHIFT)
00040 
00041 #define SET_LINEAR_SIZE         4               /* must be <= than VEC_INTEGRAL_SIZE */
00042 #define SET_INITIAL_INDEX       2
00043 
00044 template <class C, class A = DefaultAlloc, int S = VEC_INTEGRAL_SHIFT_DEFAULT>  // S must be a power of 2
00045 class Vec {
00046  public:
00047   size_t        n;
00048   size_t        i;      // size index for sets, reserve for vectors
00049   C             *v;
00050   C             e[VEC_INTEGRAL_SIZE];
00051   
00052   Vec();
00053   Vec<C,A,S>(const Vec<C,A,S> &vv);
00054   Vec<C,A,S>(const C c);
00055   ~Vec();
00056 
00057   C &operator[](int i) const { return v[i]; }
00058 
00059   C get(size_t i);
00060   void add(C a);  
00061   void push_back(C a) { add(a); } // std::vector name
00062   bool add_exclusive(C a);
00063   C& add();
00064   C pop();
00065   void reset();
00066   void clear();
00067   void free_and_clear();
00068   void delete_and_clear();
00069   void set_clear();
00070   C *set_add(C a);
00071   void set_remove(C a); // expensive, use BlockHash for cheaper remove
00072   C *set_add_internal(C a);
00073   bool set_union(Vec<C,A,S> &v);
00074   int set_intersection(Vec<C,A,S> &v);
00075   int some_intersection(Vec<C,A,S> &v);
00076   int some_disjunction(Vec<C,A,S> &v);
00077   int some_difference(Vec<C,A,S> &v);
00078   void set_intersection(Vec<C,A,S> &v, Vec<C,A,S> &result);
00079   void set_disjunction(Vec<C,A,S> &v, Vec<C,A,S> &result);
00080   void set_difference(Vec<C,A,S> &v, Vec<C,A,S> &result);
00081   size_t set_count() const;
00082   size_t count() const;
00083   C *in(C a);
00084   C *set_in(C a);
00085   C first_in_set();
00086   C *set_in_internal(C a);
00087   void set_expand();
00088   ssize_t index(C a) const;
00089   void set_to_vec();
00090   void vec_to_set();
00091   void move(Vec<C,A,S> &v);
00092   void copy(const Vec<C,A,S> &v);
00093   void fill(size_t n);
00094   void append(const Vec<C> &v);
00095   template <typename CountType> void append(const C * src, CountType count);
00096   void prepend(const Vec<C> &v);
00097   void remove_index(int index);
00098   void remove(C a) { int i = index(a); if (i>=0) remove_index(i); }
00099   C& insert(size_t index);
00100   void insert(size_t index, Vec<C> &vv);
00101   void insert(size_t index, C a);
00102   void push(C a) { insert(0, a); }
00103   void reverse();
00104   void reserve(size_t n);
00105   C* end() const { return v + n; }
00106   C &first() const { return v[0]; }
00107   C &last() const { return v[n-1]; }
00108   Vec<C,A,S>& operator=(Vec<C,A,S> &v) { this->copy(v); return *this; }
00109   unsigned length () const { return n; }
00110   // vector::size() intentionally not implemented because it should mean "bytes" not count of elements
00111   int write(int fd);
00112   int read(int fd);
00113   void qsort(bool (*lt)(C,C));
00114   
00115 private:
00116   void move_internal(Vec<C,A,S> &v);
00117   void copy_internal(const Vec<C,A,S> &v);
00118   void add_internal(C a);
00119   C& add_internal();
00120   void addx();
00121 };
00122 
00123 // c -- class, p -- pointer to elements of v, v -- vector
00124 #define forv_Vec(_c, _p, _v) if ((_v).n) for (_c *qq__##_p = (_c*)0, *_p = (_v).v[0]; \
00125                     ((uintptr_t)(qq__##_p) < (_v).length()) && ((_p = (_v).v[(intptr_t)qq__##_p]) || 1); qq__##_p = (_c*)(((intptr_t)qq__##_p) + 1))
00126 #define for_Vec(_c, _p, _v) if ((_v).n) for (_c *qq__##_p = (_c*)0, _p = (_v).v[0]; \
00127                     ((uintptr_t)(qq__##_p) < (_v).length()) && ((_p = (_v).v[(intptr_t)qq__##_p]) || 1); qq__##_p = (_c*)(((intptr_t)qq__##_p) + 1))
00128 #define forvp_Vec(_c, _p, _v) if ((_v).n) for (_c *qq__##_p = (_c*)0, *_p = &(_v).v[0]; \
00129                     ((uintptr_t)(qq__##_p) < (_v).length()) && ((_p = &(_v).v[(intptr_t)qq__##_p]) || 1); qq__##_p = (_c*)(((intptr_t)qq__##_p) + 1))
00130 
00131 template <class C, class A = DefaultAlloc, int S = VEC_INTEGRAL_SHIFT_DEFAULT> class Accum { public:
00132   Vec<C,A,S> asset;
00133   Vec<C,A,S> asvec;
00134   void add(C c) { if (asset.set_add(c)) asvec.add(c); }
00135   void add(Vec<C,A,S> v) { for (int i = 0; i < v.n; i++) if (v.v[i]) add(v.v[i]); }
00136   void clear() { asset.clear(); asvec.clear(); }
00137 };
00138 
00139 // Intervals store sets in interval format (e.g. [1..10][12..12]).
00140 // Inclusion test is by binary search on intervals.
00141 // Deletion is not supported
00142 class Intervals : public Vec<int> {
00143  public:
00144   void insert(int n);
00145   bool in(int n) const;
00146 };
00147 
00148 // UnionFind supports fast unify and finding of
00149 // 'representitive elements'.
00150 // Elements are numbered from 0 to N-1.
00151 class UnionFind : public Vec<int> {
00152  public:
00153   // set number of elements, initialized to singletons, may be called repeatedly to increase size
00154   void size(int n); 
00155   // return representitive element
00156   int find(int n);
00157   // unify the sets containing the two elements
00158   void unify(int n, int m);
00159 };
00160 
00161 extern const uintptr_t prime2[];
00162 extern const uintptr_t open_hash_primes[256];
00163 
00164 /* IMPLEMENTATION */
00165 
00166 template <class C, class A, int S> inline
00167 Vec<C,A,S>::Vec() : n(0), i(0), v(0) {
00168   memset(&e[0], 0, sizeof(e));
00169 }
00170 
00171 template <class C, class A, int S> inline
00172 Vec<C,A,S>::Vec(const Vec<C,A,S> &vv) {
00173   copy(vv);
00174 }
00175 
00176 template <class C, class A, int S> inline
00177 Vec<C,A,S>::Vec(C c) {
00178   n = 1;
00179   i = 0;
00180   v = &e[0];
00181   e[0] = c;
00182 }
00183 
00184 template <class C, class A, int S> inline C
00185 Vec<C,A,S>::get(size_t i) {
00186   if (i < n && i >= 0)
00187     return v[i];
00188   else
00189     return C();
00190 }
00191 
00192 template <class C, class A, int S> inline void 
00193 Vec<C,A,S>::add(C a) {
00194   if (n & (VEC_INTEGRAL_SIZE-1))
00195     v[n++] = a;
00196   else if (!v)
00197     (v = e)[n++] = a;
00198   else
00199     add_internal(a);
00200 }
00201 
00202 template <class C, class A, int S> inline C&
00203 Vec<C,A,S>::add() {
00204   C *ret;
00205   if (n & (VEC_INTEGRAL_SIZE-1))
00206     ret = &v[n++];
00207   else if (!v)
00208     ret = &(v = e)[n++];
00209   else
00210     ret = &add_internal();
00211   return *ret;
00212 }
00213 
00214 template <class C, class A, int S> inline C
00215 Vec<C,A,S>::pop() {
00216   if (!n)
00217     return 0;
00218   n--;
00219   C ret = v[n];
00220   if (!n)
00221     clear();
00222   return ret;
00223 }
00224 
00225 template <class C, class A, int S> inline void
00226 Vec<C,A,S>::set_clear() {
00227   memset(v, 0, n * sizeof(C));
00228 }
00229 
00230 template <class C, class A, int S> inline C *
00231 Vec<C,A,S>::set_add(C a) {
00232   if (n < SET_LINEAR_SIZE) {
00233     for (C *c = v; c < v + n; c++)
00234       if (*c == a)
00235         return 0;
00236     add(a);
00237     return &v[n-1];
00238   }
00239   if (n == SET_LINEAR_SIZE) {
00240     Vec<C,A,S> vv(*this);
00241     clear();
00242     for (C *c = vv.v; c < vv.v + vv.n; c++) {
00243       set_add_internal(*c);
00244     }
00245   }
00246   return set_add_internal(a);
00247 }
00248 
00249 template <class C, class A, int S> void
00250 Vec<C,A,S>::set_remove(C a) {
00251   Vec<C,A,S> tmp;
00252   tmp.move(*this);
00253   for (C *c = tmp.v; c < tmp.v + tmp.n; c++)
00254     if (*c != a)
00255       set_add(a);
00256 }
00257 
00258 template <class C, class A, int S> inline size_t
00259 Vec<C,A,S>::count() const {
00260   int x = 0;
00261   for (C *c = v; c < v + n; c++)
00262     if (*c)
00263       x++;
00264   return x;
00265 }
00266 
00267 template <class C, class A, int S> inline C*
00268 Vec<C,A,S>::in(C a) {
00269   for (C *c = v; c < v + n; c++)
00270     if (*c == a)
00271       return c;
00272   return NULL;
00273 }
00274 
00275 template <class C, class A, int S> inline bool
00276 Vec<C,A,S>::add_exclusive(C a) {
00277   if (!in(a)) {
00278     add(a);
00279     return true;
00280   } else 
00281     return false;
00282 }
00283 
00284 template <class C, class A, int S> inline C *
00285 Vec<C,A,S>::set_in(C a) {
00286   if (n <= SET_LINEAR_SIZE)
00287     return in(a);
00288   return set_in_internal(a);
00289 }
00290 
00291 template <class C, class A, int S> inline C
00292 Vec<C,A,S>::first_in_set() {
00293   for (C *c = v; c < v + n; c++)
00294     if (*c)
00295       return *c;
00296   return 0;
00297 }
00298 
00299 template <class C, class A, int S> inline ssize_t
00300 Vec<C,A,S>::index(C a) const {
00301   for (C *c = v; c < v + n; c++) {
00302     if (*c == a) {
00303       return c - v;
00304     }
00305   }
00306   return -1;
00307 }
00308 
00309 template <class C, class A, int S> inline void 
00310 Vec<C,A,S>::move_internal(Vec<C,A,S> &vv)  {
00311   n = vv.n;
00312   i = vv.i;
00313   if (vv.v == &vv.e[0]) { 
00314     memcpy(e, &vv.e[0], sizeof(e));
00315     v = e;
00316   } else
00317     v = vv.v;
00318 }
00319 
00320 template <class C, class A, int S> inline void 
00321 Vec<C,A,S>::move(Vec<C,A,S> &vv)  {
00322   move_internal(vv); 
00323   vv.v = 0;
00324   vv.clear();
00325 }
00326 
00327 template <class C, class A, int S> inline void 
00328 Vec<C,A,S>::copy(const Vec<C,A,S> &vv)  {
00329   n = vv.n;
00330   i = vv.i;
00331   if (vv.v == &vv.e[0]) { 
00332     memcpy(e, &vv.e[0], sizeof(e));
00333     v = e;
00334   } else {
00335     if (vv.v) 
00336       copy_internal(vv);
00337     else
00338       v = 0;
00339   }
00340 }
00341 
00342 template <class C, class A, int S> inline void 
00343 Vec<C,A,S>::fill(size_t nn)  {
00344   for (size_t i = n; i < nn; i++)
00345     add() = 0;
00346 }
00347 
00348 template <class C, class A, int S> inline void
00349 Vec<C,A,S>::append(const Vec<C> &vv)  {
00350   for (C *c = vv.v; c < vv.v + vv.n; c++)
00351     if (*c != 0)
00352       add(*c);
00353 }
00354 
00355 template <class C, class A, int S>
00356 template <typename CountType>
00357 inline void
00358 Vec<C,A,S>::append(const C * src, CountType count)  {
00359   reserve(length() + count);
00360   for (CountType c = 0; c < count; ++c) {
00361     add(src[c]);
00362   }
00363 }
00364 
00365 template <class C, class A, int S> inline void
00366 Vec<C,A,S>::prepend(const Vec<C> &vv)  {
00367   if (vv.n) {
00368     int oldn = n;
00369     fill(n + vv.n);
00370     if (oldn)
00371       memmove(&v[vv.n], &v[0], oldn * sizeof(v[0]));
00372     memcpy(&v[0], vv.v, vv.n * sizeof(v[0]));
00373   }
00374 }
00375 
00376 template <class C, class A, int S> void 
00377 Vec<C,A,S>::add_internal(C a) {
00378   addx();
00379   v[n++] = a;
00380 }
00381 
00382 template <class C, class A, int S> C&
00383 Vec<C,A,S>::add_internal() {
00384   addx();
00385   return v[n++];
00386 }
00387 
00388 template <class C, class A, int S> C *
00389 Vec<C,A,S>::set_add_internal(C c) {
00390   size_t j, k;
00391   if (n) {
00392     uintptr_t h = (uintptr_t)c;
00393     h = h % n;
00394     for (k = h, j = 0; j < i + 3; j++) {
00395       if (!v[k]) {
00396         v[k] = c;
00397         return &v[k];
00398       } else if (v[k] == c) {
00399         return 0;
00400       }
00401       k = (k + open_hash_primes[j]) % n;
00402     }
00403   }
00404   Vec<C,A,S> vv;
00405   vv.move_internal(*this);
00406   set_expand();
00407   if (vv.v) {
00408     set_union(vv);
00409   }
00410   return set_add(c);
00411 }
00412 
00413 template <class C, class A, int S> C *
00414 Vec<C,A,S>::set_in_internal(C c) {
00415   size_t j, k;
00416   if (n) {
00417     uintptr_t h = (uintptr_t)c;
00418     h = h % n;
00419     for (k = h, j = 0; j < i + 3; j++) {
00420       if (!v[k])
00421         return 0;
00422       else if (v[k] == c)
00423         return &v[k];
00424       k = (k + open_hash_primes[j]) % n;
00425     }
00426   }
00427   return 0;
00428 }
00429 
00430 template <class C, class A, int S> bool
00431 Vec<C,A,S>::set_union(Vec<C,A,S> &vv) {
00432   bool changed = false;
00433   for (size_t i = 0; i < vv.n; i++) {
00434     if (vv.v[i]) {
00435       changed = set_add(vv.v[i]) || changed;
00436     }
00437   }
00438   return changed;
00439 } 
00440 
00441 template <class C, class A, int S> int
00442 Vec<C,A,S>::set_intersection(Vec<C,A,S> &vv) {
00443   Vec<C,A,S> tv;
00444   tv.move(*this);
00445   int changed = 0;
00446   for (int i = 0; i < tv.n; i++)
00447     if (tv.v[i]) {
00448       if (vv.set_in(tv.v[i]))
00449         set_add(tv.v[i]);
00450       else
00451         changed = 1;
00452     }
00453   return changed;
00454 } 
00455 
00456 template <class C, class A, int S> int
00457 Vec<C,A,S>::some_intersection(Vec<C,A,S> &vv) {
00458   for (int i = 0; i < n; i++)
00459     if (v[i])
00460       if (vv.set_in(v[i]))
00461         return 1;
00462   return 0;
00463 } 
00464 
00465 template <class C, class A, int S> int
00466 Vec<C,A,S>::some_disjunction(Vec<C,A,S> &vv) {
00467   for (int i = 0; i < n; i++)
00468     if (v[i])
00469       if (!vv.set_in(v[i]))
00470         return 1;
00471   for (int i = 0; i < vv.n; i++)
00472     if (vv.v[i])
00473       if (!set_in(vv.v[i]))
00474         return 1;
00475   return 0;
00476 } 
00477 
00478 template <class C, class A, int S> void
00479 Vec<C,A,S>::set_intersection(Vec<C,A,S> &vv, Vec<C,A,S> &result) {
00480   for (int i = 0; i < n; i++)
00481     if (v[i])
00482       if (vv.set_in(v[i]))
00483         result.set_add(v[i]);
00484 } 
00485 
00486 template <class C, class A, int S> void
00487 Vec<C,A,S>::set_disjunction(Vec<C,A,S> &vv, Vec<C,A,S> &result) {
00488   for (int i = 0; i < n; i++)
00489     if (v[i])
00490       if (!vv.set_in(v[i]))
00491         result.set_add(v[i]);
00492   for (int i = 0; i < vv.n; i++)
00493     if (vv.v[i])
00494       if (!set_in(vv.v[i]))
00495         result.set_add(vv.v[i]);
00496 } 
00497 
00498 template <class C, class A, int S> void
00499 Vec<C,A,S>::set_difference(Vec<C,A,S> &vv, Vec<C,A,S> &result) {
00500   for (int i = 0; i < n; i++)
00501     if (v[i])
00502       if (!vv.set_in(v[i]))
00503         result.set_add(v[i]);
00504 } 
00505 
00506 template <class C, class A, int S> int
00507 Vec<C,A,S>::some_difference(Vec<C,A,S> &vv) {
00508   for (int i = 0; i < n; i++)
00509     if (v[i])
00510       if (!vv.set_in(v[i]))
00511         return 1;
00512   return 0;
00513 } 
00514 
00515 template <class C, class A, int S> size_t
00516 Vec<C,A,S>::set_count() const {
00517   size_t x = 0;
00518   for (size_t i = 0; i < n; i++) {
00519     if (v[i]) {
00520       x++;
00521     }
00522   }
00523   return x;
00524 } 
00525 
00526 template <class C, class A, int S> void
00527 Vec<C,A,S>::set_to_vec() {
00528   C *x = &v[0], *y = x;
00529   for (; y < v + n; y++) {
00530     if (*y) {
00531       if (x != y)
00532          *x = *y;
00533        x++;
00534     }
00535   }
00536   if (i) {
00537     i = prime2[i];  // convert set allocation to reserve
00538     if (i - n > 0)
00539       memset(&v[n], 0, (i - n) * (sizeof(C)));
00540   } else {
00541     i = 0;
00542     if (v == &e[0] && VEC_INTEGRAL_SIZE - n > 0)
00543       memset(&v[n], 0, (VEC_INTEGRAL_SIZE - n) * (sizeof(C)));
00544   }
00545 }
00546 
00547 template <class C, class A, int S> void
00548 Vec<C,A,S>::vec_to_set() {
00549   Vec<C,A,S> vv;
00550   vv.move(*this);
00551   for (C *c = vv.v; c < vv.v + vv.n; c++)
00552     set_add(*c);
00553 }
00554 
00555 template <class C, class A, int S> void 
00556 Vec<C,A,S>::remove_index(int index) {
00557   if (n > 1)
00558     memmove(&v[index], &v[index+1], (n - 1 - index) * sizeof(v[0]));
00559   n--;
00560   if (n <= 0)
00561     v = e;
00562 }
00563 
00564 template <class C, class A, int S> void
00565 Vec<C,A,S>::insert(size_t index, C a) {
00566   add();
00567   memmove(&v[index+1], &v[index], (n - index - 1) * sizeof(C));
00568   v[index] = a;
00569 }
00570 
00571 template <class C, class A, int S> void
00572 Vec<C,A,S>::insert(size_t index, Vec<C> &vv) {
00573   fill(n + vv.n);
00574   memmove(&v[index+vv.n], &v[index], (n - index - 1) * sizeof(C));
00575   for (int x = 0; x < vv.n; x++)
00576     v[index + x] = vv[x];
00577 }
00578 
00579 template <class C, class A, int S>  C &
00580 Vec<C,A,S>::insert(size_t index) {
00581   add();
00582   memmove(&v[index+1], &v[index], (n - index - 1) * sizeof(C));
00583   memset(&v[index], 0, sizeof(C));
00584   return v[index];
00585 }
00586 
00587 template <class C, class A, int S> void 
00588 Vec<C,A,S>::reverse() {
00589   for (int i = 0; i < n/2; i++) {
00590     C *s = &v[i], *e = &v[n - 1 - i];
00591     C t;
00592     memcpy(&t, s, sizeof(t));
00593     memcpy(s, e, sizeof(t));
00594     memcpy(e, &t, sizeof(t));
00595   }
00596 }
00597 
00598 template <class C, class A, int S> void
00599 Vec<C,A,S>::copy_internal(const Vec<C,A,S> &vv) {
00600   int l = n, nl = (1 + VEC_INITIAL_SHIFT);
00601   l = l >> VEC_INITIAL_SHIFT;
00602   while (l) { l = l >> 1; nl++; }
00603   nl = 1 << nl;
00604   v = (C*)A::alloc(nl * sizeof(C));
00605   memcpy(v, vv.v, n * sizeof(C));
00606   memset(v + n, 0, (nl - n) * sizeof(C)); 
00607   if (i > n)  // reset reserve
00608     i = 0;
00609 }
00610 
00611 template <class C, class A, int S> void
00612 Vec<C,A,S>::set_expand() {
00613   if (!n)
00614     i = SET_INITIAL_INDEX;
00615   else
00616     i = i + 1;
00617   n = prime2[i];
00618   v = (C*)A::alloc(n * sizeof(C));
00619   memset(v, 0, n * sizeof(C));
00620 }
00621 
00622 template <class C, class A, int S> inline void 
00623 Vec<C,A,S>::reserve(size_t x) {
00624   if (x <= n)
00625     return;
00626   unsigned xx = 1 << VEC_INITIAL_SHIFT;
00627   while (xx < x) xx *= 2;
00628   i = xx;
00629   void *vv = (void*)v;
00630   v = (C*)A::alloc(i * sizeof(C));
00631   if (vv && n)
00632     memcpy(v, vv, n * sizeof(C));
00633   memset(&v[n], 0, (i-n) * sizeof(C));
00634   if (vv && vv != e)
00635     A::free(vv);
00636 }
00637 
00638 template <class C, class A, int S> inline void 
00639 Vec<C,A,S>::addx() {
00640   if (!v) {
00641     v = e;
00642     return;
00643   }
00644   if (v == e) {
00645     v = (C*)A::alloc(VEC_INITIAL_SIZE * sizeof(C));
00646     memcpy(v, &e[0], n * sizeof(C));
00647     ink_assert(n < VEC_INITIAL_SIZE);
00648     memset(&v[n], 0, (VEC_INITIAL_SIZE - n) * sizeof(C));
00649   } else {
00650     if ((n & (n-1)) == 0) {
00651       size_t nl = n * 2;
00652       if (nl <= i) {
00653         return;
00654       } else {
00655         i = 0;
00656       }
00657       void *vv = (void*)v;
00658       v = (C*)A::alloc(nl * sizeof(C));
00659       memcpy(v, vv, n * sizeof(C));
00660       memset(&v[n], 0, n * sizeof(C));
00661       A::free(vv);
00662     }
00663   }
00664 }
00665 
00666 template <class C, class A, int S> inline void
00667 Vec<C,A,S>::reset() {
00668   v = NULL;
00669   n = 0;
00670   i = 0;
00671 }
00672 
00673 template <class C, class A, int S> inline void
00674 Vec<C,A,S>::clear() {
00675   if (v && v != e) A::free(v);
00676   reset();
00677 }
00678 
00679 template <class C, class A, int S> inline void
00680 Vec<C,A,S>::free_and_clear() {
00681   for (int x = 0; x < n; x++)
00682     if (v[x])
00683       A::free(v[x]);
00684   clear();
00685 }
00686 
00687 template <class C, class A, int S> inline void
00688 Vec<C,A,S>::delete_and_clear() {
00689   for (size_t x = 0; x < n; x++) {
00690     if (v[x]) {
00691       delete v[x];
00692     }
00693   }
00694   clear();
00695 }
00696 
00697 template <class C, class A, int S> 
00698 inline Vec<C,A,S>::~Vec() { 
00699   if (v && v != e) A::free(v); 
00700 }
00701 
00702 template <class C, class A, int S> 
00703 inline int marshal_size(Vec<C,A,S> &v) {
00704   int l = sizeof(int) * 2;
00705   for (int x = 0; x < v.n; x++)
00706     l += ::marshal_size(v.v[x]);
00707   return l;
00708 }
00709 
00710 template <class C, class A, int S> 
00711 inline int marshal(Vec<C,A,S> &v, char *buf) {
00712   char *x = buf;
00713   *(int*)x = v.n; x += sizeof(int);
00714   *(int*)x = v.i; x += sizeof(int);
00715   for (int i = 0; i < v.n; i++)
00716     x += ::marshal(v.v[i], x);
00717   return x - buf;
00718 }
00719 
00720 template <class C, class A, int S> 
00721 inline int unmarshal(Vec<C,A,S> &v, char *buf) {
00722   char *x = buf;
00723   v.n = *(int*)x; x += sizeof(int);
00724   v.i = *(int*)x; x += sizeof(int);
00725   if (v.n) {
00726     v.v = (C*)A::alloc(sizeof(C) * v.n);
00727     memset(v.v, 0, sizeof(C) * v.n);
00728   } else
00729     v.v = v.e;
00730   for (int i = 0; i < v.n; i++)
00731     x += ::unmarshal(v.v[i], x);
00732   return x - buf;
00733 }
00734 
00735 template <class C, class A, int S> 
00736 inline int Vec<C,A,S>::write(int fd) {
00737   int r = 0, t = 0;
00738   if ((r = ::write(fd, this, sizeof(*this))) < 0) return r; t += r;
00739   if ((r = ::write(fd, v, n * sizeof(C))) < 0) return r; t += r;
00740   return t;
00741 }
00742 
00743 template <class C, class A, int S> 
00744 inline int Vec<C,A,S>::read(int fd) {
00745   int r = 0, t = 0;
00746   if ((r = ::read(fd, this, sizeof(*this))) < 0) return r; t += r;
00747   v = (C*)A::alloc(sizeof(C) * n);
00748   memset(v, 0, sizeof(C) * n);
00749   if ((r = ::read(fd, v, n * sizeof(C))) < 0) return r; t += r;
00750   return t;
00751 }
00752 
00753 template <class C> 
00754 inline void qsort_Vec(C *left, C *right, bool (*lt)(C,C)) {
00755  Lagain:
00756   if (right - left < 5) {
00757     for (C *y = right - 1; y > left; y--) {
00758       for (C *x = left; x < y; x++) {
00759         if (lt(x[1],x[0])) {
00760           C t = x[0];
00761           x[0] = x[1];
00762           x[1] = t;
00763         }
00764       }
00765     }
00766   } else {
00767     C  *i = left + 1, *j = right - 1;
00768     C x = *left;
00769     for (;;) {
00770       while (lt(x,*j)) j--;
00771       while (i < j && lt(*i,x)) i++;
00772       if (i >= j) break;
00773       C t = *i;
00774       *i = *j;
00775       *j = t;
00776       i++; j--;
00777     }
00778     if (j == right - 1) {
00779       *left = *(right - 1);
00780       *(right - 1) = x;
00781       right--;
00782       goto Lagain;
00783     }
00784     if (left < j) qsort_Vec<C>(left, j + 1, lt);
00785     if (j + 2 < right) qsort_Vec<C>(j + 1, right, lt);
00786   }
00787 }
00788 
00789 template <class C> 
00790 inline void qsort_VecRef(C *left, C *right, bool (*lt)(C&,C&)) {
00791  Lagain:
00792   if (right - left < 5) {
00793     for (C *y = right - 1; y > left; y--) {
00794       for (C *x = left; x < y; x++) {
00795         if (lt(x[1],x[0])) {
00796           C t = x[0];
00797           x[0] = x[1];
00798           x[1] = t;
00799         }
00800       }
00801     }
00802   } else {
00803     C  *i = left + 1, *j = right - 1;
00804     C x = *left;
00805     for (;;) {
00806       while (lt(x,*j)) j--;
00807       while (i < j && lt(*i,x)) i++;
00808       if (i >= j) break;
00809       C t = *i;
00810       *i = *j;
00811       *j = t;
00812       i++; j--;
00813     }
00814     if (j == right - 1) {
00815       *left = *(right - 1);
00816       *(right - 1) = x;
00817       right--;
00818       goto Lagain;
00819     }
00820     if (left < j) qsort_VecRef<C>(left, j + 1, lt);
00821     if (j + 2 < right) qsort_VecRef<C>(j + 1, right, lt);
00822   }
00823 }
00824 
00825 template <class C, class A, int S> 
00826 inline void Vec<C,A,S>::qsort(bool (*lt)(C,C)) {
00827   if (n)
00828     qsort_Vec<C>(&v[0], end(), lt);
00829 }
00830 
00831 void test_vec();
00832 
00833 #endif