vector.c

   1 /* A vector class.
   2  * - By Richard W.M. Jones <rich@annexia.org>
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public
  15  * License along with this library; if not, write to the Free
  16  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17  *
  18  * $Id: vector.c,v 1.4 2002/10/27 16:04:42 rich Exp $
  19  */
  20
  21 #include "config.h"
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25
  26 #ifdef HAVE_STRING_H
  27 #include <string.h>
  28 #endif
  29
  30 #ifdef HAVE_ASSERT_H
  31 #include <assert.h>
  32 #endif
  33
  34 #include <pstring.h>
  35 #include <pool.h>
  36 #include <vector.h>
  37
  38 #define INCREMENT 16
  39
  40 vector
  41 _vector_new (pool pool, size_t size)
  42 {
  43   vector v = pmalloc (pool, sizeof *v);
  44
  45   v->pool = pool;
  46   v->size = size;
  47   v->data = 0;
  48   v->used = v->allocated = 0;
  49
  50   return v;
  51 }
  52
  53 inline vector
  54 new_subvector (pool pool, vector v, int i, int j)
  55 {
  56   vector new_v = pmalloc (pool, sizeof *v);
  57
  58   assert (0 <= i && j <= v->used);
  59
  60   new_v->pool = pool;
  61   new_v->size = v->size;
  62
  63   if (i < j)
  64     {
  65       new_v->data = pmemdup (pool, v->data + i * v->size, (j - i) * v->size);
  66       new_v->used = new_v->allocated = j - i;
  67     }
  68   else
  69     {
  70       new_v->data = 0;
  71       new_v->used = new_v->allocated = 0;
  72     }
  73
  74   return new_v;
  75 }
  76
  77 vector
  78 copy_vector (pool pool, vector v)
  79 {
  80   return new_subvector (pool, v, 0, v->used);
  81 }
  82
  83 inline void
  84 _vector_push_back (vector v, const void *ptr)
  85 {
  86   if (v->used >= v->allocated)
  87     {
  88       int a = v->allocated + INCREMENT;
  89       void *d = prealloc (v->pool, v->data, a * v->size);
  90       v->allocated = a;
  91       v->data = d;
  92     }
  93
  94   if (ptr) memcpy (v->data + v->used * v->size, ptr, v->size);
  95   v->used++;
  96 }
  97
  98 void
  99 _vector_pop_back (vector v, void *ptr)
 100 {
 101   assert (v->used > 0);
 102   v->used--;
 103   if (ptr) memcpy (ptr, v->data + v->used * v->size, v->size);
 104 }
 105
 106 inline void
 107 vector_insert_array (vector v, int i, const void *ptr, int n)
 108 {
 109   int j;
 110
 111   assert (0 <= i && i <= v->used);
 112
 113   /* Insert n dummy elements at the end of the list. */
 114   for (j = 0; j < n; ++j) _vector_push_back (v, 0);
 115
 116   /* Move the other elements up. */
 117   for (j = v->used-1; j > i; --j)
 118     memcpy (v->data + j * v->size, v->data + (j-n) * v->size, v->size);
 119
 120   /* Insert these elements at position i. */
 121   if (ptr) memcpy (v->data + i * v->size, ptr, v->size * n);
 122 }
 123
 124 void
 125 _vector_insert (vector v, int i, const void *ptr)
 126 {
 127   vector_insert_array (v, i, ptr, 1);
 128 }
 129
 130 void
 131 _vector_push_front (vector v, const void *ptr)
 132 {
 133   _vector_insert (v, 0, ptr);
 134 }
 135
 136 void
 137 _vector_pop_front (vector v, void *ptr)
 138 {
 139   _vector_get (v, 0, ptr);
 140   vector_erase (v, 0);
 141 }
 142
 143 void
 144 vector_push_back_vector (vector v, const vector w)
 145 {
 146   int size = v->size;
 147
 148   assert (size == w->size);
 149
 150   if (v->used + w->used > v->allocated)
 151     {
 152       int a = v->used + w->used;
 153       void *d = prealloc (v->pool, v->data, a * size);
 154       v->allocated = a;
 155       v->data = d;
 156     }
 157
 158   memcpy (v->data + v->used * size, w->data, size * w->used);
 159   v->used += w->used;
 160 }
 161
 162 void
 163 vector_push_front_vector (vector v, const vector w)
 164 {
 165   int size = v->size;
 166
 167   assert (size == w->size);
 168
 169   if (v->used + w->used > v->allocated)
 170     {
 171       int a = v->used + w->used;
 172       void *d = prealloc (v->pool, v->data, a * size);
 173       v->allocated = a;
 174       v->data = d;
 175     }
 176
 177   memmove (v->data + w->used * size, v->data, v->used * size);
 178   memcpy (v->data, w->data, size * w->used);
 179   v->used += w->used;
 180 }
 181
 182 void
 183 _vector_replace (vector v, int i, const void *ptr)
 184 {
 185   assert (0 <= i && i < v->used);
 186
 187   if (ptr) memcpy (v->data + i * v->size, ptr, v->size);
 188 }
 189
 190 inline void
 191 vector_erase_range (vector v, int i, int j)
 192 {
 193   assert (0 <= i && i < v->used && 0 <= j && j <= v->used);
 194
 195   if (i < j)
 196     {
 197       int n = j - i, k;
 198
 199       for (k = i+n; k < v->used; ++k)
 200         memcpy (v->data + (k-n) * v->size, v->data + k * v->size, v->size);
 201
 202       v->used -= n;
 203     }
 204 }
 205
 206 void
 207 vector_erase (vector v, int i)
 208 {
 209   vector_erase_range (v, i, i+1);
 210 }
 211
 212 void
 213 vector_clear (vector v)
 214 {
 215   v->used = 0;
 216 }
 217
 218 void
 219 _vector_get (vector v, int i, void *ptr)
 220 {
 221   assert (0 <= i && i < v->used);
 222   if (ptr) memcpy (ptr, v->data + i * v->size, v->size);
 223 }
 224
 225 const void *
 226 _vector_get_ptr (vector v, int i)
 227 {
 228   assert (0 <= i && i < v->used);
 229   return v->data + i * v->size;
 230 }
 231
 232 void
 233 _vector_sort (vector v, int (*compare_fn) (const void *, const void *))
 234 {
 235   qsort (v->data, v->used, v->size, compare_fn);
 236 }
 237
 238 int
 239 _vector_compare (vector v1, vector v2,
 240                  int (*compare_fn) (const void *, const void *))
 241 {
 242   int i, r;
 243   void *p1, *p2;
 244
 245   if (vector_size (v1) < vector_size (v2)) return -1;
 246   else if (vector_size (v1) > vector_size (v2)) return 1;
 247
 248   for (i = 0; i < vector_size (v1); ++i)
 249     {
 250       vector_get_ptr (v1, i, p1);
 251       vector_get_ptr (v2, i, p2);
 252
 253       r = compare_fn (p1, p2);
 254
 255       if (r != 0) return r;
 256     }
 257
 258   return 0;
 259 }
 260
 261 void
 262 _vector_fill (vector v, const void *ptr, int n)
 263 {
 264   while (n--)
 265     _vector_push_back (v, ptr);
 266 }
 267
 268 void
 269 vector_swap (vector v, int i, int j)
 270 {
 271   void *pi, *pj;
 272   char data[v->size];
 273
 274   if (i == j) return;
 275
 276   vector_get_ptr (v, i, pi);
 277   vector_get_ptr (v, j, pj);
 278
 279   memcpy (data, pi, v->size);
 280   memcpy (pi, pj, v->size);
 281   memcpy (pj, data, v->size);
 282 }
 283
 284 void
 285 vector_reallocate (vector v, int n)
 286 {
 287   if (n > v->allocated)
 288     {
 289       void *d = prealloc (v->pool, v->data, n * v->size);
 290       v->allocated = n;
 291       v->data = d;
 292     }
 293 }
 294
 295 vector
 296 vector_grep (pool p, vector v, int (*match_fn) (const void *))
 297 {
 298   vector nv = _vector_new (p, v->size);
 299   int i;
 300
 301   for (i = 0; i < v->used; ++i)
 302     if (match_fn (v->data + i * v->size))
 303       _vector_push_back (nv, v->data + i * v->size);
 304
 305   return nv;
 306 }
 307
 308 vector
 309 vector_grep_pool (pool p, vector v, int (*match_fn) (pool, const void *))
 310 {
 311   vector nv = _vector_new (p, v->size);
 312   int i;
 313
 314   for (i = 0; i < v->used; ++i)
 315     if (match_fn (p, v->data + i * v->size))
 316       _vector_push_back (nv, v->data + i * v->size);
 317
 318   return nv;
 319 }
 320
 321 vector
 322 _vector_map (pool p, vector v,
 323              void (*map_fn) (const void *, void *),
 324              size_t result_size)
 325 {
 326   vector nv = _vector_new (p, result_size);
 327   int i;
 328
 329   vector_reallocate (nv, v->used);
 330   nv->used = v->used;
 331
 332   for (i = 0; i < v->used; ++i)
 333     map_fn (v->data + i * v->size, nv->data + i * nv->size);
 334
 335   return nv;
 336 }
 337
 338 vector
 339 _vector_map_pool (pool p, vector v,
 340                   void (*map_fn) (pool, const void *, void *),
 341                   size_t result_size)
 342 {
 343   vector nv = _vector_new (p, result_size);
 344   int i;
 345
 346   vector_reallocate (nv, v->used);
 347   nv->used = v->used;
 348
 349   for (i = 0; i < v->used; ++i)
 350     map_fn (p, v->data + i * v->size, nv->data + i * nv->size);
 351
 352   return nv;
 353 }