2 * By Richard W.M. Jones <rich@annexia.org>
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.
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.
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.
18 * $Id: vector.h,v 1.4 2002/10/27 16:04:42 rich Exp $
34 typedef struct vector *vector;
36 /* Function: new_vector - allocate a new vector
37 * Function: _vector_new
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.
44 #define new_vector(pool,type) _vector_new ((pool), sizeof (type))
45 extern vector _vector_new (pool, size_t size);
47 /* Function: copy_vector - copy a vector
48 * Function: new_subvector
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.
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
59 extern vector copy_vector (pool, vector v);
60 extern vector new_subvector (pool, vector v, int i, int j);
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
71 * The @code{*_push_*} functions push objects onto vectors.
73 * The @code{*_pop_*} functions pop objects off vectors into local variables.
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
80 * The @code{*_back} functions push and pop elements
81 * off the end of the vector, which is efficient.
83 * Each function has two forms: a macro version and an underlying
86 * Array indexes are checked. You cannot pop an empty vector. If
87 * @code{ptr} is @code{NULL} then the popped object is discarded.
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);
98 /* Function: vector_push_back_vector - push list of objects on to vector
99 * Function: vector_push_front_vector
101 * @code{vector_push_back_vector} appends the elements of vector
102 * @code{w} on to the end of vector @code{v}.
104 * @code{vector_push_front_vector} prepends the elements of vector
105 * @code{w} on to the front of vector @code{v}.
107 * In both cases, vector @code{w} is left unchanged.
109 * See also: @ref{vector_push_back(3)}, @ref{vector_push_front(3)}.
111 extern void vector_push_back_vector (vector v, const vector w);
112 extern void vector_push_front_vector (vector v, const vector w);
114 /* Function: vector_get - array-style indexing for vectors
115 * Function: _vector_get
116 * Function: vector_get_ptr
117 * Function: _vector_get_ptr
119 * @code{vector_get} copies the element at index @code{v[i]} into
120 * local variable @code{obj}. The vector is unaffected.
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.
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
134 * Array indexes are checked. An attempt to access an out-of-bounds
135 * element will result in a call to @ref{abort(3)}.
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);
142 /* Function: vector_insert - insert elements into a vector
143 * Function: _vector_insert
144 * Function: vector_insert_array
146 * @code{vector_insert} inserts a single object @code{obj} before element
147 * @code{i}. All other elements are moved up to make space.
149 * @code{vector_insert_array} inserts an array of @code{n} objects
150 * starting at address @code{ptr} into the vector before index
153 * Array indexes are checked.
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);
159 /* Function: vector_replace - replace elements of a vector
160 * Function: _vector_replace
161 * Function: vector_replace_array
163 * @code{vector_replace} replaces the single element at
164 * @code{v[i]} with object @code{obj}.
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}.
170 * Array indexes are checked.
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);
176 /* Function: vector_erase - erase elements of a vector
177 * Function: vector_erase_range
178 * Function: vector_clear
180 * @code{vector_erase} removes the element @code{v[i]}, shuffling
181 * the later elements down by one place to fill the space.
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
187 * @code{vector_clear} removes all elements from the vector, setting
188 * its size to @code{0}.
190 * Array indexes are checked.
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);
196 /* Function: vector_fill - fill a vector with identical elements
197 * Function: _vector_fill
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.
203 #define vector_fill(v,obj,n) _vector_fill((v),&(obj),(n))
204 extern void _vector_fill (vector, const void *ptr, int n);
206 /* Function: vector_size - return the size of a vector
208 * Return the size (ie. number of elements) in the vector.
210 #define vector_size(v) ((v)->used)
212 /* Function: vector_allocated - return the space allocated to a vector
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)}).
220 #define vector_allocated(v) ((v)->allocated)
222 /* Function: vector_element_size - return the size of each element of a vector
224 * Return the size in bytes of each element in vector.
226 #define vector_element_size(v) ((v)->size)
228 /* Function: vector_reallocate - change allocation for a vector
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.
236 extern void vector_reallocate (vector v, int n);
238 /* Function: vector_grep - produce a new vector containing elements of the old vector which match a boolean function
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.
244 extern vector vector_grep (pool, vector v, int (*match_fn) (const void *));
246 /* Function: vector_grep_pool - produce a new vector containing elements of the old vector which match a boolean function
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.
252 extern vector vector_grep_pool (pool, vector v, int (*match_fn) (pool, const void *));
254 /* Function: vector_map - apply function to each element of a vector
255 * Function: _vector_map
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.
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);
264 /* Function: vector_map_pool - apply function to each element of a vector
265 * Function: _vector_map_pool
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.
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);
274 /* Function: vector_sort - sort a vector in-place
275 * Function: _vector_sort
277 * Sort a vector in-place, comparing elements using @code{compare_fn}.
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 *));
282 /* Function: vector_compare - compare two vectors
283 * Function: _vector_compare
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}.
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 *));
292 /* Function: vector_reverse - reverse the elements of a vector in-place
294 * Reverse the elements of a vector in-place.
296 extern void vector_reverse (vector v);
298 /* Function: vector_swap - swap two elements of a vector
300 * Swap elements @code{i} and @code{j} of vector @code{v}.
302 extern void vector_swap (vector v, int i, int j);
304 #endif /* VECTOR_H */