vector.h

   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.h,v 1.4 2002/10/27 16:04:42 rich Exp $
  19  */
  20
  21 #ifndef VECTOR_H
  22 #define VECTOR_H
  23
  24 #include <pool.h>
  25
  26 struct vector
  27 {
  28   pool pool;
  29   size_t size;
  30   void *data;
  31   int used, allocated;
  32 };
  33
  34 typedef struct vector *vector;
  35
  36 /* Function: new_vector - allocate a new vector
  37  * Function: _vector_new
  38  *
  39  * Allocate a new vector in @code{pool} of type @code{type}. The
  40  * first form is just a macro which evaluates the size of @code{type}.
  41  * The second form creates a vector with elements of the given
  42  * @code{size} directly.
  43  */
  44 #define new_vector(pool,type) _vector_new ((pool), sizeof (type))
  45 extern vector _vector_new (pool, size_t size);
  46
  47 /* Function: copy_vector - copy a vector
  48  * Function: new_subvector
  49  *
  50  * Copy a vector @code{v} into pool @code{pool}. If the vector
  51  * contains pointers, then this function will not copy the pointed-to
  52  * data as well: you will need to copy this yourself if appropriate.
  53  *
  54  * @code{new_subvector} creates a copy of part of an existing vector.
  55  * The new vector contains the @code{j-i} elements of the old vector
  56  * starting at element number @code{i} and finishing at element number
  57  * @code{j-1}.
  58  */
  59 extern vector copy_vector (pool, vector v);
  60 extern vector new_subvector (pool, vector v, int i, int j);
  61
  62 /* Function: vector_push_back - push and pop objects into and out of vectors
  63  * Function: _vector_push_back
  64  * Function: vector_pop_back
  65  * Function: _vector_pop_back
  66  * Function: vector_push_front
  67  * Function: _vector_push_front
  68  * Function: vector_pop_front
  69  * Function: _vector_pop_front
  70  *
  71  * The @code{*_push_*} functions push objects onto vectors.
  72  *
  73  * The @code{*_pop_*} functions pop objects off vectors into local variables.
  74  *
  75  * The @code{*_front} functions push and pop objects off the front
  76  * of a vector. This type of operation is not very efficient, because
  77  * it involves moving all other elements of the vector up or down
  78  * by one place.
  79  *
  80  * The @code{*_back} functions push and pop elements
  81  * off the end of the vector, which is efficient.
  82  *
  83  * Each function has two forms: a macro version and an underlying
  84  * function.
  85  *
  86  * Array indexes are checked. You cannot pop an empty vector. If
  87  * @code{ptr} is @code{NULL} then the popped object is discarded.
  88  */
  89 #define vector_push_back(v,obj) _vector_push_back((v),&(obj))
  90 extern void _vector_push_back (vector, const void *ptr);
  91 #define vector_pop_back(v,obj) _vector_pop_back((v),&(obj))
  92 extern void _vector_pop_back (vector, void *ptr);
  93 #define vector_push_front(v,obj) _vector_push_front((v),&(obj))
  94 extern void _vector_push_front (vector, const void *ptr);
  95 #define vector_pop_front(v,obj) _vector_pop_front((v),&(obj))
  96 extern void _vector_pop_front (vector, void *ptr);
  97
  98 /* Function: vector_push_back_vector - push list of objects on to vector
  99  * Function: vector_push_front_vector
 100  *
 101  * @code{vector_push_back_vector} appends the elements of vector
 102  * @code{w} on to the end of vector @code{v}.
 103  *
 104  * @code{vector_push_front_vector} prepends the elements of vector
 105  * @code{w} on to the front of vector @code{v}.
 106  *
 107  * In both cases, vector @code{w} is left unchanged.
 108  *
 109  * See also: @ref{vector_push_back(3)}, @ref{vector_push_front(3)}.
 110  */
 111 extern void vector_push_back_vector (vector v, const vector w);
 112 extern void vector_push_front_vector (vector v, const vector w);
 113
 114 /* Function: vector_get - array-style indexing for vectors
 115  * Function: _vector_get
 116  * Function: vector_get_ptr
 117  * Function: _vector_get_ptr
 118  *
 119  * @code{vector_get} copies the element at index @code{v[i]} into
 120  * local variable @code{obj}. The vector is unaffected.
 121  *
 122  * @code{_vector_get} copies the element into the memory pointed
 123  * to by @code{ptr}. If @code{ptr} is @code{NULL} then the effect
 124  * is simply to check that element @code{v[i]} exists.
 125  *
 126  * @code{vector_get_ptr} and @code{_vector_get_ptr} are used to
 127  * get a pointer to an element in the vector. This pointer actually
 128  * points to the vector's internal data array. It is only valid
 129  * as long as the user does not cause the internal data array to
 130  * be reallocated or moved - typically this can happen when the
 131  * user performs some operation which inserts more elements into
 132  * the array.
 133  *
 134  * Array indexes are checked. An attempt to access an out-of-bounds
 135  * element will result in a call to @ref{abort(3)}.
 136  */
 137 #define vector_get(v,i,obj) _vector_get((v),(i),&(obj))
 138 extern void _vector_get (vector, int i, void *ptr);
 139 #define vector_get_ptr(v,i,ptr) (ptr) =((typeof (ptr))_vector_get_ptr((v),(i)))
 140 extern const void *_vector_get_ptr (vector, int i);
 141
 142 /* Function: vector_insert - insert elements into a vector
 143  * Function: _vector_insert
 144  * Function: vector_insert_array
 145  *
 146  * @code{vector_insert} inserts a single object @code{obj} before element
 147  * @code{i}. All other elements are moved up to make space.
 148  *
 149  * @code{vector_insert_array} inserts an array of @code{n} objects
 150  * starting at address @code{ptr} into the vector before index
 151  * @code{i}.
 152  *
 153  * Array indexes are checked.
 154  */
 155 #define vector_insert(v,i,obj) _vector_insert((v),(i),&(obj))
 156 extern void _vector_insert (vector, int i, const void *ptr);
 157 extern void vector_insert_array (vector v, int i, const void *ptr, int n);
 158
 159 /* Function: vector_replace - replace elements of a vector
 160  * Function: _vector_replace
 161  * Function: vector_replace_array
 162  *
 163  * @code{vector_replace} replaces the single element at
 164  * @code{v[i]} with object @code{obj}.
 165  *
 166  * @code{vector_replace_array} replaces the @code{n} elements
 167  * in the vector starting at index @code{i} with the @code{n}
 168  * elements from the array @code{ptr}.
 169  *
 170  * Array indexes are checked.
 171  */
 172 #define vector_replace(v,i,obj) _vector_replace((v),(i),&(obj))
 173 extern void _vector_replace (vector, int i, const void *ptr);
 174 extern void vector_replace_array (vector v, int i, const void *ptr, int n);
 175
 176 /* Function: vector_erase - erase elements of a vector
 177  * Function: vector_erase_range
 178  * Function: vector_clear
 179  *
 180  * @code{vector_erase} removes the element @code{v[i]}, shuffling
 181  * the later elements down by one place to fill the space.
 182  *
 183  * @code{vector_erase_range} removes a range of elements @code{v[i]}
 184  * to @code{v[j-1]} (@code{i <= j}), shuffling later elements down
 185  * to fill the space.
 186  *
 187  * @code{vector_clear} removes all elements from the vector, setting
 188  * its size to @code{0}.
 189  *
 190  * Array indexes are checked.
 191  */
 192 extern void vector_erase (vector v, int i);
 193 extern void vector_erase_range (vector v, int i, int j);
 194 extern void vector_clear (vector v);
 195
 196 /* Function: vector_fill - fill a vector with identical elements
 197  * Function: _vector_fill
 198  *
 199  * @code{vector_fill} appends @code{n} identical copies of
 200  * @code{obj} to the vector. It is equivalent to calling
 201  * @ref{vector_push_back(3)} in a loop @code{n} times.
 202  */
 203 #define vector_fill(v,obj,n) _vector_fill((v),&(obj),(n))
 204 extern void _vector_fill (vector, const void *ptr, int n);
 205
 206 /* Function: vector_size - return the size of a vector
 207  *
 208  * Return the size (ie. number of elements) in the vector.
 209  */
 210 #define vector_size(v) ((v)->used)
 211
 212 /* Function: vector_allocated - return the space allocated to a vector
 213  *
 214  * Return the amount of space which has been allocated for storing
 215  * elements of the vector. This is different from the number of
 216  * elements actually stored by the vector (see @ref{vector_size(3)})
 217  * and also different from the size of each element in bytes
 218  * (see @ref{vector_element_size(3)}).
 219  */
 220 #define vector_allocated(v) ((v)->allocated)
 221
 222 /* Function: vector_element_size - return the size of each element of a vector
 223  *
 224  * Return the size in bytes of each element in vector.
 225  */
 226 #define vector_element_size(v) ((v)->size)
 227
 228 /* Function: vector_reallocate - change allocation for a vector
 229  *
 230  * Increase the amount of space allocated to a vector. See also
 231  * @ref{vector_allocated(3)}. This function can be used to avoid
 232  * the vector itself making too many calls to the underlying
 233  * @ref{prealloc(3)}, particularly if you know in advance exactly
 234  * how many elements the vector will contain.
 235  */
 236 extern void vector_reallocate (vector v, int n);
 237
 238 /* Function: vector_grep - produce a new vector containing elements of the old vector which match a boolean function
 239  *
 240  * This macro calls @code{match_fn(&t)} for each element @code{t} of
 241  * vector @code{v}. It constructs and returns a new vector containing
 242  * all those elements where the function returns true.
 243  */
 244 extern vector vector_grep (pool, vector v, int (*match_fn) (const void *));
 245
 246 /* Function: vector_grep_pool - produce a new vector containing elements of the old vector which match a boolean function
 247  *
 248  * This macro calls @code{match_fn(pool, &t)} for each element @code{t} of
 249  * vector @code{v}. It constructs and returns a new vector containing
 250  * all those elements where the function returns true.
 251  */
 252 extern vector vector_grep_pool (pool, vector v, int (*match_fn) (pool, const void *));
 253
 254 /* Function: vector_map - apply function to each element of a vector
 255  * Function: _vector_map
 256  *
 257  * Call @code{map_fn(&t, &r)} for each element @code{t} of vector @code{v}.
 258  * The result (@code{r}) should have type @code{result_type}
 259  * and these are concatenated to form a new vector which is returned.
 260  */
 261 #define vector_map(pool,v,map_fn,result_type) _vector_map ((pool), (v), (map_fn), sizeof (result_type))
 262 extern vector _vector_map (pool, vector v, void (*map_fn) (const void *, void *), size_t result_size);
 263
 264 /* Function: vector_map_pool - apply function to each element of a vector
 265  * Function: _vector_map_pool
 266  *
 267  * Call @code{map_fn(pool, &t, &r)} for each element @code{t} of vector
 268  * @code{v}. The result (@code{r}) should have type @code{result_type}
 269  * and these are concatenated to form a new vector which is returned.
 270  */
 271 #define vector_map_pool(pool,v,map_fn,result_type) _vector_map_pool ((pool), (v), (map_fn), sizeof (result_type))
 272 extern vector _vector_map_pool (pool, vector v, void (*map_fn_pool) (pool, const void *, void *), size_t result_size);
 273
 274 /* Function: vector_sort - sort a vector in-place
 275  * Function: _vector_sort
 276  *
 277  * Sort a vector in-place, comparing elements using @code{compare_fn}.
 278  */
 279 #define vector_sort(v,compare_fn) _vector_sort ((v), (int (*)(const void *,const void *)) (compare_fn))
 280 extern void _vector_sort (vector v, int (*compare_fn) (const void *, const void *));
 281
 282 /* Function: vector_compare - compare two vectors
 283  * Function: _vector_compare
 284  *
 285  * Compare two vectors. This returns 0 if the two vectors are
 286  * identical. It returns > 0 if @code{v1} > @code{v2}. This
 287  * returns < 0 if @code{v1} < @code{v2}.
 288  */
 289 #define vector_compare(v1,v2,compare_fn) _vector_compare ((v1), (v2), (int (*)(const void *,const void *)) (compare_fn))
 290 extern int _vector_compare (vector, vector, int (*compare_fn) (const void *, const void *));
 291
 292 /* Function: vector_reverse - reverse the elements of a vector in-place
 293  *
 294  * Reverse the elements of a vector in-place.
 295  */
 296 extern void vector_reverse (vector v);
 297
 298 /* Function: vector_swap - swap two elements of a vector
 299  *
 300  * Swap elements @code{i} and @code{j} of vector @code{v}.
 301  */
 302 extern void vector_swap (vector v, int i, int j);
 303
 304 #endif /* VECTOR_H */