2 Copyright (C) 2012 Modelon AB
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the BSD style license.
7 This program is distributed in the hope that it will be useful,
8 but WITHOUT ANY WARRANTY; without even the implied warranty of
9 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 FMILIB_License.txt file for more details.
12 You should have received a copy of the FMILIB_License.txt file
13 along with this program. If not, contact Modelon AB <http://www.modelon.com>.
21 #include "jm_callbacks.h"
27 \file jm_vector.h Definition of ::jm_vector and supporting functions
37 \addtogroup jm_vector A vector of items (dynamic array)
41 /** \brief jm_mange macro is used to construct names for the template instances
42 Extra level (jm_mange_ex) is needed to force argument expansion (pre-scan)
44 #define jm_mangle_ex(name, type) name## _ ##type
45 #define jm_mangle(name, type) jm_mangle_ex(name,type)
47 /** \brief jm_vector(T) is the type name (i.e., to be used as jm_vector(int) vi;) */
48 #define jm_vector(T) jm_mangle(jm_vector, T)
51 * \name Vector handling functions.
53 * \brief Allocates a vector on heap with the specified size and specified number of preallocated items (can be larger than size).
55 * extern jm_vector(T)* jm_vector_alloc(T)(size_t size, size_t capacity, jm_callbacks*c );
56 * Note that there is no need to call jm_vector_init for a vector allocated with this function.
57 * @param size - initial size of the vector, can be 0
58 * @param capacity - initial capacity of the vector, can be 0. At least initSize elements are allocated.
59 * @param c - jm_callbacks callbacks, can be zero
60 * @return Newly allocated vector
62 #define jm_vector_alloc(T) jm_mangle(jm_vector_alloc, T)
65 jm_vector_free releases the memory allocated by jm_vector_alloc.
66 extern void jm_vector_free(T)(jm_vector(T)* a);
68 #define jm_vector_free(T) jm_mangle(jm_vector_free, T)
71 * \brief jm_vector_init initializes a vector allocated on stack.
74 * a - pointer to the vector to be initialized;
75 * size - initial size of the vector, can be 0
76 * c - jm_callbacks callbacks, can be zero
78 * size of the vector (can be zero for non-zero size if memory allocation failed)
79 * Note that for initSize < JM_VECTOR_MINIMAL_CAPACITY no heap memory allocation is needed
80 * size_t jm_vector_init(T)(jm_vector(T)* a, size_t initSize, jm_callbacks* c)
82 #define jm_vector_init(T) jm_mangle(jm_vector_init, T)
85 * jm_vector_free_data releases memory allocated for vector data
86 * This only needs to be called for stack allocated vectors
87 * (jm_vector_free does the job for heap vectors automatically)
88 * inline void jm_vector_free_data(T)(jm_vector(T)* a)
90 #define jm_vector_free_data(T) jm_mangle(jm_vector_free_data, T)
93 jm_vector_get_size get the vector size
94 inline size_t jm_vector_get_size(T)(jm_vector(T)* a)
96 #define jm_vector_get_size(T) jm_mangle(jm_vector_get_size, T)
99 jm_vector_get_item returns the specified item. Range checking is done with an assert.
100 inline T jm_vector_get_item(jm_vector(T)* a, size_t index)
102 #define jm_vector_get_item(T) jm_mangle(jm_vector_get_item, T)
105 jm_vector_get_itemp returns a pointer to the specified item. Range checking is done with an assert.
106 inline T* jm_vector_get_itemp(jm_vector(T)* a, size_t index)
108 #define jm_vector_get_itemp(T) jm_mangle(jm_vector_get_itemp, T)
112 jm_vector_get_lastp returns a pointer to the last item in the vector. It is an error to call this if size=0
113 inline T jm_vector_get_last(jm_vector(T)* a)
115 #define jm_vector_get_last(T) jm_mangle(jm_vector_get_last, T)
118 jm_vector_get_lastp returns a pointer to the last item in the vector. Zero pointer is returned if size=0
119 inline T* jm_vector_get_lastp(jm_vector(T)* a)
121 #define jm_vector_get_lastp(T) jm_mangle(jm_vector_get_lastp, T)
124 \brief Function type for item comparison. Can be generated with jm_define_comp_f.
127 typedef int (*jm_compare_ft) (const void* , const void*);
130 \brief A conveniece macro for comparison function definition
132 #define jm_define_comp_f(F, T, COMPAR_OP) is a conveniece macro for comparison function definition to be used in sort/search operations.
133 Here F - is the defined function name;
134 T - type of the argument;
135 COMPAR_OP(A,B) is a macro that returns an integer less than, equal to, or greater than zero if the first argument
136 is considered to be respectively less than, equal to, or greater than the second. If two members compare as
137 equal, their order in the sorted array is undefined.
138 Default definition below is jm_diff and is implemented as (int)(first-second)
140 #define jm_define_comp_f(F, T, COMPAR_OP) \
141 static int F (const void* first, const void* second) { \
142 return COMPAR_OP( (*(T*)first), (*(T*)second)); \
145 #define jm_diff(first, second) (int)(first-second)
148 \brief jm_vector_find functions use linear search to find items in a vector. JM_COMPAR_OP is used for comparison.
150 T* jm_vector_find(T)(jm_vector(T)* a, T item, jm_compare_ft f)
152 size_t jm_vector_find_index(T)(jm_vector(T)* a, T item, jm_compare_ft f)
154 @param a - the vector;
155 @param item - the searched item;
158 T* jm_vector_find(T)(jm_vector(T)* a, T item, jm_compare_ft f) returns a pointer to the found item or NULL if not found
159 size_t jm_vector_find_index(T)(jm_vector(T)* a, T item, jm_compare_ft f) return the index of the found item or size of the vector if not found.
161 #define jm_vector_find(T) jm_mangle(jm_vector_find, T)
162 #define jm_vector_find_index(T) jm_mangle(jm_vector_find_index, T)
165 jm_vector_qsort uses standard quick sort to sort the vector contents.
166 JM_COMPAR_OP is used for comparison.
168 void jm_vector_qsort(T)(jm_vector(T)* v, jm_compare_ft f);
170 #define jm_vector_qsort(T) jm_mangle(jm_vector_qsort, T)
173 jm_vector_bsearch uses standard binary search (bsearch) to find elements in a sorted vector.
174 It returns the index of an item in the vector or vector's size if not found.
175 JM_COMPAR_OP is used for comparison.
177 T* jm_vector_bsearch(T)(jm_vector(T)* v, T* key, jm_compare_ft f)
178 size_t jm_vector_bsearch_index(T)(jm_vector(T)* v, T* key, jm_compare_ft f)
180 #define jm_vector_bsearch(T) jm_mangle(jm_vector_bsearch, T)
181 #define jm_vector_bsearch_index(T) jm_mangle(jm_vector_bsearch_index, T)
184 jm_vector_set_item sets the specified item. Range checking is done with an assert.
185 void jm_vector_set_item(T)(jm_vector(T)* a, size_t index, T item)
187 #define jm_vector_set_item(T) jm_mangle(jm_vector_set_item, T)
190 jm_vector_zero sets all elements in the vector to zero
191 void jm_vector_zero(T)(jm_vector(T)* a);
193 #define jm_vector_zero(T) jm_mangle(jm_vector_zero, T)
196 * jm_vector_resize resizes the vector
201 * size of the vector after operation. Can be less than size if memory allocation failed.
202 * Note: resizing to smaller vector does not release memory.
203 * size_t jm_vector_resize(T)(jm_vector(T)* a, size_t size)
205 #define jm_vector_resize(T) jm_mangle(jm_vector_resize, T)
208 * jm_vector_reserve preallocates memory for the vector (to speed up consequent push_back)
209 * Returns: the actually reserved space. Can be smaller than requested "capacity" if memory allocation failed.
210 * Can be larger than "capacity" if more memory was previously allocated.
211 * size_t jm_vector_reserve(T)(jm_vector(T)* a, size_t capacity)
213 #define jm_vector_reserve(T) jm_mangle(jm_vector_reserve, T)
216 * jm_vector_copy copies source vector into destination.
217 * Returns the number of elements actually copied (may be less than the source size if allocation failed).
218 * size_t jm_vector_copy(T)(jm_vector(T)* destination, jm_vector(T)* source)
220 #define jm_vector_copy(T) jm_mangle(jm_vector_copy, T)
223 * jm_vector_clone creates a copy of the provided vector on heap and returns it.
224 * Allocated capacity matches the size of the given vector. Returns the vector pointer or zero if memory allocation failed.
225 * jm_vector(T)* jm_vector_clone(T)(jm_vector(T)* source)
227 #define jm_vector_clone(T) jm_mangle(jm_vector_clone, T)
230 * jm_vector_append appends source vector into destination.
231 * Returns the number of elements actually appended (may be less than the source size if allocation failed).
232 * size_t jm_vector_append(T)(jm_vector(T)* destination, jm_vector(T)* source)
234 #define jm_vector_append(T) jm_mangle(jm_vector_append, T)
237 * jm_vector_insert inserts an element at a given location.
238 * Returns a pointer to the inserted element or zero pointer if failed
239 * T* jm_vector_insert(T)(jm_vector(T)* a, size_t index, T item)
241 #define jm_vector_insert(T) jm_mangle(jm_vector_insert, T)
244 * jm_vector_remove_item removes an item from the vector.
245 * Vector size is reduced by 1. Supplying index > size gives assertion fault.
246 * void jm_vector_remove_item(T)(jm_vector(T)* v, size_t index)
248 #define jm_vector_remove_item(T) jm_mangle(jm_vector_remove_item, T)
251 * T* jm_vector_resize1(jm_vector(T)* a)
252 * Increase the size of the vector by 1 and return a pointer to the last item.
253 * Return 0 if memory allocation failed.
255 #define jm_vector_resize1(T) jm_mangle(jm_vector_resize1, T)
258 * jm_vector_push_back
259 * Returns a pointer to the inserted element or zero pointer if failed.
260 * T* jm_vector_push_back(jm_vector(T)* a, T item)
262 #define jm_vector_push_back(T) jm_mangle(jm_vector_push_back, T)
265 * jm_vector_foreach calls f for each element in the vector. "contect" parameter
266 * is passed directly to the function as the second argument for the second version.
267 * void jm_vector_foreach(T)(jm_vector(T)* a, void (*f)(T))
268 * void jm_vector_foreach_c(T)(jm_vector(T)* a, void (*f)(T, void*), void * context)
270 #define jm_vector_foreach(T) jm_mangle(jm_vector_foreach, T)
271 #define jm_vector_foreach_c(T) jm_mangle(jm_vector_foreach_c, T)
275 /** number of items always allocated on the stack */
276 #define JM_VECTOR_MINIMAL_CAPACITY 16
278 /** maximum memory chunk (in items) to be allocated in push_back. */
279 #define JM_VECTOR_MAX_MEMORY_CHUNK 1024
281 /** Declare the struct and functions for the specified type. */
282 #define jm_vector_declare_template(T) \
283 typedef struct jm_vector(T) { \
284 jm_callbacks* callbacks; \
288 T preallocated[JM_VECTOR_MINIMAL_CAPACITY]; \
291 extern jm_vector(T)* jm_vector_alloc(T)(size_t size,size_t capacity, jm_callbacks*); \
293 extern size_t jm_vector_copy(T)(jm_vector(T)* destination, jm_vector(T)* source); \
294 static jm_vector(T)* jm_vector_clone(T)(jm_vector(T)* v) { \
295 jm_vector(T)* ret = jm_vector_alloc(T)(v->size, v->size, v->callbacks);\
296 if(ret) jm_vector_copy(T)(ret, v) ; \
300 extern void jm_vector_free(T)(jm_vector(T) * a); \
302 extern size_t jm_vector_init(T)(jm_vector(T)* a, size_t size,jm_callbacks*); \
304 static void jm_vector_free_data(T)(jm_vector(T)* a) { \
306 if(a->items != a->preallocated) { \
307 a->callbacks->free((void*)(a->items)); \
308 a->items = a->preallocated; \
309 a->capacity=JM_VECTOR_MINIMAL_CAPACITY;\
315 static size_t jm_vector_get_size(T)(jm_vector(T)* a) { return a->size; } \
317 static T jm_vector_get_item(T)(jm_vector(T)* a, size_t index) { \
318 assert(index < a->size); \
319 return a->items[index]; \
321 static T* jm_vector_get_itemp(T)(jm_vector(T)* a, size_t index) { \
322 assert(index < a->size); \
323 return (a->items+index); \
325 static T jm_vector_get_last(T)(jm_vector(T)* a) { \
327 return (a->items[a->size-1]); \
329 static T* jm_vector_get_lastp(T)(jm_vector(T)* a) { \
330 if(a->size) return (a->items+(a->size-1)); \
333 static void jm_vector_set_item(T)(jm_vector(T)* a, size_t index, T item) {\
334 *(jm_vector_get_itemp(T)(a, index)) = item; \
336 extern size_t jm_vector_resize(T)(jm_vector(T)* a, size_t size); \
337 extern size_t jm_vector_reserve(T)(jm_vector(T)* a, size_t capacity); \
338 extern size_t jm_vector_append(T)(jm_vector(T)* destination, jm_vector(T)* source); \
339 extern T* jm_vector_insert(T)(jm_vector(T)* a, size_t index, T item);\
340 extern T* jm_vector_push_back(T)(jm_vector(T)* a, T item);\
341 extern T* jm_vector_resize1(T)(jm_vector(T)* a);\
342 extern void jm_vector_remove_item(T)(jm_vector(T)* v, size_t index); \
343 extern size_t jm_vector_find_index(T)(jm_vector(T)* a, T *itemp, jm_compare_ft f); \
344 extern T* jm_vector_find(T)(jm_vector(T)* a, T *itemp, jm_compare_ft f); \
345 extern void jm_vector_qsort(T)(jm_vector(T)* v, jm_compare_ft f); \
346 extern size_t jm_vector_bsearch_index(T)(jm_vector(T)* v, T* key, jm_compare_ft f); \
347 extern T* jm_vector_bsearch(T)(jm_vector(T)* v, T* key, jm_compare_ft f); \
348 extern void jm_vector_foreach(T)(jm_vector(T)* a, void (*f)(T)); \
349 extern void jm_vector_foreach_c(T)(jm_vector(T)* a, void (*f)(T, void*), void * data); \
350 extern void jm_vector_zero(T)(jm_vector(T)* a);
352 jm_vector_declare_template(char)
353 static jm_string jm_vector_char2string(jm_vector(char)* v) {
355 if(v->size) return v->items;
359 jm_vector_declare_template(int)
360 jm_vector_declare_template(double)
361 jm_vector_declare_template(jm_voidp)
362 jm_vector_declare_template(size_t)
363 jm_vector_declare_template(jm_string)
364 jm_vector_declare_template(jm_name_ID_map_t)
367 jm_define_comp_f(jm_compare_voidp, int*, jm_diff)
368 jm_define_comp_f(jm_compare_int, int, jm_diff)
369 jm_define_comp_f(jm_compare_char, char, jm_diff)
370 jm_define_comp_f(jm_compare_double, double, jm_diff)
371 jm_define_comp_f(jm_compare_size_t, size_t, jm_diff)
372 jm_define_comp_f(jm_compare_string, jm_string, strcmp)
374 #define jm_diff_name(a, b) strcmp(a.name,b.name)
375 jm_define_comp_f(jm_compare_name, jm_name_ID_map_t, jm_diff_name)