org.simantics.fmil.core/native/FMILibrary/src/Util/include/JM/jm_vector_template.h

   1 /*
   2     Copyright (C) 2012 Modelon AB
   3
   4     This program is free software: you can redistribute it and/or modify
   5     it under the terms of the BSD style license.
   6
   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.
  11
  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>.
  14 */
  15
  16 /**
  17 * \file jm_vector_template.h
  18 * \brief Vector template definition.
  19 *
  20 * This file is supposed to be included into a C-file that instantiate the template.
  21 * jm_vector.h must be included before this file.
  22 * It expects JM_TEMPLATE_INSTANCE_TYPE to be defined to the template type to be instantiated.
  23 */
  24
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include "jm_vector.h"
  28
  29 /** \addtogroup jm_vector  A vector of items (dynamic array)*/
  30 /** @{
  31 */
  32
  33 #ifndef JM_TEMPLATE_INSTANCE_TYPE
  34 #error "JM_TEMPLATE_INSTANCE_TYPE must be defined before including this file"
  35 #endif
  36
  37 jm_vector(JM_TEMPLATE_INSTANCE_TYPE) * jm_vector_alloc(JM_TEMPLATE_INSTANCE_TYPE) (size_t size, size_t capacity, jm_callbacks* c) {
  38         size_t reserve;
  39         jm_callbacks* cc;
  40         jm_vector(JM_TEMPLATE_INSTANCE_TYPE) * v;
  41         if(c)
  42             cc = c;
  43         else
  44             cc = jm_get_default_callbacks();
  45
  46         reserve = capacity;
  47         if(reserve < size) reserve = size;
  48         if(reserve > JM_VECTOR_MINIMAL_CAPACITY) {
  49             v = (jm_vector(JM_TEMPLATE_INSTANCE_TYPE)*)cc->malloc(
  50                         sizeof(jm_vector(JM_TEMPLATE_INSTANCE_TYPE)) +
  51                         sizeof(JM_TEMPLATE_INSTANCE_TYPE) * (reserve -JM_VECTOR_MINIMAL_CAPACITY));
  52             if(!v) return 0;
  53             v->capacity = reserve;
  54         }
  55         else {
  56             v = (jm_vector(JM_TEMPLATE_INSTANCE_TYPE)*)cc->malloc(sizeof(jm_vector(JM_TEMPLATE_INSTANCE_TYPE)));
  57             if(!v) return 0;
  58             v->capacity = JM_VECTOR_MINIMAL_CAPACITY;
  59         }
  60         v->callbacks = cc;
  61         v->items = &(v->preallocated[0]);
  62         v->size = size;
  63         return v;
  64 }
  65
  66 void jm_vector_free(JM_TEMPLATE_INSTANCE_TYPE) (jm_vector(JM_TEMPLATE_INSTANCE_TYPE) * a) {
  67     if(!a) return;
  68     jm_vector_free_data(JM_TEMPLATE_INSTANCE_TYPE)(a);
  69     a->callbacks->free(a);
  70 }
  71
  72 size_t jm_vector_init(JM_TEMPLATE_INSTANCE_TYPE)(jm_vector(JM_TEMPLATE_INSTANCE_TYPE)* a, size_t initSize, jm_callbacks* c) {
  73         if(c)
  74             a->callbacks = c;
  75         else
  76             a->callbacks = jm_get_default_callbacks();
  77         a->items = a->preallocated;
  78         a->size = 0;
  79         a->capacity = JM_VECTOR_MINIMAL_CAPACITY;
  80
  81         if(initSize > a->size)
  82             return jm_vector_resize(JM_TEMPLATE_INSTANCE_TYPE)(a, initSize);
  83         return 0;
  84 }
  85
  86 size_t jm_vector_resize(JM_TEMPLATE_INSTANCE_TYPE)(jm_vector(JM_TEMPLATE_INSTANCE_TYPE)* a, size_t size) {
  87         if(size > a->capacity)  {
  88             if(jm_vector_reserve(JM_TEMPLATE_INSTANCE_TYPE)(a, size) < size) {
  89                 a->size = a->capacity;
  90                 return a->capacity;
  91             }
  92         }
  93         a->size = size;
  94         return size;
  95 }
  96
  97 size_t jm_vector_reserve(JM_TEMPLATE_INSTANCE_TYPE)(jm_vector(JM_TEMPLATE_INSTANCE_TYPE)* a, size_t size) {
  98         void* newmem;
  99         if(size <= a->capacity) return a->capacity;
 100         newmem = a->callbacks->malloc(size * sizeof(JM_TEMPLATE_INSTANCE_TYPE));
 101         if(!newmem) return a->capacity;
 102         memcpy(newmem, a->items, a->size * sizeof(JM_TEMPLATE_INSTANCE_TYPE));
 103         if(a->items !=  a->preallocated) a->callbacks->free((void*)(a->items));
 104         a->items = newmem;
 105         a->capacity = size;
 106         return a->capacity;
 107 }
 108
 109 size_t jm_vector_copy(JM_TEMPLATE_INSTANCE_TYPE)(jm_vector(JM_TEMPLATE_INSTANCE_TYPE)* destination, jm_vector(JM_TEMPLATE_INSTANCE_TYPE)* source) {
 110         size_t destsize = jm_vector_resize(JM_TEMPLATE_INSTANCE_TYPE)(destination, source->size);
 111         if(destsize > 0) {
 112             memcpy((void*)destination->items, (void*)source->items, sizeof(JM_TEMPLATE_INSTANCE_TYPE)*destsize);
 113         }
 114         return destination->size;
 115 }
 116
 117 size_t jm_vector_append(JM_TEMPLATE_INSTANCE_TYPE)(jm_vector(JM_TEMPLATE_INSTANCE_TYPE)* destination, jm_vector(JM_TEMPLATE_INSTANCE_TYPE)* source) {
 118         size_t oldsize, newsize;
 119         oldsize = jm_vector_get_size(JM_TEMPLATE_INSTANCE_TYPE)(destination);
 120         newsize = jm_vector_resize(JM_TEMPLATE_INSTANCE_TYPE)(destination, source->size + oldsize);
 121         memcpy((void*)(destination->items + oldsize), (void*)source->items, sizeof(JM_TEMPLATE_INSTANCE_TYPE)*(newsize - oldsize));
 122         return (newsize - oldsize);
 123 }
 124
 125 JM_TEMPLATE_INSTANCE_TYPE* jm_vector_insert(JM_TEMPLATE_INSTANCE_TYPE)(jm_vector(JM_TEMPLATE_INSTANCE_TYPE)* a, size_t index, JM_TEMPLATE_INSTANCE_TYPE item) {
 126         size_t reserve;
 127         JM_TEMPLATE_INSTANCE_TYPE* pitem;
 128         if(index >= a->size) return 0;
 129         if(a->size == a->capacity) {
 130                 if(a->capacity > JM_VECTOR_MAX_MEMORY_CHUNK)
 131                         reserve = JM_VECTOR_MAX_MEMORY_CHUNK + a->capacity;
 132                 else
 133                         reserve = a->capacity * 2;
 134                 if( jm_vector_reserve(JM_TEMPLATE_INSTANCE_TYPE)(a, reserve) != reserve) return 0;
 135         }
 136         assert(a->size < a->capacity);
 137         memmove((void*)(a->items+index+1),(void*)(a->items+index), (a->size - index)*sizeof(JM_TEMPLATE_INSTANCE_TYPE));
 138         a->items[index] = item;
 139         pitem = &(a->items[index]);
 140         a->size++;
 141         return pitem;
 142 }
 143
 144 JM_TEMPLATE_INSTANCE_TYPE* jm_vector_resize1(JM_TEMPLATE_INSTANCE_TYPE) (jm_vector(JM_TEMPLATE_INSTANCE_TYPE) * a) {
 145         size_t reserve;
 146         JM_TEMPLATE_INSTANCE_TYPE* pitem;
 147         if(a->size == a->capacity) {
 148                 if(a->capacity > JM_VECTOR_MAX_MEMORY_CHUNK)
 149                         reserve = JM_VECTOR_MAX_MEMORY_CHUNK + a->capacity;
 150                 else
 151                         reserve = a->capacity * 2;
 152                 if( jm_vector_reserve(JM_TEMPLATE_INSTANCE_TYPE)(a, reserve) != reserve) return 0;
 153         }
 154         assert(a->size < a->capacity);
 155         pitem = &(a->items[a->size]);
 156         a->size++;
 157         return pitem;
 158 }
 159
 160 JM_TEMPLATE_INSTANCE_TYPE* jm_vector_push_back(JM_TEMPLATE_INSTANCE_TYPE) (jm_vector(JM_TEMPLATE_INSTANCE_TYPE) * a, JM_TEMPLATE_INSTANCE_TYPE item) {
 161         JM_TEMPLATE_INSTANCE_TYPE* pitem= jm_vector_resize1(JM_TEMPLATE_INSTANCE_TYPE) (a);
 162         if(!pitem) return 0;
 163         *pitem = item;
 164         return pitem;
 165 }
 166
 167 void jm_vector_remove_item(JM_TEMPLATE_INSTANCE_TYPE)(jm_vector(JM_TEMPLATE_INSTANCE_TYPE)* v, size_t index) {
 168     size_t n =v->size - index -1;
 169     assert(index < v->size);
 170     if(n) {
 171         memmove((void*)&(v->items[index]),(void*) &(v->items[index+1]), n * sizeof(JM_TEMPLATE_INSTANCE_TYPE));
 172     }
 173     v->size--;
 174 }
 175
 176 void jm_vector_zero(JM_TEMPLATE_INSTANCE_TYPE)(jm_vector(JM_TEMPLATE_INSTANCE_TYPE)* a) {
 177     if(jm_vector_get_size(JM_TEMPLATE_INSTANCE_TYPE)(a) > 0) {
 178         memset((void*)a->items,0,a->size * sizeof(JM_TEMPLATE_INSTANCE_TYPE));
 179     }
 180 }
 181
 182 void jm_vector_foreach_c(JM_TEMPLATE_INSTANCE_TYPE)(jm_vector(JM_TEMPLATE_INSTANCE_TYPE)* a,
 183                                                     void (*f)(JM_TEMPLATE_INSTANCE_TYPE, void*), void * data) {
 184         size_t i;
 185         for(i = 0; i < jm_vector_get_size(JM_TEMPLATE_INSTANCE_TYPE)(a); i++)
 186             f(jm_vector_get_item(JM_TEMPLATE_INSTANCE_TYPE)(a, i), data);
 187 }
 188
 189 void jm_vector_foreach(JM_TEMPLATE_INSTANCE_TYPE)(jm_vector(JM_TEMPLATE_INSTANCE_TYPE)* a,
 190                                                     void (*f)(JM_TEMPLATE_INSTANCE_TYPE)) {
 191         size_t i;
 192         for(i = 0; i < jm_vector_get_size(JM_TEMPLATE_INSTANCE_TYPE)(a); i++)
 193             f(jm_vector_get_item(JM_TEMPLATE_INSTANCE_TYPE)(a, i));
 194 }
 195
 196 void jm_vector_qsort(JM_TEMPLATE_INSTANCE_TYPE)(jm_vector(JM_TEMPLATE_INSTANCE_TYPE)* v, jm_compare_ft f) {
 197     if(jm_vector_get_size(JM_TEMPLATE_INSTANCE_TYPE)(v) > 1) {
 198         qsort((void*)v->items, jm_vector_get_size(JM_TEMPLATE_INSTANCE_TYPE)(v), sizeof(JM_TEMPLATE_INSTANCE_TYPE),f);
 199     }
 200 }
 201
 202 #define jm_vector_ptr2index(T) jm_mangle(jm_vector_ptr2index, T)
 203
 204 static size_t jm_vector_ptr2index(JM_TEMPLATE_INSTANCE_TYPE)(jm_vector(JM_TEMPLATE_INSTANCE_TYPE)* v, JM_TEMPLATE_INSTANCE_TYPE* itemp) {
 205     if(itemp)
 206         return (itemp - v->items);
 207     else
 208         return jm_vector_get_size(JM_TEMPLATE_INSTANCE_TYPE)(v);
 209 }
 210
 211
 212 size_t jm_vector_bsearch_index(JM_TEMPLATE_INSTANCE_TYPE)(jm_vector(JM_TEMPLATE_INSTANCE_TYPE)* v, JM_TEMPLATE_INSTANCE_TYPE* key, jm_compare_ft f) {
 213     return jm_vector_ptr2index(JM_TEMPLATE_INSTANCE_TYPE)(v, jm_vector_bsearch(JM_TEMPLATE_INSTANCE_TYPE)(v, key,f));
 214 }
 215
 216 JM_TEMPLATE_INSTANCE_TYPE* jm_vector_bsearch(JM_TEMPLATE_INSTANCE_TYPE)(jm_vector(JM_TEMPLATE_INSTANCE_TYPE)* v, JM_TEMPLATE_INSTANCE_TYPE* key, jm_compare_ft f) {
 217     return bsearch(key, v->items,
 218                    jm_vector_get_size(JM_TEMPLATE_INSTANCE_TYPE)(v),
 219                    sizeof(JM_TEMPLATE_INSTANCE_TYPE),
 220                    f);
 221 }
 222
 223 JM_TEMPLATE_INSTANCE_TYPE* jm_vector_find(JM_TEMPLATE_INSTANCE_TYPE)(jm_vector(JM_TEMPLATE_INSTANCE_TYPE)* a, JM_TEMPLATE_INSTANCE_TYPE* itemp, jm_compare_ft f) {
 224     size_t i = jm_vector_get_size(JM_TEMPLATE_INSTANCE_TYPE)(a);
 225     while(i--) {
 226         JM_TEMPLATE_INSTANCE_TYPE* cur = jm_vector_get_itemp(JM_TEMPLATE_INSTANCE_TYPE)(a, i);
 227         if(f(cur, itemp) == 0)
 228            return cur;
 229     };
 230     return 0;
 231 }
 232
 233 size_t jm_vector_find_index(JM_TEMPLATE_INSTANCE_TYPE)(jm_vector(JM_TEMPLATE_INSTANCE_TYPE)* v, JM_TEMPLATE_INSTANCE_TYPE* itemp, jm_compare_ft f) {
 234     return jm_vector_ptr2index(JM_TEMPLATE_INSTANCE_TYPE)(v,jm_vector_find(JM_TEMPLATE_INSTANCE_TYPE)(v, itemp, f));
 235 }
 236
 237 /** @}
 238 */